Algorithmic complexity attack

      An Algorithmic complexity Attack (ACA) is a form of attack in which the system is attacked by an exhaustion resource to take advantage of worst-case performance.  Worst-case performance through a back-end algorithm results in the exhaustion of the server, this creates algorithmic complexity vulnerabilities. According to Adam Jacobson and Dr. David Renardy, research scientists from Two Six Labs,  “An AC Time vulnerability causes denial of service by exhausting CPU while AC Space vulnerabilities exhaust RAM or disk space.” Examples of ACA attacks are zip-bombs, billion laughs, and ReDoS which are Malicious files aimed to render a program useless. Additionally, as stated by the Cybersecurity and Infrastructure Security Agency, a department within the Department of Homeland Security, “A denial-of-service (DoS) attack occurs when legitimate users are unable to access information systems, devices, or other network resources due to the actions of a malicious cyber threat actor. Services affected may include email, websites, online accounts (e.g., banking), or other services that rely on the affected computer or network.” In other words, DoS attacks are a form of an attack in which a hacker can flood a server which outputs a denial of service error. ACA and DDoS attacks are forms of denial of service attacks in which the hacker can gain information through the Schemas files and its structure. On October 2022, Google released that they experienced the largest DDoS attack to date that took place in September of 2017. Algorithmic complexity and its vulnerabilities are the main components that have given hackers ways to attack algorithms and its servers.

Examples

• Billion laughs
• 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" (PDF). Archived (PDF) from the original on 2010-07-14. Retrieved 2010-06-16.
• Scott A Crosby; Dan S Wallach (2003). "Denial of Service via Algorithmic Complexity Attacks". Archived from the original on 2007-02-02. Retrieved 2010-06-16.