Catastrophic Backtracking: How One Regex Can Take Your Site Down

On 20 July 2016, Stack Overflow went down for 34 minutes because of a regex that trimmed whitespace. On 2 July 2019, Cloudflare took a large chunk of the internet offline for 27 minutes because of a regex in a WAF rule. Neither pattern looked dangerous in code review. Both passed every test. I keep coming back to these two incidents because they cured me of a belief most developers quietly hold — that a regex which produces correct matches is a finished regex. It isn't. A regex has a worst-case runtime, and if you never asked what it is, someone else's input will answer for you.

Two Post-Mortems Worth Studying

Stack Overflow, 2016. The culprit was essentially ^[\s‌]+|[\s‌]+$ — trim whitespace from both ends. A post landed on the home page containing a line with roughly 20,000 consecutive whitespace characters that ended in a non-whitespace character. The trailing-trim half of the pattern matched whitespace, hit the non-whitespace end, failed, backed up one character, tried again — about 200 million operations per attempt. This wasn't even exponential — quadratic was enough to pin the CPU of every web server rendering the page.

Cloudflare, 2019. A new WAF rule contained a pattern whose core reduced to .*.*=.*. Two adjacent .* tokens can split the same input between themselves in n different ways, and when the overall match fails the engine dutifully tries all of them. CPU on every edge server worldwide went to 100%, and the outage lasted until the rule was globally killed. Cloudflare's own post-mortem is admirably blunt: the regex was the root cause, and they subsequently moved WAF rules to a non-backtracking engine.

The pattern behind both incidents is the same and it has a name: catastrophic backtracking, or ReDoS (Regular expression Denial of Service) when someone triggers it on purpose.

Why Backtracking Explodes

Most regex engines you use daily — PCRE in PHP, re in Python, JavaScript's engine, Java's — are backtracking engines. They try one way of matching; when it fails, they rewind to the last choice point and try the next alternative. Usually that's fast. It stops being fast when the pattern is ambiguous: when the same input can be consumed by the pattern in many different ways.

The textbook demonstration is ^(a+)+$ against a string of as followed by !:

Input:  aaaaaaaaaaaaaaaaaaaaaaaaa!
Pattern: ^(a+)+$

The inner a+ can take one a or several; the outer + can repeat the group any number of times. Twenty-five as can therefore be partitioned between the inner and outer quantifiers in an enormous number of ways — and because the ! guarantees the overall match fails, the engine must exhaust every single partition before giving up:

Ten more characters of input, a thousand times the work. That is the signature of ReDoS: the attacker controls the exponent.

Note the two ingredients, because both are required: ambiguity in how the pattern consumes input, and an overall failure (or a long deferral of success). If the match succeeds early, the engine never explores the alternatives. This is why vulnerable patterns sail through test suites — tests feed them valid input, and valid input is exactly the case that doesn't backtrack.

Spotting a Vulnerable Pattern

Three red flags cover nearly every real-world case:

• Nested quantifiers where the inner token can match what the outer repetition also matches: (a+)+, (\d+)*, (\s*)+, ([a-zA-Z]+)*. This is the exponential class.
• Adjacent overlapping tokens: .*.*, \s*\s*, .+\w+ — anything where two neighbouring quantified tokens compete for the same characters. Cloudflare's .*.*=.* is this class; typically polynomial, which is still fatal at scale.
• Overlapping alternation under a quantifier: (a|ab)*, (\w|d)+ — the branches can consume the same text, multiplying the ways to partition input.

The common thread is always the question: given a string that ultimately fails to match, how many different ways can the engine slice it before concluding failure? If the answer grows faster than linearly with input length, you have a problem.

Make It Blow Up on Purpose

The test that should accompany any regex that touches user input is the evil-input test: build a string that maximises ambiguity and ends with a character that forces failure, then time the match.

const evil = 'a'.repeat(30) + '!';
console.time('redos');
/^(a+)+$/.test(evil);   // adjust the pattern and evil input to your case
console.timeEnd('redos');

Start at 20 repetitions and step up. Linear patterns stay flat; vulnerable ones go from microseconds to seconds within a few steps — you don't need to wonder, the curve is unmistakable. You can run the same experiment interactively in the regex tester; it executes JavaScript's real engine, so a pattern that freezes there will freeze your Node.js backend too (start with short evil strings — the freeze is the demonstration). For automated scanning of an existing codebase, regexploit finds most exponential patterns statically.

Fixes That Actually Work

Rewrite for disjointness

The cleanest fix is making sure neighbouring parts of the pattern cannot match the same characters. The standard example is parsing quoted strings:

Vulnerable:  "(.*?)"      backtracks badly inside malformed input
Safe:        "([^"]*)"    the inner token can never consume the closing quote

[^"]* and " are disjoint, so there is exactly one way to consume any input — nothing to backtrack into. Most vulnerable patterns can be rewritten this way, and the rewritten version is usually faster on valid input as well. The building blocks — character classes, anchors, quantifier behaviour — are covered in the regex guide if you need the vocabulary.

Possessive quantifiers and atomic groups

PCRE (PHP), Java and Perl support quantifiers that refuse to give back what they matched: a++ (possessive) and (?>a+) (atomic group). They turn "try every partition" into "commit to the greedy one":

// PHP - possessive: matches or fails in linear time
preg_match('/^(a++)+$/', $input);

JavaScript and Python's built-in re have neither — in those languages your options are rewriting the pattern or changing the engine.

Switch to a linear-time engine

RE2 (used by Go's regexp, available for Node as re2 and Python as google-re2) and Rust's regex crate guarantee linear-time matching by construction — the Cloudflare fix. .NET 7+ offers the same via RegexOptions.NonBacktracking. The trade-off: no backreferences and no lookarounds, because those features are fundamentally incompatible with the guarantee. In my experience the patterns guarding hot paths almost never need either.

Defence in depth

PHP deserves a special mention: preg_match() returning false because the backtrack limit tripped looks identical to "no match" unless you check preg_last_error(). A validation function that treats limit-exceeded as "invalid input, reject" is safe by accident; one that treats it as "no dangerous content found, allow" has turned the safety net into a bypass.

The Checklist

Before a regex ships anywhere user input can reach it: scan for the three red flags (nested quantifiers, adjacent overlap, overlapping alternation); run the evil-input test with 20, 30, 40 repetitions and watch the curve; prefer disjoint rewrites over clever quantifiers; and cap input length regardless, because the cheapest fix for an exponential is denying it a big n. The whole ritual takes five minutes — Stack Overflow's 34-minute outage was caused by a pattern that would have failed step two instantly.