TopolearnOne bad pattern on a server can be frozen by a 30-character string; this has taken down major sites.
Catastrophic backtracking happens when a pattern can match the same text in exponentially many ways, and the overall match then fails. The engine dutifully tries every split before giving up. The classic shape is a nested quantifier like (a+)+$ or overlapping alternatives like (a|a)* or (\w|\d)+. On "aaaa...a!" each extra a roughly doubles the work.
Real-world variants hide in validators: ^(\w+\s?)*$, email patterns with nested groups, or (.*,)* for CSV. When an attacker controls the input, this is a ReDoS (regular expression denial of service).
How to fix or prevent it:
- Make alternatives mutually exclusive and each character matchable in only one way:
^\w+(?:\s\w+)*$instead of^(\w+\s?)*$. - Use possessive quantifiers or atomic groups so the engine can't re-split:
(?:\w++\s?)*+. - Bound input length before matching, and set timeouts where the platform allows (.NET
MatchTimeout, Java via interruptible input). - For untrusted patterns or inputs, use a linear-time engine (RE2, Go, Rust, or
google-re2for Python). - Lint for it: tools like
safe-regex, CodeQL's ReDoS queries andrecheckfind vulnerable patterns automatically.
Example
import re, time
evil = re.compile(r"^(\w+\s?)*$")
safe = re.compile(r"^\w+(?:\s\w+)*$")
for n in (18, 20, 22):
s = "a" * n + "!" # fails at the very end
t = time.perf_counter(); evil.match(s); e = time.perf_counter() - t
t = time.perf_counter(); safe.match(s); f = time.perf_counter() - t
print(n, f"evil {e:.3f}s", f"safe {f:.6f}s")
# 18 evil 0.08s safe 0.000008s
# 20 evil 0.25s ... each extra character roughly doubles the time
# 22 evil 1.0s
print(bool(safe.match("hello big world"))) # True, same language as intendedRemember
- Nested or overlapping quantifiers plus a failing match = exponential time
- Make each character matchable in only one way, or use atomic/possessive constructs
- For untrusted input, cap lengths or use a linear-time engine
Watch out for
- Testing a pattern only on inputs that match; catastrophic cases appear on near-misses that fail at the end.