Why a Regex Can’t Count: Chomsky’s Hierarchy and the Cloudflare Outage

The math that stops a regex from counting also lets it run in linear time; Cloudflare’s 2019 outage came from giving that up.

Three circles and a handful of arrows: a finite machine that knows whether any binary number, however long, is divisible by three. Figure by the author.

At 13:42 UTC on 2 July 2019, the servers that carry a large share of the world’s web traffic began answering requests with error pages. Cloudflare’s machines had run every processor core nearly to full load, and for the next 27 minutes visitors to millions of sites saw HTTP 502 errors. The cause, traced in the company’s postmortem, was a single new rule in its web-application firewall: a regular expression, pushed to Cloudflare’s servers worldwide in one step, whose troublesome core was the short fragment .*(?:.*=.*). The (?:…) only groups what it encloses, without recording what that part matched, so the fragment amounts to .*.*=.*: any text, more text, an equals sign, and more text after it.

Regular expressions ship with every mainstream programming language, and a few dozen characters of one can recognise a date, an email address or a credit-card number. Far fewer of the programmers who write them could say what a regex is underneath, or name a string that no regex could ever be written to recognise. The two questions turn out to have the same answer, and it comes from mathematics done in…