Regex Performance and Catastrophic Backtracking

In July 2019, Cloudflare's edge network stopped serving HTTP traffic for 27 minutes. The root cause was a single regular expression in the WAF engine whose performance, on a crafted input, blew up from linear to exponential. A global outage from one regex is memorable, but it is not rare — similar incidents have hit Stack Overflow, GitHub, and dozens of services that use regex to validate or extract user input. The phenomenon has a name: catastrophic backtracking.

How a backtracking engine works

Most regex engines in wide use (PCRE, Java, JavaScript, Python, .NET, Ruby) are NFA-based with backtracking. When the engine encounters a branch — a|b, a quantifier like a*, or a group — it records the state and tries one alternative. If that alternative fails further down the pattern, the engine backs up and tries another.

For most patterns on most inputs, this is fine. The engine spends linear time in the length of the input. But certain combinations of nested quantifiers and overlapping alternatives can produce exponentially many backtracking paths on a carefully-chosen input.

The classic example

The canonical bad pattern is (a+)+b matched against aaaa…aa (no b at the end). To the engine, there are many ways to split a string of 30 as into groups captured by the outer +: one group of 30, or two groups (say, 5 and 25), or three, all the way down to 30 groups of one. Each split is a separate backtracking path. The engine tries all of them before giving up, and the count is exponential in the number of as.

In practice, 30 as already takes seconds. 35as takes tens of seconds. 40 takes minutes. On a web server this is not a performance bug; it is a denial-of-service vulnerability, and it has a name: ReDoS.

Patterns in the wild

The pathological shape is: two or more nested unbounded quantifiers that can match overlapping substrings. Real-world examples that have caused outages:

^(a+)+$ — the textbook version.
^(\s*)*$ — trimming whitespace. Looks innocent.
^(\w+\s?)*$ — matching a list of words separated by optional whitespace.
^(.*?)*x$ — non-greedy nested matching.
Email validators assembled from blog-post-grade regexes. Several popular ones are quadratic or worse on crafted input.

Spotting it

A few heuristics flag suspicious patterns without running them:

Two or more quantifiers stacked: (…+)+, (…*)*, (…+)*. Each outer quantifier multiplies the number of ways to partition a match; if the inner and outer can match the same characters, that is the hazard.
Alternations inside a quantifier where both branches can match an empty or overlapping string: (a|a?)+.
Non-atomic groups around variable-length patterns the engine can greedily split multiple ways.

When in doubt, test the pattern against a long input that nearly-but-doesn't match. If the Regex Tester on ToolPad visibly hangs for a second or two, the pattern is almost certainly quadratic or worse.

Fixing it

Most catastrophic-backtracking patterns can be rewritten so there is only one way to partition a match:

Collapse nested quantifiers. (a+)+ matches the same language as a+. The outer quantifier is redundant. Removing it collapses the exponential behavior.
Use possessive quantifiers or atomic groups where your engine supports them (Java, PCRE, Ruby, .NET). (?>a+)+b tells the engine not to backtrack into the inner group. If b is not there, it fails immediately instead of re-splitting.
Anchor tightly. A pattern without ^ or \A lets the engine try starting positions linearly; add anchors where the match is required to start at the beginning.
Use a non-backtracking engine for untrusted input. Go's regexp, Rust's regex, and re2 guarantee linear-time matching by construction, at the cost of features like backreferences. If the pattern is running on user-supplied input on a production server, this is often the correct engine.

Defensive engineering

Even with careful patterns, a single sloppy regex can leak in through a dependency. Mitigations that do not depend on the pattern being perfect:

Enforce a timeout on regex matching. .NET, Java, and Python (via regex module) support this natively. Node.js users can run regex in a worker thread with a watchdog.
Cap the input length before matching. A 64 KB cap turns a latent exponential blowup into a single slow request rather than a server freeze.
Use a static analyzer (such as Semgrep's regex rules or dedicated tools like vuln-regex-detector) in CI to flag suspect patterns.

Test your regex on ToolPad

The Regex Tester highlights matches in real time against a sample input. Paste a long "almost matching" input to see whether the pattern completes instantly or visibly stalls. A stall in the browser is a warning sign that the same pattern on a production server could cost you far more than a spinner.