Catastrophic Backtracking

The exponential trap

Some innocent-looking regex patterns become exponentially slow on certain inputs. The pattern (a+)+b matches 'aaaab' instantly. Run it against 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaa' (no 'b' at the end) and your CPU spins for minutes or hangs forever.

Why this happens

The engine tries every possible way to split the input among the iterations of a+. With 30 a's, that's 2^30 (~1 billion) splits. Each split fails because there's no 'b'. The engine tries them all before giving up.

The danger pattern

Look for nested quantifiers where the inner and outer can both match the same characters:

(a+)+ — inner and outer both match a's
(a*)* — same
(a|a)+ — alternatives match the same thing
(a|b)*c — when the input lacks c, every char can be tried as a or b
(\w+\s)+ — when the input ends without space

Anywhere a quantifier-bearing piece can be split multiple ways AND the rest of the pattern fails, you have potential explosion.

Fixes

Atomic groups / possessive quantifiers — disable backtracking. (?>a+)+b or a++b.
Negated character classes — [^X]+ can't backtrack to find X. [^"]* instead of .*?.
Anchoring — ^pattern$ at least limits the engine to one position.
Use RE2/Go for adversarial input — RE2 doesn't backtrack; impossible to ReDoS.

Code

Catastrophic patterns·python

import re
import time

# Don't actually run these on long input — they hang
# (a+)+b   matches 'aaaab' instantly
# (a+)+b   on 'a' * 30 + 'X' takes minutes
# (a*)*    same explosion
# (a|a)+   same

# Quick demo of how backtracking hits performance
def time_match(pattern, text, label):
    start = time.time()
    re.search(pattern, text)
    print(f'{label}: {time.time() - start:.3f}s')

# Safe size to demonstrate
text = 'a' * 25 + 'X'  # no 'b' at the end
time_match(r'a+b', text, 'simple')
# time_match(r'(a+)+b', text, 'catastrophic')  # would take seconds

# Atomic group fix (Python 3.11+)
import sys
if sys.version_info >= (3, 11):
    time_match(r'(?>a+)+b', text, 'atomic')  # immediate

# Negated class fix — works everywhere
text = 'a' * 100 + 'X'
time_match(r'a*X', text, 'simple a*X')        # fast
# time_match(r'(a*)*X', text, 'nested')        # explodes

Catastrophic Backtracking

The exponential trap

Why this happens

The danger pattern

Fixes

Code

External links

Exercise

Progress

Comments 0