Catastrophic Backtracking and ReDoS

On July 2, 2019, Cloudflare deployed a new WAF rule and CPU usage on every edge machine serving HTTP went to 100%. Global traffic dropped for about 27 minutes. The culprit was a regex containing .*(?:.*=.*). Three years earlier, on July 20, 2016, Stack Overflow was down for 34 minutes because a whitespace-trimming regex, ^[\s\u200c]+|[\s\u200c]+$, met a post containing roughly 20,000 consecutive whitespace characters. Neither pattern looks dangerous. That's the point.

Why it blows up

Take ^(a+)+$ against aaaaaaaaaaaaaaaaaaaaaa!. The $ can never match, so the engine must prove failure by trying every way to split the run of as between the inner + and the outer +. There are 2^(n-1) splits. Each extra character doubles the work:

const evil = /^(a+)+$/;
for (const n of [16, 18, 20, 22, 24]) {
  const input = "a".repeat(n) + "!";
  const t0 = performance.now();
  evil.test(input);
  console.log(n, (performance.now() - t0).toFixed(1) + " ms");
}
// each +2 characters is roughly 4x slower; ~30 characters is seconds, ~40 is "page the on-call"

The three shapes that cause it

1. Nested quantifiers: (a+)+, (\w+\s?)*, (\d+)*$. Exponential.
2. Overlapping alternation under a quantifier: (\w|\d)+, (a|ab)*c, (\s|\S)*. Exponential.
3. Adjacent quantifiers over the same characters: .*.*=.*, \s*\s+$, \d+\d+x. Polynomial: quadratic, cubic, worse with each extra term.

The Stack Overflow case was shape 3 combined with an unanchored search: for each of the 20,000 starting positions, \s+$ scanned to the end of the whitespace run and failed on the next character. That's n²/2, about 200 million steps, for one string.

Fixes, in order of preference

1. Remove the ambiguity. ^(a+)+$ becomes ^a+$, and (\w+\s?)* becomes \w+(?:\s\w+)*. When only one path can match each character, there's nothing to backtrack through.
2. Bound the input. Reject anything over a sane length before the regex sees it. A 4 KB cap turns "exponential" into "annoying."
3. Atomic groups and possessive quantifiers, where supported: (?>\w+), \w++ in PCRE, Java, Python 3.11+.
4. Use a linear-time engine for untrusted input. RE2 (re2 on npm, google-re2 on PyPI), Go, Rust regex. Cloudflare's post-mortem committed to exactly this.
5. Timeouts as a backstop. .NET supports new Regex(pattern, options, TimeSpan.FromMilliseconds(100)). Node and Python have no per-regex timeout, so isolate risky matching in a worker you can kill.

Stack Overflow's actual fix was the best kind: they replaced the regex with a plain trim function. str.trimEnd() cannot backtrack.

Find them before attackers do

• eslint-plugin-regexp with regexp/no-super-linear-backtracking flags risky shapes in review.
• CodeQL ships js/redos and js/polynomial-redos queries. Run them in CI.
• recheck analyzes a pattern and generates an attack string for it.
• Fuzz with near-misses: a long run of the repeated character followed by one that forces failure.

Field notes

• The attack input is always a near-miss. Matching inputs are fast. Almost-matching inputs are where the time goes.
• A user-supplied regex (search filters, "custom alert rules") is untrusted code. Run it on RE2 or not at all.
• Compile once. Pattern.compile inside a Java loop and String.matches (which compiles on every call) are classic hot spots. Python caches recent patterns, but hoist them anyway.
• Put failing-input timing tests next to every regex that guards an endpoint.