TRE regex engine shrugs off ReDoS attacks that choke Python's re module

Simon Willison built an experimental Python ctypes binding to Ville Laurikari’s TRE regex library after noticing antirez had pulled it into Redis. The motivation: TRE’s matching algorithm doesn’t backtrack, which makes it structurally immune to the catastrophic-backtracking patterns that turn Python’s built-in re into a denial-of-service vector.

Benchmarks bear this out. TRE chews through known-evil patterns against 10-million-character inputs faster than re handles the same patterns on tiny strings, and runtime scales linearly with input length rather than exponentially. For any service that compiles untrusted regexes or runs trusted regexes against untrusted input, that’s the difference between a bounded operation and a server-killing one.

The binding itself is minimal — a proof-of-concept Claude Code generated to demonstrate the robustness claim rather than a production library — but it points at a recurring lesson: ReDoS is an algorithmic-choice problem, not a tuning problem, and engines built on NFA simulation rather than backtracking sidestep the entire class of attacks.