A variety of techniques and strategies are presented for protecting a data structure, e.g., a hash table, from an attacker who wishes to force worst-case performance. Many data structures are designed with fast and efficient insertion and lookup functionality under normal use-case scenarios. However, when forced into a worst-case context, the performance of the data structure is undermined and services relying on the data structure are impacted. The techniques presented maintain the high performance under normal use-case while protecting the data structure from malicious use.
Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.
Pike, Geoffrey and Lebar, Justin, "TWO-STEP BUCKETING TO ACHIEVE HIGH PERFORMANCE DATA STRUCTURES", Technical Disclosure Commons, (February 25, 2015)