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
In computer science, best, worst, and average cases of a given algorithm express what the resource usage is ''at least'', ''at most'' and ''on average'', respectively. Usually the resource being considered is running time, i.e. time complexity, b ...
of the algorithms it uses. In turn, this may exhaust the resources the system uses. Examples of such attacks include
ReDOS
A regular expression denial of service (ReDoS)
is an algorithmic complexity attack that produces a denial-of-service by providing a regular expression and/or an input that takes a long time to evaluate. The attack exploits the fact that many re ...
,
and
exponential entity expansion attacks.
References
Related works
*
*
* 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
{{computer-security-stub