Longest collision chain in symbol table now exceeds maximum -- suspect a DoS attack

[pauldraper]

Jackson fails to parse the simple JSON below

{
    "\u0000":0,
    "\u0001":1,
    "\u0002":2,
    "\u0003":3,
    "\u0004":4,
    "\u0005":5,
    "\u0006":6,
    "\u0007":7,
    "\u0008":8,
    "\u0009":9,
    "\u000a":10,
    "\u000b":11,
    "\u000c":12,
    "\u000d":13,
    "\u000e":14,
    "\u000f":15,
    "\u0010":16,
    "\u0011":17,
    "\u0012":18,
    "\u0013":19,
    "\u0014":20,
    "\u0015":21,
    "\u0016":22,
    "\u0017":23,
    "\u0018":24,
    "\u0019":25,
    "\u001a":26,
    "\u001b":27,
    "\u001c":28,
    "\u001d":29,
    "\u001e":30,
    "\u001f":31,
    "\u0020":32,
    "\u0021":33,
    "\u0022":34,
    "\u0023":35,
    "\u0024":36,
    "\u0025":37,
    "\u0026":38,
    "\u0027":39,
    "\u0028":40,
    "\u0029":41,
    "\u002a":42,
    "\u002b":43,
    "\u002c":44,
    "\u002d":45,
    "\u002e":46,
    "\u002f":47,
    "\u0030":48,
    "\u0031":49,
    "\u0032":50,
    "\u0033":51,
    "\u0034":52,
    "\u0035":53,
    "\u0036":54,
    "\u0037":55,
    "\u0038":56,
    "\u0039":57,
    "\u003a":58,
    "\u003b":59,
    "\u003c":60,
    "\u003d":61,
    "\u003e":62,
    "\u003f":63,
    "\u0040":64,
    "\u0041":65,
    "\u0042":66,
    "\u0043":67,
    "\u0044":68,
    "\u0045":69,
    "\u0046":70,
    "\u0047":71,
    "\u0048":72,
    "\u0049":73,
    "\u004a":74,
    "\u004b":75,
    "\u004c":76,
    "\u004d":77,
    "\u004e":78,
    "\u004f":79,
    "\u0050":80,
    "\u0051":81,
    "\u0052":82,
    "\u0053":83,
    "\u0054":84,
    "\u0055":85,
    "\u0056":86,
    "\u0057":87,
    "\u0058":88,
    "\u0059":89,
    "\u005a":90,
    "\u005b":91,
    "\u005c":92,
    "\u005d":93,
    "\u005e":94,
    "\u005f":95,
    "\u0060":96,
    "\u0061":97,
    "\u0062":98,
    "\u0063":99,
    "\u0064":100,
    "\u0065":101,
    "\u0066":102,
    "\u0067":103,
    "\u0068":104,
    "\u0069":105,
    "\u006a":106,
    "\u006b":107,
    "\u006c":108,
    "\u006d":109,
    "\u006e":110,
    "\u006f":111,
    "\u0070":112,
    "\u0071":113,
    "\u0072":114,
    "\u0073":115,
    "\u0074":116,
    "\u0075":117,
    "\u0076":118,
    "\u0077":119,
    "\u0078":120,
    "\u0079":121,
    "\u007a":122,
    "\u007b":123,
    "\u007c":124,
    "\u007d":125,
    "\u007e":126,
    "\u007f":127,
    "\u0080":128,
    "\u0081":129,
    "\u0082":130,
    "\u0083":131,
    "\u0084":132,
    "\u0085":133,
    "\u0086":134,
    "\u0087":135,
    "\u0088":136,
    "\u0089":137,
    "\u008a":138,
    "\u008b":139,
    "\u008c":140,
    "\u008d":141,
    "\u008e":142,
    "\u008f":143,
    "\u0090":144,
    "\u0091":145,
    "\u0092":146,
    "\u0093":147,
    "\u0094":148,
    "\u0095":149,
    "\u0096":150,
    "\u0097":151,
    "\u0098":152,
    "\u0099":153,
    "\u009a":154,
    "\u009b":155,
    "\u009c":156,
    "\u009d":157,
    "\u009e":158,
    "\u009f":159,
    "\u00a0":160,
    "\u00a1":161,
    "\u00a2":162,
    "\u00a3":163,
    "\u00a4":164,
    "\u00a5":165,
    "\u00a6":166,
    "\u00a7":167,
    "\u00a8":168,
    "\u00a9":169,
    "\u00aa":170,
    "\u00ab":171,
    "\u00ac":172,
    "\u00ad":173,
    "\u00ae":174,
    "\u00af":175,
    "\u00b0":176,
    "\u00b1":177,
    "\u00b2":178,
    "\u00b3":179,
    "\u00b4":180,
    "\u00b5":181,
    "\u00b6":182,
    "\u00b7":183,
    "\u00b8":184,
    "\u00b9":185,
    "\u00ba":186,
    "\u00bb":187,
    "\u00bc":188,
    "\u00bd":189,
    "\u00be":190,
    "\u00bf":191,
    "\u00c0":192,
    "\u00c1":193,
    "\u00c2":194,
    "\u00c3":195,
    "\u00c4":196,
    "\u00c5":197,
    "\u00c6":198,
    "\u00c7":199,
    "\u00c8":200,
    "\u00c9":201,
    "\u00ca":202,
    "\u00cb":203,
    "\u00cc":204,
    "\u00cd":205,
    "\u00ce":206,
    "\u00cf":207,
    "\u00d0":208,
    "\u00d1":209,
    "\u00d2":210,
    "\u00d3":211,
    "\u00d4":212,
    "\u00d5":213,
    "\u00d6":214,
    "\u00d7":215,
    "\u00d8":216,
    "\u00d9":217,
    "\u00da":218,
    "\u00db":219,
    "\u00dc":220,
    "\u00dd":221,
    "\u00de":222,
    "\u00df":223,
    "\u00e0":224,
    "\u00e1":225,
    "\u00e2":226,
    "\u00e3":227,
    "\u00e4":228,
    "\u00e5":229,
    "\u00e6":230,
    "\u00e7":231,
    "\u00e8":232,
    "\u00e9":233,
    "\u00ea":234,
    "\u00eb":235,
    "\u00ec":236,
    "\u00ed":237,
    "\u00ee":238,
    "\u00ef":239,
    "\u00f0":240,
    "\u00f1":241,
    "\u00f2":242,
    "\u00f3":243,
    "\u00f4":244,
    "\u00f5":245,
    "\u00f6":246,
    "\u00f7":247,
    "\u00f8":248,
    "\u00f9":249,
    "\u00fa":250,
    "\u00fb":251,
    "\u00fc":252,
    "\u00fd":253,
    "\u00fe":254,
    "\u00ff":255,
    "\u0100":256,
    "\u0101":257,
    "\u0102":258,
    "\u0103":259,
    "\u0104":260,
    "\u0105":261,
    "\u0106":262,
    "\u0107":263,
    "\u0108":264,
    "\u0109":265,
    "\u010a":266,
    "\u010b":267,
    "\u010c":268,
    "\u010d":269,
    "\u010e":270,
    "\u010f":271,
    "\u0110":272,
    "\u0111":273,
    "\u0112":274,
    "\u0113":275,
    "\u0114":276,
    "\u0115":277,
    "\u0116":278,
    "\u0117":279,
    "\u0118":280,
    "\u0119":281,
    "\u011a":282,
    "\u011b":283,
    "\u011c":284,
    "\u011d":285,
    "\u011e":286,
    "\u011f":287,
    "\u0120":288,
    "\u0121":289,
    "\u0122":290,
    "\u0123":291,
    "\u0124":292,
    "\u0125":293,
    "\u0126":294,
    "\u0127":295,
    "\u0128":296,
    "\u0129":297,
    "\u012a":298,
    "\u012b":299,
    "\u012c":300,
    "\u012d":301,
    "\u012e":302,
    "\u012f":303,
    "\u0130":304,
    "\u0131":305,
    "\u0132":306,
    "\u0133":307,
    "\u0134":308,
    "\u0135":309,
    "\u0136":310,
    "\u0137":311,
    "\u0138":312,
    "\u0139":313,
    "\u013a":314,
    "\u013b":315,
    "\u013c":316,
    "\u013d":317,
    "\u013e":318,
    "\u013f":319,
    "\u0140":320,
    "\u0141":321,
    "\u0142":322,
    "\u0143":323,
    "\u0144":324,
    "\u0145":325,
    "\u0146":326,
    "\u0147":327,
    "\u0148":328,
    "\u0149":329,
    "\u014a":330,
    "\u014b":331,
    "\u014c":332,
    "\u014d":333,
    "\u014e":334,
    "\u014f":335,
    "\u0150":336,
    "\u0151":337,
    "\u0152":338,
    "\u0153":339,
    "\u0154":340,
    "\u0155":341,
    "\u0156":342,
    "\u0157":343,
    "\u0158":344,
    "\u0159":345,
    "\u015a":346,
    "\u015b":347,
    "\u015c":348,
    "\u015d":349,
    "\u015e":350,
    "\u015f":351,
    "\u0160":352,
    "\u0161":353,
    "\u0162":354,
    "\u0163":355,
    "\u0164":356,
    "\u0165":357,
    "\u0166":358,
    "\u0167":359,
    "\u0168":360,
    "\u0169":361,
    "\u016a":362,
    "\u016b":363,
    "\u016c":364,
    "\u016d":365,
    "\u016e":366,
    "\u016f":367,
    "\u0170":368,
    "\u0171":369,
    "\u0172":370,
    "\u0173":371,
    "\u0174":372,
    "\u0175":373,
    "\u0176":374,
    "\u0177":375,
    "\u0178":376,
    "\u0179":377,
    "\u017a":378,
    "\u017b":379,
    "\u017c":380,
    "\u017d":381,
    "\u017e":382,
    "\u017f":383,
    "\u0180":384,
    "\u0181":385,
    "\u0182":386,
    "\u0183":387,
    "\u0184":388,
    "\u0185":389,
    "\u0186":390,
    "\u0187":391,
    "\u0188":392,
    "\u0189":393,
    "\u018a":394,
    "\u018b":395,
    "\u018c":396,
    "\u018d":397,
    "\u018e":398,
    "\u018f":399
}

