Regex Performance and Catastrophic Backtracking

Most regex patterns run in microseconds. A few run in seconds. A few run forever. The difference is rarely the data, the language, or the engine — it is the structure of the pattern, specifically whether it admits exponential backtracking on adversarial input. Detecting and avoiding those patterns is the difference between a regex you can use on user input and a regex that hands an attacker a 60-second denial of service button.

How backtracking works, in one sentence

A regex engine that supports backreferences (which is every mainstream engine except RE2) tries the longest possible match, fails, gives up one character, tries again, fails, gives up another character, tries again, ad infinitum. With a well-shaped pattern, this backtracking is bounded; the worst-case time is O(n × m) where n is input length and m is pattern length. With a badly-shaped pattern, the worst case is O(2^n) — exponential. A 10-character pattern on 60 characters of input can take 60 seconds; a 20-character pattern on 100 characters of input can take longer than the age of the universe.

The signature: nested quantifiers around shared characters

The classic catastrophic-backtracking pattern is (a+)+, (a*)*, (a|a)+, or anything where a quantified group can match the same text in multiple ways. The text engine has to try every possible way to split the text between the two quantifiers, and the count of splits grows exponentially with input length.

Concrete examples that have shipped in production code (each of these will freeze a Node.js process on a 50-character input):

(a+)+$ against aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa! — the trailing character that prevents the match makes the engine try every split of the a-run between the two quantifiers.
^(\d+)+$ against 12345678901234567890123456789012345678901234567890! — same shape, same outcome, more digits.
^([a-z]+)+$ against any string of letters that fails to fully match — exponential in length.
(.*a){20} against a string ending in a non-a character — exponential in input length.
^(\w+\s?)*$ against a long whitespace-only string — exponential.

Why timeouts are not the cure

The instinctive fix for a runaway regex is to wrap it in a timeout: if the match takes longer than N seconds, kill it. This is necessary as a defence-in-depth measure and as a backstop, but it is not a cure. The reasons:

Timeouts reject the result after the work has been done. The CPU has already been burned; the latency has already been added to the caller's response time. A 60-second match consumes 60 seconds of CPU before the timeout fires, and during that 60 seconds the matcher may have allocated gigabytes of memory for the backtracking stack.
Timeouts are hard to set correctly. Too short and legitimate long matches on huge inputs (think a 100 MB log line) get rejected. Too long and a single malicious request can stall a worker thread.
Most regex APIs in most languages do not natively support cancellation. Workaround libraries that add a timeout (often using setTimeout + setImmediate tricks) leak the worker thread until the original call returns or the OS reaps the process.

So: keep the timeout, but treat it as the last line of defence. The real cure is rewriting the pattern to be immune to exponential backtracking.

Five patterns that are immune

Disjoint character classes for alternation. ([a-z]+|[0-9]+)+ is also vulnerable because the two branches overlap on the empty match. ([a-z]+|[A-Z]+|[0-9]+)+ is not — the branches are disjoint, so the engine has no ambiguity to backtrack into. Rewrite alternations where the branches share characters into either disjoint classes or a single character class with a quantifier.
Atomic groups where supported. (?>...) in PCRE / Java tells the engine "if this match succeeds, no later backtracking can reopen it". This eliminates the ambiguity that produces exponential cases. ECMAScript and Python do not support atomic groups, but the next four techniques give you the same effect.
Possessive quantifiers where supported. a++, a+? with possessive semantics, [a-z]{n,m}+. Same effect as atomic groups, but at the quantifier level. Supported in PCRE and Java; not in ECMAScript or Python.
Prevent the engine from matching twice. The signature of every catastrophic pattern is "the same text could be matched twice in different ways". When you see that, rewrite to prevent the second match. The general recipe: replace a*a* with a*; replace a*a with a+; replace (a*)* with a*; replace nested quantifiers around shared atoms with a single quantifier.
Use an engine that does not backtrack. RE2 (Go), RE2-derived libraries in C++ and Rust, and any language's hyperscan-family bindings. These engines guarantee linear time in input length. The cost: no backreferences, no lookaround (in the simple cases), and a slightly different feature set. The payoff: regex can run on user input without a timeout.

Detecting before you ship

The static-analysis tools for regex catastrophic backtracking have matured. Run any of these in CI for every regex pattern that touches user input:

regexploit — Python; analyses your patterns against a corpus of evil inputs.
rxxr — JavaScript; static analyser for ECMAScript regex.
The repl — open the Regex Tester on this site, paste your pattern and the smallest failing input you can construct, watch the engine spin. A 1 KB input that takes more than 100 ms is suspect.

Manual detection rules: any time you have a quantifier that contains another quantifier, or an alternation that can produce the empty match, or a backreference to a group whose content overlaps with another group, write the pattern in three different ways and benchmark each one on a 10 KB string of the most adversarial input you can produce. The slowest of the three rewrites is the right place to fix.

Closing

Catastrophic backtracking is the most common regex-related production outage in 2026, and the only durable cure is writing patterns that the engine cannot match in ambiguous ways. The five techniques above are short, they apply to every mainstream regex flavour, and they turn regex from a security liability into a useful tool. Defence: the Regex Tester for sanity-checking, the regex basics guide for background on the features in play.