Regular Expressions and Catastrophic Backtracking

A regular expression that matches instantly on every input you tried can take exponential time on a string a few characters longer. Not slow — exponentially slow, to the point where a 30-character input takes longer than the age of the universe.

For a separate people-operations application of the same measurement discipline, see mouse jiggler detection software.

This is a denial-of-service vector with its own name, and the shape that causes it is recognisable once you know it.

Two kinds of engine

The distinction that explains everything.

Automaton-based engines — the classic theoretical approach, used in RE2, Go's standard library, Rust's regex crate — compile the pattern into a state machine and run the input through once. Time is linear in the input length, guaranteed.

The cost is that they cannot support backreferences or lookaround, because those constructs are not regular in the formal sense.

Backtracking engines — PCRE, and the standard libraries of Java, Python, JavaScript, .NET, Ruby — try one possibility, and on failure back up and try another. This supports backreferences and lookaround, and it can require exponential time.

Most languages you use ship a backtracking engine, which is why this matters in practice rather than only in theory.

Why it explodes

The dangerous shape is nested quantifiers over overlapping alternatives.

(a+)+$

Against aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!, the match must fail — there is no ! handling and the anchor cannot be satisfied.

Before concluding that, the engine tries every way of partitioning those a characters into groups. One group of thirty, twenty-nine plus one, twenty-eight plus two, and so on through every combination. The number of partitions grows exponentially with the length.

Each individual attempt is fast. There are 2^n of them.

The same shape appears in patterns that look entirely reasonable:

^(\w+\s?)*$          -- validating a sentence
^([a-zA-Z0-9]+\.)*   -- validating a domain
(\s*,\s*)*           -- splitting a list

All three are exponential on input that nearly matches. That is the important detail: the failure requires a string that almost matches but does not, which is precisely what an attacker supplies and what your test fixtures do not.

Recognising the shape

A quantifier inside a group that is itself quantified. (x+)+, (x*)*, (x+)*.

Alternation where the branches can match the same text, inside a quantifier. (a|a)+, and more subtly (\w|\d)+ — a digit matches both branches, so the engine tries both ways for every character.

Adjacent quantifiers that can match the same characters. \s*\s*, or .*.*.

Anything with a trailing anchor after a complex quantified group, because the anchor is what forces the exhaustive failure search.

The heuristic: if two parts of your pattern can both consume the same character, and one of them is inside a repetition, look carefully.

Fixing it

Make the alternatives disjoint. If exactly one branch can match any given character, there is nothing to backtrack through.

(\w|\d)+ becomes \w+, since \w already includes digits.

Remove nested quantification. (a+)+ is a+. This is frequently the whole fix, because the outer quantifier adds nothing but ambiguity.

Use possessive quantifiers or atomic groups where the engine supports them. (?>a+)+ or a++ tell the engine not to backtrack into that group at all. Java and PCRE support these; JavaScript does not.

Anchor early. A pattern that can fail fast at the start avoids the expensive path entirely.

Split the problem. Instead of one pattern validating a whole structure, split on a delimiter and validate the parts. Usually faster, always more readable, and far easier to reason about.

Do not validate with regex what a parser should parse. Email addresses, URLs and dates all have libraries. A regular expression that attempts full correctness on any of them is both wrong and slow.

The defences that work regardless

Because you will not catch every case by inspection.

Use a linear-time engine where you can. RE2 is available as a library for most languages. For any pattern applied to input you do not control, this removes the entire class of problem — at the cost of backreferences and lookaround, which such patterns rarely need.

Never build a pattern from user input. This is the regex equivalent of SQL injection, and it is worse, because a user-supplied pattern can be deliberately catastrophic.

Set a timeout on matching where the platform supports it — .NET and some libraries allow this. Where it does not, run untrusted matching in a context you can interrupt.

Bound the input length before matching. If the field is a name, reject at 200 characters before the pattern ever runs. This is the cheapest mitigation available and it converts exponential-on-unbounded-input into exponential-on-something-small.

Scan your patterns. Static analysis tools that detect vulnerable regular expressions exist for most ecosystems and they find real cases in real codebases, including inside dependencies.

Testing for it

Test with near-miss input. Take a string that matches, extend the repeated portion, and break the end. "a" * 30 + "!" against a pattern expecting as. If the match does not return promptly, you have found one.

Increase the length and watch the time. Linear growth is fine. Doubling the time for each additional character is the signature.

Include this in tests for any pattern applied to external input. One test per pattern, and it takes a line.

Where these show up

Worth knowing where to look first.

Input validation — the most common location, and the one directly reachable by an attacker.

Log parsing, where the input comes from systems you may not control.

Dependencies. A vulnerable pattern inside a library is exploitable through whatever calls it, and this has been the cause of real widespread advisories.

Anything applied to a header, a user agent, or a URL — all attacker-controlled, all commonly regex-validated.

The summary

Backtracking engines can take exponential time, and most standard libraries ship one.

The dangerous shape is a quantifier inside a quantified group, or alternatives that overlap — and it triggers on input that nearly matches.

Bound the input length, avoid patterns built from user input, and prefer a linear-time engine for anything touching data you do not control.

Test with near-miss strings. One line per pattern, and it finds the problem before someone else does.