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?