The regex that took down the site

In July 2019 Cloudflare took down a large part of its network with a single regular expression. The pattern was deployed to a WAF rule, and one clause in it could backtrack exponentially. CPU across the fleet went to 100 per cent. The pattern looked entirely ordinary.

Why backtracking exists

Most regex engines, including JavaScript's, are backtracking engines. When a quantifier can match in more than one way, the engine tries one, continues, and if the rest of the pattern fails it returns and tries a different split. For most patterns this is a handful of attempts. For some it is astronomically more.

The shape to recognise

// A repeated group that itself contains a quantifier.
/^(a+)+$/.test("aaaaaaaaaaaaaaaaaaaaaaaaaaaaX");

There are many ways to divide a run of a characters between the inner a+ and the outer +. Because the string ends in X, the overall match must fail — but the engine can only conclude that after trying every division. Each additional a doubles the work. At about thirty characters this stops being instant; at forty it will outlive your patience.

The dangerous input is not the one that matches. It is the one that almost matches and then fails at the very end, forcing the engine to exhaust every possibility before giving up.

The patterns that bite in practice

• Email validators built from (\w+\.)+ — a long dotted local part with an invalid domain is the worst case
• Nested optional groups such as (a|a?)+
• Multiple .* segments in one pattern, each of which can absorb a different amount of text
• Trimming with ^\s+|\s+$ applied to a long line of whitespace that then fails to end as expected

Why it becomes a denial of service

It matters most when the pattern runs against untrusted input. A form field validated with a vulnerable email regex means anyone can send a forty-character string and occupy a CPU core for minutes. On Node.js, where request handling is single-threaded, that request blocks every other request the process was serving. A handful of them is an outage.

Fixing it

Remove the ambiguity

Rewrite so that only one division of the input is possible. Replacing (a+)+ with a+ matches exactly the same strings with no backtracking at all. Most catastrophic patterns are the result of adding a group that was never needed.

Use specific character classes

[^"]* cannot overlap with a following quote, so the engine never has a choice to reconsider. .* can absorb anything, including the delimiter you are looking for, which is what creates the branching in the first place.

Do not use a regex for structure

Email addresses, URLs, HTML and JSON all have parsers. RFC 5322 email validation by regular expression is a well-known folly — checking for an @ with something on either side, then sending a confirmation message, validates more than any pattern can.

Bound the input

Reject anything over a sensible length before it reaches the pattern. Exponential growth on a string capped at 100 characters is survivable; on an unbounded field it is not.

Testing for it

Feed the pattern a string of thirty to fifty repeating characters that fails at the end. If evaluation stalls, you have found one. Testing in a worker that can be terminated — as this site does — means the tab survives the experiment.