Performance and Catastrophic Backtracking

How a backtracking engine spends its time

Most regex engines in programming languages are backtracking engines. They walk through the pattern and the text together; at every choice (how many characters a quantifier takes, which branch of an alternation to try) they pick one option and remember the others. When the rest of the pattern fails, they go back to the last choice and try the next option. If every option at every start position fails, the answer is "no match", but only after all of them have been tried.

For most patterns that is fast, because each choice has only a few options and a failing option fails quickly. The trouble starts when the number of combinations of choices grows with the length of the input. Take (a+)+$: "one or more rounds of one or more a, then the end". On aaaa! the engine can split the a's over the rounds in many ways (aaaa, aaa|a, aa|aa, a|a|a|a …), and because the ! makes $ fail every time, it tries them all. The model below counts those attempts, the way a simple backtracking engine would make them:

def count_attempts(text):
    """Count how often a backtracking engine tries a split for (a+)+$ on text."""
    attempts = 0

    def outer(pos):
        # One more round of the outer +: an inner a+ of length 1, 2, 3, ...
        nonlocal attempts
        end = pos
        while end < len(text) and text[end] == "a":
            end += 1
        for stop in range(end, pos, -1):      # greedy: longest first
            attempts += 1
            if stop == len(text):             # $ succeeds only at the very end
                return True
            if outer(stop):                   # try another round
                return True
        return False

    for start in range(len(text)):            # the engine tries every start position
        if outer(start):
            return True, attempts
    return False, attempts

for n in [4, 8, 12, 16]:
    matched, attempts = count_attempts("a" * n + "!")
    print(f"n={n:2}  matched={matched}  attempts={attempts:,}")

n= 4  matched=False  attempts=26
n= 8  matched=False  attempts=502
n=12  matched=False  attempts=8,178
n=16  matched=False  attempts=131,054

Every extra a roughly doubles the work: a string of n a's can be split into rounds in 2ⁿ⁻¹ ways. In terms of time complexity, the pattern is O(2ⁿ) on this input. Real engines have optimizations that change the exact counts, but not the shape of the curve.

Catastrophic backtracking

Catastrophic backtracking is what happens when a backtracking engine has so many ways to try a pattern against a text that the running time explodes, usually exponentially (sometimes polynomially) with the length of the input. It almost always shows up on input that does not match: a successful match stops at the first way that works, but a failure has to rule out every way.

Nested quantifiers and other warning signs

The classic cause is a nested quantifier: a quantified group that itself contains a quantifier, such as (a+)+ or (\w+\s?)*, where the inner and outer repetition can divide the same text in many ways. Nesting is harmless when the pieces cannot overlap (in ([0-9]+,)+ each round must end at a comma, so there is only one way to divide the text). It is dangerous when the same characters can belong to different rounds. The warning signs:

The first two rows are based on OWASP's list of "evil" patterns; the third is close to the pattern behind the Cloudflare outage and the fourth to the Stack Exchange outage, both described below. A pattern also needs a way to fail late for the problem to show: an anchor such as $ or a required character after the repeated part.

The same pattern in real engines

On short input every engine finishes instantly, and the dangerous pattern gives the same answers as the safe rewrites. That is why these bugs pass review and ordinary tests. The atomic group (?>a+) and the possessive quantifier a++ never give back what they matched (see quantifiers), so they remove the extra ways to split; Python supports both since version 3.11.

import re

patterns = {
    "nested   (a+)+$": re.compile(r"(a+)+$"),
    "simple   a+$": re.compile(r"a+$"),
    "atomic   (?>a+)+$": re.compile(r"(?>a+)+$"),
    "possess. a++$": re.compile(r"a++$"),
}

for text in ["kWh aaaa", "a" * 16 + "!"]:
    print(f"text of length {len(text)}:")
    for name, pattern in patterns.items():
        m = pattern.search(text)
        print(f"  {name:20} {m.group() if m else 'no match'}")

text of length 8:
  nested   (a+)+$      aaaa
  simple   a+$         aaaa
  atomic   (?>a+)+$    aaaa
  possess. a++$        aaaa
text of length 17:
  nested   (a+)+$      no match
  simple   a+$         no match
  atomic   (?>a+)+$    no match
  possess. a++$        no match

The output hides the difference in time. Measured on the machine that checks this page's examples (Python 3.11, Node.js 24), the nested pattern on 16 a's and a ! takes a few milliseconds; at 24 a's it takes a second or two in Python and between half a second and a few seconds in Node.js, and every two extra characters multiply that by about four. Thirty characters would take a minute or more (an extrapolation, not a measurement). The atomic version stays well under a millisecond. That is why the example stops at 16.

PHP and grep give up instead of hanging

PCRE2, the engine behind PHP's preg_* functions and grep -P, counts its backtracking steps and stops at a limit. PHP then returns false instead of 0 or 1:

<?php
$text = str_repeat('a', 30) . '!';

echo 'backtrack limit: ', ini_get('pcre.backtrack_limit'), "\n";

