Algorithmic-complexity attacks have been all over the news lately:

• Supercolliding a PHP array
• Effective DoS attacks against Web Application Plattforms – #hashDos
• oCERT Advisory: multiple implementations denial-of-service via hash algorithm collision

This type of attack is well known, causes significant service failures, and can even happen accidentally (such as when Wikipedia crashed while covering news of Michael Jackson’s Death, [1], [2]).

Ever since I discovered my first algorithmic-complexity vulnerability while in undergrad, I’ve kept an eye out for these vulnerabilities. They’re everywhere. I’ve even used an algorithmic-complexity attack to take down a radar during a live-fire ballistic-missile-defense exercise. Our servers, operating systems, programming languages, and best practices do not prevent them.

So while I was in grad school I set out to change that by developing a method to probabilistically guarantee immunity against algorithmic complexity attacks.

Here’s the gist of how you can defend your software from alg-complexity attacks.

Provably Protecting Servers From Algorithmic Complexity Attacks

1. Enforce a minimum inter-arrival time between incoming requests (you really only need to do this during an overload)
2. When the system becomes overloaded, do not queue up incoming requests. Rather, kick out old requests that are using up too many resources.
3. By assuming a probability distribution on the resource requirements of legitimate requests, this method can provide guarantees of the form: with probability at least X, at least Y legitimate requests will complete on time.

You can read the nitty gritty details in this technical report (including a mathematical proof of the guarantee as well as experimental results from attacking Mediawiki).

To finish the work I’m planning on (1) implementing my technique as an enhancement to FastCGI, (2) finding a bunch of real-world vulnerabilities, (3) then doing experiments that demonstrate the effectiveness of my defense against 0-day attacks. Anyone interested on collaborating?

Hit me up with an email (mikegagnon at gmail) or follow me on Twitter.