ReDoS and catastrophic backtracking: when a regex hangs your server

Most regular expressions run in time proportional to the length of the input. A few do not. Feed the wrong pattern a 30 character string and it can run for longer than the universe has existed, pinning a CPU core until the process is killed. That failure mode is called catastrophic backtracking, and when an attacker can reach it through user input it becomes a denial of service vulnerability: ReDoS.

This is not a theoretical concern. Stack Overflow went down for 34 minutes in July 2016 because a regex that trimmed whitespace from post text met a post containing about 20,000 consecutive space characters. Cloudflare took a large part of its network offline in July 2019 after deploying a firewall rule whose regex consumed unbounded CPU. In both cases the pattern looked entirely ordinary.

Why backtracking explodes

Most regex engines, including the ones in JavaScript, Python, Java, Ruby, PHP and .NET, are backtracking engines. When a pattern can match the input in more than one way, the engine tries one path, and if that path eventually fails it returns and tries the next. For most patterns there are only a handful of paths to try.

The problem starts when one quantifier is nested inside another, so the same characters can be divided between the two in many different ways.

Take (a+)+$ against the string aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!.

The inner a+ can match one a, or two, or all thirty. The outer + then repeats that choice. The number of distinct ways to split thirty identical characters into ordered groups is 2^29, roughly half a billion. The trailing ! guarantees that every one of those splits ultimately fails the $ anchor, so the engine is forced to try all of them before it can report "no match".

Add one more character to the input and the work doubles. This is the signature of catastrophic backtracking: the input grows linearly, the time grows exponentially, and the failing case is always a string that almost matches.

The patterns to look for

Three shapes cause nearly all real cases.

Nested quantifiers. A quantifier applied to a group that already contains a quantifier: (a+)+, (a*)*, (\d+)*, ([a-z]+)+. The inner and outer quantifiers compete for the same characters.

Alternation where the branches overlap. (a|a)*, or more realistically (\w|\d)+. Because \w already includes digits, every digit can be matched by either branch, and the engine must try both.

A quantified group followed by something that can fail. ^(\w+\s?)*$ is fine on matching input and pathological on input that ends with a character the pattern cannot accept. The failure at the end is what forces the exhaustive search.

The common thread is ambiguity. If there is exactly one way for the pattern to match a given string, backtracking has nothing to explore. Danger comes from patterns where the same input can be carved up many ways.

Recognising it in ordinary code

The dangerous patterns rarely look dangerous. These are all realistic and all vulnerable:

Email validation is the most common real world offender, because people write increasingly elaborate patterns to handle the format's genuine complexity, and elaboration means alternation and nesting. If you are validating email addresses with a regex, keep it deliberately loose and check deliverability separately.

Fixing it

Remove the ambiguity first. This is the real fix and it usually simplifies the pattern. ^(\s*\w+)*$ becomes ^\s*\w+(\s+\w+)*\s*$, where each character has exactly one possible role. Ask of every quantified group: can these characters be divided between the quantifiers in more than one way? If yes, restructure.

Make character classes disjoint. Replace (\w|\d)+ with \w+. Replace [\s\S]* inside a group with a class that cannot also be matched by the surrounding pattern.

Anchor the pattern. An unanchored search restarts at every position in the string, multiplying the cost of an already slow pattern by the input length. If you mean to match the whole string, say so with ^ and $.

Bound the input. Reject anything longer than a sensible limit before the regex sees it. A 200 character cap on an email field removes the exponent's room to grow. This is the cheapest mitigation and it belongs in the code regardless of what the pattern looks like.

Use possessive quantifiers or atomic groups where the language has them. In Java, PHP, Ruby and PCRE, (?>a+) or a++ tells the engine never to give back what it matched, which prunes the search entirely. JavaScript and Python support neither, which is why the restructuring advice above matters more there.

The JavaScript problem specifically

JavaScript gives you no escape hatch. There is no regex timeout, no atomic groups, no possessive quantifiers, and because the runtime is single threaded, one bad match blocks the entire event loop. A Node process caught in catastrophic backtracking stops serving every other request, not just the one that triggered it.

Practical options:

• Validate length before matching, always.
• Move untrusted matching into a worker thread that you can terminate on a timer.
• Use a linear time engine such as RE2 through a binding, which cannot backtrack because it does not support the features that require it.
• Prefer a real parser for structured input. URLs, dates and JSON all have parsers in the standard library that are faster and safer than any regex you will write.

V8 ships an experimental non-backtracking engine, but it is not enabled by default and it only supports patterns without backreferences or lookaround, so do not rely on it.

Test before you ship

The reliable test is not a matching string, it is a nearly matching one. Take the longest input your pattern could plausibly receive, make it match right up to the final character, then break it at the end.

For ^(\d+,?)+$, that means a long run of digits and commas ending in a letter:

12345678901234567890123456789012345678901234567890x

Paste your pattern and that string into the regex tester and add characters to the run. A safe pattern stays instant. A vulnerable one becomes visibly slow within a few additions and then stops responding altogether. That doubling is the whole diagnostic: if each character you add noticeably increases the delay, the pattern is exponential and needs restructuring before it goes anywhere near user input.

If you are building the pattern from scratch, the regex cheat sheet covers the syntax, and the guide to greedy versus lazy quantifiers explains the matching order that backtracking depends on.