Fix [Issue-21] for 1.9.9
diff --git a/release-notes/VERSION b/release-notes/VERSION
index be10e23..77bbdb2 100644
--- a/release-notes/VERSION
+++ b/release-notes/VERSION
@@ -8,6 +8,10 @@
Fixes:
+ * [Issue-21]: Improve handling of String hash code collisions for
+ symbol tables; exception for degenerate cases (attacks), improvements
+ for calculation otherwise
+
------------------------------------------------------------------------
=== History: ===
------------------------------------------------------------------------
diff --git a/src/java/org/codehaus/jackson/sym/BytesToNameCanonicalizer.java b/src/java/org/codehaus/jackson/sym/BytesToNameCanonicalizer.java
index 9eb505c..fc50806 100644
--- a/src/java/org/codehaus/jackson/sym/BytesToNameCanonicalizer.java
+++ b/src/java/org/codehaus/jackson/sym/BytesToNameCanonicalizer.java
@@ -18,9 +18,7 @@
/**
* Let's not expand symbol tables past some maximum size;
* this should protected against OOMEs caused by large documents
- * with uniquer (~= random) names.
- *
- * @since 1.5
+ * with unique (~= random) names.
*/
protected static final int MAX_TABLE_SIZE = 0x10000; // 64k entries == 256k mem
@@ -31,6 +29,29 @@
*/
final static int MAX_ENTRIES_FOR_REUSE = 6000;
+ /**
+ * Also: to thwart attacks based on hash collisions (which may or may not
+ * be cheap to calculate), we will need to detect "too long"
+ * collision chains. Let's start with static value of 255 entries
+ * for the longest legal chain.
+ *<p>
+ * Note: longest chain we have been able to produce without malicious
+ * intent has been 60 (with "com.fasterxml.jackson.core.main.TestWithTonsaSymbols");
+ * our setting should be reasonable here.
+ *
+ * @since 1.9.9
+ */
+ final static int MAX_COLL_CHAIN_LENGTH = 255;
+
+ /**
+ * And to support reduce likelihood of accidental collisions causing
+ * exceptions, let's prevent reuse of tables with long collision
+ * overflow lists as well.
+ *
+ * @since 1.9.9
+ */
+ final static int MAX_COLL_CHAIN_FOR_REUSE = 63;
+
final static int MIN_HASH_SIZE = 16;
final static int INITIAL_COLLISION_LEN = 32;
@@ -47,8 +68,19 @@
/**********************************************************
*/
- final BytesToNameCanonicalizer _parent;
+ final protected BytesToNameCanonicalizer _parent;
+ /**
+ * Seed value we use as the base to make hash codes non-static between
+ * different runs, but still stable for lifetime of a single symbol table
+ * instance.
+ * This is done for security reasons, to avoid potential DoS attack via
+ * hash collisions.
+ *
+ * @since 1.9.9
+ */
+ final private int _hashSeed;
+
/*
/**********************************************************
/* Main table state
@@ -59,7 +91,7 @@
* Whether canonial symbol Strings are to be intern()ed before added
* to the table or not
*/
- final boolean _intern;
+ private final boolean _intern;
// // // First, global information
@@ -68,6 +100,15 @@
*/
private int _count;
+ /**
+ * We need to keep track of the longest collision list; this is needed
+ * both to indicate problems with attacks and to allow flushing for
+ * other cases.
+ *
+ * @since 1.9.9
+ */
+ protected int _longestCollisionList;
+
// // // Then information regarding primary hash array and its
// // // matching Name array
@@ -162,19 +203,37 @@
/**********************************************************
*/
+ /**
+ * Factory method to call to create a symbol table instance with a
+ * randomized seed value.
+ */
public static BytesToNameCanonicalizer createRoot()
{
- return new BytesToNameCanonicalizer(DEFAULT_TABLE_SIZE, true);
+ /* [Issue-21]: Need to use a variable seed, to thwart hash-collision
+ * based attacks.
+ */
+ long now = System.currentTimeMillis();
+ // ensure it's not 0; and might as well require to be odd so:
+ int seed = (((int) now) + ((int) now >>> 32)) | 1;
+ return createRoot(seed);
}
/**
+ * Factory method that should only be called from unit tests, where seed
+ * value should remain the same.
+ */
+ protected static BytesToNameCanonicalizer createRoot(int hashSeed) {
+ return new BytesToNameCanonicalizer(DEFAULT_TABLE_SIZE, true, hashSeed);
+ }
+
+ /**
* @param intern Whether canonical symbol Strings should be interned
* or not
*/
public synchronized BytesToNameCanonicalizer makeChild(boolean canonicalize,
boolean intern)
{
- return new BytesToNameCanonicalizer(this, intern);
+ return new BytesToNameCanonicalizer(this, intern, _hashSeed);
}
/**
@@ -196,13 +255,12 @@
}
}
- private BytesToNameCanonicalizer(int hashSize, boolean intern)
+ private BytesToNameCanonicalizer(int hashSize, boolean intern, int seed)
{
_parent = null;
+ _hashSeed = seed;
_intern = intern;
- /* Sanity check: let's now allow hash sizes below certain
- * min. value
- */
+ // Sanity check: let's now allow hash sizes below certain minimum value
if (hashSize < MIN_HASH_SIZE) {
hashSize = MIN_HASH_SIZE;
} else {
@@ -223,9 +281,11 @@
/**
* Constructor used when creating a child instance
*/
- private BytesToNameCanonicalizer(BytesToNameCanonicalizer parent, boolean intern)
+ private BytesToNameCanonicalizer(BytesToNameCanonicalizer parent, boolean intern,
+ int seed)
{
_parent = parent;
+ _hashSeed = seed;
_intern = intern;
// First, let's copy the state as is:
@@ -236,6 +296,7 @@
_collList = parent._collList;
_collCount = parent._collCount;
_collEnd = parent._collEnd;
+ _longestCollisionList = parent._longestCollisionList;
_needRehash = false;
// And consider all shared, so far:
_mainHashShared = true;
@@ -246,6 +307,7 @@
private void initTables(int hashSize)
{
_count = 0;
+ _longestCollisionList = 0;
_mainHash = new int[hashSize];
_mainNames = new Name[hashSize];
_mainHashShared = false;
@@ -273,7 +335,8 @@
* One way to do this is to just purge tables if they grow
* too large, and that's what we'll do here.
*/
- if (child.size() > MAX_ENTRIES_FOR_REUSE) {
+ if (child.size() > MAX_ENTRIES_FOR_REUSE
+ || child._longestCollisionList > MAX_COLL_CHAIN_FOR_REUSE) {
/* Should there be a way to get notified about this
* event, to log it or such? (as it's somewhat abnormal
* thing to happen)
@@ -282,6 +345,7 @@
initTables(DEFAULT_TABLE_SIZE);
} else {
_count = child._count;
+ _longestCollisionList = child._longestCollisionList;
_mainHash = child._mainHash;
_mainNames = child._mainNames;
_mainHashShared = true; // shouldn't matter for parent
@@ -309,15 +373,52 @@
public int size() { return _count; }
/**
+ * @since 1.9.9
+ */
+ public int bucketCount() { return _mainHash.length; }
+
+ /**
* Method called to check to quickly see if a child symbol table
* may have gotten additional entries. Used for checking to see
* if a child table should be merged into shared table.
*/
- public boolean maybeDirty()
- {
+ public boolean maybeDirty() {
return !_mainHashShared;
}
+ /**
+ * @since 1.9.9
+ */
+ public int hashSeed() { return _hashSeed; }
+
+ /**
+ * Method mostly needed by unit tests; calculates number of
+ * entries that are in collision list. Value can be at most
+ * ({@link #size} - 1), but should usually be much lower, ideally 0.
+ *
+ * @since 1.9.9
+ */
+ public int collisionCount() {
+ return _collCount;
+ }
+
+ /**
+ * Method mostly needed by unit tests; calculates length of the
+ * longest collision chain. This should typically be a low number,
+ * but may be up to {@link #size} - 1 in the pathological case
+ *
+ * @since 1.9.9
+ */
+ public int maxCollisionLength() {
+ return _longestCollisionList;
+ }
+
+ /*
+ /**********************************************************
+ /* Public API, accessing symbols:
+ /**********************************************************
+ */
+
public static Name getEmptyName()
{
return Name1.getEmptyName();
@@ -441,11 +542,9 @@
*/
public Name findName(int[] quads, int qlen)
{
- /* // Not needed, never gets called
if (qlen < 3) { // another sanity check
return findName(quads[0], (qlen < 2) ? 0 : quads[1]);
}
- */
int hash = calcHash(quads, qlen);
// (for rest of comments regarding logic, see method above)
int ix = (hash & _mainHashMask);
@@ -476,9 +575,6 @@
/**********************************************************
*/
- /**
- * @since 1.6.0
- */
public Name addName(String symbolStr, int q1, int q2)
{
if (_intern) {
@@ -495,7 +591,12 @@
if (_intern) {
symbolStr = InternCache.instance.intern(symbolStr);
}
- int hash = calcHash(quads, qlen);
+ int hash;
+ if (qlen < 3) {
+ hash = (qlen == 1) ? calcHash(quads[0]) : calcHash(quads[0], quads[1]);
+ } else {
+ hash = calcHash(quads, qlen);
+ }
Name symbol = constructName(hash, symbolStr, quads, qlen);
_addSymbol(hash, symbol);
return symbol;
@@ -507,45 +608,72 @@
/**********************************************************
*/
- public final static int calcHash(int firstQuad)
+ /* Note on hash calculation: we try to make it more difficult to
+ * generate collisions automatically; part of this is to avoid
+ * simple "multiply-add" algorithm (like JDK String.hashCode()),
+ * and add bit of shifting. And other part is to make this
+ * non-linear, at least for shorter symbols.
+ */
+
+ // JDK uses 31; other fine choices are 33 and 65599, let's use 33
+ // as it seems to give fewest collisions for us
+ // (see [http://www.cse.yorku.ca/~oz/hash.html] for details)
+ private final static int MULT = 33;
+
+ public final int calcHash(int firstQuad)
{
+ int hash = firstQuad ^ _hashSeed;
+ hash += (hash >>> 15); // to xor hi- and low- 16-bits
+ hash ^= (hash >>> 9); // as well as lowest 2 bytes
+ return hash;
+ }
+
+ public final int calcHash(int firstQuad, int secondQuad)
+ {
+ /* For two quads, let's change algorithm a bit, to spice
+ * things up (can do bit more processing anyway)
+ */
+
int hash = firstQuad;
- hash ^= (hash >>> 16); // to xor hi- and low- 16-bits
- hash ^= (hash >>> 8); // as well as lowest 2 bytes
+ hash += (hash >>> 15); // try mixing first and second byte pairs first
+ hash ^= ((secondQuad + _hashSeed) * MULT); // then add second quad
+ hash += (hash >>> 9); // and shuffle some more
return hash;
}
- public final static int calcHash(int firstQuad, int secondQuad)
+ public final int calcHash(int[] quads, int qlen)
{
- int hash = (firstQuad * 31) + secondQuad;
-
- // If this was called for single-quad instance:
- //int hash = (secondQuad == 0) ? firstQuad : ((firstQuad * 31) + secondQuad);
-
- hash ^= (hash >>> 16); // to xor hi- and low- 16-bits
- hash ^= (hash >>> 8); // as well as lowest 2 bytes
- return hash;
- }
-
- public final static int calcHash(int[] quads, int qlen)
- {
- // Note: may be called for qlen < 3
- int hash = quads[0];
- for (int i = 1; i < qlen; ++i) {
- hash = (hash * 31) + quads[i];
+ // Note: may be called for qlen < 3; but has at least one int
+ if (qlen < 3) {
+ throw new IllegalArgumentException();
}
- hash ^= (hash >>> 16); // to xor hi- and low- 16-bits
- hash ^= (hash >>> 8); // as well as lowest 2 bytes
+ /* And then change handling again for "multi-quad" case; mostly
+ * to make calculation of collisions less fun. For example,
+ * add seed bit later in the game, and switch plus/xor around,
+ * use different shift lengths.
+ */
+ int hash = quads[0];
+ hash ^= (hash >>> 9);
+ hash += ((quads[1] + _hashSeed) * MULT);
+ hash ^= (hash >>> 15);
+ hash ^= (quads[2] * MULT);
+ hash += (hash >>> 17);
+
+ for (int i = 3; i < qlen; ++i) {
+ hash = (hash * MULT) + (quads[i] + 1);
+ // for longer entries, mess a bit in-between too
+ hash ^= (hash >>> 3);
+ }
+ // and finally shuffle some more once done
+ hash += (hash >>> 15); // to get high-order bits to mix more
+ hash ^= (hash >>> 9); // as well as lowest 2 bytes
return hash;
}
- /* 26-Nov-2008, tatu: not used currently; if not used in near future,
- * let's just delete it.
- */
- /*
- public static int[] calcQuads(byte[] wordBytes)
+ // Method only used by unit tests
+ protected static int[] calcQuads(byte[] wordBytes)
{
int blen = wordBytes.length;
int[] result = new int[(blen + 3) / 4];
@@ -565,7 +693,6 @@
}
return result;
}
- */
/*
/**********************************************************
@@ -647,7 +774,6 @@
if (_collListShared) {
unshareCollision(); // also allocates if list was null
}
-
++_collCount;
int entryValue = _mainHash[ix];
int bucket = entryValue & 0xFF;
@@ -669,7 +795,13 @@
}
// And then just need to link the new bucket entry in
- _collList[bucket] = new Bucket(symbol, _collList[bucket]);
+ Bucket newB = new Bucket(symbol, _collList[bucket]);
+ _collList[bucket] = newB;
+ // but, be careful wrt attacks
+ _longestCollisionList = Math.max(newB.length(), _longestCollisionList);
+ if (_longestCollisionList > MAX_COLL_CHAIN_LENGTH) {
+ reportTooManyCollisions(MAX_COLL_CHAIN_LENGTH);
+ }
}
/* Ok. Now, do we need a rehash next time? Need to have at least
@@ -735,6 +867,7 @@
*/
int oldEnd = _collEnd;
if (oldEnd == 0) { // no prior collisions...
+ _longestCollisionList = 0;
return;
}
@@ -742,6 +875,8 @@
_collEnd = 0;
_collListShared = false;
+ int maxColl = 0;
+
Bucket[] oldBuckets = _collList;
_collList = new Bucket[oldBuckets.length];
for (int i = 0; i < oldEnd; ++i) {
@@ -774,11 +909,15 @@
--bucket; // 1-based index in value
}
// And then just need to link the new bucket entry in
- _collList[bucket] = new Bucket(symbol, _collList[bucket]);
+ Bucket newB = new Bucket(symbol, _collList[bucket]);
+ _collList[bucket] = newB;
+ maxColl = Math.max(maxColl, newB.length());
}
} // for (... buckets in the chain ...)
} // for (... list of bucket heads ... )
+ _longestCollisionList = maxColl;
+
if (symbolsSeen != _count) { // sanity check
throw new RuntimeException("Internal error: count after rehash "+symbolsSeen+"; should be "+_count);
}
@@ -791,6 +930,7 @@
private void nukeSymbols()
{
_count = 0;
+ _longestCollisionList = 0;
Arrays.fill(_mainHash, 0);
Arrays.fill(_mainNames, null);
Arrays.fill(_collList, null);
@@ -906,6 +1046,21 @@
/*
/**********************************************************
+ /* Other helper methods
+ /**********************************************************
+ */
+
+ /**
+ * @since 1.9.9
+ */
+ protected void reportTooManyCollisions(int maxLen)
+ {
+ throw new IllegalStateException("Longest collision chain in symbol table (of size "+_count
+ +") now exceeds maximum, "+maxLen+" -- suspect a DoS attack based on hash collisions");
+ }
+
+ /*
+ /**********************************************************
/* Helper classes
/**********************************************************
*/
@@ -914,21 +1069,16 @@
{
protected final Name _name;
protected final Bucket _next;
+ private final int _length;
Bucket(Name name, Bucket next)
{
_name = name;
_next = next;
+ _length = (next == null) ? 1 : next._length+1;
}
- public int length()
- {
- int len = 1;
- for (Bucket curr = _next; curr != null; curr = curr._next) {
- ++len;
- }
- return len;
- }
+ public int length() { return _length; }
public Name find(int hash, int firstQuad, int secondQuad)
{
diff --git a/src/java/org/codehaus/jackson/sym/CharsToNameCanonicalizer.java b/src/java/org/codehaus/jackson/sym/CharsToNameCanonicalizer.java
index 76badc3..11c0650 100644
--- a/src/java/org/codehaus/jackson/sym/CharsToNameCanonicalizer.java
+++ b/src/java/org/codehaus/jackson/sym/CharsToNameCanonicalizer.java
@@ -346,9 +346,11 @@
*/
public int size() { return _size; }
-
+
public boolean maybeDirty() { return _dirty; }
+ public int bucketCount() { return _symbols.length; }
+
/**
* Method mostly needed by unit tests; calculates number of
* entries that are in collision list. Value can be at most
@@ -392,8 +394,7 @@
return new String(buffer, start, len);
}
- hash &= _indexMask;
-
+ hash = _hashToIndex(hash);
String sym = _symbols[hash];
// Optimal case; checking existing primary symbol for hash index:
@@ -429,7 +430,7 @@
/* Need to recalc hash; rare occurence (index mask has been
* recalculated as part of rehash)
*/
- hash = calcHash(buffer, start, len) & _indexMask;
+ hash = _hashToIndex(calcHash(buffer, start, len));
}
String newSymbol = new String(buffer, start, len);
@@ -453,6 +454,12 @@
return newSymbol;
}
+ /*
+ /**********************************************************
+ /* Hash calculation
+ /**********************************************************
+ */
+
/**
* Implementation of a hashing method for variable length
* Strings. Most of the time intention is that this calculation
@@ -479,6 +486,16 @@
return hash;
}
+ /**
+ * Helper method that takes in a "raw" hash value, shuffles it as necessary,
+ * and truncates to be used as the index.
+ */
+ private final int _hashToIndex(int rawHash)
+ {
+ rawHash += (rawHash >>> 15); // this seems to help quite a bit, at least for our tests
+ return (rawHash & _indexMask);
+ }
+
/*
/**********************************************************
/* Internal methods
@@ -546,7 +563,7 @@
String symbol = oldSyms[i];
if (symbol != null) {
++count;
- int index = calcHash(symbol) & _indexMask;
+ int index = _hashToIndex(calcHash(symbol));
if (_symbols[index] == null) {
_symbols[index] = symbol;
} else {
@@ -564,7 +581,7 @@
while (b != null) {
++count;
String symbol = b.getSymbol();
- int index = calcHash(symbol) & _indexMask;
+ int index = _hashToIndex(calcHash(symbol));
if (_symbols[index] == null) {
_symbols[index] = symbol;
} else {
diff --git a/src/mapper/java/org/codehaus/jackson/map/ser/BasicSerializerFactory.java b/src/mapper/java/org/codehaus/jackson/map/ser/BasicSerializerFactory.java
index 5f6f418..76de697 100644
--- a/src/mapper/java/org/codehaus/jackson/map/ser/BasicSerializerFactory.java
+++ b/src/mapper/java/org/codehaus/jackson/map/ser/BasicSerializerFactory.java
@@ -7,7 +7,6 @@
import java.util.*;
import org.codehaus.jackson.map.*;
-import org.codehaus.jackson.map.annotate.JacksonStdImpl;
import org.codehaus.jackson.map.annotate.JsonSerialize;
import org.codehaus.jackson.map.ext.OptionalHandlerFactory;
import org.codehaus.jackson.map.introspect.*;
diff --git a/src/test/org/codehaus/jackson/map/ser/TestNullSerialization.java b/src/test/org/codehaus/jackson/map/ser/TestNullSerialization.java
index 37b0947..4a3ca98 100644
--- a/src/test/org/codehaus/jackson/map/ser/TestNullSerialization.java
+++ b/src/test/org/codehaus/jackson/map/ser/TestNullSerialization.java
@@ -51,7 +51,7 @@
ObjectMapper mapper = new ObjectMapper();
mapper.setAnnotationIntrospector(new JacksonAnnotationIntrospector());
mapper.setSerializationInclusion(Inclusion.NON_NULL);
- assertEquals("{\"value\":\"abc\"}", mapper.writeValueAsString(new NullBean("abc")));
- assertEquals("{}", mapper.writeValueAsString(new NullBean(null)));
+ assertEquals("{\"value\":\"abc\"}", mapper.writeValueAsString(new NullBean<String>("abc")));
+ assertEquals("{}", mapper.writeValueAsString(new NullBean<String>(null)));
}
}
diff --git a/src/test/org/codehaus/jackson/sym/TestSymbolTables.java b/src/test/org/codehaus/jackson/sym/TestSymbolTables.java
index c6d6664..023ff71 100644
--- a/src/test/org/codehaus/jackson/sym/TestSymbolTables.java
+++ b/src/test/org/codehaus/jackson/sym/TestSymbolTables.java
@@ -1,5 +1,7 @@
package org.codehaus.jackson.sym;
+import java.io.IOException;
+
public class TestSymbolTables extends main.BaseTest
{
// 11 3-char snippets that hash to 0xFFFF (with default JDK hashCode() calc),
@@ -51,4 +53,80 @@
assertEquals(CharsToNameCanonicalizer.MAX_COLL_CHAIN_LENGTH+2, sym.size());
}
}
+
+ // Test for verifying stability of hashCode, wrt collisions, using
+ // synthetic field name generation and character-based input
+ public void testSyntheticWithChars()
+ {
+ // pass seed, to keep results consistent:
+ CharsToNameCanonicalizer symbols = CharsToNameCanonicalizer.createRoot();
+ final int COUNT = 6000;
+ for (int i = 0; i < COUNT; ++i) {
+ String id = fieldNameFor(i);
+ char[] ch = id.toCharArray();
+ symbols.findSymbol(ch, 0, ch.length, CharsToNameCanonicalizer.calcHash(id));
+ }
+
+ assertEquals(8192, symbols.bucketCount());
+ assertEquals(COUNT, symbols.size());
+
+//System.out.printf("Char stuff: collisions %d, max-coll %d\n", symbols.collisionCount(), symbols.maxCollisionLength());
+
+ // original hashCode calc gave very high rate (3567), but with shuffling comes down a bit
+ // (changing mult to 33 would help more)
+ assertEquals(1905, symbols.collisionCount());
+ // esp. with collisions; first got about 30
+ assertEquals(6, symbols.maxCollisionLength());
+ }
+
+ // Test for verifying stability of hashCode, wrt collisions, using
+ // synthetic field name generation and byte-based input (UTF-8)
+ public void testSyntheticWithBytes() throws IOException
+ {
+ // pass seed, to keep results consistent:
+ BytesToNameCanonicalizer symbols = BytesToNameCanonicalizer.createRoot(1);
+ final int COUNT = 6000;
+ for (int i = 0; i < COUNT; ++i) {
+ String id = fieldNameFor(i);
+ int[] quads = BytesToNameCanonicalizer.calcQuads(id.getBytes("UTF-8"));
+ symbols.addName(id, quads, quads.length);
+ }
+ assertEquals(COUNT, symbols.size());
+ assertEquals(8192, symbols.bucketCount());
+
+//System.out.printf("Byte stuff: collisions %d, max-coll %d\n", symbols.collisionCount(), symbols.maxCollisionLength());
+
+ // Fewer collisions than with chars, but still quite a few
+ assertEquals(1770, symbols.collisionCount());
+ // but not super long collision chains:
+ assertEquals(9, symbols.maxCollisionLength());
+ }
+
+ protected void fieldNameFor(StringBuilder sb, int index)
+ {
+ /* let's do something like "f1.1" to exercise different
+ * field names (important for byte-based codec)
+ * Other name shuffling done mostly just for fun... :)
+ */
+ sb.append("f");
+ sb.append(index);
+ if (index > 50) {
+ sb.append('.');
+ if (index > 200) {
+ sb.append(index);
+ if (index > 4000) { // and some even longer symbols...
+ sb.append(".").append(index);
+ }
+ } else {
+ sb.append(index >> 3); // divide by 8
+ }
+ }
+ }
+
+ protected String fieldNameFor(int index)
+ {
+ StringBuilder sb = new StringBuilder(16);
+ fieldNameFor(sb, index);
+ return sb.toString();
+ }
}
