Catastrophic Backtracking
The regex ^(a+)+$ matches aaaaaaaaaa in 6 units of PCRE2's match counter and rejects aaaaaaaaaa! in 2,560; in PCRE2, Python and JavaScript every extra a doubles the rejection, so ten more as cost about a thousand times as much, and PCRE2 gives up at 22 with a match-limit error.
- ▸For
(a+)+$in PCRE2, Python and JavaScript, a run ofas matches instantly; a near-miss likeaaaa!doubles the work with every extraa, because rejecting it means trying every split. - ▸The fuel is redundancy: when text can be split many equal ways, a backtracking engine tries them all before it can fail, unless a pre-check rules the input out first, as PCRE2 does for
.*.*=.*on text with no=. - ▸
.*.*=.*is Cloudflare's simplification of the WAF rule behind its 27-minute outage on July 2, 2019. Its two overlapping.*grow the work polynomially, not by doubling (in PCRE2 on inputs that match, in Python and JavaScript whether it matches or not), so the danger is overlap, not the(a+)+spelling.
Take ^(a+)+$, a pattern that accepts a line of nothing but as. Feed it aaaaaaaaaa and it says yes before you can blink. Now feed it aaaaaaaaaa!, the same ten as with one stray character on the end. The string is one symbol away from matching, yet the no costs 2,560 units on PCRE2's match counter against 6 for the yes, and in PCRE2, Python and JavaScript every a you add doubles it. Saying yes is cheap. Saying no to an input that came *close* is what costs, and that gap is the whole story.