Catastrophic Backtracking: The Regex That Took Down Cloudflare for 27 Minutes
In July 2019, Cloudflare, the company that keeps a huge share of the internet online, went down for 27 minutes. The cause was a single regular expression in their web application firewall, something like .*.*=.*. One line of regex. Twenty-seven minutes of 502 errors worldwide. No attacker needed: ordinary traffic was enough.
This is catastrophic backtracking, and it is the most expensive class of regex bug there is. Here is how it works, measured in real step counts, and how to make sure your patterns never do it.
Catastrophic backtracking, explained with real numbers
Cloudflare's WAF was written in Lua using PCRE, which, in the postmortem's words, "uses backtracking for matching and has no mechanism to protect against a runaway expression." Watch what a backtracking engine does with .*.*=.*. The first .* greedily takes the whole input. The second gets nothing. There is no = left to match, so the engine gives back one character from the first .* and tries again, and again, and for each split it also tries every split of the second .*. When there is an = in the input, it eventually finds it. When there is not, and most strings a WAF inspects do not contain the thing it is looking for, the engine has to try every combination before it can say no.
The postmortem's appendix counts the steps, and they are worth staring at: for x=x the engine takes 23 steps. For 20 x's with no = at all, 4,067 steps. Add a trailing ; to the pattern and it gets worse: 5,353 steps for those same 20 x's. The count grows far faster than the input, so a long request is disproportionately slower. Now run that on every HTTP request, on every server, on every core, and each core spends its time failing to match. When an attacker triggers this on purpose it is called ReDoS, regular expression denial of service. Here nobody needed to.
Why it explodes
The trigger is always the same shape: two parts of the pattern can match the same text, so the engine must try every way of splitting the input between them. The classic forms are nested quantifiers, (a+)+ or (\w+\s?)+, and overlapping alternatives like (a|a?b)*. The worst case is an input that almost matches but fails at the very end, because the engine does all the work before it is allowed to give up.
The signature symptom: execution time doubles with each added character. A Python demo makes it concrete. The pattern ^(\w+\s?)+$ takes 0.045 seconds on 20 a's followed by !, and 0.718 seconds on 24 a's followed by !. Each 2 extra characters cost roughly 4x. The restructured pattern ^\w+(?:\s\w+)*$ handles 10,000 a's followed by ! in 0.0002 seconds. Same job, different universe.
The fixes, in order of preference
1. Restructure to remove the nesting. This is the real fix, and it usually means deleting characters, not adding them. (a+)+ becomes a+. (\w+\s?)+ becomes \w+(?:\s\w+)*, moving the separator inside a non-capturing group so exactly one partition of the input is possible. .*<tag> becomes [^<]*<tag>.
2. Use negated character classes. Whenever you know what a field cannot contain, encode that instead of reaching for .*. "Up to the next quote" is [^"]*, and it cannot backtrack because there is nothing to reconsider.
3. Atomic groups and possessive quantifiers, where your engine supports them. (?>...) tells the engine to throw away backtracking points once the group matches; *+ and ++ are the shorthand. PCRE, Java, .NET, and Python 3.11+ support them. JavaScript does not, so in JS you restructure instead.
4. Timeouts as a safety net. Cap how long a match may run, especially on user-controlled input. Note that Python's built-in re has no timeout support; you need the third-party regex module or a watchdog. And for guarantees rather than seatbelts, engines like RE2, Go's regexp, and Rust's regex crate run in linear time by construction.
5. Test the failure, not the success. This is the habit that catches it. Matching fast means nothing. Test every pattern against long inputs that do not match, especially near-misses, and watch the clock. If time doubles per added character, the pattern is vulnerable no matter how clever it looks.
My opinion, and I feel strongly about this one: the scary part of the Cloudflare story is not that it happened to Cloudflare. It is that this bug class hides in form validation and API input checks everywhere, written by people who tested the happy path and moved on. The fix is almost always simplification. When your regex is slow, the answer is usually fewer characters, not more.
Test your pattern like an attacker would. Paste it into the regex builder on the homepage and hammer the live tester with long near-miss strings. The side that fails slowly is the side that pages you at 3 AM.