catastrophic backtracking

Most of the time a regex match feels instant, so it is a shock when one pattern on a slightly longer input suddenly hangs for seconds, minutes, or forever. Catastrophic backtracking is the name for this trap: a backtracking regex engine getting lost in an astronomical number of ways to try matching, when in fact no match exists.

It happens when a pattern lets the same input be split among repetition operators in many overlapping ways, classically nested or adjacent quantifiers like (a+)+ or (a|a)*. Faced with a long run of a's followed by a character that prevents a final match, the engine tries one division of the a's among the repetitions; that fails at the end; it backs up and tries another division; that fails too; and the number of divisions to try grows exponentially with the input length. So a 30-character string can force on the order of 2^30 attempts, freezing the program. The engine is not buggy; it is faithfully exploring a search tree that happens to be exponentially large.

This matters for real systems: a carelessly written pattern handling untrusted input becomes a denial-of-service vulnerability (often called ReDoS), where an attacker submits a short crafted string to exhaust the server. The honest framing is that this is a property of backtracking engines plus certain patterns, not of regular languages themselves: an automaton-based engine (Thompson NFA or DFA, as in RE2 or grep) matches the same truly-regular patterns in guaranteed linear time and cannot catastrophically backtrack. The fixes are to avoid ambiguous nested quantifiers, use atomic groups or possessive quantifiers, or switch to a linear-time engine.