$result = preg_match('/(a+)+$/', $text);
var_dump($result);
echo preg_last_error_msg(), "\n";

$result = preg_match('/a+$/', $text);
var_dump($result);
echo preg_last_error_msg(), "\n";

backtrack limit: 1000000
bool(false)
Backtrack limit exhausted
int(0)
No error

GNU grep shows both worlds. Without -P it uses its own matcher, which does not backtrack for patterns without backreferences; with -P it uses PCRE2 and hits the limit:

# One line of 5000 times "a" followed by "!"
printf 'a%.0s' $(seq 5000) > long.txt
printf '!\n' >> long.txt
wc -c < long.txt

grep -cE '(a+)+$' long.txt
echo "grep -E exit status: $?"

grep -cP '(a+)+$' long.txt
echo "grep -P exit status: $?"

5002
0
grep -E exit status: 1
grep: long.txt: exceeded PCRE's backtracking limit
grep -P exit status: 2

grep -E answers "0 matching lines" (exit status 1) immediately, even for 5000 characters. grep -P reports an error with exit status 2, which a script must not confuse with "no match".

ReDoS: slow patterns as an attack

Catastrophic backtracking becomes a security problem when someone else controls the input. ReDoS (regular expression denial of service) is an attack, or an accident, in which input makes a vulnerable pattern run for so long that the service stops responding. OWASP describes it as a denial of service that "exploits the fact that most Regular Expression implementations may reach extreme situations that cause them to work very slowly (exponentially related to input size)".

Unlike a distributed denial of service, ReDoS needs no botnet: one short request can occupy a CPU core, and a handful of requests can occupy all of them. Vulnerable patterns hide in many places: form validation, log parsers, web application firewall rules, routing tables, and libraries you did not write. A defender's job is to recognize the risky shapes, prevent them in code review and tests, and limit the damage when one slips through:

• Recognize: nested or overlapping quantifiers followed by something that can fail; requests that use 100% of a CPU core while the rest of the system is idle; timeouts that cluster around one endpoint or one log source.
• Prevent: review patterns that touch untrusted input, rewrite risky shapes, and never build a pattern from user input without escaping it (see escaping).
• Mitigate: input length limits, engine limits and timeouts, a linear-time engine for untrusted patterns, and monitoring of CPU time per request.

Two real outages

Stack Exchange, July 2016

On 20 July 2016 Stack Overflow and the other Stack Exchange sites were down for 34 minutes. A post contained about 20,000 consecutive whitespace characters, and a regular expression meant to trim whitespace from the start and end of a line (^[\s\u200c]+|[\s\u200c]+$) ran on it; the slow part was the second alternative, similar to \s+$. That post was on the home page, which the load balancer used as its health check, so the servers failed the check and were taken out of rotation. The postmortem stresses that this was not exponential, "only" quadratic: starting at each of the 20,000 spaces, the engine scanned to the end of the run before finding that it was not the end of the string.

import re

def trim_checks(n):
    r"""Model of \s+$ on n spaces followed by one letter."""
    checks = 0
    for start in range(n):          # every space is a possible start
        checks += n - start         # \s+ runs to the letter, then $ fails
    return checks

for n in [10, 100, 1_000, 20_000]:
    print(f"{n:>6,} spaces -> {trim_checks(n):>11,} checks")

text = "Meter KE-0042 replaced." + " " * 2_000 + "x"
print(re.search(r"\s+$", text))       # right answer, wasted work
print(text.rstrip() == text)          # same question, one pass from the end

    10 spaces ->          55 checks
   100 spaces ->       5,050 checks
 1,000 spaces ->     500,500 checks
20,000 spaces -> 200,010,000 checks
None
True

About 200 million checks for one post. Stack Exchange fixed it by replacing the regex with a plain substring operation; they found the cause in 10 minutes, fixed it in 14 and deployed in 10.

Cloudflare, July 2019

On 2 July 2019 Cloudflare deployed a new rule to its web application firewall at 13:42 UTC. The rule contained a regular expression with the part .*(?:.*=.*), several .* next to each other, and running it on HTTP requests "caused CPUs to become exhausted on every CPU core that handles HTTP/HTTPS traffic on the Cloudflare network worldwide". Visitors to sites behind Cloudflare got 502 errors until the firewall was disabled globally at 14:07 UTC; by 14:09, about 27 minutes after the deployment, traffic and CPU were back to normal. Among the follow-up actions, Cloudflare planned to switch to the RE2 or Rust regex engine, "which both have run-time guarantees".

Neither outage needed an attacker, and neither pattern looked like the textbook (a+)+. Both were ordinary patterns meeting unusual input at scale.

Writing safer patterns

1. Remove the nesting. (a+)+ means the same as a+; (\w|\d)+ means the same as \w+. Many dangerous patterns are simply redundant.
2. Make alternatives and neighbors mutually exclusive. Replace .* by a class that cannot eat the next delimiter: [^=]*= instead of .*=, "[^"]*" instead of ".*". Then there is only one way to divide the text.
3. Use atomic groups or possessive quantifiers where the flavor has them (PCRE, Python 3.11 and later). They tell the engine "do not come back in here".
4. Anchor what you can. A pattern that must match at the start (^, or re.match()) is tried at one position instead of every position.

