The Regex That Took Down Cloudflare for 27 Minutes

On July 2, 2019, Cloudflare's entire network hit close to 100% CPU across every edge server handling HTTP and HTTPS traffic. Sites went down globally for 27 minutes. A single regular expression did it.

The pattern

The category of pattern is well understood: nested quantifiers on the same character class — something structurally like (a+)+b — create exponential backtracking. Give a backtracking regex engine an input that almost matches but doesn't, and it tries every possible way to partition the string across those nested quantifiers before it gives up.

For an input of length n, that's roughly 2^(n-1) partitions to try:

Input length