Algorithmic complexity attacks

Most code is fast on average and slow in the worst case. An algorithmic complexity attack is an attacker choosing the worst case deliberately. No memory corruption and no injection, just input costing 100,000 times more to process than to send.

The economics make it dangerous: a 50-byte request burning 30 seconds of CPU lets one laptop saturate a fleet, and it bypasses rate limiting because the request rate is trivially low.

1. ReDoS: catastrophic backtracking

Most engines (PCRE, Java, JavaScript, Python re, .NET, Ruby) backtrack. On a non-match they try every way to divide the input among quantifiers. When two quantifiers can match the same characters, the number of ways is exponential.

Vulnerable shapes:

(a+)+          nested quantifier
(a|a)*         alternation with overlapping branches
(a|ab)*        overlapping alternatives
\s*$           trailing quantifier with an anchor on a long whitespace run
^(\w+\s?)*$    the classic, since \w and \s? both consume the boundary