How Regex Engines Actually Match: Backtracking vs. Finite Automata (and Why "Catastrophic Backtracking" Happens)

Most regex engines in everyday use, PCRE, and the engines built into Python's re module, Java, .NET, and JavaScript, work by backtracking. Matching proceeds by trying one possible way to satisfy the pattern, and if that path fails partway through, the engine backs up to the last point where it had another option and tries that instead, repeating until it finds a match or exhausts every possibility. This is what lets these engines support features like backreferences, matching whatever an earlier group captured, and lookahead or lookbehind assertions, since backtracking can express essentially any pattern you can describe, at the cost of not guaranteeing how long that search takes.

That cost is where catastrophic backtracking comes from. Certain patterns, classically something like nested or overlapping quantifiers, such as (a+)+b matched against a long string of a's with no trailing b, create an exponential number of ways to partition the input among the repeated groups. The engine tries combination after combination, backtracking through nearly all of them before concluding there is no match at all, and what should be a fast check instead pegs a CPU core for seconds, minutes, or effectively forever on a long enough input. This is a real, exploitable failure mode, it is the basis of ReDoS, regular expression denial of service, attacks against services that run untrusted input through a vulnerable pattern.

The alternative is an automata-based engine, the approach RE2, and the regex engines built into Rust and Go, takes. Instead of trying possibilities at match time, these engines compile the pattern ahead of time into a finite automaton, conceptually an NFA that gets simulated, or converted to a DFA, so that every character of input is examined roughly once, tracking every possible match state simultaneously rather than trying them one at a time and backing up. This guarantees matching runs in time proportional to the length of the input, with no pathological blowup, regardless of the pattern.

The catch is that automata-based matching cannot express everything a backtracking engine can. Backreferences and lookaround assertions require remembering what matched earlier or checking context outside the current position in ways that do not fit cleanly into a state machine that only tracks which states are currently possible. That is a real, permanent trade-off, not a temporary limitation: automata-based engines like RE2 explicitly refuse to support those features in exchange for their speed and safety guarantees, while backtracking engines keep the fuller feature set and put the burden of avoiding pathological patterns on whoever writes the regex.