One regular expression, every CPU on the edge

At 13:42 UTC on Tuesday 2 July 2019, sites behind Cloudflare started answering with 502 Bad Gateway. Not one region or one product: every server in every city at once, with CPU on every core that serves HTTP pinned near 100%. At its worst, traffic through the network fell by 82%. It was Cloudflare’s first global outage in six years, it lasted 27 minutes, and it came from one regular expression in a rule that was only supposed to watch.

How a WAF rule reaches every server

A web application firewall (WAF) inspects each HTTP request before it reaches the customer’s own server, the origin, and blocks the ones that look like attacks: SQL injection, cross-site scripting (XSS), exploits for known bugs. Most of its checks are regular expressions run against the URL, the headers and the body.

Cloudflare’s WAF was written in Lua and ran inside NGINX on every edge server, as one step in handling each request. Rules were compiled into Lua, and their regular expressions went to PCRE, a widely used Perl-compatible regex library. When the design was described in 2013, the goal was a median block-or-allow decision in under a millisecond, and it was running at 380 to 480 microseconds per request.

Cloudflare’s own team writes the managed rules and changes them constantly: 476 change requests in the 60 days before the outage, about one every three hours. A new rule usually starts in simulate mode. It runs against real traffic and logs what it would have blocked, but blocks nothing, so the team can measure false positives before switching it on.

Rules reach the edge through Quicksilver, Cloudflare’s replicated key-value store. Every server keeps its own copy, fed through a fan-out tree of replicas, so a data centre keeps serving even when it is cut off from the core. It carried about 350 changes a second, and the 99th percentile for a change to reach every machine in more than 180 cities was 2.29 seconds.

That speed is the point. When a serious SharePoint vulnerability was published in May 2019, a rule pushed the same way protected customers while attempts to exploit it spiked. So the path for rules was different, on purpose, from the path for software:

A software release goes from DOG to PIG to three canary data centres and only then everywhere, which takes hours or days. The procedure for a WAF rule change allowed a global push instead, because a rule that takes a day to arrive is no use against an exploit published this morning.

How one regex can eat a CPU

Most regex engines in popular languages, PCRE included, work by backtracking. They walk the pattern and the text together, and whenever the pattern allows a choice (how many characters should .* take?) they pick one and remember the others. If the match fails further on, they go back to the most recent choice and try the next option.

The trouble was at the end of the rule, .*(?:.*=.*). Without the group, that is .*.*=.*: anything, then anything, then an equals sign, then anything. Cloudflare’s postmortem counted the steps an engine takes:

Input	Steps to finish
x=x	23
x=xx	33
x=xxx	45
x= then 20 x’s	555
20 x’s, no =	4,067

Take x=x. The first .* grabs all three characters, the second gets none, and there is no = left, so the match fails. The engine gives back one character and tries again, and keeps sharing the text between the two .* in every possible way until the = lines up. For text that doesn’t match at all, it tries every split from every starting position before it gives up. The work grows with a power of the input length. That is polynomial, not exponential, and it was still enough: WAF rules run on long strings that attackers control, on every request.

A different kind of engine avoids the problem entirely. In 1968 Ken Thompson described running a regex as a set of states tracked together: read each character once, and move every live state forward at the same time. Nothing is ever retried, so the time is proportional to the length of the pattern times the length of the text. Google’s RE2 and Rust’s regex crate work this way. The price is a few features, such as backreferences, that need backtracking.

For the curious, the whole expression:

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

What happened

At 13:31 an engineer on the firewall team merged a pull request with a minor change to the XSS rules, after review and approval. At 13:37 TeamCity, the build system, built the rules and ran the WAF test suite: unit tests for the matching functions, then a large set of HTTP requests that must be blocked and others that must get through. Everything passed. The suite had no way to notice runaway CPU, and when the team later went back through old build logs, even its run time hadn’t moved with the new rule.

At 13:42 TeamCity started deploying automatically, in simulate mode, and Quicksilver carried the rule to every server within seconds. CPU on the cores that handle HTTP and HTTPS went to nearly 100% across the network. The front-line servers that accept connections still had spare cores, but they got no answer from the processes behind them, so they returned 502s: for customers’ sites, for Cloudflare’s dashboard and API, and for Cloudflare’s own internal tools.

