Regex was built in 1968 to never hang, and the engines in Python, Java and Perl that can freeze on (a+)+$ walked away from it

Regular expressions have a famous way of going wrong. Hand a backtracking engine a pattern like (a+)+$ and the wrong short string, and the program sits there burning a CPU core. Security teams call it ReDoS. Cox’s 2007 article calls the underlying problem a failure to use “good theory.”

The theory is old. Thompson described it in the June 1968 issue of Communications of the ACM, volume 11, issue 6, pages 419 to 422. Cox’s history section says Thompson’s implementation “was for his QED editor running on the CTSS operating system on the IBM 7094,” and that it “creates IBM 7094 machine code.” In Cox’s words, “the states of the NFA were represented by small machine-code sequences, and the list of possible states was just a sequence of function call instructions.” Put simply, the pattern was compiled into a program, and that program tracked every place the match might be at once.

That is the trick. A backtracking engine picks one option, runs ahead, and goes back to try another when it fails. A Thompson-style engine “advances all the states along all the arrows that match the letter,” so each character of the text is visited once. The match time follows the text, not the cleverness of the pattern.

Cox put numbers on it. On the pattern a? repeated n times followed by a repeated n times, matched against n copies of a, “Perl requires over sixty seconds to match a 29-character string.” The Thompson implementation “requires twenty microseconds,” which Cox calls “a million times faster than Perl.” At 100 characters, the automaton finishes in under 200 microseconds, where “Perl would require over 10^15 years.” He lists Perl, PCRE, Python and Ruby as using recursive backtracking, and says Java does too, because its java.util.regex interface requires it.

The twist is who stopped using it. Cox notes that Thompson himself did not put the method into ed in 1971 or grep in 1973, both of which “used recursive backtracking!” His verdict on the result: “Today, regular expressions have also become a shining example of how ignoring good theory leads to bad programs.”

There is a price for the fix, and Cox names it. Backreferences, the \1 that matches whatever group one matched, are the feature that forces backtracking: “no one knows how to implement regular expressions with backreferences efficiently.” Engines that never had backreferences had no reason to give up the 1968 method.

What happened to the second half of the name, “regular”? Whether the word’s trail through Kleene’s 1956 nerve-net paper runs the way the usual retelling says is a claim this piece could not check against Cox, who doesn’t cover it.

My money says the next regex security advisory will be the same story with a new library name on it. The cure has been sitting in a 1968 journal for fifty-eight years.

Twenty microseconds against a minute.