TRE Regex Engine Python Bindings in Practice: Comprehensive Defense Against ReDoS Attacks

Background: Why a Regex Engine Used by Redis Deserves Attention

Simon Willison (renowned developer and creator of Datasette) recently shared an experimental study on the TRE regular expression engine. His reasoning was straightforward — if Redis creator antirez considered TRE good enough to integrate into Redis, then this regex engine developed by Ville Laurikari clearly deserves deeper exploration.

TRE is a lightweight C-based regular expression library. Its most prominent feature is support for approximate matching, and its design avoids the backtracking performance traps of traditional regex engines. Simon used Claude Code to build an experimental Python binding and conducted comparative tests specifically targeting ReDoS (Regular Expression Denial of Service) attacks.

Salvatore Sanfilippo (antirez), the creator of Redis, integrated TRE primarily to support fuzzy string matching capabilities. When making this technical choice, antirez valued several qualities of TRE: first, its pure C implementation with a small codebase aligns perfectly with Redis's engineering philosophy of lean efficiency; second, TRE's good POSIX compatibility and clean API design; most importantly, TRE's approximate matching functionality provides Redis with differentiated string processing capabilities. As one of the world's most widely used in-memory databases, Redis's technology selection decisions carry significant reference value — if an infrastructure project with extremely high performance and stability requirements chose TRE, that itself serves as a strong endorsement of TRE's quality.

ReDoS Attack Principles: How Regular Expressions Become Security Vulnerabilities

ReDoS (Regular Expression Denial of Service) is a denial-of-service attack that exploits the backtracking mechanism of regex engines. When regular expressions contain nested quantifiers or ambiguous branches, traditional backtracking-based NFA engines can fall into exponential time complexity.

To understand the root cause of ReDoS, you need to understand the two major schools of regex engines. DFA (Deterministic Finite Automaton) engines process each character of the input string only once, with strict O(n) time complexity, but don't support advanced features like backreferences, and building the DFA itself can consume significant memory (state explosion problem). NFA (Non-deterministic Finite Automaton) engines work by simulating multiple parallel paths, supporting richer regex syntax, but naive backtracking NFA implementations try all possible paths one by one when encountering ambiguous branches, producing exponential time overhead in the worst case. Among modern programming languages, mainstream languages including Perl, Python, Java, JavaScript, and Ruby almost all use backtracking NFA implementations for their built-in regex engines, meaning they all theoretically face ReDoS risks. Meanwhile, traditional Unix tools like awk and grep mostly use Thompson NFA or DFA implementations, making them naturally immune to such attacks. The historical root of this divide lies in the fact that backtracking NFA more easily implements backreferences and lookaround assertions — Perl-style extended syntax that is widely used in actual development.

A classic malicious regular expression like (a+)+$, combined with a carefully crafted input string, can freeze Python's standard library re module for seconds or even minutes. This type of vulnerability is especially dangerous in web applications — an attacker only needs to submit a specially constructed input to potentially spike server CPU usage to 100%.

