Catastrophic Backtracking and ReDoS: How to Tell If a Regex Will Hang (With Measured Timings)

A regex that works fine in every test can still take down a server the first time it meets an unlucky input. The pattern ^(a+)+$ matches aaaa in microseconds, but hand it 30 as followed by a single ! and it runs for six seconds on one CPU core doing nothing but backtracking. Add two more characters and it runs for 24 seconds. That is a Regular Expression Denial of Service (ReDoS): no bug in the input, no infinite loop in your code, just a pattern whose worst case is exponential.

This guide shows the two structural shapes that cause it, gives you real measured timings so you can see the exponential curve instead of taking it on faith, and shows the one-line rewrite that makes the same intent scale to a 100,000-character input without breaking a sweat. All numbers below were measured on Node.js 22 (V8), single-threaded, and are reproducible.

What backtracking actually does

A backtracking regex engine (the kind in JavaScript, Python re, Java, PCRE, .NET, Ruby) matches greedily, then unwinds when a later part of the pattern fails. Take a+b against aaa. The a+ grabs all three as, then b fails at end-of-string, so the engine gives one a back and tries b again, fails, gives another back, fails, and only then reports no match. Three attempts. Linear. Fine.

The trouble starts when one quantifier is nested inside another, because now there are multiple different ways to split the same characters, and a failing match forces the engine to try all of them before giving up.

Red flag #1: a quantifier inside a quantifier

^(a+)+$ is the textbook "evil regex." The inner a+ can grab 1, 2, 3... as, and the outer + can repeat the group any number of times. For a string of n as there are 2^n-1 distinct ways to partition it into groups: (aaa), (aa)(a), (a)(aa), (a)(a)(a), and so on. As long as the string is all as the whole thing matches on the first try, fast. But append one character that cannot match, like !, and the final $ fails, so the engine is forced to try every one of those 2^n-1 partitions before it can conclude "no match."

That is the exponential. Here is the same pattern, ^(a+)+$, measured against 'a' repeated n times + '!':

Every two characters multiplies the time by roughly 4 (that is 2², exactly what the 2ⁿ partition count predicts). At n=40 this pattern would run for over an hour. The input is 31 bytes. That is the entire attack: a tiny, cheap-to-send string that pins a core.

Red flag #2: overlapping alternation under a quantifier

The nesting does not have to be literal parentheses-inside-parentheses. ^(a|a)+$ has the same disease: the alternation a|a gives the engine two ways to match each single a, and the outer + multiplies those choices across the string. Measured against the same 'a'*n + '!' input:

The real-world version of this is an alternation whose branches can match the same text, e.g. (\w|\d)+ (every digit is also a word character) or (.*|[a-z]*)+. The rule of thumb: if two branches of an alternation can both match the same character, and that alternation sits under a + or *, you have red flag #2. (cat|car|ca.)+ is dangerous; (cat|dog|fish)+ is not, because no input character is claimed by two branches.

The ones that look innocent: nested \d and email validators

You rarely write (a+)+ by hand. What people actually ship are patterns that hide the nesting behind character classes. ^(\d+)*$ to "validate a number" is the same exponential shape as (a+)+. Measured against '1'*n + '!':

The most infamous real case is naive email validation. A pattern of the shape ^([a-z]+)*@, fed a long run of letters with no @, backtracks exponentially trying every way to group the letters before it can decide there is no @: 77 ms at 24 chars, 1,271 ms at 28, 4,791 ms at 30 in the same measurement run. This is exactly the class of pattern behind the 2019 Cloudflare outage and the 2016 Stack Overflow outage: legitimate-looking validators that nobody stress-tested with a hostile string.

The counter-example: not every nested quantifier is exponential

It is worth knowing what is safe, so you do not rewrite patterns that were fine. (.*a){20} looks alarming, but measured against a long input it stays flat at about 9 ms regardless of length, because the .* is anchored by a required a on each repetition, so there is no ambiguity to explode. The danger is specifically ambiguity: the engine must have more than one way to match the same characters, and a downstream failure must force it to explore all of them. A nested quantifier with a fixed, unambiguous internal structure does not backtrack catastrophically. When in doubt, measure it: paste the pattern and a worst-case input into the regex tester and watch whether the time grows with input length.

The fix: de-nest, then measure the same input

