Algorithmic complexity attack

An algorithmic complexity attack is a form of computer attack that exploits known cases in which an algorithm used in a piece of software will exhibit worst case behavior. This type of attack can be used to achieve a denial-of-service.

Examples
gollark: What's this used for?
gollark: CraftOS is fine because it's basically potatOS.
gollark: Well, squid also does.
gollark: Without hydraz, who would tell us that making OSes is just a really stupid idea?
gollark: I suggested that?

See also
  • Adversarial input
  • Quicksort - popular and fast in-place sorting algorithm, running on average, but having behaviour if implemented naïvely.

Further reading
  • M. D. McIlroy (1999). "A Killer Adversary for Quicksort" (PDF). Archived (PDF) from the original on 2010-06-16. Retrieved 2010-06-16.
  • Scott A Crosby; Dan S Wallach (2003). "Denial of Service via Algorithmic Complexity Attacks". Archived from the original on 2007-02-02. Retrieved 2010-06-16.


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.