Strings & regex

Catastrophic backtracking: when one regex melts a CPU

The mistake

A regex feels like a lookup: you hand it a string, it says yes or no, and it does that in about the time it takes to read the string once. So a pattern that is a little redundant seems harmless. (a+)+$ is just “one or more groups of one or more a’s, to the end”. It matches the same strings as a+$, so who cares if it is written the long way.

The engine cares. PHP’s preg_* functions use PCRE, a backtracking engine: it tries one way to match, and if that fails it backs up and tries another, until something works or every option is exhausted. For most patterns that is quick. For a nested quantifier over an overlapping class, the number of options grows as 2^n, and the slow case is not the match, it is the failure. A string that does not match can take longer to reject than the universe has existed, on input short enough to fit in this sentence.

The machine

Simulator · Catastrophic backtracking

The path count, the outcome and the backtrack limit run on the tested reducer, computed from the maths, so the count is exact and nothing ever hangs.

The naive pattern (a+)+$ against six a’s and a "!". A match must try 32 groupings before it can fail.

Drive it

The panel boots with (a+)+$ against six a’s and a !. It cannot match, but the big number already says 32: the paths it must rule out before it can say so.

Run it, then add a letter and run again. Seven letters is 64 paths, eight is 128. Every single letter doubles the work. This is the whole catastrophe in one number.
Make it match, and run. One attempt. A matching input is instant, because the greedy first try succeeds and nothing has to backtrack. The blow-up only ever happens on input that fails.
Grow it to nineteen letters, then switch to an atomic group. Nineteen is where the million step budget runs out, so you watch PHP give up and return false instead of a clean no match. Then (?>a+)+$ drops the same input to a single path.

The mechanism

(a+)+ matching a run of n a’s is ambiguous. The inner a+ and the outer + are both greedy and both match a’s, so the run can be carved up in many ways: one group of all n, or n-1 then 1, or 1 then n-1, and so on. Each way is an ordered partition of n, and there are exactly 2^(n-1) of them.

Watch what the engine does against aaaaaa!. Greedy, it takes the coarsest option first: the inner a+ swallows all six a’s in one group. Then $ checks for the end of the string, finds !, and fails. So the engine backtracks: the inner a+ gives back one a, the outer + opens a second group for it, and $ is tried again. Still !. Still fails. It keeps going, redistributing the a’s into every possible grouping, and every grouping ends at the same !, so every grouping fails. Only after all 2^(n-1) of them does the engine conclude there is no match.

That is why adding one letter doubles the time: one more a is one more place to split, which doubles the groupings. Nothing here depends on the a’s being a’s. Any nested quantifier over classes that can match the same characters does it: (\s*\w+\s*)*, (.*)*, (a|a)*. These hide in real validation patterns, and because the trigger is an input that almost matches, an attacker who controls the string can hang your request with a few dozen characters. That is a denial of service, sometimes written ReDoS.

In your code

PHP does not hang forever, which is both a mercy and a trap. PCRE has a pcre.backtrack_limit, one million steps by default. When a match blows past it, preg_match does not return 0, it returns false:

$ok = preg_match('/^(a+)+$/', $input);

if ($ok === false && preg_last_error() === PREG_BACKTRACK_LIMIT_ERROR) {
    // the match never finished; it was cut off at the limit
}

The trap is that most code never checks for false. if (preg_match($pattern, $input)) treats false as “no match”, so a validator quietly waves through, or rejects, an input it never actually finished checking, and burns a CPU core doing it.

The fix is to remove the ambiguity so there is nothing to backtrack. An atomic group or a possessive quantifier tells the engine that once the inner part has matched, it may never give those characters back:

preg_match('/^(?>a+)+$/', $input);   // atomic group: no giving back
preg_match('/^a++$/', $input);       // possessive quantifier: same effect
preg_match('/^a+$/', $input);        // best of all: no nesting to begin with

All three are linear. When the nesting is essential to what you are matching, reach for (?>...) or the possessive ++, *+, ?+. When it is not, the real fix is to stop writing a group you did not need.

The fine print

The simulator counts the distinct groupings the engine must rule out, which is the exact source of the blow-up. PCRE counts something finer: internal backtracking steps, several per grouping. For this pattern it is exactly five, measured on PHP 8.4 with PCRE2 10.44, which is why the million step budget buys 200,000 groupings and runs out at nineteen letters rather than at the twenty-one the grouping count alone would suggest. The 2^(n-1) shape is the same either way; only the constant in front of it differs.
This is a property of backtracking engines, which most languages use: PCRE, and the regex engines in Java, JavaScript, .NET and Python. Engines built on automata, like Go’s regexp and RE2, cannot backtrack, so their cost cannot grow like this. They give up a few features in exchange.
Raising pcre.backtrack_limit does not fix anything; it just moves the cliff. The fix is the pattern.
A cheap defence in depth is to cap input length before matching. 2^n is only scary because n is allowed to grow; a length limit bounds the worst case.
Matching inputs stay fast even with the naive pattern, which is exactly why this bug survives testing: the happy path never triggers it. Only the crafted, failing input does.