In recent years, multiple well-known projects and platforms have been affected by ReDoS vulnerabilities, including several npm packages in the Node.js ecosystem, and that globally notable Cloudflare outage. On July 2, 2019, Cloudflare experienced a global service outage lasting approximately 27 minutes. The direct cause was a regular expression deployed to their WAF (Web Application Firewall) rule engine that triggered catastrophic backtracking. The regular expression (?:(?:\\\")+)+ caused CPU usage to spike to 100% under specific inputs, affecting all of Cloudflare's data centers worldwide. Since Cloudflare provides CDN and security protection services for millions of websites globally, the outage directly caused massive numbers of websites to become inaccessible. Cloudflare's post-mortem report detailed the root cause analysis, driving widespread industry attention to regex security and prompting more teams to evaluate backtracking-free engines like RE2 as alternatives.

TRE's Core Advantage: Backtracking-Free Design Eliminates Exponential Backtracking

The key reason TRE can defend against ReDoS attacks lies in its backtracking-free implementation.

Traditional regex engines (such as Python's re module, Java's java.util.regex) use backtracking NFA algorithms, with worst-case time complexity reaching exponential levels. TRE instead uses a TNFA (Tagged NFA) based algorithm that can complete matching in polynomial time, fundamentally eliminating the performance risks brought by backtracking.

The TNFA (Tagged Non-deterministic Finite Automaton) algorithm is an innovative method proposed by Ville Laurikari in his master's thesis. While traditional NFA needs backtracking to explore all possible matching paths when processing regular expressions, TNFA records sub-match position information by adding "tags" to the automaton's transition edges, thereby completing both matching and capture group extraction in a single traversal. This method has time complexity of O(n·m), where n is the input string length and m is the regex size — a fundamental improvement compared to the worst-case O(2^n) of backtracking engines. Notably, this approach shares lineage with the NFA simulation algorithm Ken Thompson proposed in 1968, but Laurikari's contribution was solving the historical difficulty of Thompson's algorithm in handling sub-match capture.

This means that regardless of how complex the regular expression is or how adversarial the input string might be, TRE's execution time remains within a predictable range. For applications that need to process untrusted input, the value of this property is self-evident.

The Experiment: Rapidly Building Python Bindings with Claude Code

What's noteworthy is not just the experimental conclusions, but Simon's experimental methodology itself. He used Claude Code (Anthropic's AI programming assistant) to build TRE's Python bindings, choosing Python's ctypes module to directly call TRE's C dynamic library.

Python's ctypes is a Foreign Function Interface (FFI) module in the standard library that allows Python code to directly call functions in C-language dynamic libraries (.so/.dll/.dylib) without writing any C extension code. It works by defining C function parameter types and return types at the Python level, then dynamically loading shared libraries and making function calls at runtime. Compared to traditional CPython C extensions (which require writing extensive boilerplate code, handling reference counting, and using the Python/C API) or tools like CFFI and SWIG, ctypes's advantage lies in zero compilation dependencies and an extremely low barrier to entry. However, its downsides are also clear: type safety must be manually ensured by the developer, call overhead is slightly higher than native C extensions, and mapping complex data structures can be cumbersome. For rapid prototype verification scenarios like Simon's, ctypes is the ideal choice.

This approach has several clear benefits:

• No need to write C extensions: ctypes allows directly calling functions in shared libraries from Python, bypassing the complex process of writing CPython extension modules
• Rapid prototype verification: With AI programming tools, going from idea to running demo can be completed in very short time
• Focus on core verification: The experiment's focus was verifying TRE's ReDoS defense capabilities, not building production-grade bindings

Test Results Comparison

Experimental results show that against various known malicious regex patterns, TRE's performance far exceeds Python's standard library re module. Python re hangs for extended periods when processing patterns like (a+)+$, while TRE returns results quickly, completely unaffected by backtracking traps.

Practical Implications and Regex Engine Selection Recommendations

Regex Engine Selection for Security-Sensitive Scenarios

For applications that need to process user-provided regular expressions (such as log analysis platforms, search engines, WAF rule engines), choosing a ReDoS-resistant regex engine is crucial. Current mainstream secure regex engines include:

• TRE: Supports approximate matching, validated by the Redis project. TRE's approximate/fuzzy matching capability allows specifying a maximum edit distance to find "approximately matching" strings, which is extremely useful in scenarios like spell correction, DNA sequence alignment, and fuzzy search.
• RE2: Developed by Google, widely deployed in production environments. RE2 was developed by Russ Cox, based on a hybrid strategy of DFA and NFA, achieving linear time complexity matching by building DFA states on-demand at runtime. To guarantee safety, RE2 deliberately foregoes support for certain regex features, including backreferences and lookaround assertions. This is a conscious engineering trade-off — choosing safety over feature completeness.
• Rust regex crate: Excellent performance with guaranteed safety. Rust's regex library adopts a design philosophy similar to RE2, also guaranteeing linear time complexity, but thanks to Rust's zero-cost abstractions and memory safety properties, it typically performs better in performance benchmarks.

Each has its own strengths: TRE excels in its unique approximate matching capability, RE2 excels in Google-scale production validation and extensive language binding ecosystem, and Rust regex leads in pure performance dimensions. Developers should make choices based on their specific scenario's functional requirements and technology stack.

New Workflows for AI-Assisted Security Research

This case also demonstrates the practical value of AI programming tools in security research. Simon used Claude Code to quickly set up the testing environment, freeing more energy for security verification and analysis rather than writing low-level binding code. This "AI-assisted rapid prototyping" pattern is tangibly changing security researchers' workflows.

The Current State of Regex Security in the Python Ecosystem

Python 3.11 introduced some regex performance improvements, but the standard library's re module is still based on a backtracking engine and fundamentally cannot completely avoid ReDoS risks. The community has alternatives like google-re2 available, and TRE, with its approximate matching capabilities and Redis-validated reliability, provides another option worth evaluating.

Conclusion

Although this experiment is modest in scale, it reveals an engineering decision point that's easy to overlook: in security-sensitive scenarios, the choice of regex engine directly affects system availability and security. TRE, as a long-validated C library, fundamentally solves the ReDoS problem through its backtracking-free design. For Python developers handling untrusted regex input, understanding and evaluating alternative engines like TRE and RE2 is a pragmatic step toward improving application security.

Key Takeaways

• TRE regex engine is based on the TNFA algorithm rather than traditional backtracking NFA, fundamentally defending against ReDoS denial-of-service attacks by reducing time complexity from exponential to O(n·m)
• Simon Willison used Claude Code to rapidly build TRE's Python bindings via ctypes for security testing
• Against malicious regular expressions, TRE's performance far exceeds Python's standard library re module
• TRE has been adopted by Redis, its reliability validated in large-scale production environments, and offers unique approximate matching capabilities
• Mainstream secure regex engines (TRE, RE2, Rust regex) each have different strengths; developers should select based on scenario requirements
• AI programming tools are changing security research workflows, enabling rapid prototype verification