Detecting Catastrophic Backtracking in Regex Engines

A single unauthenticated request containing forty-two repeated whitespace characters took down a Node.js API gateway for eleven minutes last year — not through volumetric flood, but through a validation regex that nobody had load-tested against pathological input. This is catastrophic backtracking: a worst-case exponential blowup in backtracking regex engines that turns a microsecond-scale string match into a CPU-pinned hang. If your platform accepts user-supplied strings anywhere near a regular expression — header parsing, log ingestion, form validation, WAF rulesets — you have a latent denial-of-service vector sitting in plain sight. This article builds a diagnostic tool that finds it before production does.

#The Bottleneck: Exponential-Time Regex Evaluation

Most language runtimes (PCRE, Python’s re, JavaScript’s RegExp, .NET’s Regex) implement backtracking virtual machines rather than true finite automata. These engines support backreferences and lookaround by walking the pattern depth-first, and on failure, unwinding to try alternative paths. This gives enormous expressive power at the cost of a worst-case time complexity that is not linear in input length — it can be O(2^n) for pathological patterns.

The canonical trigger is a quantified group whose inner expression can match the same substring in multiple overlapping ways, nested inside an outer quantifier. Consider:

1const vulnerable = /^(a+)+$/;
2const input = "a".repeat(30) + "!";
3
4const start = process.hrtime.bigint();
5vulnerable.test(input);
6console.log(Number(process.hrtime.bigint() - start) / 1e6, "ms");

With thirty repetitions this executes in a handful of milliseconds. At thirty-five it takes seconds. At forty it will exceed most HTTP request timeouts entirely, because the engine is exploring an exponentially growing tree of ways to partition the “a” run between the inner and outer + quantifiers before finally failing against the trailing !. This is the exact mechanism behind several documented incidents referenced in the OWASP ReDoS advisory, and it is not an exotic edge case — it is a direct consequence of how backtracking VMs are architected.

#Architectural Breakdown: Why Backtracking Engines Fail

#Thompson NFA Simulation vs Backtracking VM

Engines such as RE2 and the Rust regex crate sidestep the problem entirely by compiling patterns to a Thompson-construction NFA and simulating all active states simultaneously using a bitset, guaranteeing O(n) matching regardless of pattern shape. The trade-off is that backreferences and certain lookaround constructs become unrepresentable, because they require remembering which specific path led to a state rather than just which states are reachable. Backtracking engines choose the opposite trade-off: full expressive power, no complexity guarantee.

This is the architectural fork every platform team eventually has to reckon with when choosing a validation layer, and it belongs in the same category of decision as the request-routing and state-management choices discussed under architectural patterns more broadly — you are trading expressiveness for a worst-case bound, and that trade-off needs to be explicit rather than accidental.

#Ambiguity: EDA and IDA

The formal way to characterise catastrophic backtracking is through the degree of ambiguity of the pattern’s underlying automaton, a concept from the static ReDoS analysis literature (Weideman et al.). A pattern exhibits:

• Exponential Degree of Ambiguity (EDA) — two or more distinct, overlapping loops exist that can each consume the same substring, causing worst-case exponential time. This is the (a+)+ class of vulnerability.
• Infinite/Polynomial Degree of Ambiguity (IDA) — a single ambiguous loop exists, producing polynomial (often quadratic or cubic) blowup rather than exponential — still dangerous under sustained load but not an instant kill.
• Constant/None — no overlapping repetition paths; matching is bounded regardless of input shape.

Detecting catastrophic backtracking, therefore, is not a matter of pattern-matching against a blocklist of “bad-looking” regexes. It requires building the automaton and proving whether an ambiguous, self-intersecting loop exists in it.

#Implementation Logic: Building the Detector

A production-grade catastrophic backtracking detector combines static automaton analysis with dynamic attack-string fuzzing, because static analysis alone produces false positives on patterns that are technically ambiguous but practically bounded by anchors or length limits elsewhere in the application.

#Step 1 — Parse to AST

Use a proper regex parser (for example regexp-tree or a hand-rolled recursive-descent parser) rather than string heuristics, so nested groups, alternations, and quantifiers are represented as a real tree.

#Step 2 — Thompson Construction

Compile the AST into an epsilon-NFA. Tag every transition with the AST node it originated from, which is essential later for pointing the developer at the exact offending sub-pattern.

#Step 3 — Self-Product Ambiguity Check

Construct the cross-product automaton of the NFA with itself. Search for a pair of distinct paths that start from the same state, consume an identical non-empty substring, and return to overlapping states within a quantified loop. A cycle satisfying this condition is proof of an EDA loop — the structural signature of catastrophic backtracking.

#Step 4 — Attack String Synthesis

Once a vulnerable loop is located, generate a pump string automatically: a prefix that reaches the loop, a repeated “pump” segment that exploits the ambiguity, and a suffix engineered to force final failure (the failure is what forces the engine to exhaust every backtracking path rather than short-circuiting on first match).

#Step 5 — Timeout-Bounded Dynamic Verification

Execute the synthesised string against the real engine under a hard timeout, doubling the pump length on each pass, and plot execution time. A curve that doubles roughly every increment confirms exponential behaviour and rules out static false positives.

#Code and Configuration

A simplified structural detector, ignoring full automaton construction for brevity, flags the two most common catastrophic backtracking shapes — nested quantifiers over overlapping character classes, and quantified alternations with overlapping branches:

