Jump to content

Algorithmic complexity attack

Edit links
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Jasper Deng (talk | contribs) at 01:27, 9 June 2023 (→Algorithmic complexity: cut down tangential content). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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

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.” [3] 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.[4]

Exponential entity expansion attack

Main article: Billion laughs attack

Zip bomb

Main article: Zip bomb

References

  1. ^ "Algorithmic Complexity Vulnerabilities: An Introduction". 7 August 2019.
  2. ^ "(ST04-015) Understanding Denial-of-Service Attacks".
  3. ^ "Regular expression Denial of Service - ReDoS | OWASP Foundation". owasp.org. Retrieved 2022-11-28.
  4. ^ "ReDoS Attack". www.contrastsecurity.com. {{cite web}}: |access-date= requires |url= (help); Missing or empty |url= (help)

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.


Stub icon

This computer security article is a stub. You can help Wikipedia by expanding it.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Algorithmic_complexity_attack&oldid=1159222497"