Why Your Regex Is Slow: Catastrophic Backtracking

A regex that runs in microseconds on a thousand inputs can hang for minutes on the thousand-and-first. Nothing changed in the engine; the input crossed a threshold that turns a well-behaved pattern into an exponential search. This is catastrophic backtracking, and it is behind most regex performance bugs and every ReDoS vulnerability. This post covers exactly why it happens, how to recognise the shapes that cause it, and what to do about them. The Complete Guide to Regular Expressions has the wider context; this is the deep dive on the one failure mode worth losing sleep over.

Backtracking Is Normal

Most engines you use daily — JavaScript, Python, Java, .NET, PCRE, Ruby, PHP — are backtracking engines. They match by trial and error: take a path, and if it dead-ends, rewind to the last decision point and take the next option. Every quantifier and every alternation creates such a decision point.

For almost every pattern this is fast and fine: a greedy .+ that overshoots and gives back ten characters has done ten units of extra work. The problem starts when decision points multiply rather than add.

The Textbook Case: ^(a+)+$

Consider ^(a+)+$ against the string aaaaaaaaaaaaaaaaaaaaaaaaaaaaaab — thirty a characters and one b.

The inner a+ can match any number of as. The outer + can repeat the group any number of times. So the question the engine keeps asking is: how do I divide these thirty as among the repetitions? One group of 30? Two groups of 15? Groups of 1, 4, 2, 23? Every one of those is a distinct path.

The count is exact and easy to state: dividing n consecutive characters into an ordered sequence of non-empty groups has 2^(n-1) possibilities. For 30 characters that is over half a billion.

On input that matches, none of this bites. Greedy matching takes the whole run in one go, $ is satisfied on the first try, done. The blowup happens only on input that almost matches — and the trailing b is what makes it almost. Every path the engine tries succeeds all the way through the as and then dies at the $, forcing a full rewind and the next split. It must exhaust all 2^29 arrangements before it can honestly report "no match".

The practical signature is unmistakable once you time it. In Node, twenty as finish instantly; twenty-six take a couple of seconds; thirty take close to a minute; thirty-five would run for the better part of an hour. Each character you add roughly doubles the work.

Why Anchoring Isn't Enough

A common piece of half-advice is "anchor it and you're fine". Anchoring is worth doing, but for a different reason. Without a leading ^, the engine retries the entire search from every start position in the string, multiplying the cost by the input length. Adding ^ removes that multiplier — a linear factor off an exponential problem. ^(a+)+$ is still catastrophic.

The fix has to remove the ambiguity itself.

The Shapes to Recognise

(a+)+ is a teaching example; nobody writes it deliberately. Real vulnerable patterns look ordinary:

• ^(\w+\s?)*$ — meant to validate "words separated by optional spaces". Because the space is optional, \w+ repeats can split a run of word characters arbitrarily. Feed it forty letters and a !.
• ^(\s*\w+)*$ — same problem: \s* can match nothing, so the group's boundaries are undetermined.
• (a|a)* and (a|ab)+ — overlapping alternatives. Two branches that can match the same text double the paths at every repetition.
• ^(\d+)*$, ([a-z]+)+, (x*)* — every variation of a quantifier wrapping a quantifier.
• .*.*=.* — no nesting at all, but three unbounded .* runs competing for the same characters. This one is polynomial rather than exponential, and still catastrophic in practice: this exact shape, inside a WAF rule, caused Cloudflare's global outage in July 2019.

The single rule underneath all of them: a repeated construct whose parts can match the same characters in more than one way. If two different splits of the input produce the same consumed text, the engine has to try both.

Polynomial cases matter too. Stack Overflow's 2016 outage came from an unremarkable trailing-whitespace trimming pattern meeting a post that contained around 20,000 consecutive space characters — no nested quantifier required, just quadratic behaviour and enough input to make it hurt.

Testing a Pattern Safely

Do not test a suspect pattern by pasting it into your production service. Test it in isolation, with input you control, and increase the length one step at a time.

Build the attack string in two parts: a pump of the repeated character, and a suffix of one character that cannot match. For ^(\w+\s?)*$ the pump is a letter and the suffix is !. Start at 20 pumps, then 24, then 28, and time each. Doubling times mean exponential; growth with the square or cube of the length means polynomial. Either way, fix it.

The Regex Tester & Matcher is a reasonable place to do this at small sizes — it runs the pattern in your browser tab rather than on a server, so a hang costs you a tab reload and nothing else. Keep the pump modest for exactly that reason. When you are auditing a pattern you did not write, the Regex Explainer & Pattern Breakdown is faster than reading it by eye: nested quantifiers stand out immediately once the pattern is laid out token by token.

Five Fixes

1. Make the parts mutually exclusive. This is the real fix, and it usually makes the pattern clearer too. Rewrite ^(\w+\s?)*$ so the separator is mandatory inside the repetition:

^\w+(?:\s\w+)*$

Now each repetition must begin with a space, and \s and \w cannot match the same character, so there is exactly one way to parse any input. The pattern is also honest about what it accepts — single spaces between words — where the original was vague. Similarly ^(\s*\w+)*$ becomes ^\s*\w+(?:\s+\w+)*\s*$, and (a|a)* was only ever a*. After a rewrite, confirm the new pattern still matches everything the old one did: running both over the same sample in Regex Find & Replace and comparing the output is a quick way to catch a rewrite that quietly narrowed the accepted set.

2. Prefer negated classes to .* and .*?. "[^"]*" cannot cross a quote, so it has nothing to backtrack over; ".*?" explores every position between quotes. The same logic that makes negated classes the better choice for greedy versus lazy matching makes them the safer choice here. If you are shaky on class syntax, Regex Character Classes and Quantifiers Explained covers the edge cases, and several of the safe patterns in Regex for Beginners — <[^>]+>, https?://[^\s)]+ — are built this way for precisely this reason.

3. Use atomic groups or possessive quantifiers where available. (?>...) and ++/*+ match greedily and then discard their backtracking positions, so a failure fails immediately. ^(?>a+)+$ cannot blow up. Java, PCRE, PHP, .NET, and Ruby support these. JavaScript does not, so in JS you either restructure the pattern or emulate an atomic group with (?=(a+))\1.

4. Cap the input length. A 256-character limit checked before the match bounds an otherwise exponential pattern. This is a mitigation, not a cure — do it in addition to fixing the pattern, and size the cap to the field's real requirements.

5. Change engines for untrusted input. Go's regexp and Rust's regex crate are finite-automata engines with a linear-time guarantee; they give up backreferences and lookaround to get it. .NET offers RegexOptions.NonBacktracking for the same trade, plus a per-match timeout that works with the normal engine. Python 3.11+ improved its matching but offers no timeout. Node has neither, which is why capping input and fixing patterns matter more there — a blocked event loop stalls every concurrent request on the process.

The Review Habit

Add one question to code review: does this pattern apply to input a user controls, and does it contain a quantifier inside a quantified group? That catches nearly everything. Patterns compiled from user-supplied strings deserve more suspicion still — if your search feature lets people type a regex, run it in a worker you can kill on a deadline.

Catastrophic backtracking is not a reason to avoid regular expressions. It is one narrow failure mode with a small set of recognisable shapes and a smaller set of reliable fixes. Once you can see the shape, you stop writing it.