Cloudflare 2019: The Regex That Took Down a Global Network

On July 2, 2019, at 13:42 UTC, Cloudflare deployed new rules to its managed WAF. Among the rules was rule 100137, intended to detect XSS attacks. The core regex of the rule was:

(?:(?:"|'|\]|\[|\\|(?:nan|infinity|true|false|null|undefined|symbol|math)|\`|\-|\+)+[)]*;?((?:\s|-|~|!|{}|\|\||&&)*(?:[0-9]{0,4}d?(?:x|xx|xxx|xxxx)?)(?:;|\\|,|\+|\-|\*|\/|%|&|\||\^|<|>|=|!)))+

The problem lies in the group ((?:\s|-|~|!|{}|\|\||&&)*) combined with the outer + quantifier. This pattern creates what computer science calls catastrophic backtracking: for a string that does not match the pattern but is long enough, the regex engine tries exponentially more combinations before giving up. Execution time ceases to be O(n) and becomes O(2ⁿ) relative to input length.

Cloudflare was using Lua's regex engine (based on PCRE — Perl Compatible Regular Expressions), which has no native protection against this behavior. Unlike finite automaton-based engines (such as RE2 or Rust's regex crate), PCRE performs backtracking without a time limit by default.

Each HTTP request processed by the WAF began consuming 100% of a CPU core for as long as the matching attempt lasted. With real traffic arriving at hundreds of thousands of requests per second at each PoP, all cores on all servers in all data centers were saturated almost instantaneously. Cloudflare's own DDoS protection system — which depends on the same NGINX processes — stopped working. Legitimate traffic was dropped alongside malicious traffic.

This incident is pedagogically valuable precisely because Cloudflare had quality controls. The rule passed human code review. It passed an automated test suite. It passed a staging environment. And yet it reached global production carrying a catastrophic pattern. Why?

Human code review is effective for business logic, but detecting catastrophic backtracking in regex requires specialized knowledge in automata theory that is not universally distributed among engineers. The regex looked reasonable on visual inspection — it covered the intended XSS cases in the example tests.

Automated tests validated that the rule worked — that it detected the XSS payloads it was designed for. But the tests did not include pathological edge cases: long strings that almost match but don't, which are exactly the inputs that maximize backtracking. This is a classic gap: testing the happy path is not sufficient for security systems that process adversarial input.

Staging replicated the production configuration, but did not replicate traffic volume. With few requests per second, even a pathological regex may not be observable — the impact only becomes visible under real load. This is a common trap in performance testing: the staging environment rarely has the pressure needed to reveal algorithmic complexity problems.

Simultaneous global deploy was the architectural decision that turned a bug into a catastrophe. If Cloudflare had done a staged rollout — starting with 1% of PoPs, observing CPU metrics for 5 minutes, and only then progressing — the impact would have been contained. The absence of staged rollout for WAF changes is surprising given the industry's history with gradual deploys. The implicit justification was probably threat response speed: when you discover a new attack vector, you want immediate global protection. But that speed has a risk cost that this incident quantified painfully.

Cloudflare published a detailed post-mortem and implemented a substantial set of changes. I analyze each with the eye of someone who has operated edge systems at financial scale:

1. Regex engine replacement (PCRE → RE2/Rust)

The most important change. RE2 and Rust's regex crate guarantee O(n) complexity for any regular expression, eliminating the possibility of catastrophic backtracking by construction. This is not a mitigation — it is an elimination of the failure class. The trade-off is that RE2 does not support some PCRE features (negative lookahead, backreferences), which may require rewriting existing rules. For a WAF, this trade-off is clearly favorable: performance predictability outweighs regex expressiveness.

2. Static complexity analysis in CI

Tools like rxxr2 or automata-theory-based regex complexity analysis were added to the pipeline. Any regex that can exhibit super-linear behavior is rejected before merge. This is correct defense-in-depth: not relying solely on human review for properties that can be automatically verified.

3. Mandatory staged rollout for WAF changes

Rule deployments now follow a gradual rollout process: a subset of PoPs first, with automatic observation of CPU and latency metrics, before global progression. This is the correct standard for any change that affects the critical path of traffic processing.

4. Per-operation CPU limit for regex

Even with RE2, a per-WAF-operation timeout was added as an additional protection layer. If an operation exceeds a time threshold, it is aborted and the request is either passed (fail-open) or blocked (fail-closed) according to the configured policy. This is defense-in-depth: multiple independent layers.

5. Test case improvement

The test suite was expanded to include pathological inputs: long strings, strings that almost match, strings with character repetition. This should have existed from the start for a system that processes adversarial input.

The set of changes is exemplary. Cloudflare did not just fix the symptom (the specific rule) but attacked the root cause at multiple layers: the engine, the deploy process, the CI pipeline, and the tests. This is how a well-executed post-mortem should result in action.