JavaScript has neither atomic groups nor possessive quantifiers (as of 2026, not in any edition of the standard). Lookahead offers a workaround, because a lookahead that has succeeded is never re-entered:

for (const source of ["(?>a+)+$", "(a++)+$"]) {
  try {
    new RegExp(source);
  } catch (error) {
    console.log(error.message);
  }
}

// Same effect as the atomic group (?>a+): a lookahead captures the a's,
// then \1 consumes exactly what was captured. The engine can't give back
// part of it, because a lookahead is never re-entered once it has succeeded.
const emulated = /(?:(?=(a+))\1)+$/;
const text = "a".repeat(16) + "!";
console.log(emulated.test(text), emulated.test("kWh aaaa"));

Invalid regular expression: /(?>a+)+$/: Invalid group
Invalid regular expression: /(a++)+$/: Nothing to repeat
false true

The trick works, but it is hard to read. In JavaScript the better fix is usually the rewrite (a+$). See lookahead and lookbehind for how lookaround works.

Running patterns safely

Careful patterns are the first line of defense. The second is to make sure that even a bad pattern cannot take the service down.

Limit the input first

Exponential blow-up needs input of only a few dozen characters, but quadratic blow-up needs thousands. A maximum length that fits the field (a postal code needs about 10 characters, a name perhaps 100, a log line a few kilobytes) checked before the regex runs removes most quadratic cases and costs nothing. See validating input.

Backtrack limits and timeouts

A backtrack limit is a maximum number of steps a backtracking engine may take for one match attempt; when it is reached, the engine stops with an error instead of running on. PCRE2 has one, set in PHP by pcre.backtrack_limit (1,000,000 by default). The catch is that the error arrives as a return value of false, which if (preg_match(…)) silently treats like "no match". Check it with === and fail closed:

<?php
function matches(string $pattern, string $subject): bool
{
    $result = preg_match($pattern, $subject);
    if ($result === false) {
        // Fail closed: an engine error is never treated as "valid".
        throw new RuntimeException(preg_last_error_msg());
    }
    return $result === 1;
}

$text = str_repeat('a', 30) . '!';
var_dump(matches('/(a++)+$/', $text));   // possessive: fast "no"
var_dump(matches('/(?>a+)+$/', $text));  // atomic group: same
var_dump(matches('/(a+)+$/', $text));    // nested: limit hit

bool(false)
bool(false)
Fatal error: Uncaught RuntimeException: Backtrack limit exhausted in example.php:7

Other platforms, as of 2026:

• .NET accepts a match timeout per regex or for the whole process, and throws RegexMatchTimeoutException when it expires. The default is no timeout at all, so set one for untrusted input.
• Python's re has no timeout and no step limit. The third-party regex module accepts a timeout argument. Otherwise, run risky matching in a separate process you can stop.
• JavaScript has no regex timeout either. In Node.js, common options are a linear-time engine such as the re2 package, or running untrusted patterns in a worker thread or child process that can be terminated.

Linear-time engines

The real cure is an engine that cannot backtrack catastrophically. A linear-time regex engine simulates all possible paths through the pattern at once (an automaton, in the tradition of Ken Thompson's 1968 algorithm) instead of trying them one by one, so its running time grows in proportion to the length of the input, whatever the pattern. The price: such engines leave out features that need backtracking, mainly backreferences and lookaround.

• RE2 (Google's C++ library) and Go's regexp package, which uses the same syntax.
• Rust's regex crate, which promises worst-case O(m × n) time (pattern size times input size); the ripgrep search tool is built on it.
• .NET 7 and later: RegexOptions.NonBacktracking, which "guarantees linear-time processing in the length of the input".
• GNU grep (without -P), sed and awk: their POSIX matchers do not backtrack for patterns without backreferences, as the grep -E run above showed.
• V8 (the JavaScript engine of Chrome and Node.js) has an experimental linear engine behind the --enable-experimental-regexp-engine flag. It is off by default and not meant for production.

If your service lets users type their own patterns (a log search box, a filter rule), use a linear-time engine for them. Never run user-supplied patterns on a backtracking engine without strict limits.

Everyday performance habits

Most regex slowness is not catastrophic, just wasteful. A few habits help:

• Do not use a regex for a plain substring. "ERROR" in line (Python), line.includes("ERROR") (JavaScript) or str_contains() (PHP) is simpler and faster; the PHP manual says so itself in its preg_match() entry. grep -F does the same on the command line.
• Compile once, use many times in loops. Python caches recently used patterns, so this matters less there than readability does, but a compiled pattern with a name documents itself.
• Be specific. [0-9]{4} fails faster than .* followed by something, because the engine has fewer options to try.
• Test with long and failing input, not only with the happy path. A test that feeds a pattern a few thousand characters of near-miss input catches most problems before production; see testing, debugging and readability.