adversarial input
Input chosen deliberately by someone who wants your code to behave badly, often by hitting its worst case.
Any structure whose worst case is slow can be driven there by whoever controls its input.
In more detail
Average-case promises assume inputs are typical, and an attacker is under no obligation to be typical. Crafted colliding keys defeat a predictable hash table, and sorted input turns an unbalanced search tree into a list. Worst-case guarantees, such as those of AVL trees or randomised hashing, are what hold up against it.
Related terms
- hash flooding — An attack that sends a server many keys crafted to collide in its hash tables, turning each O(1) operation into O(n) and exhausting its CPU.
- worst case — The input of a given size that makes an algorithm do the most work, and the cost on that input.
- AVL tree — A self-balancing binary search tree in which the heights of every node's two subtrees differ by at most one.
Taught in
- What A Hash Function Promises — Algorithms & Data Structures for Working Engineers
- Collisions In Practice And Hash Flooding — Algorithms & Data Structures for Working Engineers
- AVL Trees: Rotations That Keep The Guarantee — Algorithms & Data Structures for Working Engineers