Regex Backtracking and ReDoS: Why Your Pattern Hangs and How to Fix It

Two Kinds of Regex Engine

Not all regex implementations share the same performance model, and the difference decides whether a pattern can be attacked.

The trade is explicit: backtracking engines buy backreferences and lookaround at the cost of a worst-case time bound. JavaScript uses a backtracking engine, so every pattern you run against untrusted input carries a performance contract you need to understand.

How Backtracking Actually Fails

Take the pattern ^(a+)+$ and the input aaaa!.

1. The inner a+ is greedy, so it consumes all four a characters.
2. The outer + tries to repeat; there is nothing left, so it stops.
3. $ is checked. The next character is !, not end-of-string. Fail.
4. The engine backtracks: what if the inner a+ had taken three characters and the outer group repeated to take the fourth?
5. Fail again. What about 2 + 2? 2 + 1 + 1? 1 + 3? 1 + 1 + 2? 1 + 1 + 1 + 1?

Each of those is a distinct partition of the input, and every one must be tried before the engine can report no match. The number of ways to partition n items into ordered groups grows as 2^(n-1).

Add five characters, take thirty-two times longer. That is the entire mechanism behind ReDoS.

The critical precondition: the overall match must fail. A pattern that matches successfully finds its answer on the first greedy pass. This is why a vulnerable pattern looks perfectly fast in tests using valid inputs, and only detonates on malformed data — which is exactly what an attacker supplies.

The Three Vulnerable Shapes

Almost every real ReDoS reduces to one of three structures.

1. Nested Quantifiers

/^(a+)+$/          // quantifier inside a quantified group
/^(\d+)*$/
/^([a-z]+)+$/

The outer repetition and the inner repetition compete for the same characters. Ambiguity is the fuel.

2. Overlapping Alternation Under a Quantifier

/^(a|aa)+$/        // both branches match the letter a
/^(\w|\d)+$/       // \w already includes \d
/^(\s|\t|\n)*$/    // \s already includes \t and \n

If two branches can match the same text, the engine has two routes to every position, doubling the search space at each step.

3. Greedy Dot-Star Next to a Similar Pattern

/^(.*),(.*)$/           // both sides compete for every comma
/<div>(.*)<\/div>/      // .* happily crosses tag boundaries
/^(.*?)(.*?)(.*?)$/     // three lazy groups over one string

. matches almost everything, including the delimiter you are trying to find, so the engine must try every split point.

The Real-World Case

On 2 July 2019, Cloudflare’s global network returned HTTP 502 errors for roughly 30 minutes. The published post-mortem attributes the outage to a newly deployed WAF rule containing .*(?:.*=.*) — a nested greedy quantifier that consumed CPU across every machine in the fleet. One regular expression, global outage. The pattern shape above is not academic.

The Rewrites That Fix It

Replace nested quantifiers with a single one

/^(a+)+$/     // vulnerable
/^a+$/        // equivalent, linear

Ask what the outer quantifier adds. In the majority of vulnerable patterns, the answer is nothing.

Make alternation branches mutually exclusive

/^(a|aa)+$/   // vulnerable — branches overlap
/^a+$/        // same language, no ambiguity

/^(\w|\d)+$/  // vulnerable — \w contains \d
/^\w+$/       // same language

Swap greedy dots for negated character classes

/"(.*)"/      // dot crosses the closing quote and backtracks
/"([^"]*)"/   // cannot cross the delimiter at all — no ambiguity

This single substitution — [^delimiter]* instead of .* — is the highest-value change in practice. It also usually fixes the correctness bug where a greedy pattern swallowed two fields.

Emulate atomic groups with a lookahead

JavaScript has no atomic groups (?>...) and no possessive quantifiers a++. You can simulate them with a lookahead plus a backreference, which discards the inner group’s backtracking positions:

// Atomic equivalent of (?>\d+)
const atomic = /(?=(\d+))\1/;

The lookahead matches greedily, the backreference consumes exactly that text, and the engine cannot revisit the choice.

Bound the input before matching

const MAX = 512;

function safeTest(pattern, input) {
  if (typeof input !== 'string' || input.length > MAX) return false;
  return pattern.test(input);
}

Even an exponential pattern is harmless on 512 bytes. A length cap is a blunt instrument, but it is the one mitigation that works without understanding the pattern — apply it at every trust boundary.

Flags Worth Knowing

The tester exposes the five flags that matter most day to day:

ECMAScript also defines y (sticky), d (hasIndices, ES2022), and v (set notation, ES2024).

The lastIndex Trap

A regex literal with g carries mutable state. Reusing one across calls produces alternating results:

const re = /\d+/g;

re.test('123');  // true  — lastIndex is now 3
re.test('123');  // false — resumes from index 3, finds nothing
re.test('123');  // true  — lastIndex reset to 0 after the failure

Use a non-global regex for test, create the regex inside the function, or reset re.lastIndex = 0 before each use. The same hazard applies to exec in a loop — which is the intended use of g, but only when the loop consumes matches until null.

Detection and Tooling

Static analysis catches most real cases before deployment:

• eslint-plugin-regexp with the no-super-linear-backtracking rule flags exponential and polynomial patterns in CI.
• recheck performs both static and fuzzing-based analysis and reports an attack string.
• Dependency advisories matter too: ReDoS reports against popular parsing and validation libraries are common, so keep npm audit in your pipeline.

Runtime containment for patterns you cannot rewrite — user-supplied search expressions, for instance:

• Run matching in a worker thread you can terminate on a timeout. JavaScript regex evaluation is synchronous and uninterruptible on the main thread, so this is the only way to enforce a deadline.
• Use a linear-time engine via bindings such as node-re2, accepting the loss of backreferences and lookaround.
• Never compile a pattern supplied by a user without both of the above.

Step-by-Step: Diagnosing a Pattern with Toolbox

1. Open the tool: visit the Toolbox RegEx Tester & Group Matcher.
2. Start from a preset or paste your own pattern into the pattern field.
3. Toggle the flags — g, i, m, s, u — and watch the match set change, which is the fastest way to confirm a flag is the actual cause of a bug.
4. Read the token explanation. The explainer breaks the pattern into tokens, which makes nested quantifiers and overlapping alternations visible rather than buried in punctuation.
5. Inspect capture groups against your sample text to verify indices and named groups resolve as expected.
6. Test the failure case, not the success case. Paste input that nearly matches — the right prefix with one wrong character at the end. Slow, vulnerable patterns only reveal themselves when the match fails.

Everything is evaluated by your browser’s own RegExp implementation, so test data never leaves the device — which matters when the sample text is a production log line or a customer record.

For the adjacent problem of validating structured text rather than free-form strings, JSON schema validation is usually the better tool than a regular expression.