7
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ I recently heard a nice talk about work on password protection (salt/pepper stuff) that proposed adding "garlic" to enforce a certain level of non-parallelism for the attacker. The security argument was via a pebbling game that showed that processor parallelism required high memory (which defeats, e.g., highly parallel GPU attacks on password databases). The point being: the intuitive (though informal) contrapositive would be "Highly parallel algorithms are more resistant to resource consumption attacks." It's unclear how generally this can be applied, but it's a starting thought. =) $\endgroup$
    – Daniel Apon
    Commented Dec 18, 2012 at 15:47
  • $\begingroup$ @Daniel Apon that is a good point. $\endgroup$
    – The Rook
    Commented Dec 18, 2012 at 17:07

1 Answer 1

Reset to default
1
$\begingroup$

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, & 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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.