← Back to blog

Catastrophic Backtracking: How One Regex Broke Cloudflare

Published October 25, 2026 · 10 min read

On July 2, 2019, a Cloudflare engineer shipped a small change to a firewall rule. Within minutes, every CPU core serving HTTP traffic on Cloudflare's network was pinned near 100%, and visitors to Cloudflare-backed sites got 502 errors for 27 minutes. The cause was one regular expression doing catastrophic backtracking.

The scary part is that the regex was ordinary. It passed review and it passed the test suite. You have patterns like it in your codebase right now, and so do your dependencies.

Here's what you'll get: what happened at Cloudflare, timings I measured myself so you can see the blowup, how to spot a risky pattern, how to test for one, and the three fixes that work. My take up front: rewriting a regex helps, but the fix that lets you stop worrying is an engine that can't backtrack.

What happened at Cloudflare on July 2, 2019

John Graham-Cumming, who had written the original WAF code, published a detailed post-mortem ten days later. The short version: at 13:42 UTC, an automated process deployed an updated XSS detection rule to Cloudflare's web application firewall (WAF). WAF rules went out through a key-value store that pushes changes worldwide in seconds, so there was no gradual rollout. Graham-Cumming was told they had "lost 80% of our traffic." The team killed the WAF globally at 14:07, and traffic was back to normal by 14:09.

The rule contained this, which you don't need to read closely:

