The regular expression that took Cloudflare down for 27 minutes

What happened

On 2 July 2019, at 13:42 UTC, Cloudflare's firewall team deployed "a minor change to the rules for XSS detection via an automatic process." It was meant to be harmless: the rule went out in "'simulate' mode where real customer traffic passes through the rule but nothing is blocked."

Simulate mode still runs the rule. Within moments, visitors to any Cloudflare site were getting 502 errors, and the company's own write-up says "we had lost 80% of our traffic." The cause, in their words: "a single WAF rule that contained a poorly written regular expression that ended up creating excessive backtracking." The team switched the firewall off globally, and by 14:09 traffic and CPU were back to normal. From deploy to recovery took 27 minutes.

The part of the pattern that did it

The full expression is long, but the post singles out one piece: .*(?:.*=.*). Read aloud, that is "any characters, then any characters, then an equals sign, then any characters".

Two .* in a row can split the same text between them in many ways. When the text has no = in it, the engine has to try every split before it's allowed to say "no match", and it tries again from every starting position. Cloudflare's engine was PCRE, which "uses backtracking for matching and has no mechanism to protect against a runaway expression." Their post walks through the steps by hand and shows the count climbing "super-linearly" as the input grows.

Python's re module is a backtracking engine too, so you can see the same shape here. The input is just x repeated, with no = anywhere:

import re, time

pattern = re.compile(r".*(?:.*=.*)")

previous = None
for n in [200, 400, 800, 1600]:
    text = "x" * n
    start = time.perf_counter()
    pattern.search(text)
    ms = (time.perf_counter() - start) * 1000
    growth = f"  ({ms / previous:.0f}x the last one)" if previous else ""
    print(f"{n:>5} characters: {ms:8.1f} ms{growth}")
    previous = ms

  200 characters:      1.4 ms
  400 characters:     10.6 ms  (8x the last one)
  800 characters:     79.2 ms  (7x the last one)
 1600 characters:    611.6 ms  (8x the last one)

Doubling the input makes it roughly eight times slower. At 1,600 characters it takes more than half a second on one core. A request body is easily longer than that, and a firewall sees every request.

Say what you mean

All the pattern really asks is "is there an = in here?". It takes two changes to say that without the backtracking, and the second one is easy to miss.

Make the neighbours disjoint. [^=]* means "anything except an equals sign", so it can't swallow the = that comes after it. At any one starting position there is now only one way to split the text.

Anchor it. search still tries every starting position. Without an anchor, a failed match is repeated from position 1, then 2, and so on. ^ pins the pattern to the start of the text, so it fails once and stops.

First, check that all three give the same answers:

import re

patterns = {
    "original": re.compile(r".*(?:.*=.*)"),
    "disjoint": re.compile(r"[^=]*=.*"),
    "anchored": re.compile(r"^[^=]*=.*"),
}

for text in ["a=1", "x=y=z", "no equals here", "=", "", "line one\nkey=value"]:
    answers = {bool(p.search(text)) for p in patterns.values()}
    print(f"{text!r:22} match={answers.pop()!s:5} all agree={not answers}")

'a=1'                  match=True  all agree=True
'x=y=z'                match=True  all agree=True
'no equals here'       match=False all agree=True
'='                    match=True  all agree=True
''                     match=False all agree=True
'line one\nkey=value'  match=True  all agree=True

Then time them on the same kind of input. The original gets only 1,600 characters because anything longer takes too long to wait for:

import re, time

def ms(pattern, n):
    text = "x" * n
    start = time.perf_counter()
    re.compile(pattern).search(text)
    return (time.perf_counter() - start) * 1000

print(f"original,   1,600 chars: {ms(r'.*(?:.*=.*)', 1600):9.1f} ms")
for n in [1600, 3200, 6400]:
    print(f"disjoint, {n:>7,} chars: {ms(r'[^=]*=.*', n):9.1f} ms")
for n in [1600, 100_000]:
    print(f"anchored, {n:>7,} chars: {ms(r'^[^=]*=.*', n):9.1f} ms")

original,   1,600 chars:     623.0 ms
disjoint,   1,600 chars:       1.1 ms
disjoint,   3,200 chars:       4.4 ms
disjoint,   6,400 chars:      17.4 ms
anchored,   1,600 chars:       0.1 ms
anchored, 100,000 chars:       0.1 ms

The disjoint version is hundreds of times faster, but look at the growth: each doubling still costs about four times more, because of the retries. Only the anchored one stays flat. If you had stopped after the first fix and tested at 1,600 characters, you'd have shipped a smaller version of the same problem.

And if all you need is "is there an equals sign?", "=" in text answers it without a regex at all.

It wasn't one mistake

It's tempting to blame the person who wrote the pattern. Cloudflare's own account doesn't, and it's worth reading why: several safety nets were missing at once.

• The guard had gone. "A protection that would have helped prevent excessive CPU use by a regular expression was removed by mistake during a refactoring of the WAF weeks prior."
• The rollout was instant. Firewall rules went out through their Quicksilver store so they could answer new attacks fast, and "a change to the rules went global in seconds." There was no stage where a few servers got it first.
• The engine made no promises. "The regular expression engine being used didn't have complexity guarantees."

Their follow-up list fixed the system rather than the person. They put the CPU protection back, inspected all 3,868 WAF rules by hand for more of the same, added performance profiling for every rule to the test suite, planned a move to "either the re2 or Rust regex engine which both have run-time guarantees", and changed the procedure to stage rule rollouts the way they already staged other software.

What you can take from it

• Test the near miss. A pattern that matches quickly can still fail slowly. Time it on a long input that almost matches and then doesn't, like the x string above.
• Watch for two quantifiers that can eat the same characters: .*.*, (a+)+, (\w|\d)+. Make neighbours disjoint, as [^=]*= does, and anchor the pattern when you can.
• Don't run a regex on untrusted input if a string method will do. in, startswith, split and partition never backtrack.
• Where you must accept patterns or input you don't control, use an engine that guarantees linear time. RE2 is one of the engines Cloudflare named, and it's available for Python as the google-re2 package.
• Roll out in stages. Even a correct change can meet data nobody tested. Letting a few machines take it first turns an outage into a graph that looks odd.