What is catastrophic backtracking in regex?

Catastrophic backtracking happens when a regex engine tries an exponentially growing number of ways to match a pattern against a string that nearly matches. A pattern that matches in microseconds on valid input can hang for minutes on invalid input. It is caused by nested quantifiers like (a+)+b.

How do I fix catastrophic backtracking?

Use atomic groups (?>...) to prevent backtracking, rewrite nested quantifiers as possessive quantifiers ++, or simplify the pattern to avoid ambiguity. Test your regex against both matching and non-matching strings using a regex tester.

Is catastrophic backtracking a security risk?

Yes. Catastrophic backtracking is the root cause of ReDoS (Regular Expression Denial of Service) attacks, where crafted input causes a server to hang. Any application that runs user-supplied regexes against user-supplied input is vulnerable.

Regex Performance: Catastrophic Backtracking Explained

You write a regex. It passes all your test cases. It works on the happy path. Then someone submits input that looks almost valid but isn't, and the regex that ran in microseconds now takes 40 seconds to fail.

That is catastrophic backtracking. It is the single most expensive performance bug in regular expressions, and most developers do not discover it until it hits production. Here is how it works, which patterns trigger it, and how to fix it.

How Backtracking Works

Most regex engines use backtracking: they try a match, and if it fails, they go back and try an alternative path. For simple patterns this is fast. For patterns with nested flexibility, the number of paths grows exponentially.

Pattern: ^(a+)+$
String:  "aaaaX"

The engine tries: 4 a's as one group → fail → 3+1 → fail → 2+2 → fail → 2+1+1 → fail → 1+1+1+1 → fail. For an n-character string, the engine tries approximately 2ⁿ paths. At n=20 that is a million attempts. At n=30 it is a billion.

Patterns That Trigger It

Dangerous Pattern	Why It Is Dangerous
`(a+)+b`	Nested quantifiers — the classic trap
`(a\|aa)+b`	Alternatives inside a quantifier
`(.)b`	Wildcard with nested quantifier — matches everything
`\s,\s` on long strings	Quantifier-heavy splitting
`(a+b+c+)+$`	Multiple quantified groups

Any pattern where the engine can try many ways to divide the same characters into groups is suspect. The key sign: the pattern matches quickly on valid input and hangs on invalid input that almost matches.

Three Fixes

1. Atomic Groups (?>...)

Atomic groups tell the engine: once you match this group, never backtrack into it.

// Before: catastrophic
^(a+)+b$

// After: safe
^(?>a+)+b$

2. Possessive Quantifiers ++

A possessive quantifier matches as many characters as possible and never gives them back.

// Before
^(a+)+b$

// After
^(a++)+b$

3. Simplify the Pattern

Often the best fix is to remove the nested quantifier entirely.

// If you just need one or more a's followed by b:
// Before (dangerous): ^(a+)+b$
// After (safe):       ^a+b$

Testing for Catastrophic Backtracking

Use the Regex Tester on anan to test your patterns. Run the same regex against a short matching string and a longer non-matching string. If the non-matching test takes noticeably longer, your pattern has a backtracking problem.

Real-World Impact

Cloudflare, Stack Overflow, and multiple programming languages have shipped ReDoS vulnerabilities caused by catastrophic backtracking. A Cloudflare incident in 2019 was triggered by a single regex that matched a 50-character string in microseconds and hung the entire edge network on a 200-character string.

The fix always follows the same pattern: identify the nested quantifier, add an atomic group, and move on.

TL;DR

	Normal Pattern	Catastrophic Pattern
Structure	Linear	Nested quantifiers
Performance on bad input	Linear (O(n))	Exponential (O(2ⁿ))
Fix time	—	+1 atomic group

If your regex has (something+)+, you have a landmine. Defuse it before production finds it.