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

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. All factors such as the hardware, networking, programming language, and performance constraints play into the time a program takes to output the desired project. It is important for data scientists to calculate the time an algorithm will take to better under ways to make it more efficient. According to a study done by, The University of Southern California, "The complexity is defined as a numerical function T(n). T(n) is the time that the algorithm performs versus the input size n." In other words, the complexity is calculated by the time the algorithm takes to run the module, T(n) multiplied by the input size of the program(n). This is otherwise known as the big O notation. Additionally, Allen Tucker, a computer science professor at Bowdoin College, stated "Computational complexity is a continuum, in that some algorithms require linear time (that is, the time required increases directly with the number of items or nodes in the list, graph, or network being processed), whereas others require quadratic or even exponential time to complete " As previously stated, although there are multiple ways to create a program it is important to be able calculate the efficiency of an algorithm to better classify and make the algorithms run on a best-case scenario. "The goal of computational complexity is to classify algorithms according to their performances."(Adamchik)

ReDoS

Regular expression Denial of Service attacks are a type of DoS in which the attacker uses inputs that take a long time for the computer to evaluate/process. ReDoS attacks take advantage of the most expensive regular expression features, which overloads the server making it inaccessible to its users. According to a study by Adar Weidman, a Code Analysis Architect at the OWASP Foundation, “In every layer of the WEB there are Regular Expressions, that might contain an Evil Regex. An attacker can hang a WEB-browser (on a computer or potentially also on a mobile device), hang a Web Application Firewall (WAF), attack a database, and even stack a vulnerable WEB server.” This type of an attack could be costly to big corporations because application outages caused by ReDoS can degrade the operational efficiency, reduced revenues, and damaged the brand reputation.

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.