(?:(?:\"|'|\]|\}|\\|\d|(?:nan|infinity|true|false|null|undefined|symbol|math)|\`|\-|\+)+[)]*;?((?:\s|-|~|!|{}|\|\||\+)*.*(?:.*=.*)))

The post-mortem narrows the trouble to one fragment, .*(?:.*=.*), which behaves like .*.*=.*. Two "match anything" pieces in a row give the engine many ways to split the same text, and when a match fails it tries them all.

What I like about this write-up is that it refuses to blame one engineer. It lists 11 things that went wrong. Three are about the regex itself: a pattern that could backtrack enormously, a CPU-limit safeguard that had been removed by mistake during a refactor weeks earlier, and an engine (PCRE, called from Lua) with no complexity guarantee. A fourth is about testing: the suite checked which requests got blocked, but never measured CPU. Cloudflare's fix list included manually reviewing all 3,868 WAF rules, adding performance profiling to tests, and switching to RE2 or the Rust regex engine, "which both have run-time guarantees."

Thirty characters, five seconds: catastrophic backtracking you can measure

The textbook evil regex is ^(a+)+$. It reads as "one or more a's, one or more times, then the end." It matches the same strings as ^a+$. The difference shows up when the input almost matches.

I ran both against a string of a's followed by one !, on Node 20.19.2 (V8) on an 8-core cloud VM. Times are for a single test() call:

Every two extra characters multiply the time by about four. At 30 characters, one call blocks Node's main thread for over five seconds. On the same curve, 40 characters would take about an hour and a half. The fixed version chewed through 100,000 a's in 0.2 ms.

Wall-clock time depends on hardware, so I also counted work. PCRE2 10.46, the C library behind PHP's preg_ functions, can report how many internal match steps a search needed. For ^(a+)+$ on the same inputs, it needed 80 steps at 5 a's, 2,560 at 10, 81,920 at 15, and 2,621,440 at 20. That's a doubling with every character. For ^a+$, it needed 2 steps at every length I tried, up to 1,000 characters.

Python 3.13 behaves the same way: 24 a's and a ! took 502 ms with re.match.

Why the engine tries every split

The regex engines in Perl, PCRE, Python, JavaScript's V8, and .NET (by default) are backtracking engines. When one path fails, they back up to the last choice they made and try the next option.

In (a+)+, every a can either extend the current inner group or start a new one. Four a's can be grouped as aaaa, aaa|a, a|aaa, aa|aa, and so on: eight ways in total, or 2 to the power of (n − 1). If the string ends in a, the first grouping succeeds and nobody notices. If it ends in !, nothing can succeed, and the engine has to prove that by trying every grouping. OWASP's ReDoS page puts it as 16 paths for aaaaX and 65,536 for sixteen a's and an X.

That's the whole bug: an ambiguous pattern plus an input that fails late. Attackers call it ReDoS, regular expression denial of service. You don't need a botnet. You need one request with the right string.

It doesn't have to be exponential to take you down

(a+)+ is exponential. Plenty of real outages came from patterns that are "only" polynomial, which sounds safe until your input is long.

Stack Overflow went down for 34 minutes on July 20, 2016. A post contained roughly 20,000 consecutive whitespace characters, and a regex meant to trim whitespace from the ends of lines ran on every home page view. Their simplified version of the problem is \s+$. The engine starts at the first space, runs to the end of the spaces, hits a non-space, fails, then starts over from the second space. That's about 200 million character checks. The home page was also the load balancer's health check, so the load balancer pulled every web server out of rotation. Their fix: replace the regex with a substring function.

I measured /\s+$/ in Node against a run of spaces followed by an x:

Double the input, quadruple the time. That's quadratic. JavaScript's built-in trimEnd() handled the 40,000-space string in 0.6 ms.

Cloudflare's reduced pattern is worse. The post-mortem points out that adding a literal semicolon, .*.*=.*;, would have been far more catastrophic, and walks through the step counts. I timed that version in Node on x= followed by x's: 30 ms at 500 characters, 238 ms at 1,000, and 1,830 ms at 2,000. Each doubling costs about eight times more, which is cubic. Two kilobytes is a small request body.

How to spot an evil regex

OWASP's rule of thumb: be suspicious of a repeated group that contains its own repetition or overlapping alternatives. Their examples:

• (a+)+$ (nested quantifiers)
• ([a-zA-Z]+)*$ (same thing with a character class)
• (a|aa)+$ and (a|a?)+$ (alternatives that can match the same text)

To those I'd add two shapes from the outages above: two adjacent pieces that can match the same characters, like .*.* or \s*\s+, and an unanchored pattern that ends with something the input might not have, like \s+$.

Don't trust your eyes too much, though. A 2018 study by James Davis and colleagues scanned 375,652 npm modules and 72,750 PyPI modules and found that about 1% of unique regexes had super-linear worst cases, affecting over 10,000 modules. Nearly 300 were exponential. The same study found these anti-pattern rules "necessary, but not sufficient": nearly every slow regex fits one, but lots of fast ones do too. Treat a match as a reason to test, not a verdict.

This isn't academic. In June 2023, GitHub's advisory database added CVE-2022-25883, a high-severity ReDoS in semver, the npm version-parsing package. Versions before 7.5.2 were vulnerable when untrusted input reached new Range.

How to test a regex for catastrophic backtracking

The test that catches this is simple: make the input almost match, then make it longer.

1. Pick a string your pattern accepts, like aaaa.
2. Add one character at the end that breaks the match, like !.
3. Repeat the matching part at 10, 15, 20, and 25 characters and watch the time.

If time grows in proportion to length, you're fine. If it doubles per character or quadruples when the input doubles, you've found one.

You can do this by hand in the CyberScryb regex tester. It runs your pattern in your browser with JavaScript's own engine as you type, so what you see is what V8 does. It has no time limit, which makes it a decent smoke detector. If the page starts to lag when you paste 25 characters, you found the bug at your desk instead of in production. Keep test strings short until you know.

For code, a few lines of Node do the same job:

const re = /^(a+)+$/;
for (const n of [10, 15, 20, 25]) {
  const s = 'a'.repeat(n) + '!';
  const t0 = performance.now();
  re.test(s);
  console.log(n, (performance.now() - t0).toFixed(2), 'ms');
}

Then automate it, because nobody tests by hand twice. eslint-plugin-regexp has a no-super-linear-backtracking rule that's on in its recommended config. GitHub's CodeQL ships an inefficient regex query for JavaScript. recheck combines static analysis and fuzzing to find attack strings.

And steal Cloudflare's lesson: add a test that fails when a rule gets slow, not only when it gets the wrong answer. Their suite passed because nobody was timing it.

Three fixes, in the order I'd use them

1. Remove the ambiguity, then measure the fix

Most evil regexes have a calmer twin. ^(a+)+$ is ^a+$. For key-value text, .*.*=.*; can become [^=]*=[^;]*;: each piece now stops at a specific character instead of grabbing everything and backing up.

Measure the fix anyway. My first rewrite, /[^=]*=[^;]*;/ without an anchor, still took 268 ms at 20,000 characters and 29.6 seconds at 200,000. Unanchored, the engine retries the whole thing from every starting position. Adding ^ dropped 200,000 characters to 0.45 ms. Same idea, one character, from 30 seconds to under a millisecond.

Some engines can also lock in a match so it's never revisited. Atomic groups (?>...) and possessive quantifiers like a++ exist in PCRE and .NET, and Python's re gained both in 3.11. In Python 3.13, ^(?>a+)+$ and ^(a++)+$ finished the 24-character attack string in well under a millisecond, versus 502 ms. JavaScript doesn't have them: Node 20 rejects (?>a+) as an invalid group.

Also ask whether you need a regex at all. Stack Overflow swapped theirs for a substring call. For trimming, use trim().

2. Cap the input, and set a time limit where you can

A backtracking regex's worst case depends on input length, so cut the input before it reaches the regex. An email field doesn't need 10,000 characters. Neither does a username or a header value. A length check is boring, and it's the only defense that works the same in every language.

.NET lets you set a match timeout per regex or process-wide. The default is Regex.InfiniteMatchTimeout, meaning no limit, and Microsoft recommends always setting one when a pattern can backtrack. Their docs also say timeouts and non-backtracking mode guard against accidental slowness in patterns you wrote, and are "not intended as a security boundary" against malicious patterns. So never build a regex from user input, and escape user text with Regex.Escape if you must embed it.

3. Use an engine that can't backtrack

This is the fix Cloudflare chose, and it's the one I'd pick for anything handling untrusted input at volume. Some engines are built so match time grows linearly with input, no matter the pattern:

• RE2 (C++) guarantees match time "linear in the length of the input string" and was built to handle regexes from untrusted users.
• Go's regexp package is "guaranteed to run in time linear in the size of the input."
• Rust's regex crate promises worst-case O(m × n) time, where m is the regex size and n is the input size.
• .NET 7 added RegexOptions.NonBacktracking, which guarantees linear-time processing.
• Node can use RE2 through the node-re2 bindings.

The price is features. RE2 doesn't support backreferences or lookaround, because those have no known non-backtracking solution. The Rust crate drops them too. Most validation and parsing patterns don't need them.

V8 also has an experimental linear-time engine, shipped in V8 8.8 behind flags. With --enable-experimental-regexp-engine, I ran /^(a+)+$/l on 100,000 a's and a ! in Node 20: 10 ms, where the normal engine needs over five seconds at 30 characters. It's experimental and flag-only, so treat it as a demo of the idea, not a production setting.

FAQ

Are lazy quantifiers a fix for catastrophic backtracking?

Not reliably. Cloudflare's post-mortem shows .*?.*?=.*? cutting steps for one input shape, but the semicolon version .*?.*?=.*?; took exactly as many steps as the greedy one. Laziness changes the order the engine tries things, not how many things it might try.

Does a WAF protect me from ReDoS?

Not by itself. Cloudflare's WAF was the thing that fell over. Your own input limits and a safe engine protect you no matter what sits in front.

Is ReDoS a real security vulnerability or only a performance bug?

Both, and it gets CVEs. The semver advisory, CVE-2022-25883, was rated high severity. If an attacker can send the input, a slow regex is a denial-of-service hole.

Find the slow one before your traffic does

Catastrophic backtracking is not a freak event. It's what a backtracking engine does with an ambiguous pattern and an input that almost fits. Cloudflare's rule passed code review and CI. The suite never timed anything.

Pick the regex in your code that touches the most user input, paste it into the regex tester, and feed it a string that almost matches at 10, 20, and 30 characters. If the timing climbs fast, you know your next fix. Like the Year 2038 problem, it's a bug that sits quietly until the input shows up. And like random UUID keys, it looks fine in testing and falls over at scale.