Regex Catastrophic Backtracking (tested)

Catastrophic backtracking is when a regex engine's running time explodes on certain non-matching input, because nested or overlapping quantifiers force it to try an exponential number of ways to fail. We reproduced it with real timings, then measured three different fixes.

1. Reproduced: a pattern that looks harmless

$ cat backtrack.py
import re, time, sys
pattern = re.compile(r"^(a+)+$")
n = int(sys.argv[1])
s = "a" * n + "!"
t0 = time.perf_counter()
m = pattern.match(s)
t1 = time.perf_counter()
print(f"n={n} match={m} elapsed={t1-t0:.4f}s")

^(a+)+$ matches one or more "a"s. We fed it strings of all "a"s followed by one "!" so it can never match, and timed how long the engine takes to give up and report that:

Each +5 characters multiplied the time by roughly 30×. That's exponential growth, not linear or even polynomial: the same engine that rejects a 25-character string in 1.5 seconds doesn't finish a 30-character string in 5 full seconds. A real input of a few hundred characters would not finish this century.

2. Why it happens

(a+)+ nests one "one or more" quantifier inside another. For an input of all "a"s, there are many different ways to split those "a"s between the inner and outer repetition that all consume the same characters — for example 20 a's could be grouped as one block of 20, two blocks of 10, four of 5, and so on. When the overall match fails (because of the trailing !), the engine backtracks and tries the next grouping instead of concluding immediately that no grouping will ever help, since none of them touch the real problem: the ! at the end. The number of groupings grows exponentially with the number of a's, and Python's re tries them one at a time.

3. Reproduced: it's a real hang, not just "slow"

$ timeout 5 python3 backtrack.py 30; echo "exit=$?"
exit=124

Exit code 124 is what GNU timeout returns when it had to kill the process. This is the actual risk: a regex like this, fed user input (a search box, a log line, a URL), can tie up a worker thread or an entire request indefinitely. It is a known denial-of-service vector (sometimes called ReDoS), not a theoretical curiosity.

4. Fix 1 — rewrite the pattern

(a+)+ is redundant: one or more of "one or more a's" is exactly the same language as one or more a's. We measured the simplified pattern ^a+$ against an input 3,000× longer than the one the original pattern couldn't finish in 5 seconds:

$ cat fixed_rewrite.py
import re, time, sys
pattern = re.compile(r"^a+$")
n = int(sys.argv[1])
s = "a" * n + "!"
t0 = time.perf_counter()
m = pattern.match(s)
print(f"rewrite n={n} match={m} elapsed={time.perf_counter()-t0:.4f}s")

$ python3 fixed_rewrite.py 100000
rewrite n=100000 match=None elapsed=0.0007s

100,000 characters in under a millisecond, versus the original pattern not finishing 30 characters in 5 seconds. The best fix for catastrophic backtracking is almost always removing the redundant nesting that caused it — it's worth checking whether the "safe" pattern just does, too.

5. Fix 2 — atomic group, when you can't simplify the pattern

Python's re module (3.11+) supports atomic groups with (?>...). An atomic group commits to whatever it matched and never backtracks into it, which removes the exponential blowup even when you keep the nested structure:

$ cat fixed_atomic.py
import re, time, sys
pattern = re.compile(r"^(?>a+)+$")
n = int(sys.argv[1])
s = "a" * n + "!"
t0 = time.perf_counter()
m = pattern.match(s)
print(f"atomic n={n} match={m} elapsed={time.perf_counter()-t0:.4f}s")

$ python3 fixed_atomic.py 100000
atomic n=100000 match=None elapsed=0.0001s

We measured the same 100,000-character input instant with the atomic group added, with the original nested shape otherwise untouched.

6. Fix 3 — possessive quantifiers

Also added to re in Python 3.11, ++ is a possessive version of +: it matches greedily like normal but, like an atomic group, never gives back characters by backtracking:

$ cat fixed_possessive.py
import re, time, sys
pattern = re.compile(r"^(a++)+$")
n = int(sys.argv[1])
s = "a" * n + "!"
t0 = time.perf_counter()
m = pattern.match(s)
print(f"possessive n={n} match={m} elapsed={time.perf_counter()-t0:.4f}s")

$ python3 fixed_possessive.py 100000
possessive n=100000 match=None elapsed=0.0001s

Same result as the atomic group: instant on 100,000 characters. Use whichever reads clearer in context; they solve the same problem the same way.

7. Fix 4 — a hard timeout as a backstop

None of the above helps if you don't control the pattern (for example, a user-supplied regex). As a last resort we measured a hard wall-clock budget using signal.setitimer, which works because SIGALRM interrupts even a CPU-bound C-level match in progress:

$ cat sigtimeout.py
import re, signal, time
class RegexTimeout(Exception): pass
def handler(signum, frame): raise RegexTimeout()
pattern = re.compile(r"^(a+)+$")
s = "a" * 30 + "!"
signal.signal(signal.SIGALRM, handler)
signal.setitimer(signal.ITIMER_REAL, 2.0)
t0 = time.perf_counter()
try:
    m = pattern.match(s)
    print("matched:", m)
except RegexTimeout:
    print(f"aborted: regex exceeded 2.0s budget (elapsed {time.perf_counter()-t0:.2f}s)")
finally:
    signal.setitimer(signal.ITIMER_REAL, 0)

$ python3 sigtimeout.py
aborted: regex exceeded 2.0s budget (elapsed 2.00s)

This cleanly aborted the same pattern that otherwise hangs past 5 seconds, at exactly the 2-second budget we set. Caveat we didn't disprove but didn't need to test further: SIGALRM is Unix-only and fires on the main thread, so this exact approach doesn't work unmodified inside a thread or on Windows — there, a separate worker process with a timeout is the equivalent backstop.

8. Checklist

• Look for nested or adjacent quantifiers on patterns that can overlap the same characters: (a+)+, (a|a)*, (a*)*, (.*)*.
• First try removing the redundant nesting — it's usually both faster and more correct.
• If the structure is genuinely needed, add atomic groups (?>...) or possessive quantifiers (++, *+, ?+); both are in Python's re since 3.11.
• For patterns you don't control (user-supplied regex), wrap matching in a hard timeout as a backstop, not as the primary fix.
• Test with adversarial input before shipping: a long run of the repeated character followed by one character that can't match, like our "a"*n + "!".

If the pattern itself is failing to compile rather than hanging, see Python's invalid escape sequence warning, a different regex gotcha we measured on the same box.

Written with AI assistance. Measured on 2026-10-03 with CPython 3.13.5 on a real Linux box. Every timing below is from time.perf_counter() around a single match() call; runs that could hang were hard-capped with the shell's timeout(1) at 5s so none ran unbounded. PlainHeaders is our extension; Python is free.