Catastrophic Backtracking

"Catastrophic Backtracking" is a pathological performance behavior of NFA-based, backtracking regex engines — the family that includes Perl, PCRE, Java's java.util.regex, .NET, JavaScript, and Python's standard re module. When a pattern contains ambiguous repetition (nested quantifiers, or quantified alternations whose branches can match the same text), the engine may try every possible partition of the input before declaring failure. The number of partitions grows exponentially with the length of the candidate string, so a pattern that completes instantly on short input can hang for seconds, minutes, or longer on input only a few characters longer. The textbook example is the pattern "(a+)+b" applied to a string of "a" characters followed by something other than "b", such as "aaaaaaaaaaaaaa!". The inner "a+" and outer "+" can divide the run of a's in many ways, all of which the engine explores before concluding no "b" exists. Twenty a's already produce more than a million paths; thirty produce more than a billion. The same shape appears in real-world patterns whenever ".*" sequences or alternations overlap. The bug is the basis of regular expression denial of service (ReDoS), in which an attacker submits short, crafted input that pins a server's CPU. Its highest-profile incident was the Cloudflare 2019 Outage: on 2 July 2019 a new web application firewall rule containing the subpattern ".*.*=.*" was deployed globally and exhausted CPUs across Cloudflare's edge network, taking large parts of the web offline for about 27 minutes. Standard mitigations are to flatten nested quantifiers, use Atomic Group (Regex)s or possessive quantifiers, set matching timeouts, or switch to a non-backtracking engine such as RE2 (Regex Engine) that guarantees linear time.