1const { parse } = require("regexp-tree");
2
3function findCatastrophicPatterns(ast, path = []) {
4  const findings = [];
5
6  function walk(node, parentQuantified) {
7    if (!node) return;
8
9    if (node.type === "Repetition" && parentQuantified) {
10      const inner = node.expression;
11      if (inner.type === "Group" || inner.type === "Repetition") {
12        findings.push({
13          type: "nested-quantifier",
14          offset: node.loc ? node.loc.start.offset : null
15        });
16      }
17    }
18
19    const nowQuantified = node.type === "Repetition" || parentQuantified;
20
21    if (node.expression) walk(node.expression, nowQuantified);
22    if (node.body) node.body.forEach(n => walk(n, nowQuantified));
23    if (node.alternatives) {
24      node.alternatives.forEach(alt => walk(alt, nowQuantified));
25    }
26  }
27
28  walk(ast.body, false);
29  return findings;
30}
31
32const { body } = parse("/^(a+)+$/");
33console.log(findCatastrophicPatterns({ body }));

This structural pass is deliberately conservative — it over-reports so that no true positive is missed, and every finding is then confirmed dynamically. The verification harness pumps the input and measures wall-clock growth:

1import re, signal, time
2
3class TimeoutError(Exception):
4    pass
5
6def _handler(signum, frame):
7    raise TimeoutError()
8
9def probe(pattern, pump_char, prefix, suffix, max_pump=40, budget_s=1.5):
10    compiled = re.compile(pattern)
11    signal.signal(signal.SIGALRM, _handler)
12
13    for n in range(5, max_pump, 5):
14        attack = prefix + (pump_char * n) + suffix
15        signal.setitimer(signal.ITIMER_REAL, budget_s)
16        start = time.monotonic()
17        try:
18            compiled.match(attack)
19            elapsed = time.monotonic() - start
20            print(f"n={n:>3}  elapsed={elapsed:.4f}s")
21        except TimeoutError:
22            print(f"n={n:>3}  TIMEOUT (>{budget_s}s) -- confirmed exponential")
23            return True
24        finally:
25            signal.setitimer(signal.ITIMER_REAL, 0)
26    return False
27
28probe(r"^(a+)+$", "a", "", "!")

Wire the two stages into a CI gate so no ambiguous pattern reaches production without an explicit override:

1jobs:
2  regex-safety-scan:
3    runs-on: ubuntu-latest
4    steps:
5      - uses: actions/checkout@v4
6      - name: Install detector
7        run: npm ci --prefix tools/redos-scanner
8      - name: Static ambiguity scan
9        run: node tools/redos-scanner/scan.js --path src/ --fail-on eda
10      - name: Dynamic pump verification
11        run: python3 tools/redos-scanner/probe.py --budget 1.5 --report findings.json
12      - name: Upload report
13        uses: actions/upload-artifact@v4
14        with:
15          name: redos-report
16          path: findings.json

#Failure Modes and Edge Cases

A detector built purely on structural heuristics will misfire in both directions. Character classes that appear to overlap syntactically ([a-z]+[a-zA-Z]+) may not actually be ambiguous once Unicode case folding and anchoring are accounted for, producing false positives that erode developer trust in the tool. Conversely, ambiguity can be hidden behind indirection: a pattern assembled at runtime from configuration strings, or composed via RegExp constructor concatenation, will not appear as a literal in source and will slip past a purely static AST scan.

Named capture groups and atomic-group emulation via lookahead ((?=(...))1) also confuse naive parsers, since the AST shape no longer maps cleanly onto a simple quantifier-over-quantifier pattern, yet the underlying ambiguity is identical. Grapheme-cluster-aware patterns using p{...} Unicode property escapes introduce another wrinkle: the effective alphabet size explodes, which changes the pump-string synthesis strategy because a single-character pump may not trigger the ambiguous branch at all.

The dynamic verification stage has its own failure mode: engines with internal memoisation (some PCRE builds, .NET’s regex cache under certain compilation flags) can suppress catastrophic backtracking for specific pump characters while remaining vulnerable to a differently shaped attack string. A detector that only tries one pump character and declares the pattern safe on a negative result is providing false assurance — the probe harness should iterate across a small alphabet, not a single repeated character.

#Scaling and Security Trade-offs

• Static-only scanning is fast enough for pre-commit hooks (sub-second per file) but produces a non-trivial false-positive rate on legitimately safe but structurally ambiguous patterns, requiring an allowlist mechanism to avoid alert fatigue.
• Dynamic pump verification is authoritative but expensive — each confirmed catastrophic backtracking case can consume the full timeout budget by design, so CI jobs must run probes in parallel worker processes with hard SIGKILL fallback, not just SIGALRM, since some backtracking states are unresponsive to signal delivery until the current C-level loop yields.
• Runtime mitigation via engine substitution (moving hot-path validation to RE2 or the Rust regex crate via FFI) eliminates the class of vulnerability entirely at the cost of losing backreference support — acceptable for input validation, unacceptable for text-processing pipelines that depend on backreferences for correctness.
• Runtime mitigation via request-level timeouts (wrapping match calls in a worker thread with a kill switch) bounds the blast radius per request but does not fix the underlying pattern, and under sustained attack still allows thread-pool exhaustion if the timeout is set conservatively high.
• Defence-in-depth combines both: CI-time static and dynamic detection to stop new catastrophic backtracking patterns from merging, plus a per-request evaluation timeout as the last line of defence against patterns that predate the tooling or arrive via third-party dependencies.

None of these controls are mutually exclusive, and in practice the CI gate catches the majority of cases before they ship, while the runtime timeout absorbs whatever the static analysis inevitably misses. Treat the detector as a continuously tuned pipeline rather than a one-off audit — new catastrophic backtracking shapes surface every time a developer reaches for a “clever” nested quantifier under deadline pressure.