A Regex That Pins the CPU
// Validating a 'domain'—looks harmless:
/^(\w+\.)+\w+$/.test('a'.repeat(30) + '!')
The input is 30 as plus a !, and it does not match. The call does not return false immediately; the engine spends exponential time exhausting every split before giving up. At length 60 or 100 the machine freezes. That is catastrophic backtracking.
How an NFA Engine Works
PCRE, Java, Python, and most JS implementations use an NFA (nondeterministic finite automaton) engine driven by backtracking:
- Try a sub-expression at the current position;
- Let the quantifier take as much as it can (greedy);
- On final failure, step back one slot and try a different consumption.
Flexible and easy to write, at the cost of probing the same position over and over. A successful match returns quickly; an eventual failure forces every earlier probe to be replayed.
Why Nested Quantifiers Explode
The danger in (a+)+: the outer + decides how many groups, the inner one decides how many per group. The number of groupings is the number of compositions of n, which is exponential. The engine dutifully tries each:
(a+b)+ on 'aaaab' (no match):
try (a)(a)(a)(b) ✗ → (aa)(a)(b) ✗ → (a)(aa)(b) ✗ → (aaa)(b) ✗ ...
Only the last character fails, yet every earlier split must be exhausted first — O(n) on success, O(2ⁿ) on failure. Triggering therefore needs both conditions at once: a pattern with exponential structure, and a non-matching input that is long enough. Short or matching input feels instant, which is why the explosion only shows up on large production text.
Three High-Risk Shapes
(a+)+ nested quantifiers: groups × per-group = combinatorial blowup
(.*)* swallow everything then repeat: swallowing modes multiply
(.|a)* alternation inside a quantifier: each char picks a branch
Real code more often hides them inside "normal-looking" patterns:
^(\w+\.)+\w+$ domain/subdomain validation
^(([a-z])+.)+[A-Z]([a-z])+$ multi-segment password-style input
^(\d+);(\d+;)*\d*$ semicolon-separated number list
The common trait: repeatable sub-expressions that are adjacent and overlap. Valid input passes instantly; barely-mismatching input with a long prefix falls into exponential hell.
Three Fixes That Work
1. Atomic groups / possessive quantifiers — consume and never give back
(?>a+)b atomic group: eat a+, never retreat
a++b possessive quantifier: same idea
This forbids backtracking that part and removes the sub-expression's exponential behavior at the root — the cleanest fix. If the JS engine lacks both, use the next two.
2. Front-loaded whole-string lookahead — validate shape first
(?=[a-z0-9.]+$)^(\w+\.)+\w+$ run the format lookahead over the whole string first
The backtracking-hungry judgment "is this format valid" happens in one lookahead before the quantifier ever runs; bad input is rejected in step one and never reaches the explosion.
3. Timeout + length cap — never hang, right or wrong
// Node: wrap a timeout so bad input cannot kill the process
const r = new RegExp(pattern, 'd'); // with indices
await Promise.race([doMatch(r, s), sleep(50)]);
Universal discipline: cap untrusted input with s.slice(0, 1000) before matching, and cap what public endpoints accept. However correct the pattern, never bet the process on user input.
How to Verify
Measure the same pattern on the same bad string while adding two characters at a time; the exponential curve is unmistakable:
import re, time
pat = re.compile(r'^(a+)+$')
for n in (22, 24, 26, 28):
s = 'a' * n + '!'
t0 = time.perf_counter(); pat.match(s)
print(f"n={n}: {time.perf_counter() - t0:.4f}s")
# n=22: 0.12s → n=24: 0.47s → n=26: 1.93s → n=28: 17.8s
The control group: the semantically equivalent linear ^a*!$ needs 0.0001 s at n=28. Same requirement, 100,000x apart, because the nested quantifier makes the engine enumerate every split.
To see where it retreats, feed the pattern and a failing string into a tester with backtracking highlight. Red highlighting that revisits the same position and clusters near the tail is the signature. Our regex tester also lets you compare timing before and after a rewrite.