TRE Regex Engine: Python Bindings and ReDoS Defense in Practice

Background: When a Regex Engine Used by Redis Deserves Attention

Simon Willison (renowned developer and Datasette creator) recently shared his exploration of the TRE regular expression engine. Simon Willison is one of the co-creators of the Django Web framework, who later created Datasette—an open-source tool for exploring and publishing data that can instantly transform SQLite databases into interactive Web APIs and interfaces. He's well known in the developer community for actively sharing technical explorations and experiments, with a particular focus on practical applications of AI tools in development workflows.

The experiment originated from a simple observation—Redis creator antirez integrated Ville Laurikari's TRE regex engine into Redis. Redis (Remote Dictionary Server) is one of the world's most widely used in-memory data structure stores, extensively employed for caching, message queues, session management, and more. Its creator Salvatore Sanfilippo (known online as antirez) is renowned for his relentless pursuit of code quality and performance. Redis underwent a license change in 2024 (from BSD to RSALv2/SSPLv1), after which antirez became active in the community again, influencing Redis's technical direction. His choice to integrate TRE over other regex engines reflects a commitment to security and predictable performance. If it's good enough for Redis, it's worth a deeper look.

Simon had Claude Code build an experimental Python binding and tested TRE against malicious regular expression attacks (ReDoS). The results showed that TRE performs far better than Python's standard re module when facing such attacks.

What Is a ReDoS Attack?

The Hidden Killer in Regular Expressions

ReDoS (Regular Expression Denial of Service) is a denial-of-service attack that exploits flaws in regex engines. The core principle is that most programming languages (including Python, Java, and JavaScript) use regex engines based on backtracking algorithms. When encountering carefully crafted malicious input, the time complexity of backtracking can grow exponentially, causing prolonged CPU consumption.

Backtracking is the core mechanism NFA regex engines use when processing branches and quantifiers. When a regular expression has multiple possible matching paths, the engine chooses one path to attempt matching; if it fails, it "backtracks" to the previous decision point and tries another path. Under normal circumstances this strategy performs adequately, but when a regex contains nested quantifiers (like (a+)+) and the input string nearly but doesn't completely match, the number of possible paths can explode exponentially. For example, with an input of length n, the number of backtracks may reach 2^n—this is known as "catastrophic backtracking."

A classic example is the regex (a+)+$ matching the string aaaaaaaaaaaaaaaaX. Python's re module falls into catastrophic backtracking when processing such input, with execution time growing exponentially with input length. This is especially dangerous in web applications—an attacker only needs to submit a carefully crafted string to potentially bring a server to its knees.

Real-World Impact of ReDoS

ReDoS is not merely a theoretical threat—it has caused real production incidents. In 2016, Stack Overflow experienced a site-wide outage lasting approximately 34 minutes due to a single regex—one containing nested quantifiers that triggered catastrophic backtracking when processing whitespace strings of certain lengths. In 2019, Cloudflare's global CDN service suffered CPU exhaustion due to a regex in a WAF rule, causing approximately 27 minutes of global service disruption. The npm ecosystem has also seen multiple discoveries of regex libraries with ReDoS vulnerabilities, affecting tens of thousands of downstream projects. These cases demonstrate that even experienced engineering teams can make mistakes regarding regex security.

Why Python's Standard Library Is Vulnerable to ReDoS

Python's re module uses an NFA (Nondeterministic Finite Automaton) + backtracking implementation. This approach supports rich regex features (such as backreferences), but the tradeoff is extremely poor worst-case performance.

From a computational theory perspective, regex engine implementations fall into two main camps: NFA-based backtracking implementations and DFA (Deterministic Finite Automaton) based deterministic implementations. NFAs and DFAs are equivalent in expressive power—any NFA can be converted to an equivalent DFA. However, NFA-to-DFA conversion may cause exponential state growth (the state explosion problem). Ken Thompson's 1968 Thompson construction provides an efficient NFA simulation algorithm that can complete matching in O(mn) time (where m is the regex length and n is the input length)—this is precisely the theoretical foundation for engines like TRE and RE2. Python's re module chose the backtracking route to support more features, which creates serious security vulnerabilities in scenarios where regex input is user-controlled.

