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.

Back-end Algorithms

Back-end Algorithms refers to the subjects that the user can not interact with. In other words, It is the instructions for the computer: it is how everything works in the background. A recent study done by Seyed Alireza Fayazi and Ardalan Vahidi on the timing of pre-timed traffic signals in the presence of algorithmic queues gives an example on how back-end algorithms work, “The input data source of the crowdsourced-based SPaT estimation is probe vehicle data which can be gathered from vehicles of any kind reporting at least their GPS coordinate and velocity at a timestamp, as long as the location privacy of contributing vehicles is preserved. This input data feed is collected by the Crowdsourcing Server” In short, the data from the vehicles velocity to the GPS coordinate are stored into the Crowdsourced server, all of this happens in the back, but all the driver knows is that the light is timed. While the front-end part of the algorithm is the part of the website users can see and interact with such as the graphical user interface (GUI), the back-end aspect are the lines of code behind the project.

·      

Algorithmic Complexity

Algorithmic complexity is the rate in which an algorithm preforms. The complexity is defined as a numerical function T(n). T(n) is the time that the algorithm preforms versus the input size n. Acording to an academic published

“The goal of computational complexity is to classify algorithms according to their performances."

ReDoS

Regular expression Denial of Service attacks are a type of DDoS in which the attacks uses a regular expression(Regex) to create a denial of service error. The error is produced when the program is unable the evaluate the expression because of the input size. 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.”

Billion Laughs

Also known as XML bombs these attacks are a form of DDoS attacks in which is aimed at parsers of XML documents. In short it is the transport or data stream of information on strictly text files. For example, XML documents of e-commerce transactions, server APIs, and costumer information can be stolen through XML attacks. “Documents that include and obey a schema rather than a DTD are considered to be "schema-valid." Schemas are files describing the XML document and its precise structure.”  (microfocus)

Zip Bomb

“These crafted packets, which we call heavy packets, are on the one hand easy to construct, while on the other hand, require very intensive processing from the system. This implies that with a little effort on the attacker side, the target system spends a lot of effort and is bound to lose.” (Afek, Barr, Harchol, Hay, Koral)  ZIP bombs in line of NIPs Attacks are malicious archive file designed to crash or render the program useless.  (Crafted pockets)

Google DDoS Attack

A chart of the DDoS attack Google prevented through the cloud.

The attack targeted Google services and reached a size of 2.54 Tbps. Google Cloud disclosed the attack in October 2020. Google was able to stop the breach attack through google cloud server algorithms. Accoding to the Google Cloud Blog, "On June 1, a Google Cloud Armor customer was targeted with a series of HTTPS DDoS attacks which peaked at 46 million requests per second. This is the largest Layer 7 DDoS reported to date—at least 76% larger than the previously reported record."

Work 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: 012064. 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.