At 13:45 the first PagerDuty page fired: one of hundreds of synthetic tests that check the WAF from outside. Then came failing end-to-end tests, a global traffic-drop alert, a wall of 502 errors, and reports of CPU exhaustion from data centres around the world. John Graham-Cumming, the CTO, saw the alerts on his watch in a meeting; on his way back to his desk, a leader in Solutions Engineering told him they had lost 80% of their traffic. SRE declared a P0 and pulled in engineering leadership. The London engineering team, gathered for an internal tech talk, moved into one large conference room.

For the first few minutes the leading theory was an attack of a kind nobody had seen before. By 14:00 the evidence pointed elsewhere. The Performance team pulled live CPU data from a machine that clearly showed the WAF, someone confirmed it with strace, and another team found WAF errors in the logs. At 14:02 the proposal on the table was a global terminate: a built-in mechanism that disables one component everywhere.

Why it took 25 minutes to stop

From the deploy to the kill switch took 25 minutes, and most of that had nothing to do with the regex.

Cloudflare uses its own products, including Access, the login service in front of its internal tools. With the edge down, Access was down, and engineers couldn’t sign in to the control panel that held the switch. Some engineers who did get back in then found their accounts disabled, because a security feature switches off credentials that go unused for a while. Jira and the build system were out of reach too. The way in was a bypass mechanism that was rarely used, so nobody had it in muscle memory.

The other levers were slower. The prepared rollback plan meant running the complete WAF build twice. And the safeguard that should have stopped a runaway expression wasn’t there: it had been removed by mistake a few weeks earlier, in a refactor whose goal was to make the WAF use less CPU.

The postmortem lists 11 things that went wrong, and most are ordinary: the first alert for the global traffic drop fired too slowly, the status page lagged, and customers couldn’t turn anything off themselves because the dashboard and API also ran through the edge. Together they stretched a mistake that spread in seconds into 27 minutes of 502s.

How they fixed it

At 14:07 a team member ran the global WAF termination. By 14:09 traffic and CPU were back to normal everywhere, and the rest of Cloudflare’s protections had kept running throughout.

Bringing the WAF back was done slowly. In a single city, with paying customers’ traffic moved away, the team tested both ways: that the rule really was the cause, and that the rollback really fixed it. At 14:52 the WAF was re-enabled globally.

Then all WAF release work stopped while they:

• put back the CPU safeguard that had been removed;
• inspected all 3,868 managed rules by hand for other patterns that could backtrack badly;
• added performance profiling for every rule to the test suite;
• planned the move to RE2 or Rust’s regex engine, both of which have run-time guarantees;
• changed the procedure so rules roll out in stages like software, keeping a global push for active attacks;
• built a way to take the dashboard and API off the edge in an emergency, and automated the status page.

Longer term, they committed to replacing the Lua WAF with the newer firewall engine.

What I'd take from it

1. "Simulate" is not "off". A rule that only logs still runs on every request. Anything on the hot path, dry run or not, deserves the same rollout as a change that blocks traffic.
2. Don't send routine changes down the emergency path. This was a routine improvement, and it went out the way an emergency would. Stage routine rule changes through one data centre first; a few minutes there would have shown the CPU graph.
3. Put a ceiling on per-request work. Use a regex engine with linear-time guarantees (RE2, Rust's regex), or a match limit where you can't. Then test for it: a rule suite that fails when CPU time per request jumps.
4. Break-glass access must not run through the thing that breaks. The kill switch sat behind a login served by the failing edge, and some credentials had expired from disuse. Drill the bypass until it is boring.

Sources

• Cloudflare: Details of the Cloudflare outage on July 2, 2019
• Cloudflare: Cloudflare outage caused by bad software deploy (updated)
• Cloudflare: CloudFlare's new WAF: compiling to Lua
• Cloudflare: Introducing Quicksilver: Configuration Distribution at Internet Scale
• Russ Cox: Regular Expression Matching Can Be Simple And Fast