Your Regex Can Hang Your Server: Catastrophic Backtracking Explained

Here is a regular expression that looks completely ordinary: ^(a+)+$. Here is a 31-character string: thirty a characters and one !. On Node 22 the match takes 31 seconds — one core pinned, event loop dead, every other request queued behind it. Add ten more characters and you are into the hours. The pattern is not malicious and the input is not huge; the blowup comes from the engine’s search strategy, and almost every regex engine you use in production has it.

That failure has a name — catastrophic backtracking — and a security name when the input comes from a user: ReDoS, regular expression denial of service. It has taken down large chunks of the internet more than once. It is also completely predictable once you know the three pattern shapes that cause it.

What backtracking actually is

A backtracking engine matches by trial and error. It walks the pattern, and every time it hits a construct with more than one possible answer — a quantifier that can consume more or fewer characters, an alternation with several branches — it picks one, remembers the alternatives, and walks on. If the rest of the pattern fails, it backtracks: returns to the last remembered choice point, takes the next alternative, and tries again.

Microsoft’s .NET documentation puts the cost plainly: for a pattern with no optional quantifiers or alternation, “the maximum number of comparisons required to match the regular expression pattern with the input string is roughly equivalent to the number of characters in the input string.” Add one optional quantifier and “the number of comparison operations required to match the pattern is more than twice the number of characters in the input string.” Still linear. The cliff is elsewhere.

The cliff is nested quantifiers. In ^(a+)+$, the inner a+ can split a run of as many ways, and the outer + can group those splits many ways. For a string of n as there are 2^(n-1) ways to partition it into groups, and if the string ends in something that can never match — a ! — the engine must try every one of them before it can report failure. .NET’s docs describe this exact pattern as “an O(2^n) or an exponential operation,” noting that a 30-character input “requires approximately 1,073,741,824 comparisons.”

Measured on Node 22.18.0, one fresh process per run:

Input	Pattern	Time
24 as + !	^(a+)+$	496 ms
26 as + !	^(a+)+$	1,942 ms
28 as + !	^(a+)+$	7,874 ms
30 as + !	^(a+)+$	31,520 ms
100,000 as + !	^a+$	0.12 ms

Every two characters multiplies the time by four. Extrapolate to 40 characters and one match attempt runs for roughly nine hours. The last row is the punchline: the same input class against a pattern without the nested quantifier is instant at a hundred thousand characters. The input size is rarely the problem. The pattern is.

Note also which case is slow. The successful match on a string of all as returns immediately; it is the failing match that explodes, because failure is the only outcome that requires exhausting the search space. This is why ReDoS payloads always end with one character that cannot match — and why a pattern can pass every test in your suite and still be a live grenade.

The three shapes to look for

Almost every catastrophic pattern in the wild is one of these:

Shape	Example	Why it explodes
Nested quantifiers	(a+)+, (\w*)*, ([a-z]+)*	Inner and outer quantifiers can divide the same characters exponentially many ways
Overlapping alternation under a quantifier	(a|a)*, (\d|\w)+	Both branches match the same character, so each character doubles the branch count
Adjacent unbounded quantifiers with a required suffix	.*.*=.*, \s+\s+$	Two greedy runs must agree on where to split a single stretch of text

That third row is the one that took Cloudflare down. On July 2, 2019 at 13:42 UTC, a WAF rule containing this pattern deployed globally:

