Catastrophic backtracking, explained with ^(a+)+$

Answer

^(a+)+$ has a quantifier inside a quantifier. When the input is a long run of a followed by something else, the engine tries every way of dividing the run between the inner and outer + before it gives up, which doubles with each extra character. The fix is ^a+$, which matches the same strings.

JavaScript ✓PCRE ✓

Catastrophic backtracking risk. Nested quantifier: a+ is repeated inside (a+)+. On a long string that almost matches, the engine can try every way of splitting the text between the inner and outer repeat: exponential time (catastrophic backtracking). Make the pieces unambiguous (each repetition should start or end with a character the inner part cannot match), drop one of the quantifiers, or use an atomic group / possessive quantifier in PCRE.

^Start of the stringanchor
(…)Capturing group #1: remembers what it matchedgroup
aThe character 'a'literal
+Repeat it one or more times, as many as possible (greedy)quantifier
+Then repeat the whole group one or more times, as many as possible (greedy)quantifier
$End of the stringanchor

1 capturing group.

Examples

Checked at build time in JavaScript and in Python's re.

Input	Matches?
`a`	✓ match
`aaaa`	✓ match
`aaab`	✗ no match
`(empty string)`	✗ no match
`baaa`	✗ no match

Try your own text

One string per line: each line is tested on its own (the m flag is added here).

How it works

On aaab, the inner a+ first takes all three a. Then $ fails at the b. The engine backtracks: the inner a+ gives up one a, and the outer + starts a second repetition with it. That fails too, so it tries a|aa, aa|a, a|a|a, and so on. A run of n characters can be split in 2^(n-1) ways, and every one is tried. At 30 characters that is over 500 million attempts.

JavaScript, Python, Java, .NET, Perl and PCRE all use backtracking engines, and all are affected. RE2, Go's regexp and Rust's regex crate guarantee linear time by not backtracking, at the cost of dropping backreferences and lookarounds. On a server, a pattern like this run on user input is a denial-of-service hole (ReDoS): one request can pin a CPU core. Cloudflare's global outage on July 2, 2019 came from a WAF rule containing .*(?:.*=.*), a related pattern with overlapping .* repeats.

To fix it, make each part of the input matchable in only one way. Remove the redundant quantifier. Or make each repetition start with a character the inner part cannot match, as in ^\w+(?:-\w+)*$, where every repetition begins with -. PCRE, Java, and Python 3.11+ also support atomic groups (?>a+) and possessive quantifiers a++, which refuse to give back characters. JavaScript has neither.

Variants

/^a+$/
The fix: the same set of matching strings, in linear time.
/^(?=(a+))\1$/
Atomic-group emulation in JavaScript: the lookahead captures greedily and the backreference cannot be re-split.

Gotchas

The slowdown only shows on input that almost matches. Tests with valid input pass quickly, so the bug ships.
Hidden versions are common: (\w+\s?)+$, (\d+)*, (.*,)*. Look for a repeated group whose contents can match the same text in more than one way.
(a|a)+ and (\d|\w)+ are the alternation form of the same problem: two branches that can match the same character.
Limit input length before matching untrusted strings. A 2^n pattern on 20 characters is still fast; on 50 it never finishes.

Related explainers

← Explain any regular expression