Algorithmic complexity attack

An algorithmic complexity attack is a form of computer attack that exploits known cases in which an algorithm used in a piece of software will exhibit worst case behavior. This type of attack can be used to achieve a denial-of-service.

Examples

• Billion laughs
• ReDoS
• Zip bomb

See also

• Adversarial input
• Quicksort - popular and fast in-place sorting algorithm, running $O(n \log n)$ on average, but having $O(n^2)$ behaviour if implemented naïvely.

Further reading

• M. D. McIlroy (1999). "A Killer Adversary for Quicksort". Archived from the original (PDF) on 2010-06-16. Retrieved 2010-06-16.
• Scott A Crosby; Dan S Wallach (2003). "Denial of Service via Algorithmic Complexity Attacks". Archived from the original on 2008-02-23. Retrieved 2010-06-16.