Strings & regex

Catastrophic backtracking: when one regex melts a CPU

The mistake

A regex feels like a lookup. You hand it a string and it says yes or no, 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, which is a backtracking engine. It tries one way to match. 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. The slow case is not the match. It is the failure. On input short enough to fit in this sentence, a string that does not match can take longer to reject than the universe has existed.

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. Each one ends at the same !, so each one 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, and that 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. The trigger is an input that almost matches, so 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. That is a mercy, and it is also 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 accepts or rejects an input it never finished checking, and burns a CPU core on the way.

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. How many depends on one setting. With PCRE’s JIT on, which is what PHP ships, ruling out g groupings costs 4g - 2 steps. With pcre.jit=0, which Laravel Herd sets in its own php.ini, it costs exactly 5g. Both were measured on PHP 8.4 with PCRE2 10.44, by binary searching the smallest pcre.backtrack_limit that still lets preg_match finish. Either way the million step budget runs out at nineteen letters, not at the twenty-one the grouping count alone would suggest. The 2^(n-1) shape is the same in every case; only the constant in front of it moves.
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.