Algorithmic complexity attack explained

An algorithmic complexity attack (ACA) is a form of attack in which an attacker sends a pattern of requests to a computer system that triggers the worst-case performance of the algorithms it uses. In turn, this may exhaust the resources the system uses.^[1] Examples of such attacks include ReDOS,^[2] zip bombs and exponential entity expansion attacks.

Related works

• Grechishnikov . E V . Dobryshin . M M . Kochedykov . S S . Novoselcev . V I . Algorithmic model of functioning of the system to detect and counter cyber attacks on virtual private network . Journal of Physics: Conference Series . April 2019 . 1203 . 1 . 012064 . . 10.1088/1742-6596/1203/1/012064 . 2019JPhCS1203a2064G . 149475216. free .
• Afek . Yehuda . Bremler-Barr . Anat . Anat Bremler-Barr. Harchol . Yotam . Hay . David . Koral . Yaron . Making DPI Engines Resilient to Algorithmic Complexity Attacks . IEEE/ACM Transactions on Networking . December 2016 . 24 . 6 . 3262–3275 . 10.1109/TNET.2016.2518712 . 14522075 .
• Vahidi, Ardalan. “Crowdsourcing Phase and Timing of Pre-Timed Traffic Signals in the Presence of Queues: Algorithms and Back-End System Architecture.” Ieeexplore, 1 Nov. 2019, https://ieeexplore.ieee.org/abstract/document/7323843.
• Kiner, Emil, and Satya Konduru. “How Google Cloud Blocked the Largest Layer 7 DDoS Attack yet, 46 Million Rps.” Google Cloud Blog, 18 Aug. 2022, cloud.google.com/blog/products/identity-security/how-google-cloud-blocked-largest-layer-7-ddos-attack-at-46-million-rps.

Notes and References

1. Crosby . Scott A. . Wallach . Dan S. . 2003 . Denial of Service via Algorithmic Complexity Attacks . Proceedings of the 12th USENIX Security Symposium . en.
2. Web site: Regular expression Denial of Service - ReDoS OWASP Foundation . 2023-10-17 . owasp.org . en.