In practice, pure DFA implementations face the state explosion problem—when converting NFA to DFA, the number of states can, in the worst case, grow from n to 2^n. Therefore, modern non-backtracking engines typically employ hybrid strategies: Lazy DFA builds DFA states on demand, only computing state transitions when actually encountered, and caches computed states. When the cache reaches its limit, some states are discarded and recomputed. Both RE2 and Rust regex use this strategy. TRE employs the Tagged NFA simulation algorithm proposed by Laurikari in his doctoral thesis, which attaches tags to NFA states to track sub-match positions, avoiding DFA state explosion while maintaining linear time complexity. This approach represents an elegant compromise both theoretically and in engineering.

TRE Engine: A Non-Backtracking Design Philosophy

Core Advantages of TRE

TRE is a POSIX-compatible regular expression library developed by Finnish developer Ville Laurikari. Its most critical design decision is not using backtracking algorithms. TRE is based on deterministic automaton theory, which means:

• Predictable time complexity: Matching time is linear with respect to input length
• Natural immunity to ReDoS: No catastrophic backtracking regardless of regex complexity
• Controllable memory usage: No crashes from backtracking stack overflow

What POSIX Compatibility Means

TRE's claim of POSIX compliance deserves special explanation. POSIX defines two regex syntaxes: BRE (Basic Regular Expressions) and ERE (Extended Regular Expressions). The POSIX standard also specifies "leftmost longest match" semantics, meaning that among all possible matches, the engine must return the longest match starting from the leftmost position. This differs subtly but importantly from the "leftmost greedy" semantics of Perl-family regex engines. Most backtracking engines implement Perl semantics, while TRE strictly follows POSIX semantics. This means that in certain edge cases, TRE's matching results may differ from Python's re module—developers need to be aware of this difference when migrating.

Additionally, TRE supports approximate matching, which allows tolerating a certain number of insertion, deletion, and substitution errors during matching—a unique feature that many other regex engines lack. TRE's approximate matching is based on edit distance (Levenshtein distance) theory, allowing users to specify the maximum tolerable number of edit operations and set different cost weights for each type of operation. This has important applications in bioinformatics (DNA sequence matching), spell correction, OCR text post-processing, and other fields. Traditionally, implementing fuzzy matching requires specialized algorithms (such as the Bitap algorithm), but TRE integrates it directly into regex syntax, significantly lowering the barrier to use.

Tradeoffs and Costs

Not using backtracking means TRE doesn't support certain advanced regex features that depend on backtracking, such as backreferences. Backreferences allow a regex to reference the actual text content matched by a previous capture group. For example, (\\w+)\\s+\\1 can match repeated words (like "the the"). This feature may seem simple, but from a computational complexity theory perspective, regex matching with backreferences is NP-complete, meaning no known polynomial-time algorithm exists. This is the fundamental reason why non-backtracking engines must forgo this feature—it is mathematically incompatible with linear time guarantees.

However, in most practical application scenarios, these features are not necessary. Security and predictable performance are often more important than feature richness.

Experiment: Building Python Bindings with Claude Code

The ctypes Approach