It fails with an exception.

Longest collision chain in symbol table (of size 294) now exceeds maximum, 100 -- suspect a DoS attack based on hash collisions
    at com.fasterxml.jackson.core.sym.CharsToNameCanonicalizer.reportTooManyCollisions(CharsToNameCanonicalizer.java:697)
    at com.fasterxml.jackson.core.sym.CharsToNameCanonicalizer._handleSpillOverflow(CharsToNameCanonicalizer.java:535)
    at com.fasterxml.jackson.core.sym.CharsToNameCanonicalizer._addSymbol(CharsToNameCanonicalizer.java:516)
    at com.fasterxml.jackson.core.sym.CharsToNameCanonicalizer.findSymbol(CharsToNameCanonicalizer.java:473)
    at com.fasterxml.jackson.core.json.ReaderBasedJsonParser._parseName2(ReaderBasedJsonParser.java:1322)
    at com.fasterxml.jackson.core.json.ReaderBasedJsonParser._parseName(ReaderBasedJsonParser.java:1268)
    at com.fasterxml.jackson.core.json.ReaderBasedJsonParser.nextToken(ReaderBasedJsonParser.java:618)
    at com.fasterxml.jackson.databind.deser.std.BaseNodeDeserializer.deserializeObject(JsonNodeDeserializer.java:218)
    at com.fasterxml.jackson.databind.deser.std.JsonNodeDeserializer.deserialize(JsonNodeDeserializer.java:62)
    at com.fasterxml.jackson.databind.deser.std.JsonNodeDeserializer.deserialize(JsonNodeDeserializer.java:14)
    at com.fasterxml.jackson.databind.ObjectMapper._readMapAndClose(ObjectMapper.java:3562)
    at com.fasterxml.jackson.databind.ObjectMapper.readTree(ObjectMapper.java:2136)

