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 fro
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. 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.

Back-end algorithms

Back-end Algorithms refers to the subjects that the user cannot 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 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 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. ReDoS attacks take advantage of "evil" aspects of a regular expression( regex) which overloads the server making it inaccessible to its users. According to a study by Adar Weidman, a Code Analysis Architect at th
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. It is also important to know that ReDoS can breach sensitive user information. According to Contrast Security, "Other repercussions include penalties from sensitive data exposure, which result in $50,000 per attack on average."

Exponential Entity Expansion Attack

Otherwise known as XML bombs, these attacks are a form of DDoS attacks that are 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 customer 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) According to an article from StackOverflow, a trusted resource for developers, data scientists, and cyber security personnel, " XXE attack when performed successfully can disclose local files in the file system of the website.  XXE is targeted to access these sensitive local files of the website that is vulnerable to unsafe parsing." It is like an unsafe guessable password; XML documents give precise information about its users.

Simplified Example of a Schema File:

Max

    26

    Lead

 

 

    Sarah

    25

    Developer

 

Zip bomb

ZIP bombs are malicious archive file designed to crash or render a program useless. One example of a zip bomb is the file ''42.zip'', which is a file consisting of 42 kilobytes of compressed data, containing five layers of each bottom-layer archive that contains 4.3- gigabytes. Unlike other ways of high-jacking a system, zip bombs use compressed files to that take excessive amount of disk space, time, or memory once unpacked/opened. Often times zip bomb attackers target unknowing employees from start-ups and big corporations to open the zip files through an email. The attacker then uses the decompressed archive file for ransomed to disarm the file. "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."(Afek, Barr, Harchol, Hay, Koral)

Google DDoS attack

DDoS attacks are a form of attack orchestrated by multiple networks pinning on one Web server to create a denial-of-service error. DDoS attacks are distributed throughout multiple networks around the globe as to where DoS attacks are done by one single attacker/network. DDoS attacks are far more difficult to address because of the multiple networks pinning to overload the server. It is difficult to find the attacks origin through a DDoS attack due to multiple networks attacking at once. 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. According 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."

References

Works cited

*
*
* 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.''

Algorithmic complexity attacks

{{computer-security-stub