How a regex takes down an API

On July 2nd a big chunk of the web returned 502s for 27 minutes because of one line in a firewall rule. Cloudflare published the full post-mortem last Friday and it’s worth reading in full, partly because it’s unusually candid and partly because the root cause is something most of us have in our own code right now.

At 13:42 UTC they deployed a new rule to their WAF, the managed firewall that sits in front of customer sites, to catch a kind of injection attack. The rule contained a regular expression. CPUs across their whole network went to nearly 100% evaluating it. The rule was going out in “simulate” mode, where real traffic passes through it but nothing gets blocked, which feels safe, except that simulate mode still has to run the regex on every request. A protection that would have limited runaway CPU from a regex had been removed by mistake in a refactor a few weeks earlier.

The expression was long, but the post narrows it down to the part that mattered:

.*(?:.*=.*)

Which is, for our purposes, .*.*=.*: anything, then anything, then an equals sign, then anything. It looks harmless. I’ve written worse in the last month.

What a backtracking engine does

Most regex engines you use day to day, PCRE, Perl, Python’s re, Java’s, JavaScript’s and .NET’s, are backtracking engines. They treat the pattern as a little program and try to match it greedily, one choice at a time, and when a choice leads to failure they back up to the most recent choice and try the next option.

For .*.*=.* against x=x that goes something like this. The first .* grabs everything, x=x. The second .* grabs nothing, because nothing is left. Then it needs an = and there’s no input left, so it fails, backs up, and makes the second .* give back… nothing, it had nothing. So it backs up further and makes the first .* give back one character, so it now holds x=. The second .* takes the last x. No = left. Fail. The second .* gives back the x. Still no = there. Fail, back up, the first .* gives back another character, and so on until the first .* holds just x, the second holds nothing, = matches, and the last .* eats the rest.

Cloudflare counted: 23 steps to match x=x. 33 for x=xx, 45 for x=xxx. For x= followed by 20 x’s it’s 555 steps. And if there’s no = at all, say 20 x’s, it’s 4,067 steps to conclude there’s no match, because the engine has to try every way of splitting the input between the two .*s, and then do it again from every starting position, since an unanchored regex can begin matching anywhere.

That’s the thing to internalize. Each .* is a choice point with as many options as there are characters left. Two of them in a row is roughly n² ways to split, the outer loop over start positions makes it n³, and a request body with a few thousand characters turns into billions of steps. And nobody notices in testing, because the test strings are 20 characters long and match quickly.

This one is polynomial. The textbook “catastrophic” cases, things like (a+)+$, are worse: nested quantifiers that give the engine an exponential number of ways to divide the input, so each extra character roughly doubles the work. But you don’t need exponential to take a site down. Stack Overflow went down for 34 minutes in July 2016 on a regex that just trimmed trailing whitespace, roughly \s+$. A post had about 20,000 consecutive whitespace characters followed by something that wasn’t whitespace. For each starting space, the engine consumed every remaining space, found the next character wasn’t the end of the line, gave up and moved on to the next start position. That’s 20,000 + 19,999 + …, about 200 million steps, for one post. That post was on the home page, and the home page was the load balancer’s health check, so the load balancer took the servers out of rotation one by one.

Thompson’s way

The frustrating part is that this was a solved problem in 1968. Ken Thompson’s paper in CACM that year described compiling a regular expression into a nondeterministic finite automaton and then simulating it in a way that never backtracks. Russ Cox wrote the definitive explainer, “Regular Expression Matching Can Be Simple And Fast”, back in 2007, and I’ve sent it to people more times than any other article.

The automaton for .*.*=.* has three states.

The trick is that instead of guessing which path to take and backing up when it’s wrong, you keep track of the set of states you could possibly be in, all at once. Read a character, compute the next set from the current set, repeat. The set can never hold more states than the automaton has, three here, so each character costs at most a constant amount of work, and the whole match is linear in the length of the input. 20 x’s, 20,000 x’s, with or without an =, it’s one pass. Unanchored search is free too: you just add the start state back into the set at every position.

The catch, and the reason Perl and friends went the other way, is that some popular regex features can’t be expressed as a finite automaton. Backreferences ((a+)\1) are the big one. Matching with backreferences is NP-hard in general, so any engine that supports them is going to have bad cases. Some lookaround constructs are awkward too. Most of the regexes I actually write never use them, but the engine has to assume they might.

So we ended up in a slightly silly place where the fast, safe algorithm is the old one, and the engines most of us use by default are the ones with the bad worst case. The exceptions are RE2, which Google built for exactly this reason (Russ Cox wrote it), Go’s regexp package, which uses the same approach, and Rust’s regex crate. Cloudflare says it’s switching the WAF to either RE2 or the Rust engine, which seems right.

What I’d check

If you run a backtracking engine on input that comes from the outside, and almost everybody does, a few things are worth doing.

Find the regexes that run on request data. Validators, routers, WAF rules, log parsers, the “strip this junk from user input” helper that someone wrote in 2014. Look for adjacent or nested unbounded quantifiers: .*.*, (x+)+, (\w|\d)*, anything where the same character could be consumed by more than one part of the pattern. That’s the shape that backtracks.

Put a limit on it. In .NET this is built in, and I’m surprised how few people know it: since 4.5 you can pass a matchTimeout to the Regex constructor, and it throws RegexMatchTimeoutException instead of spinning forever. Other platforms vary. PCRE has match and recursion limits you can configure. JavaScript has nothing built in that I know of, so a regex on the main thread in Node can stall every request on the box.

Limit the input. A lot of the danger goes away if the string can’t be longer than a few hundred characters. A regex that’s cubic on a 200-character username is fine. On a 2MB POST body, it’s an outage.

Test with the evil input, not the happy one. For each regex, the worst case is usually a long string that almost matches and then fails at the very end. Twenty thousand spaces and an x. A long run of x with no =. A fuzzer will find these, but honestly, writing one long almost-matching string per regex and timing it finds most of them.

And where you can, use a linear-time engine. Our backend is mostly Ruby and C#, so that’s not trivial for us, but for the one service that applies customer-supplied patterns to log lines I’m now looking seriously at RE2 bindings, because we don’t control the patterns at all and that’s precisely the case Cloudflare was in.

I’d add one thing that isn’t about regexes. Cloudflare’s simulate mode, Stack Overflow’s health check: in both cases the regex wasn’t the only problem, it was the regex plus a mechanism that made sure it ran everywhere at once. One of the post-mortem’s fixes is staged rollouts for WAF rules, so a new rule hits a small part of the network first, and I’d bet that does more good than the engine swap.