According to the documentation,

longest chain we have been able to produce without malicious intent has been 38 (with "com.fasterxml.jackson.core.main.TestWithTonsaSymbols")

TestWithTonsaSymbols must not try very hard :)

[cowtowncoder]

There have been recent fixes in this area (and as you point out, problem is indeed real), so just to make sure, which version are you using?

Specifically, #187 was part of 2.5.2.

[pauldraper]

2.5.2
On Apr 22, 2015 5:38 PM, "Tatu Saloranta" notifications@github.com wrote:

There have been recent fixes in this area, so just to make sure, which
version are you using?

—
Reply to this email directly or view it on GitHub
#191 (comment)
.

[cowtowncoder]

Hmmh. That is odd -- I can not reproduce this from 2.5 branch (pre-2.5.3).

As a temporary work-around, you may want to disable JsonFactory.Feature.FAIL_ON_SYMBOL_HASH_OVERFLOW. But it should be fixed for 2.5.2 and 2.6.0 (to be released).
I will add suggested test.

[cowtowncoder]

@pauldraper Would it be possible to verify that you are actually using 2.5.2: it is possible (for example) that you have 2.5.2 dependency to jackson-databind, but transitive one for jackson-core?
I don't want to ignore a real problem, but since I can not reproduce collisions locally, I want to make sure it is not just due to, say, 2.5.1 of jackson-core triggering it (which would do it).

