Algorithmic complexity attack

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” [3] 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 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."[4] 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[5] " 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."[6](Adamchik)

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 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.” [7] 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."[8]

an unsafe XML Scheme file shows the precise structure of data and the information that the user inputs.

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.” [9] (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."[10] It is like an unsafe guessable password; XML documents give precise information about its users.

Simplified Example of a Schema File:

<name> Max </name>

   <Age> 26 </Age>

   <occupation> Lead </occupation>

 </profile>

 <profile>

   <name> Sarah </name>

   <Age> 25 </Age>

   <occupation> Developer </occupation>

 </profile>

</profiles>

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."[11](Afek, Barr, Harchol, Hay, Koral)

A chart of the DDoS attack Google prevented through the cloud which totally over 46 million rps

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."[12]

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