Catastrophic backtracking: why a regex can hang

Most regexes finish in microseconds. A few, on the wrong input, run for seconds, minutes or longer, pinning a CPU core the whole time. It's called catastrophic backtracking, and it has taken down real websites.

The good news is that the dangerous patterns have a recognisable shape, and the fixes are usually small. This post shows the shape, the numbers, and the rewrites.

01How backtracking works

JavaScript, Python, Java, PHP and most other languages use a backtracking engine. When a pattern has choices (how many characters a + takes, which side of a | to try) the engine picks one and moves on. If the match fails later, it goes back and tries the next choice.

For a pattern like ^a+$ on aaaa!, there isn't much to try: a+ takes all four a's, $ fails on the !, the engine gives back one a at a time, and each attempt fails quickly. A handful of steps, then "no match".

02The shape that explodes

Now put a quantifier inside another quantifier:

(a+)+ means "one or more groups, each of one or more a's". Four a's can be split into groups in eight ways: aaaa, aaa|a, a|aaa, aa|aa, aa|a|a, and so on. When the ! makes the match fail, the engine tries every split before giving up. Each extra a doubles the number of splits.

Here's what that looks like in Node 23 on an ordinary laptop, on a string of a's followed by !:

Length	^(a+)+$	^a+$
24 a's	0.12 s	under 0.01 ms
26 a's	0.5 s	under 0.01 ms
28 a's	2 s	under 0.01 ms
40 a's	over two hours (projected)	under 0.01 ms

Same strings matched, wildly different cost. The danger is always a failing match: when the input matches, the first path usually works.

The general shape to watch for is a repeated group whose inside can match the same text in more than one way:

• Nested quantifiers: (a+)+, (\w+)*, (\d*)+
• Alternatives that overlap, repeated: (a|a)+, (\w|\d)+, (.*,)*
• Several .* in a row on the same text: .*=.*=.*

03It has happened in production

Stack Overflow, July 2016. A post contained about 20,000 consecutive whitespace characters in the middle of a line. A regex meant to trim whitespace from the end of a line, essentially \s+$, tried a match starting at every one of those spaces. Each attempt ran to the end of the whitespace, found more text instead of the end of the line, and failed. That's quadratic work, about 200 million steps, and it took the site down for 34 minutes.

Cloudflare, July 2019. A new firewall rule contained a pattern with .*(?:.*=.*) in it. Every server running the rule hit 100% CPU, and Cloudflare's network dropped traffic worldwide for about 27 minutes.

Neither pattern looked dangerous at a glance. Both were fine on normal input.

04Fix 1: make the choices exclusive

The cleanest fix is a pattern where each character can only be matched one way. Remove the nesting:

A real example: comma-separated numbers. The risky version nests a repeated group around another quantifier and lets the comma be optional, so a run of digits can be split many ways:

The safe version makes the comma required between items, so each digit belongs to exactly one place:

05Fix 2: say what can't appear

.* is often the culprit because it can match anything, including the text the next part needs. A negated class is exclusive by construction:

06Fix 3: atomic groups and possessive quantifiers

An atomic group (?>…) matches once and never gives anything back. A possessive quantifier (a++, \d*+) does the same for a single quantifier. Either one removes the alternatives the engine would otherwise retry.

Python supports both since 3.11. Java, PCRE and PHP have them too. JavaScript has neither, but a lookahead with a backreference behaves like an atomic group: (?=(a+))\1 matches the a's once and can't be split.

07Fix 4: limit the input, or the engine

• Cap the input length before matching. Many explosive patterns are harmless on 200 characters.
• Use a linear-time engine for untrusted input. Google's RE2 (with bindings for Node, Python, Go and more) and Rust's regex crate never backtrack, so they can't explode. They don't support backreferences or lookarounds, which is the price.
• Set a timeout where the platform has one. .NET's Regex takes a matchTimeout.

08Try one

Write the safe version of a comma-separated number list:

09Checklist

• Danger sign: a quantified group whose inside can match the same text in several ways: (a+)+, (\w|\d)+, (.*,)*.
• The cost shows on failing matches, and it can double with every character.
• Make each character matchable one way only: required separators, no nesting.
• Prefer [^x]* to .* when the next part starts with x.
• Use atomic groups or possessive quantifiers where you can (Python 3.11+, Java, PCRE).
• For untrusted input, cap its length or use RE2.

10Keep practising

• The guide's performance section covers this with more examples.
• The post on greedy vs lazy quantifiers explains how quantifiers choose what to take.
• Quantifier quarry is a practice pack for getting quantifiers exactly right.