If you are building with maven, mvn dependency:tree shows actual versions for example.

[pauldraper]

Thanks for the FAIL_ON_SYMBOL_HASH_OVERFLOW tip!

It turns out I was depending on 2.5.1 of jackson-core. I updated it to 2.5.2, but the problem still occurs.

pom.xml

<project>
  <modelVersion>4.0.0</modelVersion>
  <groupId>com.github.pauldraper</groupId>
  <artifactId>jackson-demo</artifactId>
  <version>0</version>
  <dependencies>
    <dependency>
      <groupId>com.fasterxml.jackson.core</groupId>
      <artifactId>jackson-databind</artifactId>
      <version>2.5.2</version>
    </dependency>
    <dependency>
      <groupId>com.fasterxml.jackson.core</groupId>
      <artifactId>jackson-core</artifactId>
      <version>2.5.2</version>
    </dependency>
  </dependencies>
  <build>
    <plugins>
      <plugin>
        <groupId>org.codehaus.mojo</groupId>
        <artifactId>exec-maven-plugin</artifactId>
        <version>1.2.1</version>
        <configuration>
           <mainClass>Main</mainClass>
        </configuration>
      </plugin>
    </plugins>
  </build>
</project>

This is the code I am using; perhaps increasing the number of keys may do it for you.

src/main/java/Main.java

import com.fasterxml.jackson.databind.*;
import java.io.IOException;

class Main {

    public static void main(String[] args) throws IOException {
        ObjectMapper mapper = new ObjectMapper();
        StringBuilder sb = new StringBuilder();
        sb.append("{");
        for (int i = 0; i < 400; i++) {
            if (i > 0) {
                sb.append(",");
            }
            sb.append(String.format("\"\\u%04x\":%d", i, i));
        }
        sb.append("}");
        mapper.readTree(sb.toString());

        System.out.println("SUCCESS!");
    }

}

[cowtowncoder]

One sort of related bug I found: jackson-databind 2.5.2 accidentally depends on 2.5.1. Grrh.
I wish Maven release plug-in worked ok if ${project.version} was used, but my experience has been it does not. Hence manual bumping of dependencies...

[cowtowncoder]

On plus side, yes, that code does trigger the problem. Mystery deepens... :)

[cowtowncoder]

Come to to think of it, my example was not strictly identical, since my escaping differed -- while decoded names are the same, escapes are different.

[cowtowncoder]

Very interesting little bug. And quite specific: only occurs with character-based sources (not byte-), and only affects escaped characters. If so, escaped characters hash code was basically taken as that of backslash; and the specific tested case of a single escaped character meant all escaped Strings hashed into same value.

So in a way, hash overflow detection correctly determined something was fishy. :-)

I'll be checking in the fix, as well as test to catch the specific problem, shortly.