Regex · Nested or overlapping quantifiers
Catastrophic backtracking
Nested quantifiers can make a regex take exponential time, a failure mode known as ReDoS.
Key facts
| Cause | Nested or overlapping quantifiers |
|---|---|
| Classic example | <code>^(a+)+$</code> against “aaaa…!” |
| Complexity | Exponential in input length for backtracking engines |
| Mitigation 1 | Anchor and bound the input |
| Mitigation 2 | Rewrite with precise classes |
| Mitigation 3 | Atomic groups or possessive quantifiers where available |
| Linear engines | RE2, Go regexp — no backtracking |
| JavaScript | Backtracking engine, no atomic groups |
How a simple pattern explodes
Consider ^(a+)+$ tested against a long run of “a” followed by a character that prevents a match. The outer and inner quantifiers describe the same partition, so the engine tries every way of splitting the run before concluding failure. Each extra character roughly doubles the work.
The same shape appears in real validation patterns: optional groups nested inside repetitions, or alternations that overlap such as (a|aa)+. It is not about pattern length; a twelve-character regex can stall a server.
Containing the risk
First, cap the input length before matching. Second, rewrite the pattern so every character has one unambiguous path: a+ instead of (a+)+, or a negated class instead of a lazy dot followed by a broad alternative. Third, prefer anchors and explicit boundaries.
Where the engine allows it, possessive quantifiers and atomic groups remove the backtracking entirely. Where it does not, run untrusted patterns in a worker with a timeout, or use a linear-time engine for the safe subset of syntax. Never expose a user-supplied pattern to a shared server thread without a time limit.
Frequently asked questions
What is ReDoS?
Regular expression denial of service: a crafted input makes a backtracking regex consume exponential CPU time, stalling the process that evaluates it.
Is (a+)+ always dangerous?
It is dangerous when a failure forces the engine to try many partitions of a long run. Anchoring and input limits reduce but do not remove the risk.
Which engines avoid catastrophic backtracking?
Linear-time engines such as RE2 and Go's regexp, at the cost of features like backreferences and lookaround.