ByteQuadsCanonicalizer: ArrayIndexOutOfBoundsException in addName

[alpire]

Fuzzing a spring boot application led to the following exception in ByteQuadsCanonicalizer.addName:

Caused by: java.lang.ArrayIndexOutOfBoundsException: 1024
        at com.fasterxml.jackson.core.sym.ByteQuadsCanonicalizer.addName(ByteQuadsCanonicalizer.java:834)
        at com.fasterxml.jackson.core.json.UTF8StreamJsonParser.addName(UTF8StreamJsonParser.java:2325)
        at com.fasterxml.jackson.core.json.UTF8StreamJsonParser.findName(UTF8StreamJsonParser.java:2198)
        at com.fasterxml.jackson.core.json.UTF8StreamJsonParser.parseMediumName2(UTF8StreamJsonParser.java:1760)
        at com.fasterxml.jackson.core.json.UTF8StreamJsonParser.parseMediumName(UTF8StreamJsonParser.java:1737)
        at com.fasterxml.jackson.core.json.UTF8StreamJsonParser._parseName(UTF8StreamJsonParser.java:1672)
        at com.fasterxml.jackson.core.json.UTF8StreamJsonParser.nextToken(UTF8StreamJsonParser.java:727)
        at com.fasterxml.jackson.core.base.ParserMinimalBase.skipChildren(ParserMinimalBase.java:237)
        at com.fasterxml.jackson.databind.DeserializationContext.handleUnknownProperty(DeserializationContext.java:817)
        at com.fasterxml.jackson.databind.deser.std.StdDeserializer.handleUnknownProperty(StdDeserializer.java:1152)
        at com.fasterxml.jackson.databind.deser.BeanDeserializerBase.handleUnknownProperty(BeanDeserializerBase.java:1589)
        at com.fasterxml.jackson.databind.deser.BeanDeserializerBase.handleUnknownVanilla(BeanDeserializerBase.java:1567)
        at com.fasterxml.jackson.databind.deser.BeanDeserializer.deserializeFromObject(BeanDeserializer.java:375)
        at com.fasterxml.jackson.databind.deser.BeanDeserializer.deserialize(BeanDeserializer.java:159)
        at com.fasterxml.jackson.databind.ObjectMapper._readMapAndClose(ObjectMapper.java:4013)
        at com.fasterxml.jackson.databind.ObjectMapper.readValue(ObjectMapper.java:3084)

I was able to reproduce the issue on the 2.10 branch (commit c8fe42d). While I'm not positive that the stacktrace above stems from the same root cause, it could be one explanation.

Failing unit test

   public void testQuads() {
        Random r = new Random(42);
        ByteQuadsCanonicalizer root = ByteQuadsCanonicalizer.createRoot();
        ByteQuadsCanonicalizer canon = root.makeChild(JsonFactory.Feature.collectDefaults());

        int n_collisions = 25;
        int[] collisions = new int[n_collisions];

        // generate collisions
        {
            int maybe = r.nextInt();
            int hash = canon.calcHash(maybe);
            int target = ((hash & (2048-1)) << 2);

            for(int i = 0; i < collisions.length; ) {
                maybe = r.nextInt();
                hash = canon.calcHash(maybe);
                int offset = ((hash & (2048-1)) << 2);

                if(offset == target) {
                    collisions[i++] = maybe;
                }
            }
        }

        // fill spillover area until _needRehash is true.
        for(int i = 0; i < 22 ; i++) {
            canon.addName(Integer.toString(i), collisions[i]);
        }
        // canon._needRehash is now true, since the spillover is full

        // release table to update tableinfo with canon's data
        canon.release();

        // new table pulls data from new tableinfo, that has a full spillover, but set _needRehash to false
        canon = root.makeChild(JsonFactory.Feature.collectDefaults());

        // canon._needRehash == false, so this will try to add another item to the spillover area, even though it is full
        canon.addName(Integer.toString(22), collisions[22]);
    }

Stacktrace

java.lang.ArrayIndexOutOfBoundsException: 512
        at com.fasterxml.jackson.core.sym.ByteQuadsCanonicalizer.addName(ByteQuadsCanonicalizer.java:767)
        at com.fasterxml.jackson.core.sym.TestHashCollisionChars.testQuads(TestHashCollisionChars.java:121)

Suggested Fix

_verifyNeedForRehash() should return true if the spillover area is full, even if the hash table is less than 50% full.

[cowtowncoder]

Ok. So, I can prevent this particular way by simply preventing merge in case where _needRehash is true; and since there's not much upside supporting that case, I'll add that check first.
But I won't close this yet, in case you can still make it crash with some other combinations.
Going through the code again I think that the way this is handled is not really optimal, too, so maybe I'll start refactoring this now to clean things up.

[cowtowncoder]

@alpire Ok so I changed code more to my liking and it should solve the problem as well as be bit more robust.
Having said that, I would be very interested in knowing if you can find remaining issues as now would be excellent time to resolve them. :)