In July 2019 Cloudflare went down for 27 minutes across its whole network. The cause was one regular expression in a firewall rule, deployed globally, that took exponentially longer as the text it examined grew. The pattern was not exotic and the mistake in it is one most people have written. Understanding why it happens takes about ten minutes, and it is the difference between a regex that scales and one that stops a service.
The Engine Tries, Fails, and Tries Again
Most regex engines in wide use, including JavaScript's, Python's, Java's and PCRE, are backtracking engines. They do not analyse your pattern and compute an answer; they walk it, and when a path fails they rewind to the last decision point and take a different branch.
Quantifiers are those decision points. When you write a+ against "aaaa", the engine first grabs all four characters, because + is greedy. If what follows the quantifier then fails to match, it gives one character back and tries again, and again, until it either succeeds or runs out of ways to divide the text.
For a single quantifier that is cheap: at most one attempt per character, so the work grows in a straight line with the length of the text. The trouble starts when one quantifier's choices multiply another's.
Where Linear Becomes Exponential
Take (a+)+$ and run it against a string of a's that ends in something else, so the match must fail.
The inner a+ can consume any number of characters. The outer + can repeat that any number of times. Together they can carve the same run of a's into an enormous number of different groupings: one group of five, a group of four then one, three then two, and so on. Every one of them is a distinct path the engine has to try before it can conclude that nothing works.
The number of those paths roughly doubles for each character you add. Twenty characters are instant. Thirty take about a second. Forty take minutes. Fifty would outlast the process. Nothing about the pattern looks dangerous, and it behaves perfectly on your test string, which is exactly why this reaches production.
The cost is only paid on failure. A string that matches is found quickly, so a pattern like this can run for months against valid input and then hang the first time someone submits something slightly wrong.
The Shapes to Recognise
The pattern to watch for is one quantifier inside another where both can match the same characters. The fix is always to remove that overlap.
| Dangerous | Why | Safer |
|---|---|---|
| (a+)+ | The inner and outer quantifiers can split the same run any number of ways | a+ |
| (\w+\s?)* | \w+ and the optional space overlap on the same input | (?:\w+\s)*\w+ |
| (.*)* | Dot-star inside a star; every division of the text is a separate path | .* |
| (\d+|\w+)+ | The branches overlap, so both can claim the same digits | \w+ |
| .*.*=.* | Two greedy runs competing for the same text before a literal | [^=]*=.* |
The Cloudflare outage, in one line
The rule contained .*.*=.*, two unbounded greedy runs before an equals sign. Against input with no equals sign, the engine has to try every way of dividing the text between those two runs before it can report failure. Cloudflare's own post-mortem identified this as the cause, and the fix included moving to a non-backtracking engine. The lesson is not that regexes are dangerous, it is that two greedy quantifiers competing over the same text is a specific, recognisable bug.
Four Ways to Not Have This Problem
In order of how much they help, and how available they are in the language you are actually using.
Make the parts not overlap
This is the real fix and it always works. If the inner expression cannot match what the outer one can, there is nothing to try a second way. Replacing (\w+\s?)* with (?:\w+\s)*\w+ makes each repetition consume something only it can consume.
Anchor and bound
Anchors cut the number of starting positions the engine has to try, and {1,64} instead of + puts a ceiling on the work. Neither removes the exponential shape, but both cap how far it can run.
Use atomic groups or possessive quantifiers
(?>a+) and a++ tell the engine never to give characters back. They solve the problem outright, and JavaScript has neither. Java, PCRE, Ruby and .NET do. In JavaScript a lookahead with a capture, (?=(a+))\1, emulates it at the cost of readability.
Run it somewhere you can stop it
A backtracking match cannot be interrupted once it starts, so the only way to survive one is for it to be running somewhere you can kill. A worker thread in the browser, a timeout in Go's RE2 or Rust's regex crate, a separate process on a server. This tool takes the first route.
Test a pattern before it ships
Live highlighting, capture groups, and runaway patterns stopped rather than left to hang.
The Engines That Cannot Hang
Not every engine backtracks. RE2, written at Google and used in Go's standard library, and the regex crate in Rust both compile the pattern into a state machine and match in time proportional to the length of the text, whatever the pattern looks like. A catastrophic pattern is simply not expressible.
The trade is features. Backreferences and lookaround need the engine to remember or re-examine text, which a plain state machine cannot do, so RE2 does not support them. That sounds like a serious loss and rarely is: most patterns in real code use neither.
The practical rule is about who wrote the pattern. If it comes from your own source, a backtracking engine is fine, because you can read it and fix it. If it comes from a user, a config file, or a rule set someone edits under pressure at three in the morning, use an engine where the worst case is bounded. That was the reasoning in Cloudflare's own remediation.
The Other Way a Regex Loops Forever
Catastrophic backtracking is slow. This one never finishes at all, and it is far more common in day-to-day code.
A pattern where everything is optional, such as a* or \d?, can match the empty string. Used with the global flag in a manual loop over exec, it matches nothing at the current position, lastIndex does not advance, and the loop runs forever at the same index.
Every correct implementation handles it the same way: after a zero-length match, move lastIndex on by one by hand. Built-in methods like matchAll and replace already do this internally, which is why the bug only shows up in hand-written loops. This tool does the same, and marks empty matches in the list rather than hiding them, because a pattern producing them is usually a pattern with a mistake in it.
Frequently Asked Questions
Related Tools
Keep Reading
JSON Errors Explained: Trailing Commas, NaN and Other Rejections
Why valid-looking JSON fails to parse, how to read a parser's error position, and the number precision bug that silently corrupts large IDs.
How Diff Works: The Algorithm That Decides What Changed
Myers walks a grid one edit at a time, and Git has run it since 1986. Why the shortest diff is not always the clearest, and what makes one look wrong.
HTML Entities: Five Characters, and Why Escaping Depends on Context
Only five characters truly need escaping, and doing it is not enough on its own. Where each context needs its own rule, and how double encoding announces itself.
URL Encoding: encodeURI vs encodeURIComponent, and the Plus Sign
The two JavaScript functions are not interchangeable, and picking the wrong one is the most common URL bug there is. Plus where %2520 comes from.