hunting-redos-and-complexity-dos

Hunting ReDoS and algorithmic-complexity denial of service: when one request burns the CPU

Most denial of service is discussed as flooding: many requests exhausting a pool. The quieter and more dangerous kind is a single small request that pins a CPU core for seconds or minutes, because somewhere the work grows faster than the input. A regular expression with an ambiguous quantifier, a loop that is accidentally quadratic, a parser with no depth limit, or a hash table fed attacker-chosen keys all turn a few kilobytes of input into a stall that a timeout may not even interrupt. You find these by tracing untrusted input to any operation whose cost is super-linear and asking whether anything bounds the work before it runs.

When to use

• Untrusted input reaches a regular expression, a parser, a sort or dedup, or a hash-keyed structure.
• A single small request could pin a CPU core or stall the event loop, not just exhaust connections.
• Input size, nesting depth, or total work is not bounded before the expensive operation runs.

Scope check

Drive worst-case input only against systems you own or are authorized to test, and coordinate: a confirmed complexity bug can take a shared service offline. Measure on a target and load where a stall is acceptable. If you can't name the authorization, stop.

The loop

1. Map untrusted input to expensive operations. Inventory where request-controlled strings, collections, or numbers reach a regular expression, a recursive or backtracking parser, a nested loop over input, a sort or dedup, or a hash-keyed collection. These are the operations whose cost can grow faster than linearly in the size of the input, so these are where a small request buys disproportionate work.

2. Find the super-linear regular expressions. Read each expression that touches untrusted input for the backtracking shapes: a quantified group inside another quantifier such as (a+)+, overlapping alternation under a quantifier such as (a|a)*, and a quantified class followed by a character the class can also match. On an input that almost matches and then fails at the end, the engine explores exponentially or polynomially many paths. A crafted string of a few kilobytes can run for seconds.