Algorithmic Complexity Attacks I am studying algorithm construction and weaknesses to resource consumption.  One vulnerability that really caught my eye was the Apache Range Header DoS Vulnerability.  The following quote was taken from Apache developers discussing the flaw:


  From looking at the code, I think the problem is the bucket structs.
  With N the number of requested ranges, the initial brigade is
  partitioned into 2*N buckets at the maximum. Then those buckets are
  copied into the output brigade N times, which means that O(N^2)
  buckets are created. The data is not copied, and only N "A-B" strings
  are allocated from the pool.


Does anyone else know of other resources about building algorithms that are resistant to resource exhaustion attacks?   Does anyone of interesting papers related to Algorithmic analysis and susceptibility to resource exhaustion?  Do you know of other resource consumption vulnerabilities that where caused by flawed algorithms?
Do you know of other resource consumption vulnerabilities that were caused by flawed algorithms?


this can be a subtle issue because basically any algorithm that processes requests with responses is subject to a Denial of Service attack vulnerability due to being overwhelmed with requests, such that even efficient algorithms can be overwhelmed. in a sense the algorithms are not considered "flawed" until an attacker exploits them, during an ongoing, adaptive race between hackers and researchers employing countermeasures. 

one famous example from history is the so-called Ping of Death which led to large attacks in 2000 against Yahoo, CNN, eBay, Dell, &amp; Amazon by the hacker "mafiaboy". ref [1] lists the 10 most famous attacks of the past 25 years several of which are DoS attacks. however, some other algorithms are not discovered to be inefficient until hackers find methods/attack vectors for "bogging them down" and the Apache vulnerability you mention apparently fits into that category. 

there are large amounts of research into DoS prevention techniques eg refs below.

[1] Hackers’ Most Destructive Attacks, DailyBeast

[2] Preventing Internet Denial-of-Service with Capabilities Anderson, Roscoe, Wetherall

[3] Denial of service attacks and how to defend against them Razmov

[4] Internet denial of service attacks and defense mechanisms Abliz