A new firewall rule contained a loosely written search pattern
(.*.*=.*) that made every Cloudflare server grind to a halt; it
went everywhere at once, with no test group and no CPU limit, and
took a large part of the web offline for 27 minutes.
Cloudflare sits between a huge share of the web's websites and the people visiting them. When you open a site that uses it, your request goes to a Cloudflare data centre near you first (they call each one a PoP), which checks it, speeds it up, and passes it on. Part of that check is a web application firewall (WAF): a set of rules that reads every request and blocks the ones that look like an attack. Think of a security desk every visitor walks past.
At 13:42 UTC on 2 July 2019, Cloudflare gave that desk a new rule.
Three minutes later, people visiting sites behind Cloudflare got an
error page (502 Bad Gateway: the server in front couldn't get an
answer from the one behind it), Cloudflare lost around 80% of its traffic, and Cloudflare's
own dashboard was unreachable too, because it sits behind the same
desk.
It wasn't an attack. It was one regular expression, and the postmortem Cloudflare published ten days later is one of the clearest write-ups of a global outage you'll find. This post walks through it with the regex running live, so you can watch it eat the CPU yourself.
27 minutes, minute by minute
Here's where the 27 minutes went. Each bar is one phase, from the times in the postmortem:
The machines spread the rule, and later the fix, in seconds. The human parts took twenty-two minutes.
What the rule was looking for
The new rule was meant to stop a common attack called cross-site scripting (XSS). An attacker types a scrap of code where a site expects plain text: a search box, a comment, a link. If the site carelessly pastes that text back into a page, every visitor's browser runs the code as if the site had written it, and it can read their login, redirect them, or act on their behalf. Here's a typical scrap, typed into a search box, landing in a site that writes the search term into its own script:
To spot text shaped like that, a firewall uses a regular expression,
or regex: a short pattern that describes what some text looks like
rather than spelling it out. \d means "any digit", . means "any
character", and * means "as many as you like, including none". So
.* reads as "anything at all", and .*= reads as "anything, then an
equals sign". Most programming languages have them built in.
The rule, piece by piece
Here's the regex exactly as it shipped, split into its parts (it was one line):
| Lines | Matches | In the attack above |
|---|---|---|
| 1-4 | Something that ends a value: a quote, bracket, brace, backslash, digit, backtick, +, -, or a #javascript literal like true or null | the ' that closes the site's text |
| 5 | Optional closing parentheses, then an optional ; that ends a statement | the ; |
| 6 | Optional whitespace, an empty {}, a double pipe, or + - ~ !: things that can start a new expression | nothing here |
| 7 | Anything, then an = somewhere later: an assignment | document.location= |
Read together: a value gets closed, a statement ends, and somewhere
after that, something is assigned. That's a fair description of
injected JavaScript. The problem is line 7. .*(?:.*=.*) with the
grouping stripped is .*.*=.*: anything, then anything, then an =,
then anything. All it really checks is that an = comes later, which
[^=]*= says without any ambiguity. But two .*
back to back can split the same run of characters between them in
every possible way, and a backtracking engine tries every one of those
splits before it gives up.
Why .*.*=.* eats a CPU
In plain terms: the rule asks a simple question, "is there an =
later on?", but phrases it so loosely that the computer checks the
same question thousands or millions of ways before it's allowed to
answer no. That checking runs on the CPU, the part of a computer that
does the thinking. Do it for every request, on every server, and the
CPUs have nothing left for anything else.
The WAF ran in #lua on
#pcre, a backtracking engine. Backtracking
treats a regex like a search tree. .* is greedy: it grabs the whole
rest of the input, lets the next token try, and when that fails, gives
back one character and tries again. With two .* in a row, each
choice the first one makes forces the second to try all of its
choices. Then the = fails, and on an input with no = at all it
fails at every one of those combinations, from every starting
position.
Here it is happening on four characters. Press next and watch the two
.* trade characters back and forth while the = fails at every
split:
Starting at position 0. .* #1 tries from position 0, taking as much as it can.
Four characters and no = already cost 55 steps. A longer input
means more places to start, more places for the first .* to stop,
and more for the second: three things that each grow with the length,
so the work grows with its cube. Double the input and the work goes up
about eight times.
The alternative has been around since
Ken Thompson's 1968 paper:
read the input once, left to right, and carry the set of places in
the pattern a match could currently be at. A pattern has a fixed
number of places, so the work per character is bounded, whatever the
input looks like. That's how #re2 and
#rust's regex
crate work.
Below, both are running for real against the same input: a small
backtracking matcher and a small Thompson-style one, counting steps.
Start with no = and drag the length.
xxxxxxxxxxxxxxxxxxxx.*.*=.* on 20 characters: backtracking takes 2,023 steps, linear takes 63. No match.
At 20 characters the backtracker needs about 2,000 steps; at 40 it's
over 13,000; the linear engine needs 63 and 123. Keep going and the
gap stops being a constant factor. On a 1,000-character body with no
= in it, this backtracker takes 168 million steps. The linear one
takes 3,003. Request bodies are routinely that long, and an edge
server sees thousands of them a second.
Two things worth trying in the explorer, because they're the fixes people reach for first:
- Lazy quantifiers (
.*?) feel like they should help, and on an input that matches they do: switch the=on and the lazy pattern finishes in a handful of steps. Switch it off and the step count is identical to the greedy one. Lazy only changes the order the engine tries splits in; when nothing matches, it still tries them all. - A trailing literal (
.*.*=.*;) turns a cheap match back into a full search. Even with an=in the input, the;never matches, so the engine has to rule out every split. Cloudflare's own appendix measured the same jump:x=plus twentyxs went from 555 steps to 5,353.
How it reached every server in seconds
Careful teams don't ship a change to everyone at once. They try it on a small group first and watch for trouble, the way a restaurant tries a new dish on a few tables before it goes on the menu. The small group is called a canary, after the birds miners carried to warn them of gas.
Cloudflare's code releases went through three of those stages: an employee-only data centre (DOG), a slice of free-plan traffic (PIG), three canary locations, then the world. That takes hours, sometimes days, and it exists to catch exactly this.
WAF rules didn't use it. They're how Cloudflare responds to a new attack, and a defence that takes a day to deploy isn't much use, so rule changes went straight to every machine through Quicksilver, the company's distributed key-value store. The postmortem quotes its p99 at 2.29 seconds to reach every server in the world: 99 changes in 100 arrive everywhere within that time.
- Code: DOG, staff only to PIG: some free traffic
- PIG: some free traffic to 3 canary locations
- 3 canary locations to Every PoP, worldwide: hours to days
- WAF rule change to Quicksilver: all machines in seconds
- Quicksilver: all machines in seconds to Every PoP, worldwide
That trade isn't wrong. Fast rule deploys are the product. But it means the rule pipeline carried the same blast radius as a code deploy with none of the stages, so every check had to happen before the push. The test suite checked that rules matched what they should and didn't match what they shouldn't. Nothing measured how much CPU they used.
Every safeguard had a hole
What makes this outage worth studying isn't the regex. Someone writes a bad regex every day. It's that every layer that should have stopped one failed at the same time, and the postmortem lists them plainly:
| Layer | Should have | Why it didn't |
|---|---|---|
| The pattern | Avoided ambiguous .*.* | Written and reviewed by people; nothing flags it automatically |
| The engine | Bounded the work per request | PCRE backtracks, with no complexity guarantee |
| The CPU guard | Capped regex CPU use | Removed by accident in a WAF refactor weeks earlier |
| The tests | Failed on a slow rule | Checked matches only, never CPU |
| The rollout | Hit one city first | Rule changes went global directly, by design |
| The rollback | Undo the change quickly | Required running the full WAF build twice |
| Alerting | Fire as soon as traffic dropped | The global traffic drop alert took too long |
| The status page | Tell customers fast | Updated by hand, late |
| Access | Let engineers reach the controls | Internal tools ran through the broken edge; the bypass was rarely practised |
| Credentials | Work in an emergency | Some had expired under a security timeout |
| Dashboard and API | Let customers react | Served through the same edge that was down |
Read down the right-hand column and almost none of it is about regex. Access and the dashboard are one lesson: the tools for fixing the outage ran through the thing that was out. Credentials and the status page are its cousin: emergency paths nobody had exercised. Together they're why turning the WAF off took five minutes after it was proposed at 14:02, and they're the part of this incident that applies to nearly every system, regex or not.
What to take from it
You probably don't run a global WAF. You almost certainly run a regex on input someone else controls: a validator, a log parser, a router, a search box. Three questions cover most of what went wrong here:
- Which engine is it? If it backtracks, a pattern with two
overlapping quantifiers (
.*.*,(a+)+,(\w|\d)*) is a CPU bomb waiting for the right input, which is why OWASP gives it a name, ReDoS. Use a linear engine where you can, and cap input length and match time where you can't. - What's the fastest path to production, and does it skip a stage? Config, feature flags and rules often go out faster than code, with less checking. They can break the system just as thoroughly.
- Does your way out depend on the thing that's broken? Dashboards, SSO, chat, runbooks: if they ride on the same infrastructure, rehearse the bypass before you need it. In this incident the fastest lever, turning the WAF off, was quick to pull and slow to reach.