On 2 July 2019, a single regular expression pushed CPU utilization to nearly 100% across Cloudflare’s entire HTTP/HTTPS serving fleet, worldwide, and held it there. No attacker was involved. No traffic spike, no zero-day, no malformed packet — just a new firewall rule containing a sub-pattern that a backtracking engine could not evaluate in reasonable time. The failure has a name, catastrophic backtracking, and it is not a bug in any of the software that failed. It is a property of the algorithm that almost every production regex engine on earth uses, and it has been avoidable since 1968.
That last part is the interesting one. A linear-time matching algorithm for regular expressions was published in Communications of the ACM the year before Unix existed, by the person who would go on to write Unix. The industry adopted the other one anyway — deliberately, in exchange for features it wanted more. Thirty years later the bill arrived, and it arrived at the edge of the internet.
What Actually Happened on 2 July 2019
The headline number in the title is a figure of speech, and it is worth retiring immediately. Cloudflare’s postmortem, written by CTO John Graham-Cumming, makes no claim about a percentage of the internet. What it does contain is measurable, and worse than a percentage:
- 13:42 UTC — a new managed rule for the Web Application Firewall is deployed globally.
- 13:45 UTC — the first alert fires. CPU is approaching 100% across the HTTP/HTTPS fleet, in every location.
- 14:07 UTC — the WAF is killed globally, restoring service. Elapsed: roughly 27 minutes.
- 14:52 UTC — the WAF is re-enabled after the offending rule is fixed.
During the incident, traffic across Cloudflare’s network dropped by roughly 80%. Not degraded — gone, because the machines that were supposed to be proxying it were busy evaluating a regular expression.
The rule itself was a cross-site-scripting rule targeting inline JavaScript. The offending fragment was .*(?:.*=.*) — a .* nested inside a .*, with a non-capturing group in between. This detail matters more than it looks, because there is a persistent and confident claim across secondary write-ups that the rule targeted SharePoint CVE-2019-0604. That attribution does not appear anywhere in Cloudflare’s own postmortem. The postmortem describes an inline-JavaScript XSS rule and prints the pattern. Cite the postmortem.
| Claim | Status |
|---|---|
| The rule was an inline-JavaScript XSS rule | In the postmortem. With the pattern printed: .*(?:.*=.*) |
| The rule targeted SharePoint CVE-2019-0604 | Not in the postmortem. Widely repeated in secondary coverage; do not carry it forward |
| The WAF was globally unavailable for ~27 minutes | In the postmortem. 13:42 deploy → 14:07 global kill |
| Traffic dropped ~80%; CPU near 100% fleet-wide | In the postmortem |
| The engine was PCRE | In the postmortem |
| An attack caused it | False. It was a routine rule deployment |
And here is the part that gets skipped in the retellings, which is the part an architect should actually take away. Two independent safety failures compounded to turn a slow regex into a global outage. A guard that limited how much CPU a single regex evaluation could consume had been removed by mistake during a WAF refactoring weeks earlier. And this class of rule deployed globally in one step, bypassing the staged rollout that would have caught it in a single location. The regex was the trigger. The missing budget and the absent canary were the outage.
The Mechanism: Why Nested .* Detonates
A backtracking engine evaluates a pattern by walking one candidate path at a time and, when a path fails, returning to the most recent decision point to try the next alternative. That is a depth-first search of the match tree. If the number of distinct paths grows exponentially with input length, the search does too.
Cloudflare’s postmortem works this through with a simplified version of its own pattern, .*.*=.*. Against x=x, the match takes 23 steps. Against x= followed by twenty x characters, it takes 5,353 steps — and each additional character roughly doubles the work. That is the whole disaster in one sentence: a linear increase in attacker-influenced input length produces a geometric increase in server work.
The canonical laboratory example is ^(a+)+$. Fed a string of n a characters followed by a single character that is not an a — say aaaaaaaaaa! — the pattern cannot match. But before it can report that, a backtracking engine must prove it, and the only way it knows to prove it is to try every way of dividing that run of as among the repeated groups. The number of ways to split a run of n identical characters into one or more non-empty groups is 2^(n−1).
Input: n as + one non-matching char | Backtracking paths to exhaust — 2^(n−1) | Thompson NFA simulation (∝ n × pattern size) |
|---|---|---|
| 10 | 512 | ~50 state-set updates |
| 20 | 524,288 | ~100 |
| 25 | 16,777,216 | ~125 |
| 30 | 536,870,912 | ~150 |
| 35 | 17,179,869,184 | ~175 |
| 40 | 549,755,813,888 | ~200 |
Forty characters. Not forty kilobytes — forty bytes, which fits in a URL path, a User-Agent header, a JSON field, or a form input, and which no rate limiter on earth will flag as abusive. The non-matching case is the dangerous one, which is deeply counterintuitive: the engine is fast when it finds a match early and pathological when it has to prove a negative.
Russ Cox’s Regular Expression Matching Can Be Simple And Fast gives the measured version of the same shape, using a?ⁿaⁿ against a string of n as. At n = 29, Perl needs over 60 seconds; a Thompson NFA simulation needs about 20 microseconds — roughly a million times faster. At n = 100, the NFA finishes in under 200 microseconds, and Perl would need more than 10¹⁵ years.
The Algorithm That Was Already Published in 1968
The fix predates the problem by five decades. Ken Thompson’s Programming Techniques: Regular Expression Search Algorithm, CACM 11(6), June 1968, pp. 419–422, describes a matcher that never backtracks.
The idea is to stop asking “does this path match?” and start asking “which states could I be in right now?” Instead of walking one path at a time, the simulation advances a set of NFA states in lockstep, consuming one input character per step. An n-state NFA can encode 2ⁿ distinct paths, but it can only ever be in some subset of n states at any single position in the input. Tracking the set instead of the paths collapses the exponent. Cost becomes proportional to length(text) × length(pattern) — linear in the input, always, for every pattern, with no pathological cases to discover in production.
Three points of provenance matter here, because all three are routinely mangled:
- Regular expressions are not a Unix invention, and neither is the theory. Stephen Kleene defined “regular events” in RAND memorandum RM-704, Representation of Events in Nerve Nets and Finite Automata, December 1951, republished in Automata Studies (Princeton University Press, 1956). The subject was McCulloch–Pitts nerve nets, not text search. Rabin and Scott introduced nondeterministic finite automata in 1959; Cox credits McNaughton & Yamada (1960) and Thompson (1968) with the first regex-to-NFA constructions.
- Thompson’s paper predates Unix. It was written for Thompson’s QED editor running on CTSS on an IBM 7094. Unix started on a PDP-7 in 1969. Regular expressions were imported into Unix by someone who already had them working elsewhere — they were not invented for it.
- The 7094 implementation compiled the regex to machine code — the paper’s own description is a compiler that “accepts a regular expression as source language and produces an IBM 7094 program as object language.” It is one of the earliest documented cases of generating code at runtime for speed, and it is cited in JIT genealogies (Aycock, A Brief History of Just-In-Time, ACM Computing Surveys 35(2), 2003). Calling it “the first JIT” overstates the record; the survey literature calls it an early ancestor, and that is the phrase to use.
The Reversal: Unix Had the Fast Algorithm and Didn’t Use It
The tidy version of this story — Thompson invents the fast algorithm, Unix ships it, the world later regresses — is wrong, and the true version is far more useful.
Per Cox’s history, early Unix ed and grep used recursive backtracking anyway, despite Thompson having published the linear-time method himself. grep is literally an ed command promoted to a program — g/re/p, global / regular expression / print — created 3 March 1973 and present in the Version 4 manual of November 1973, extracted because ed loaded whole files into memory and choked on large inputs. It inherited ed‘s backtracking matcher.
The DFA came back later, and from someone else. egrep and fgrep are Alfred Aho’s work, written around 1975 and shipped in Seventh Edition Research Unix (1979) — egrep was the first Unix tool to run full extended syntax (+ ? |) on a precomputed DFA, while fgrep dropped regular expressions entirely in favour of Aho–Corasick multi-pattern matching. Eighth Edition (1985) built the DFA on the fly. And in the early 1980s Rob Pike implemented an efficient NFA simulation with submatch tracking for the sam editor — the thing everyone would later claim was impossible without backtracking — and per Cox it went unnoticed.
So the sequence is: correct algorithm published, ignored by its own author’s operating system for six years, reintroduced by a different researcher, extended by a third, and then comprehensively out-competed by a design that threw it away again. Publication is not adoption. An algorithm that exists in the literature and not in the default toolchain is, for engineering purposes, an algorithm that does not exist — and “we already solved this in the seventies” is a sentence that should always be followed by “so why is nobody running it?”
What Perl Bought, and What It Cost
Backtracking did not win by accident or by ignorance. It won because it can do things a finite automaton structurally cannot.
Capturing groups with leftmost-first semantics, arbitrary lookahead and lookbehind, and above all backreferences — (a+)\1, “match that same text again” — are all natural in a path-walking engine and all extremely awkward or impossible in a state-set simulation. Backreferences in particular are not a convenience feature with a performance footnote. They move the matched language outside the regular languages entirely. Matching with backreferences is NP-complete; as Cox puts it, solving it efficiently would be worth a million-dollar prize.
This is the trade, stated precisely: the industry exchanged a complexity-class guarantee for expressiveness, and complexity classes are a one-way door. A safe engine cannot simply add backreferences later, because the property that makes it safe is exactly the property that forbids them.
The vehicle for that trade in production was PCRE — Philip Hazel, summer 1997, originally written for the Exim mail transfer agent, later embedded nearly everywhere. PCRE2 forked in 2015 with a revised API; PCRE1 gets bug fixes only, so “PCRE” in a modern codebase almost always means PCRE2. Cox names the backtrackers plainly: Perl, Python, PHP, Ruby, Java, PCRE. That is not a fringe minority. That is most of the regular expressions being evaluated on the internet right now, including the one that took Cloudflare down.
ReDoS Is a Weakness Class, Not a Bug
MITRE catalogues this as CWE-1333, Inefficient Regular Expression Complexity, and its highest-effectiveness mitigation is blunt and architectural rather than advisory: “Use regular expressions that do not support backtracking, e.g. by removing nested quantifiers.” Observed instances include CVE-2020-5243, CVE-2021-21317 and CVE-2019-16215 — user-agent parsers and markdown parsers, which is to say ordinary library code sitting directly in front of untrusted input. The current academic survey is Davis et al., SoK: A Literature and Engineering Review of Regular Expression Denial of Service (arXiv:2406.11618).
The other production case worth knowing is Stack Exchange’s outage of 20 July 2016, because it undercuts the comfortable assumption that only exponential blowups are dangerous. A whitespace-trimming regex, ^[\s]+|[\s]+$ (whitespace plus a zero-width non-joiner), met a post containing roughly 20,000 consecutive spaces that were not at the end of the string. Restarting the scan at each position produced 20,000 + 19,999 + … + 1 ≈ 199,990,000 character-class checks. That is O(n²), not exponential — and merely quadratic was enough to take the site down. The fix was not a cleverer regex; it was replacing the regex with a substring operation.
RE2 and the Engines That Cannot Blow Up
RE2 is Russ Cox’s answer, and its origin explains its design. It came out of Google Code Search, started summer 2006, where users supplied the regular expressions — making the worst case an obvious, immediate attack surface rather than a theoretical one. It was open-sourced in March 2010.
RE2 uses both a DFA and an NFA simulation, never backtracks, and guarantees linear-time matching. It selects among four matching strategies depending on how much submatch information the caller actually needs, and it operates inside a memory budget — roughly 1 MB per RE2 object by default — discarding cached DFA states to stay within it. It deliberately omits backreferences and arbitrary lookaround, because it “disallows PCRE features that cannot be implemented efficiently using automata.” That is an unusually clean case of a safety property outranking expressiveness in a feature decision.
It is not free, and Cox’s own accounting says so: RE2 compiles 3–4× slower than PCRE (roughly 10–24 µs versus 4–6 µs) and uses about 10 KB per regexp against PCRE’s ~0.5 KB. What you buy is not average-case speed. It is a worst case you can put in a capacity plan.
| Backtracking engines | Finite-automata engines | |
|---|---|---|
| Examples | PCRE2, Perl, Python re, Java java.util.regex, JavaScript, .NET Regex (default) | RE2, Go regexp, Rust regex, .NET RegexOptions.NonBacktracking |
| Method | Depth-first search of the match tree, one path at a time | Advance a set of reachable states, one input character at a time |
| Worst case | Exponential in input length for some patterns | Linear in input length, for every pattern |
| Backreferences | Yes | No — they take the language out of the regular class |
| Arbitrary lookaround | Yes | No (or heavily restricted) |
| Submatch capture | Yes, leftmost-first | Yes — RE2 supports both POSIX leftmost-longest and Perl leftmost-first |
| Compile cost / memory | Cheap (~4–6 µs, ~0.5 KB per pattern for PCRE) | Higher (~10–24 µs, ~10 KB per pattern for RE2) |
| Built-in blast radius control | Only if you set it: PCRE2 pcre2_set_match_limit / pcre2_set_depth_limit; .NET match timeout | Not needed for backtracking — but RE2’s DFA cache is still budgeted |
| Safe against attacker-supplied patterns | No | Yes, by construction |
Cloudflare’s own remediation is the strongest available evidence for which side of that table matters under load. They moved off PCRE to an RE2-inspired DFA engine, and today run the Rust regex crate, reporting roughly 40% lower average WAF processing time and ~4.3% lower edge CPU, with the p95 and p99 outliers compressed — exactly what a linear-time guarantee predicts, since a guarantee’s first visible effect is always on the tail, not the mean.
Go’s regexp package and the Rust regex crate both descend from this line and both state a linear-time guarantee in their own documentation. Neither supports backreferences. That is not an omission the maintainers intend to fix; it is the guarantee, restated as a feature list.
The Audit You Can Run This Week
This is a bounded exercise, and it produces a real answer rather than a vague sense of exposure.
1. Identify which engine each regex actually runs on. “Regex” is a dialect family, not a language — POSIX BRE, POSIX ERE, PCRE2, RE2, JavaScript, Java and Go differ in escaping, in whether backreferences exist, and most subtly in which match wins. The pattern a|ab against ab yields ab under POSIX leftmost-longest rules and a under Perl’s leftmost-first rules — same pattern, same input, different answer, no bug on either side. The normative text is POSIX.1-2024 / The Open Group Base Specifications Issue 8, Chapter 9, which is free to read in full. An API that accepts “a regular expression” without naming the engine has an undocumented behaviour surface.
2. Map where untrusted input reaches a regex — the subject and the pattern.
| Surface | Who controls it | Typical exposure |
|---|---|---|
| Request headers, paths, query strings, bodies | The caller | Any WAF rule, router, or validation layer |
| User-generated content in a parser | The author | Markdown, BBCode, user-agent, log parsers — the CWE-1333 examples |
| Search / filter fields that accept patterns | The caller | Attacker-supplied pattern, the worst case |
| Config, rule feeds, and dependency-supplied patterns | A third party, or your own deploy pipeline | Cloudflare, 2 July 2019 |
| Generated patterns (built from user data at runtime) | Both | Escaping bugs plus complexity bugs at once |
If the caller controls the pattern, only a non-backtracking engine is a defensible answer. Timeouts on an attacker-chosen pattern are a rate limit on your own CPU, not a fix.
3. Set a limit wherever you cannot swap the engine, and know what the limit is worth. .NET is the outlier among the mainstream backtrackers: System.Text.RegularExpressions.Regex accepts a match timeout, and since .NET 7 also offers RegexOptions.NonBacktracking, which trades backreferences and lookaround for a linear-time guarantee — Microsoft’s own best-practices guidance treats setting a timeout as the default posture. PCRE2 exposes pcre2_set_match_limit and pcre2_set_depth_limit, which exist precisely because the engine can blow up. Java’s java.util.regex has no timeout and no step limit at all — the only containment is running the match on a thread you are prepared to abandon, which leaks a thread per attack. A timeout converts an availability failure into a correctness failure: the match returns nothing, and you need a decided answer for what the caller does then. “Fail open” on a security rule is how a DoS becomes a bypass.
4. Reject “just write a better pattern” as the remediation. It is the most common conclusion drawn from these incidents and it does not survive contact with the failure mode:
- The dangerous patterns do not look dangerous.
.*(?:.*=.*)has no textbook nested quantifier in it. Stack Exchange’s was a trim regex. Neither would have been flagged in review by anyone not specifically hunting for this. - It is an unbounded, permanent review obligation with no failing test. Every engineer, every pattern, every change, forever — and the failure only appears against inputs nobody wrote a test for.
- You do not write most of your regexes. They arrive in dependencies, rule feeds, framework validators, and generated code.
- A safe pattern is a hope; a safe engine is an invariant. Only the engine can offer a worst-case bound, and a bound is the thing you can actually put in a runbook.
- Cloudflare’s own fix was an engine swap, not a rule rewrite. They had the best possible motivation to conclude “write better rules,” and did not.
5. Then go find the guardrail nobody noticed was gone. The most transferable lesson from 2 July 2019 has nothing to do with regular expressions: a CPU-consumption guard had been quietly deleted during a refactor, and the staged rollout that should have caught the rule was bypassed. The useful post-incident question is never “who wrote the bad pattern.” It is “which safety limit was silently removed, and what test would have failed when it was?” A guardrail with no test asserting its presence is a guardrail with a scheduled expiry date.
❓ Frequently Asked Questions
What is catastrophic backtracking, in one sentence?
It is the exponential blow-up that occurs when a backtracking regex engine has to exhaust every possible way of dividing an input among repeated groups before it can conclude that the pattern does not match. The engine is doing exactly what it was designed to do — depth-first search of the match tree — and the number of branches simply grows faster than the input does.
Is catastrophic backtracking a bug in PCRE or Perl?
No, and treating it as one leads to the wrong fix. Backtracking is a deliberate design choice that buys capturing groups with leftmost-first semantics, lookaround, and backreferences — features a finite-automaton engine structurally cannot provide, since backreferences take the matched language outside the regular languages and make matching NP-complete. The exponential worst case is the price of those features, documented and understood since long before PCRE existed.
Why doesn’t everyone just use RE2, Go, or Rust?
Because the guarantee costs real features and real resources. Non-backtracking engines cannot offer backreferences or arbitrary lookaround, so migrating is a rewrite of every pattern that uses them, not a configuration flag. RE2 also compiles 3–4× slower than PCRE and uses roughly 10 KB per pattern against PCRE’s ~0.5 KB. What you get in exchange is a worst case that does not depend on the input — which is why the engines that face attacker-supplied patterns, Google Code Search and Cloudflare’s WAF among them, all ended up on this side.
Can a timeout make a backtracking engine safe?
It makes it survivable, not safe. A Regex match timeout in .NET or a pcre2_set_match_limit in PCRE2 caps the damage a single evaluation can do, which is genuinely worth having and is what Cloudflare had removed by accident. But it converts an availability failure into a correctness failure — the match aborts, and you need a decided answer for what happens next. If the regex was a security rule and the fallback is “allow,” an attacker has just converted a denial of service into a filter bypass.
Which mainstream languages ship no protection at all?
Java’s java.util.regex has no match timeout and no step limit; the only containment is running the match on a thread you are willing to abandon. Python’s re, Perl, PHP, Ruby and JavaScript engines are all backtrackers as well. .NET is the notable exception among the mainstream backtrackers: it accepts a match timeout and, since .NET 7, offers RegexOptions.NonBacktracking for a linear-time guarantee at the cost of backreferences and lookaround.
Does a slow regex really need an exponential blow-up to cause an outage?
No — and this is the assumption most worth discarding. Stack Exchange’s 2016 outage came from an O(n²) whitespace-trimming pattern meeting a post with about 20,000 consecutive spaces, producing roughly 199,990,000 character-class checks. Merely quadratic was sufficient. Any super-linear relationship between attacker-controlled input length and server work is a capacity problem waiting for someone to notice it.
How much of the internet did the Cloudflare outage actually take down?
The postmortem does not make that claim, and neither should anyone citing it. What it reports is specific and verifiable: CPU near 100% across Cloudflare’s HTTP/HTTPS fleet worldwide, traffic across the network down roughly 80%, the WAF globally disabled at 14:07 UTC after a 13:42 deploy — about 27 minutes — and full restoration at 14:52. Those numbers are more than dramatic enough without a percentage attached to them.
📚 Further Reading
- Learning the Brilliance of Graph Theory: From Mazes to Complex Networks — an NFA is a directed graph, and the difference between backtracking and Thompson’s simulation is exactly the difference between depth-first path exploration and advancing a frontier.
- Learn the Typescript Algorithm for Two Sum Solution — the same underlying move in miniature: changing the complexity class of an operation rather than optimising the inner loop of the slow one.
- Prompt Injection Explained: The #1 AI Security Risk — the modern instance of the same structural problem, where untrusted input reaches a powerful interpreter that has no notion of where the data ends.
- Why reCAPTCHA and Why Should I Protect My Site? — the wider question of what belongs at the edge, and what it costs when the thing filtering your traffic becomes the thing consuming it.
- DNS Security Issues, Vulnerabilities, and Exploits — the other place where a single misconfigured layer of shared internet infrastructure takes an unrelated fraction of the web with it.
📚 Recommended Resources
Disclosure: some links below are Amazon affiliate links. If you buy through them, I earn a small commission — at no extra cost to you — which helps keep this site running.
Before any of these: the two most useful documents on this subject are free. POSIX.1-2024 / The Open Group Base Specifications Issue 8, Chapter 9 is the normative definition of BRE and ERE, including the leftmost-longest rule in its own words — the text to quote when an argument about dialect behaviour needs settling. And Russ Cox’s four-part regexp series at swtch.com is the authoritative modern treatment of everything in this article: the NFA-versus-backtracking split, RE2’s design and its honest costs, and the trigram-index work that followed. Read both before buying anything.
The Practice of Programming
Brian W. Kernighan & Rob Pike · Book
The best on-ramp from “I use regular expressions” to “I understand what the engine is doing.” Its chapter on notation builds a compact regular-expression matcher from scratch and walks the code line by line — a few dozen lines that make the recursive, path-at-a-time structure of a backtracking matcher concrete in a way no diagram does. Pike is also the author of the sam NFA simulation this article covers, which makes the treatment first-hand.
The Art of Software Security Assessment
Mark Dowd, John McDonald & Justin Schuh · Book
The methodology book for the audit at the end of this article. It is not about regular expressions specifically; it is about systematically finding where untrusted input reaches something that was not designed to survive it, in a codebase you did not write. That is exactly the exercise CWE-1333 demands, and this is the standard reference for doing it rigorously rather than by intuition.
Practical UNIX & Internet Security (3rd ed.)
Simson Garfinkel, Gene Spafford & Alan Schwartz · Book
Older than the ReDoS literature and still the clearest statement of the underlying posture: availability is a security property, resource exhaustion is an attack, and the guard you removed during a refactor was load-bearing. Grade the specific tooling as dated; the threat-modelling reasoning has not aged.
The Unix Programming Environment
Brian W. Kernighan & Rob Pike · Book
The contemporary account of the ed → grep → sed → egrep → awk toolchain this article’s history section runs through, written by people who were in the building. The tools are dated; the thinking about what a pattern language is for, and where matching belongs in a pipeline, is not.
UNIX: A History and a Memoir
Brian W. Kernighan · Book
The primary-source memoir for how grep came out of ed, why Thompson’s tools took the shape they did, and how research at Bell Labs actually proceeded — including the oral-history version of the grep origin story that circulates online in much less careful form. The single best history rung available for this material.