Engineering Atlas › Problem Solving & Incidents (AI era)

Cloudflare Regex Outage (2019)

11 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

How it works

Timeline (UTC, from Cloudflare's post)

Technical root cause

The rule's regular expression ended with .(?:.=.). In a backtracking regex engine such as PCRE, which Cloudflare's Lua-based WAF used, . first consumes as much as possible and then gives characters back one at a time when the rest of the pattern fails. With two .* pieces in sequence and an = that is not present, the engine tries every way to split the input between them, for every starting position. Cloudflare's post shows the step count rising sharply: 23 steps for x=x, 555 steps for x= followed by 20 x's, and 5,353 steps when a trailing character forces more backtracking (Cloudflare postmortem). Real HTTP requests are much longer, so a single request could cost huge amounts of CPU, and every request was checked.

Contributing factors

Detection and mitigation

The CPU spike was immediately visible, but the first hypothesis (an attack) cost time. The fastest mitigation was the "global terminate" for the WAF, a kill switch that turned off the whole component, used about 25 minutes after deployment. A plain rollback would have needed the full WAF build to run twice, which was too slow (Cloudflare postmortem).

What changed afterwards

Cloudflare listed: re-introducing the excessive-CPU protection; manually inspecting all 3,868 managed rules for backtracking risks; adding performance profiling of every rule to the test suite; switching to the re2 or Rust regex engines, which guarantee run time linear in the input; staged rollouts for rule changes, keeping an emergency global path for active attacks; an emergency way to run the dashboard and API off the edge; and automated status page updates. Longer term, the WAF moved off the Lua engine to a new firewall engine.

What I would have done as the tech lead

Treat configuration and rules as code with the same rollout safety: staged, with automatic rollback on CPU or error regressions, plus an explicit emergency path that requires a stated reason. Make CPU budgets part of the rule test suite, and use a regex engine with linear-time guarantees for untrusted input by design, not by review. Keep the WAF kill switch fast, documented and practised, and make sure incident tooling does not depend on the system that may be down.

Down the stack

Layer 1The contract

A WAF promises to inspect every request and block attacks while adding little latency, typically well under a millisecond per request. That contract has two halves: correctness (does it match attacks?) and cost (does it stay within a CPU budget?). The test suite checked only the first half.

Layer 2The mechanism

Regex engines come in two families. Backtracking engines (PCRE, the default engines in Python, JavaScript, Java and many others) explore one path at a time and back up on failure; they support features such as backreferences, but some patterns take exponential or high-polynomial time on adversarial input. Automata-based engines (RE2, Go's regexp, Rust's regex) compile the pattern to a state machine and process each input character a bounded number of times, guaranteeing time linear in the input for a fixed pattern, at the cost of not supporting backreferences (Russ Cox, Regular Expression Matching Can Be Simple And Fast). For a system that runs thousands of patterns against untrusted input, the linear-time guarantee is worth far more than backreferences.

Layer 3The machine

Each backtracking step is a few memory reads and comparisons, perhaps a nanosecond or two, so thousands of steps per request sound harmless. But a proxy handles tens of thousands of requests per second per machine, each checked against many rules, and the step count for this pattern grows roughly with the cube of input length. An input of a few kilobytes can need billions of steps, seconds of CPU for one request. When every core spends its time inside the regex engine, the event loop that should serve other requests never runs, so latency and errors hit all traffic, not just the requests that triggered the pattern.

Why it's built this way

  1. Security rules must deploy fast to respond to attacks, which creates pressure for global, instant pushes.
  2. Fast global pushes need strong pre-deployment checks, including cost, not only correctness.
  3. Backtracking engines have unbounded worst cases, so either the engine or a CPU guard must bound them.
  4. When the edge is down, tools that depend on it are down too, so recovery paths need independence.
  5. The best fix removes the failure class: linear-time engines plus staged rollout plus a guard.

Diagram

flowchart TD
  PR["Rule merged 13:31"] --> B["Tests pass: correctness only"]
  B --> Q["Quicksilver: global push in seconds 13:42"]
  Q --> S["Simulate mode still runs regex"]
  S --> RX[".*(?:.*=.*) backtracks on every request"]
  G["CPU guard removed weeks earlier"] --> RX
  RX --> CPU["100 percent CPU on all edge machines"]
  CPU --> E["502s for 27 minutes"]
  A["Internal tools on same edge"] --> SL["Slower mitigation"]
  SL --> E
  K["Global WAF kill 14:07"] --> R["Recovery 14:09"]

Worked example

A team uses a regex to validate email addresses in a signup API: ^([a-zA-Z0-9]+)@example\.com$. A user (or attacker) submits 30 letters followed by an exclamation mark. Each extra letter roughly doubles the work, because the nested quantifier ([a-zA-Z0-9]+) can split the letters into groups in exponentially many ways before concluding there is no match. In Python's re, a 30-character input can take many seconds; at 40 characters it effectively hangs a worker.

Applying Cloudflare's fixes: switch validation to a linear-time engine (the re2 bindings, or Go's regexp in a Go service) or rewrite the pattern without nested quantifiers (^[a-zA-Z0-9]+@example\.com$); add a test that runs each pattern against long adversarial inputs and fails if it takes more than a small budget; cap input length before matching; and roll out validation changes through the same canary process as code.

In the wild

Trade-offs

ApproachStrengthsWeaknessesChoose when
Backtracking engineRich features (backreferences, lookaround)Unbounded worst caseTrusted input, small patterns
Linear-time engine (RE2, Rust, Go)Guaranteed run timeFewer featuresUntrusted input, many patterns
Step or time budget per matchBounds damage from any engineMust decide fail open or closedDefence in depth
Global instant config pushFast response to attacksGlobal blast radiusEmergencies only, with a stated reason
Staged config rolloutCatches bad changes on a small sliceSlowerDefault for rules and config

Pitfalls in production

Leadership lens

Check yourself

  1. Why does ..=.* get so slow on inputs without =?

    Show answer

    A backtracking engine tries every way of splitting the input between the two .* pieces, at every starting position, before giving up, so work grows roughly with the cube of the input length.

  2. Why did "simulate" mode not protect Cloudflare?

    Show answer

    Simulate mode still evaluated the regex on live traffic and only skipped blocking, so the CPU cost was fully present.

  3. What does a linear-time regex engine give up, and why is it worth it here?

    Show answer

    Features such as backreferences; in exchange it guarantees time proportional to input length, which bounds the cost of any rule on any request.

  4. Why did mitigation take longer than the kill switch itself?

    Show answer

    Engineers first suspected an attack, and the internal tools and access they needed ran through the same failing edge, with a rarely used bypass.

Sources and further study

Primary

Systems docs

Books

Other curricula

Free resources

Open in the interactive app: practice, quiz, mock interview →