The Regex That Works Fine Until One Input Hangs Your Server

On 2 July 2019, Cloudflare went down for 27 minutes and took a large slice of the web with it. The cause was one line in a new firewall rule: a regular expression containing .* followed by another .*. It matched correctly. It also drove CPU to 100% across their global network the moment it met an input that did not match.

That failure mode is not exotic and it is not limited to firewalls. Any pattern with a certain shape will run in exponential time on the right input, and the right input is usually a string that almost matches.

Key takeaways#

• Backtracking engines try every possible way to match before giving up. Some patterns have exponentially many ways.
• The trigger is nested quantifiers — a repeated group that itself repeats, like (a+)+.
• Failure is what costs you. A matching input returns fast; a nearly matching one explodes.
• A 30-character input can take longer than the age of the universe on a bad pattern.
• The fix is almost never a faster machine. It is a pattern that cannot backtrack.

Why does a regular expression ever run slowly?#

Because most engines are backtracking engines. That includes PCRE, Python's re, Java, JavaScript and .NET. When a pattern can match in more than one way, the engine tries one, and if the overall match fails later, it returns and tries the next.

For most patterns the number of alternatives is small. For some it doubles with every added character.

Take ^(a+)+$ against a string of 30 a characters followed by a !. The inner a+ can consume the run in one chunk, or two, or three, and the outer + can group those chunks in every possible arrangement. Every one of those partitions has to be tried and rejected before the engine concludes there is no match, because the trailing ! fails at the very end.

That is 2³⁰ paths, over a billion, for a 31-character input. Add one more a and it doubles.

The engine is not doing anything wrong. It is exhaustively proving that no match exists, and the pattern gave it exponentially many possibilities to rule out. A regular expression that can be satisfied in only one way has nothing to prove and returns immediately, which is why the same input runs instantly against a well-shaped pattern.

What patterns are dangerous?#

Three shapes cause nearly all of it:

The Cloudflare rule was the third shape. So is ^\s*(.*)\s*$, a pattern people write constantly to trim whitespace, where \s* and .* overlap because . matches spaces too.

The common thread is ambiguity: more than one way for the pattern to consume the same characters. An unambiguous pattern has one path, so there is nothing to backtrack through.

Worth noting what is not on the list. Long patterns are not inherently slow, and neither are large inputs against a well-shaped pattern. A 200-character regex with no ambiguity runs in time proportional to the input, every time. Length is not the risk factor; shape is.

Why does it only blow up sometimes?#

Because backtracking only happens on failure. If the input matches, the engine finds a path and stops — often the first one it tries. Your tests pass, staging is fine, and the pattern looks fast.

The pathological case is input that satisfies most of the pattern and then fails at the end. That is exactly what a validation regex meets in production: malformed email addresses, truncated tokens, a log line with an unexpected suffix. The worse your input, the harder the engine works.

When that input can be chosen by someone else, the bug has a name: ReDoS, a denial of service delivered as one well-crafted string in a form field.

How do I fix a pattern that backtracks?#

Remove the ambiguity rather than trying to make the engine faster.

Make quantifiers disjoint. ^\s*(.*?)\s*$ is still ambiguous. Anchoring what each part may consume is not — use ^[^\s](.*)[^\s]$ shapes, or trim in code and skip the regex.

Drop the nesting. (a+)+ is exactly equivalent to a+. Nested quantifiers are frequently accidental, left behind after a group was added for capture rather than repetition.

Use a possessive quantifier or atomic group where your engine supports it. (?>a+) in PCRE, Java and .NET commits to the match and refuses to give characters back, which removes the backtracking entirely. JavaScript has no atomic groups, though a lookahead with a backreference emulates one.

Bound the input. A length check before the match caps the damage even on a pattern you cannot easily rewrite. It treats the symptom rather than the cause, but a 200-character ceiling on a form field turns an exponential blowup into a bounded one, and it costs a single line.

Stop using regex for the job. Parsing a URL, an email address, HTML or JSON with a regular expression is where the worst patterns come from. Use URL, a validator library, DOMParser, JSON.parse.

There is also a structural option if this class of bug matters to you: some engines do not backtrack at all. RE2, used by Go's regexp package and available as a library elsewhere, guarantees linear time by refusing to support backreferences and lookaround. That is a real feature loss, and for untrusted patterns it is usually the right trade.

Testing for it#

A pattern is worth checking the moment it takes user input. The test takes seconds:

1. Build a string of 20–40 repeated characters that the pattern's quantified part accepts.
2. Append one character that makes the whole thing fail.
3. Time the match, then add five more repeats and time it again.

Linear growth is fine. Doubling means exponential behaviour, and it will not stay theoretical.

const evil = 'a'.repeat(30) + '!';
console.time('match');
/^(a+)+$/.test(evil);
console.timeEnd('match');

You can build and step through a pattern against real input in the regex tester, which shows what each group actually captures — usually enough to reveal that two parts of the pattern are fighting over the same characters.

The short version#

Catastrophic backtracking is a property of pattern shape, not pattern length or input size. Nested quantifiers and overlapping .* are the tells, failure is when it bites, and it reaches production precisely because matching inputs are fast and tests use matching inputs. Look for ambiguity, and if a pattern is doing a parser's job, replace it with a parser.

Sources: Details of the Cloudflare outage on July 2, 2019