06 June 2012

Some interesting stuff has all seemed to jump across my screen over the past few weeks regarding JVM concurrency. Here's a brief run-down:

The last link about the changes to ConcurrentHashMap is interesting because we generally think of hash maps as O(1). Here, they're changing what is perhaps the most used HashMap implementation in the world to gracefully degrade to O(log(N)) in some scenarios where lookup times would exceed the general O(1) case.

What's particularly interesting about this HashMap revamp is that it helps resolve a class of security vulnerabilities around overflow bins in HashMaps when the keyspace has a large number of collisions. This ties into this sort of vulnerability, whereby attackers can craft special query parameters designed to create HashMaps that act more like O(n) lookup linked lists, and cause a DoS by causing a hash of query parameters to become extremely slow.

There are other fixes for that particular vuln (creating a random hash salt at runtime start is the way ruby does it), however, Doug Lea's approach is perhaps better in that it handles the general case of excessive hash collisions in a more elegant way by using a tree-map-like structure to handle those cases, instead of the standard linked list.



blog comments powered by Disqus