Simon used Claude Code (Anthropic's AI programming assistant) to quickly build Python bindings for TRE. The technical approach chose ctypes—a Python standard library module for calling C dynamic link libraries.

ctypes is the Foreign Function Interface (FFI) module in Python's standard library, allowing Python code to directly call functions in C shared libraries (.so/.dll/.dylib) without writing any C code or using a compiler. Developers only need to declare function signatures (parameter types and return types), and ctypes automatically handles conversion between Python objects and C data types. Compared to traditional C extensions (which require using the Python C API) or Cython (which requires additional compilation steps), ctypes' advantages lie in zero compilation dependencies and rapid iteration, though with slightly higher performance overhead—making it suitable for prototype validation rather than production-environment high-frequency calls.

This approach requires no C extension code, offers high development efficiency, and is ideal for prototype validation. The complete experimental code is open-sourced on GitHub.

Advantages of AI-Assisted Programming in FFI Binding Development

Simon's choice to use Claude Code to generate ctypes binding code reveals a sweet spot for AI programming assistants: FFI binding development. Writing ctypes bindings requires precisely translating structs, function signatures, and constant definitions from C header files into Python code—work that is highly mechanical but error-prone, involving careful type mapping, pointer handling, and memory management. AI models have seen large amounts of such binding code in their training data and can quickly generate correct type declarations and calling conventions. These tasks are characterized by fixed patterns, clear context (C header files serve as complete specifications), and easy verification (if it compiles and runs, it works)—making them ideal for AI-assisted completion. In contrast, designing high-level binding APIs or handling complex memory lifetime issues still requires deep developer involvement.

ReDoS Test Results Comparison

The experiment executed multiple known malicious regular expressions against both the TRE binding and Python's re module. The results clearly demonstrated the differences:

• Python re: Execution time ballooned dramatically with malicious input; some test cases couldn't complete within a reasonable timeframe
• TRE: All test cases completed in milliseconds with stable performance

This validates TRE's significant advantage in defending against ReDoS attacks through its non-backtracking design.

Practical Implications: When to Use a Non-Backtracking Regex Engine

Applicable Scenarios

The following scenarios are particularly suited for adopting TRE or similar non-backtracking regex engines:

1. Systems where users can input regular expressions: Such as log search and data filtering platforms
2. Services with high availability requirements: Where a single request bringing down the entire service is unacceptable
3. Security-sensitive applications: WAFs, intrusion detection systems, etc.

Alternative Solutions in the Python Regex Ecosystem

The Python community hasn't been idle regarding regex security. Beyond TRE bindings, developers have other options: google-re2 is Google RE2's official Python binding, providing an API similar to the re module; the regex module (maintained by Matthew Barnett), while still backtracking-based, offers timeout mechanisms and richer Unicode support; Python 3.11 introduced some performance optimizations to the re module but didn't fundamentally solve the backtracking problem. Notably, Python's re module in CPython has a built-in match count limit (approximately 1 million backtracks by default), throwing an error when exceeded—providing a degree of protection. However, this limit isn't supported by all Python implementations, and the threshold may not be sufficient to prevent all ReDoS scenarios.

Industry Trend: From Backtracking to Deterministic

The industry is gradually migrating toward secure regex engines. Google's RE2 and Rust's regex crate both employ similar non-backtracking designs.

Google RE2 was developed by Russ Cox (who is also a Go language team member), with its design directly inspired by Ken Thompson's original paper, guaranteeing linear-time matching with bounded memory usage. RE2 has been deployed at massive scale within Google, used in products like BigQuery and Google Sheets to process user-provided regular expressions. Rust's regex crate was developed by Andrew Galloway (burntsushi), also based on finite automaton theory, achieving extremely high performance through Rust's zero-cost abstractions. In benchmarks, Rust regex is frequently among the fastest regex engines across all languages while maintaining safety guarantees. These two projects, along with TRE, represent the core forces of the "safe regex" movement.

Redis choosing TRE is also a manifestation of this trend.

Simultaneously, this experiment demonstrates the value of AI programming assistants in rapid prototyping—using Claude Code to quickly generate ctypes binding code allows developers to focus on validating core hypotheses rather than getting bogged down in low-level binding details.

Conclusion

Regular expressions are among the most fundamental components in a developer's daily toolkit, yet their security pitfalls are often overlooked. TRE trades backtracking for predictable performance and natural ReDoS immunity. When infrastructure projects like Redis are adopting it, perhaps it's time to re-examine the regex engines we use in our own projects.