Greedy, lazy and catastrophic backtracking

How the engine searches, why nested quantifiers explode, and the practical defences against a pattern that hangs on hostile input.

How the engine actually searches

Perl-style engines walk the pattern and the input together, and when a later part fails they return to a choice point and try the next option. That return is a backtrack. A pattern only takes exponential time when the failures force the engine to retry the same combinations over and over.

pattern: a*a  input: aaaab

attempt 1: a* takes aaaa, then needs 'a', fails
attempt 2: a* gives one back, takes aaa, then needs 'a', fails
attempt 3: ... one backtrack per character, linear

pattern: (a+)+b  input: aaaaaaaa...c

the outer + can split the run into groups in 2^n ways,
and every split is tried before the engine gives up

• Backtracking is what makes backreferences, lookaround and ordered alternation possible. It is not a defect; the danger is a pattern that has many equivalent ways to fail.
• Ambiguity is the root cause. Two quantifiers that can match the same characters create the choice points that multiply.
• Anchoring helps: a failing pattern with ^...$ often fails fast because the match cannot restart at every offset.

Patterns that explode

// measuring instead of guessing: this returns in milliseconds for short input
function timePattern(re, input) {
  const t0 = performance.now();
  re.test(input);
  return performance.now() - t0;
}

const re = /^(a+)+$/;
timePattern(re, 'a'.repeat(20));   // fast
timePattern(re, 'a'.repeat(28));   // noticeably slower
timePattern(re, 'a'.repeat(32));   // seconds, then minutes

Each extra character roughly doubles the work for this pattern, so a 22-character input that finishes in a second becomes a 30-second request at 27 characters. Any regular expression applied to user-supplied text has this shape of risk until you have measured it.

Defences that actually work

import re, signal

# 1. limit the input before it reaches the pattern
def safe_match(pattern, text, max_len=10_000):
    if len(text) > max_len:
        raise ValueError('input too long')
    return re.search(pattern, text)

# 2. rewrite the pattern so it cannot be ambiguous
re.search(r'^(\w+)(\s\w+)*$', 'one two three')     # linear

# 3. atomic groups and possessive quantifiers remove the choice point entirely.
#    Python 3.11+, PCRE2 and Java have them; JavaScript does not.
re.search(r'(?>a+)b', 'aaab')                       # atomic group
re.search(r'a++b', 'aaab')                          # possessive quantifier

# 4. run the pattern with a wall-clock limit in a worker, not in the request
signal.alarm(1)                                      # Unix only, coarse but effective
try:
    re.search(pattern, hostile_input)
finally:
    signal.alarm(0)

• Split the work: extract with a linear pattern, then validate the extracted piece with a second, stricter one.
• Bound the length of every input that reaches a regex. Rewriting the pattern is better, but a length cap protects you from the patterns you have not audited yet.
• Longest-input-first is not a defence. The attacker controls the input.
• If the pattern is used on untrusted text in a hot path, prefer a linear-time engine such as RE2 or Go's regexp, where this whole class of failure does not exist.
• Add a regression test with a hostile string for every pattern you ship. A pattern that passes the happy path and hangs on a crafted string passes code review every time.

FAQ

Related

Dialects and engines: PCRE, POSIX, RE2 and .NET When not to use regex

Last refreshed 2026-09-18.