A regex that pins the CPU
// Validating a 'domain'—looks harmless:
/^(\w+\.)+\w+$/.test('a'.repeat(30) + '!')
The argument is a non-matching bad string: 30 as plus a !. The result is not a simple false — modern engines spend exponential time struggling before giving up; grow it to 60 or 100 and the machine freezes. This innocent-looking regex is the textbook case of catastrophic backtracking.
How NFA engines actually work
Most languages (PCRE, Java, Python, and much of JS syntax) default to an NFA (nondeterministic finite automaton) engine whose matching is a process of backtracking:
- Try a sub-expression at the current position;
- A quantifier takes as much as it can (greedy);
- On eventual failure, step back one slot and try a different consumption.
This is flexible and easy to write—at the cost of the same position being probed an enormous number of times.
Why complexity explodes
Nested quantifiers like (a+)+ are terrifying because the outer + decides 'how many groups' while the inner + decides 'how many per group'. For a bad string of length n the number of groupings is itself exponential (essentially the number of compositions of n). The engine faithfully tries every split:
(a+b)+ on 'aaaab' (no match):
try (a)(a)(a)(b) ✗ → (aa)(a)(b) ✗ → (a)(aa)(b) ✗ → (aaa)(b) ✗ ...
Only the last character fails to match, yet every earlier split must be exhausted first—the cost jumps from O(n) on match to O(2ⁿ) on mismatch.
Three classic high-risk patterns
(a+)+ nested quantifiers: groups × per-group = combinatorial blowup
(.*)* swallow everything then repeat: swallowing modes multiply
(.|a)* alternation inside quantifier: each char chooses a branch
Real-world danger also hides inside these "looks normal" patterns:
^(\w+\.)+\w+$ domain/subdomain validation
^(([a-z])+.)+[A-Z]([a-z])+$ multi-segment password-style input
^(\d+);(\d+;)*\d*$ semicolon-separated number list
Their common trait: repeatable sub-expressions that are adjacent and overlap. On valid well-formed input they pass instantly; on barely-mismatching input with a long matching prefix, they descend into exponential hell.
Three ways to fix it for good
1. Atomic groups / possessive quantifiers — consume and never give back
(?>a+)b atomic group
a++b possessive quantifier
This forbids the engine from backtracking that part—removing that sub-expression's backtracking at the root, the cleanest fix. JS's engine lacks these? Then use option two or three.
2. Front-loaded whole-string lookahead — validate shape first
(?=[a-z0-9.]+$)^(\w+\.)+\w+$ run the format lookahead over the whole string first
The most backtracking-hungry judgment—"is the format valid"—is done in a single lookahead before entering the quantifier match; bad input is rejected in step one and never reaches the explosion.
3. Timeout + length limit as a safety net — never hang, right or wrong
// Node: wrap a timeout so bad input can't kill the process
const r = new RegExp(pattern, 'd'); // with indices
await Promise.race([doMatch(r, s), sleep(50)]);
Universal discipline: cap untrusted input first (s.slice(0, 1000)) then match, and public validation endpoints must cap the text they accept. Even a perfect regex should not bet the process's fate on user input.
Highlight backtracking with a debugging tool
Theory fades; seeing it sticks. Feed your regex and a failing string into a tool that highlights backtracking (many regex tester sites step through where the match retreats and retries). Two things to watch: does it revisit the same position over and over? Is the red highlighting concentrated in a small tail region? Both are the literal portrait of a backtracking bomb—seeing it teaches more than ten rules.
Self-check
Build a safe version of this long bad input (JS without atomic groups/possessive quantifiers is fine):
input: 'a'.repeat(40) + '!'
pattern: ^(\w+\.)+\w+$
Rewrite it with 'length guard then whole-string lookahead', and compare before/after timing in a regex tester. If you can show a difference of several orders of magnitude, you've got the skill to dodge backtracking.