How to Avoid Catastrophic Backtracking in Regex Step by Step

A regex that handles a million lines in a second can hang for an hour on one line of 30 characters. The cause is the engine's search strategy, and it is a real security problem when the input comes from users: the denial-of-service has its own name, ReDoS. Understanding why it happens makes the risky shapes recognisable. It pairs with greedy and lazy quantifiers, and the timings below are from Python 3.13 on a laptop, so treat them as indicative.

See it happen

import re, time

pattern = re.compile(r"^(a+)+$")
for n in (20, 24, 28):
    text = "a" * n + "b"
    start = time.perf_counter()
    pattern.match(text)
    print(n, f"{time.perf_counter() - start:.3f}s")

20 0.060s
24 0.980s
28 15.700s

Every extra character multiplies the time by about 2. The string almost matches (all as) but ends in b, so the engine has to fail, and before it does it tries every way of splitting the a run between the inner and the outer +. With 28 characters that is hundreds of millions of splits. Real-world versions hide in email, URL and CSV validators.

The risky shapes

(a+)+          nested quantifiers on the same characters
(a|a)+         alternatives that overlap
(a|aa)+        alternatives where one is a prefix of another
(\w+\s?)+$     optional separator makes the split ambiguous
(.*)*, (.+)+   anything wrapped in a repeating group

The common feature is ambiguity: the same text can be matched in several ways, and the engine tries them all when the overall match fails. A search for "does this pattern allow two different parses of the same substring?" finds most of them. Static tools such as safe-regex, rxxr2 and the fuzzers in some linters flag the worst cases.

Fixes

import re

bad = re.compile(r"^(\w+\s?)+$")
good = re.compile(r"^\w+(?:\s\w+)*$")       # every character has one parse

atomic = re.compile(r"^(?>a+)$")           # Python 3.11 and later: atomic group
possessive = re.compile(r"^a++$")           # possessive quantifier, Python 3.11 and later

The rewrite makes the separator mandatory between words, removing the choice that created ambiguity. Atomic groups and possessive quantifiers forbid backtracking into what has matched; they were added to Python's re in 3.11 and exist in PCRE, Java and .NET but not in JavaScript. Where possible, replace .* with a narrow class such as [^"]*, which cannot overlap with what follows.

Defences in depth

MAX = 200
if len(value) > MAX:
    raise ValueError("too long")

Cap input length before matching, because the cost grows with it. Some engines allow a time limit (.NET has a match timeout, PHP's pcre.backtrack_limit returns an error as in PHP preg functions). Run user-supplied patterns only in a linear-time engine such as RE2, used by Go's regexp, which cannot blow up by design but gives up backreferences and lookaround. In shell work, GNU grep and awk use DFA-based matching for ordinary patterns, which is why grep -E rarely suffers the problem that grep -P can.

Why the engine behaves this way

Most mainstream regex engines, including those in Python, Java, JavaScript, Perl, PCRE and .NET, are backtracking matchers. They walk the pattern left to right, and when a choice fails they return to the most recent decision point and try the next option. This design is popular because it supports features that a pure automaton cannot, such as backreferences and lookaround, and because it is fast on ordinary patterns, where the first choice usually succeeds. The price is that the work done on a failing input is not bounded by the length of the input. It is bounded by the number of distinct paths through the pattern, and nested quantifiers can make that number exponential.

A matching input is cheap, because the engine finds one successful path and stops. A failing input is expensive, because the engine has to exhaust every path before it can say no. That is why a vulnerable pattern can pass every test with valid data and still hang in production on a string that is almost valid, such as a long run of digits followed by a stray letter. Test data for a validator should therefore include long strings that nearly match, not only strings that match and strings that are obviously wrong.

Finding a vulnerable pattern in review

A reviewer can look for three conditions together. There is a quantified group, there is another quantifier inside it, and the inner and outer parts can match the same characters. Patterns such as (\d+)* and (\w+\s*)+ satisfy all three. A second check is an alternation inside a repeated group where the branches overlap, as in (a|ab)*c, where the text ab can be consumed in two different ways. If a human can find two ways to split a string, the engine will try both.

When in doubt, measure instead of reasoning. Feed the pattern strings of 20, 25, 30 and 35 characters that almost match and watch the time. Linear growth is safe. A doubling for every added character is the signature of the exponential case, and it will not be fixed by a faster machine, since adding ten characters multiplies the cost by a thousand.

Fixing it without changing what it matches

The safest rewrite removes the ambiguity rather than limiting the damage. If the pattern means "one or more words separated by single spaces", write exactly that: a word, then zero or more groups of a space and a word. Each character now belongs to one place in the pattern, so there is one path and nothing to backtrack into. Replacing .* with a negated class that excludes the delimiter that follows it has the same effect: "[^"]*" cannot overlap with the closing quote, while ".*" can.

Atomic groups and possessive quantifiers are the second tool. They tell the engine that once a part has matched, it may not give characters back. This is correct only when giving them back could never help the overall match, and that is something to confirm with tests, because a possessive quantifier that is applied to the wrong part turns a working pattern into one that never matches.

The last option is to change the engine. Linear-time engines such as RE2 and Rust's regex crate convert the pattern to an automaton, so a match costs time proportional to the input regardless of the pattern. They reject backreferences, which is the honest trade: patterns that need them cannot be made safe by any engine, and are better replaced with a small parser. For input that crosses a trust boundary, choosing the linear engine up front is cheaper than auditing every pattern later.

Where this does not apply

Most patterns are safe, and a pattern run only on your own trusted data with a small input is not a security issue, though it may still be slow. Do not optimise a regex that does not show up in a profile. A regex used for validation of anything that crosses a trust boundary deserves a test with long near-matches, in the style of regex testing. See the OWASP page on ReDoS and the regular expression matching article by Russ Cox.