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 include zip bombs, billion laughs attacks, 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. In October 2022, Google released that they experienced the largest DDoS attack to date that took place in September 2017. Algorithmic complexity and its vulnerabilities are the main components that have given hackers ways to attack algorithms and its servers.

Algorithmic complexity

Main article: computational complexity

Algorithmic complexity is the rate in which an algorithm performs. Although there are multiple ways to solve a computational problem, the best and most effective way in doing so matters. For real programs, factors such as the hardware, networking, programming language, and performance constraints play into the time a program takes to output the desired result.

ReDoS

Main article: ReDoS

Exponential entity expansion attack

Main article: Billion laughs attack

Zip bomb

Main article: Zip bomb

Works cited

• Grechishnikov, E V; Dobryshin, M M; Kochedykov, S S; Novoselcev, V I (April 2019). "Algorithmic model of functioning of the system to detect and counter cyber attacks on virtual private network". Journal of Physics: Conference Series. 1203 (1): 012064. Bibcode:2019JPhCS1203a2064G. doi:10.1088/1742-6596/1203/1/012064. S2CID 149475216. ProQuest 2566108871.
• Afek, Yehuda; Bremler-Barr, Anat; Harchol, Yotam; Hay, David; Koral, Yaron (December 2016). "Making DPI Engines Resilient to Algorithmic Complexity Attacks". IEEE/ACM Transactions on Networking. 24 (6): 3262–3275. doi:10.1109/TNET.2016.2518712. S2CID 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, ieeexplore-ieee-org.eznvcc.vccs.edu/document/7323843.
• Kiner, Emil, and Satya Konduru. “How Google Cloud Blocked 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.
• Weidman, Regular Expression Denial of Service - ReDoS | OWASP Foundation. owasp.org/www-community/attacks/Regular_expression_Denial_of_Service_-_ReDoS.
• Microfocus ,(C) 2018 Micro Focus, www.microfocus.com/documentation/extend-acucobol/925/BKITITNONVS004.html.