(?:(?:\"|'|\]|\}|\\|\d|(?:nan|infinity|true|false|null|undefined|symbol|math)|`|\-|\+)+[)]*;?((?:\s|-|~|!|{}|\|\||\+)*.*(?:.*=.*)))

CPU across the network went to 100% and Cloudflare stopped serving traffic for 27 minutes, recovering at 14:09 UTC. Their post-mortem reduces the whole thing to the fragment .*.*=.* and counts the steps: matching the three-character string x=x takes 23 steps; x= followed by twenty xs takes 555; the variant .*.*=.*; — which fails on that input — takes 5,353. Cloudflare’s fix was not a cleverer pattern. It was to abandon backtracking: they committed to moving the WAF to “re2 or the Rust regex engine,” both of which guarantee linear time.

You do not need exponential to take down a site

The other famous outage is more instructive, because the pattern involved is one you have probably written.

Stack Overflow went down for 34 minutes on July 20, 2016, starting at 14:44 UTC. The cause was a trim regex — ^[\s‌]+|[\s‌]+$ — applied to a post containing roughly 20,000 consecutive whitespace characters on one line. That pattern has no nesting and no overlapping alternation. It is merely quadratic: for each of the n starting positions the engine walks the whitespace run looking for the anchor, so the work is 20,000 + 19,999 + … + 1 ≈ 200 million character-class checks.

Quadratic reproduces cleanly in V8 too. Trimming a string of x + n spaces + x with that same pattern, Node 22:

Spaces	Time
10,000	60 ms
20,000	230 ms
40,000	894 ms
80,000	3,514 ms

Double the input, quadruple the time. No exponential anywhere — and yet 80 KB of spaces, which fits in any comment box, holds a Node process for three and a half seconds. The bar for a denial of service is “slower than your timeout,” not “exponential.” If you are auditing patterns, don’t only hunt for nested quantifiers; hunt for any unbounded quantifier that can be forced to rescan the same characters from many starting positions.

One caution about testing this yourself: the same pattern that hangs one engine can be instant in another, and even how you call it matters. That trim regex returns immediately from .test() on a long whitespace run — the ^[\s]+ alternative matches at position 0 and the engine stops. It is .replace(…, 'g'), which must find every match, that produces the table above. If a proof of concept doesn’t reproduce, check that you are exercising the same code path as production before concluding you are safe.

Which engines are actually vulnerable

This is not a universal property of regular expressions — it is a property of backtracking implementations, and the choice differs by language:

Engine	Backtracks?	Built-in defense
JavaScript (V8, JSC, SpiderMonkey)	Yes	None by default; V8 ships an opt-in linear engine (below)
Python re	Yes	None (the third-party regex module offers timeouts)
Java java.util.regex	Yes	None; possessive quantifiers a++ and atomic groups (?>…) available
PHP PCRE	Yes	pcre.backtrack_limit (default 1,000,000) — fails the match rather than hanging
.NET	Yes	matchTimeout (opt-in), RegexOptions.NonBacktracking, atomic groups
Go regexp	No (RE2)	Linear time by construction
Rust regex	No	Linear time by construction

The two “no” rows are why Cloudflare chose them. RE2-style engines pay for their guarantee by refusing to implement backreferences and lookaround, which cannot be done in linear time. That is the actual trade: backreferences and lookaround, or a worst-case bound. Pick one.

V8 has a middle path worth knowing about. Running Node with --enable-experimental-regexp-engine turns on a non-standard l (“linear”) flag, and patterns built with it execute on a non-backtracking engine. Verified on Node 22.18.0:

// node --enable-experimental-regexp-engine
new RegExp('(a*)*b', 'l').test('a'.repeat(100));   // returns in 0.035 ms

new RegExp('(?=(a+))\\1', 'l');
// SyntaxError: Invalid regular expression: /(?=(a+))\1/l:
//   Cannot be executed in linear time

The failure mode is the good kind — a SyntaxError at construction rather than a silent hang at runtime. V8 also ships --enable-experimental-regexp-engine-on-excessive-backtracks, which falls back to the linear engine after --regexp-backtracks-before-fallback (default 50,000) backtracks, for patterns the linear engine can handle at all. Both remain experimental, and neither is available to code running in a browser.

Fixing a pattern you can’t replace

When the pattern has to stay, four techniques, roughly in order of preference:

1. Remove the ambiguity. Most nested quantifiers are accidental. ^(a+)+$ means exactly what ^a+$ means, and ^(\w+\s?)*$ is usually trying to say ^[\w\s]*$. If two parts of your pattern can both claim the same character, the engine has to try both assignments; make the claim unique and there is nothing to backtrack into.

2. Anchor and bound. ^…$ stops the engine retrying at every start offset. Replacing + and * with explicit bounds like {1,64} caps the search space at a size you chose. .NET’s docs make the same point as a first-class mitigation: “If all reasonable text inputs in your scenario are known to be under a certain length, consider rejecting longer inputs before applying the regular expression to them.” A length check before the match is the cheapest fix in this entire post.

3. Use atomic groups — or emulate them. An atomic group (?>…) refuses to give back any of what it matched. .NET’s own benchmark shows the effect on an IPv6-ish pattern: 27.4 seconds with backtracking, 0.0001 seconds with (?>…). JavaScript has no atomic group syntax, but the lookahead-plus-backreference idiom (?=(a+))\1 is exactly equivalent, and behaves accordingly on Node 22 against 30 as + !:

^(a+)+$          31,520 ms
^(?=(a+))\1$          0.017 ms

Same semantics, six orders of magnitude apart.

4. Bound the execution, not the pattern. In .NET, pass a TimeSpan — and note the default, which surprises people: “By default, the time-out interval is set to Regex.InfiniteMatchTimeout and the regular expression engine does not time out.” In Node there is no timeout parameter at all; the options are running untrusted patterns inside a worker thread you can terminate, or using an RE2 binding.

What our regex tester does — and honestly does not

Our regex tester compiles your pattern with new RegExp(pattern, flags) and runs it against your test string in the page, on the main thread, with no timeout and no match cap. That is a deliberate simplicity trade for a tool whose job is showing exactly what your engine does — but it means the tool inherits the behavior described in this post: paste a catastrophic pattern with a long enough subject and the tab freezes until the match completes, exactly as your server would.

Two practical habits when using it:

• Test the failing case first, and start short. Try your pattern against a string that almost matches — the shape ending in one wrong character — at 15 to 20 characters before pasting in 10 KB of production data. If 20 characters is visibly slow, 30 will be unusable and 40 will never finish.
• If the tab does hang, close it. There is no cancel button on a synchronous RegExp.exec, and nothing is lost — the tool keeps no server-side state.

For patterns you intend to run against untrusted input, pair this tool for correctness with a deliberate look for the three shapes above for safety. And when your pattern is a validator, ask whether it should be a regex at all: valid email syntax doesn’t mean deliverable covers a case where the famous email regex is both risky and beside the point, and why regex PII redaction leaks covers what regex fundamentally cannot decide.

The five-minute audit

Run this over your codebase before you need it:

1. Grep for the shapes, not for slow code: (\w+)+, (.*)*, (\d+)*, ([^x]+)+, and any two adjacent .* in one pattern. A nested quantifier plus a required trailing literal is the highest-signal combination.
2. For each hit, ask where the subject comes from. A pattern applied to your own config file is a bug at worst. The same pattern applied to a request header, a form field, a filename, or a User-Agent is a vulnerability.
3. Build the failing input. Take the character the inner quantifier accepts, repeat it 25 times, append one character it rejects, and time the match. If the time roughly quadruples for every two characters you add, you have found a live one.
4. Fix in this order: length limit → de-ambiguate the pattern → atomic group or emulation → engine-level timeout.
5. Add the pathological string to your test suite with an assertion on elapsed time, so the pattern cannot regress.

Worth remembering when you inherit a dependency audit report, too: the ReDoS advisories that fill up npm audit output are exactly this bug class, and whether they matter depends entirely on step 2 — see npm audit says 47 vulnerabilities for how to triage that.

The short version

The assumption	The mechanism
”It’s fast — I tested it”	You tested a match. Failure is the expensive case; test a string that almost matches
”The input would have to be huge”	31 characters is enough for 31 seconds; 80 KB of spaces is enough for a quadratic hang
”Only exotic patterns are affected”	Nested quantifiers, overlapping alternation, and adjacent .* cover nearly all real cases — Cloudflare’s was .*.*=.*
”Regex engines have a safety limit”	JS and Python have none; .NET defaults to InfiniteMatchTimeout; only PCRE ships a default backtrack limit
”All regex engines behave the same”	Go and Rust are linear by construction; V8 offers an opt-in l flag — the trade is losing backreferences and lookaround
”I’ll add a timeout”	There is no regex timeout in JavaScript. A length cap before the match is the fix you actually have