[CLOWNFISH-110] Exposure of Hash iteration order allows for O(n²) blowup

• Type: Bug
• Status: Open
• Priority: Major
• Resolution: Unresolved
• Component/s: Runtime
• Assignee: Unassigned
• Reporter: Nikolas Wellnhofer
• Created: 25/Nov/16 15:15
• Updated: 04/Feb/17 16:25

Description

Our Hash implementation uses open addressing with linear probing, so we're susceptible to the same performance bug that was recently discovered in Rust:

https://github.com/rust-lang/rust/issues/36481
http://accidentallyquadratic.tumblr.com/post/153545455987/rust-hash-iteration-reinsertion

Short explanation: When copying entries from one hash table to another using HashIterator to read the source table, the entries are inserted in in-memory order. If the target hash table wasn't resized to the final capacity yet, this can result in quadratic behavior.

We have a maximum fill factor of 2/3 compared to 9/10 in the Rust implementation, so this problem should be much less pronounced.

A possible fix is to randomize the hash function (or iteration order) for each table which is closely related to CLOWNFISH-48.

Issue Links

• is related to: CLOWNFISH-48 Protect Hash against algorithmic complexity attacks