In almost every case the catastrophic pattern has a linear equivalent that expresses the exact same intent. The fix for red flag #1 is to remove the redundant outer quantifier: ^(a+)+$ and ^a+$ match precisely the same set of strings, but the second has no nesting and therefore no ambiguity. Measured against the same pathological input that made (a+)+$ take 6 seconds:

Same result set, a hundred-million-fold speedup, and it stays flat even on a 100,000-character input. The concrete moves:

• Collapse nested quantifiers: (a+)+ to a+, (\d+)* to \d*, (x*)* to x*.
• De-overlap alternations: make branches mutually exclusive so no character can match two of them.
• Anchor greedily-repeated wildcards: a .* under a quantifier is a warning sign unless a required literal follows it on each iteration.

Note for JavaScript specifically: other engines let you defuse these with atomic groups (?>...) or possessive quantifiers a++, which tell the engine "never give these characters back." V8 (Node.js 22, and every current browser) does not support either — new RegExp('(?>a+)') throws Invalid group. In JS your only portable options are to de-nest the pattern, cap input length before matching, or run untrusted regex against untrusted input in a worker with a timeout. Do not rely on atomic groups in JavaScript.

A 30-second audit for any pattern you are about to ship

Before a regex touches user input, run it through this checklist:

1. Is there a quantifier (+, *, {n,}) directly wrapping a group that also contains a quantifier? If yes, that is red flag #1 — de-nest it.
2. Is there an alternation under a quantifier where two branches can match the same character? (\w|\d, .*|.+, a|a.) If yes, that is red flag #2 — make the branches exclusive.
3. Does the pattern end in an anchor ($) or a required literal after the risky part? The anchor is what turns a slow match into a catastrophic one, because it forces the full backtrack on non-matching input.
4. Measure it. Feed the pattern a worst-case string (a long run of the character the risky group matches, plus one character that breaks the anchor) and time it. If the time grows faster than linearly as you lengthen the input, it is exploitable. The regex tester runs entirely in your browser, so you can safely try hostile inputs without sending anything to a server.

If you cannot rewrite a third-party pattern, the defensive fallbacks are: cap input length (a 30-character limit makes even (a+)+$ harmless), set an engine-level timeout where your language supports one (.NET and Java offer this; JavaScript does not natively — use a worker), or switch to a non-backtracking engine such as RE2 (used by Go and available as a library in most languages), which guarantees linear time by design and simply cannot backtrack catastrophically.

Frequently asked questions

How can a 30-character string hang a server?

The input is small but the work is exponential in its length. A pattern like ^(a+)+$ has 2^(n-1) different ways to group n identical characters, and a single trailing character that breaks the final anchor forces the engine to try every grouping before it can report no match. At 30 characters that is over 500 million attempts, roughly 6 seconds on one core; at 40 it is over an hour. The attacker sends 31 bytes and pins a CPU.

Does catastrophic backtracking affect all regex engines?

It affects backtracking engines: JavaScript, Python's re, Java, .NET, PCRE, Ruby. It does not affect finite-automaton engines such as RE2 (Go's default, and available as a library elsewhere) or Rust's regex crate, which guarantee linear-time matching and cannot backtrack. If you must run untrusted patterns against untrusted input, a non-backtracking engine removes the entire class of problem.

Can I just add an atomic group or possessive quantifier in JavaScript?

No. Atomic groups (?>...) and possessive quantifiers (a++) defuse backtracking in Java, PCRE, .NET, and Ruby, but V8 — Node.js 22 and every current browser — supports neither and throws 'Invalid group' if you try. In JavaScript your portable fixes are de-nesting the pattern, capping input length before matching, or running the match in a worker with a timeout.

Is every nested quantifier dangerous?

No. The danger is ambiguity, not nesting itself. (.*a){20} stays flat because each repetition is anchored by a required 'a', so there is only one way to match. A nested quantifier is only catastrophic when the engine has more than one way to match the same characters and a later failure forces it to explore all of them. When unsure, measure: if match time grows faster than linearly with input length, it is exploitable.

What is the single fastest fix?

De-nest the quantifier. ^(a+)+$ and ^a+$ match exactly the same strings, but the second has no ambiguity: it drops from 6,060 ms on a 30-character worst case to 0.02 ms, and stays under 0.1 ms even on a 100,000-character input. Collapse (a+)+ to a+, (\d+)* to \d*, and (x*)* to x*.

Related tools

• Regex tester
• Regex explainer
• Regex visualizer
• Common regex library
• Regex escape tool
• Regex quantifier reference
• Regex lookaround tester
• Regex cheatsheet