[glangdale]

An interesting project would be to have a go at trying to automatically generate that malicious input. If I remember correctly, re2 has heuristics to see whether construction is "still worth it"; a particularly nasty input would stay just on the verge of "worth doing construction" but cost as much as possible (if you introduce too many novel states re2 will stop doing the construction at all).

DFA based engines are often relatively simple under the hood, and backtrackers (like modern JIT'd libpcre) may outrace them due to having optimizations.

Hyperscan (https://github.com/intel/hyperscan) a project I worked on for many years avoids the potential DoS attacks on backtrackers or the ones RE2 has, but surely has its own weak spots (notably, it assumes literal factors of the regular expression are rare in the input). We did build some mitigations to that, but fundamentally I bet Hyperscan could be made to slow down in a similar (linear) way to re2.