Regex Engines: From Expression to the Automaton That Runs It

⏱️ Lectura: 12 min

A poorly written regex can hang a server for minutes with a single request. It’s not an exotic bug: it’s called ReDoS, and it happens because most regex engines try thousands of combinations before giving up.

📑 En este artículo

1. TL;DR
2. What a regex engine is and why it matters
3. How it works internally: from expression to automaton
   1. The parser: from text to syntax tree
   2. Thompson’s construction: from tree to NFA
   3. Determinization: from NFA to DFA
4. Backtracking: how PCRE, Python re, and JavaScript work
   1. Why it explodes: ReDoS explained
5. Progressive practical examples
6. How to test it step by step
7. Real-world use cases
8. Common mistakes and best practices
9. Comparison with alternatives
10. Going deeper: the Pike virtual machine and the real cost of captures
11. Frequently Asked Questions
    1. What is ReDoS and how does it affect me
    2. Why doesn’t PCRE use automatons if they’re faster in the worst case
    3. How do I know if my regex is vulnerable to catastrophic backtracking
    4. Is RE2 slower than PCRE for simple cases
    5. Do lookahead and lookbehind work in RE2
    6. Which languages use automaton-based engines by default
12. References

The reason has to do with how the engine is built internally. Some compile the pattern into an automaton that scans the text just once. Others try paths one by one and sometimes backtrack without limit. Understanding that difference is what separates a harmless form validator from a denial-of-service vulnerability.

TL;DR

• You’ll understand how a regex pattern is compiled into an automaton (NFA) via Thompson’s construction.
• You’ll be able to spot ReDoS-vulnerable patterns before they reach production, like (a+)+$.
• You’ll be able to distinguish a backtracking engine (PCRE, Python re, V8) from an automaton-based one (RE2, Rust’s regex).
• You’ll install and test RE2 in Python with pip install google-re2 to guarantee linear time.
• You’ll be able to measure with your own stopwatch whether a regex has exponential worst-case complexity.
• You’ll learn about the Pike virtual machine, the foundation behind RE2 and the regex engines in Rust and Go.
• You’ll know when you actually need backreferences and lookaround, and when it’s worth sacrificing them for safety.

What a regex engine is and why it matters

A regex engine is the program that takes a pattern like /ab*c/ and decides whether a text string matches it. It doesn’t interpret the pattern character by character in a naive way: it first converts it into an internal structure it can run efficiently.

There are two families of regex engines depending on how they handle execution. The first, and most common, tries alternatives and backtracks when one fails (backtracking). The second compiles the pattern into a finite automaton and advances without ever backtracking. That design decision directly affects performance, the features the engine can offer, and its security against malicious input.

Engines like PCRE (used by PHP and many linting tools), Python’s re module, and V8’s Irregexp engine in JavaScript use backtracking. Engines like Google’s RE2, Rust’s regex crate, and Go’s regexp package use automatons.

How it works internally: from expression to automaton

The parser: from text to syntax tree

The first thing any engine does is parse the pattern. a(b|c)*d becomes a tree where each node represents an operation: concatenation, alternation (|), or repetition (*, +, ?). This tree is identical regardless of the engine family; the difference starts in the next step.

Thompson’s construction: from tree to NFA

Ken Thompson described an algorithm in 1968 for converting that tree into a nondeterministic finite automaton (NFA) with a number of states proportional to the size of the pattern. Each operation in the tree (concatenation, alternation, repetition) has a fixed rule for combining automaton fragments into a larger one. The result is a graph of states connected by character transitions or empty transitions (epsilon).

flowchart TD
 A["Pattern: /ab*c/"] --> B["Parser: syntax tree"]
 B --> C["Thompson's construction"]
 C --> D["NFA (nondeterministic)"]
 D --> E["Subset construction"]
 E --> F["DFA (deterministic)"]
 F --> G["Input text"]
 G --> H["Match or no match"]

The important thing about Thompson’s construction, and the reason Russ Cox documented it in detail, is that the resulting NFA has a size linear in the pattern. That’s what later allows the match to run without exploding in time.

flowchart LR
 S0(("start")) -- "a" --> S1(("middle"))
 S1 -- "b" --> S1
 S1 -- "c" --> S2(("accept"))

Determinization: from NFA to DFA

An NFA can be in several states at once, which in theory would require exploring branches. The subset construction algorithm converts that NFA into a DFA (deterministic automaton) where each DFA state represents a set of possible NFA states. The final engine scans the text just once, one character at a time, without ever backtracking.

Backtracking: how PCRE, Python re, and JavaScript work

Most programming languages don’t use pure automatons because they want to offer features a finite automaton can’t express: backreferences (\1) and lookahead/lookbehind with variable-length content. To support them, the engine tries the pattern as if it were a search with backtracking: if one alternative fails, it goes back and tries the next one.

That approach works well in the common case. The problem shows up when the pattern has nested quantifiers over the same text, like (a+)+ or (a|a)*. There, the number of ways to split the string between the groups grows exponentially with the length of the input.

Why it explodes: ReDoS explained

ReDoS (Regular Expression Denial of Service) is the class of vulnerability that results from this behavior. An attacker sends a string designed to maximize backtracking attempts (for example, many a characters followed by a character that breaks the match), and the server stays busy evaluating that single request.

⚠️ Watch out: a pattern like ^(a+)+$ looks harmless when tested with short strings. The cost only shows up when someone sends a string with thousands of characters and no matching suffix, and that’s when the engine tries every possible partition before giving up.

import re

patron = r"^[\w.+-]+@[\w-]+\.[a-zA-Z]{2,}$"
correo = "[email protected]"

if re.match(patron, correo):
 print("Valid email")
else:
 print("Invalid email")

This first example compiles a simple pattern with no nested quantifiers. Python’s engine (backtracking) resolves it in a single attempt per character because there’s no ambiguity in how to split the string between groups.

Progressive practical examples

import re
import time

patron_peligroso = re.compile(r"(a+)+$")
entrada = "a" * 30 + "!"

inicio = time.time()
patron_peligroso.match(entrada)
print(f"time: {time.time() - inicio:.4f}s")

Here, the group (a+)+ can split the run of “a” characters in countless different ways before confirming that the expected $ never shows up after a “!”. Bump the number of “a” characters from 25 to 30 to 35 on your own machine, and you’ll see the time doesn’t grow proportionally: it grows by multiplying, because each extra character roughly doubles the number of possible combinations.

flowchart TD
 subgraph Backtracking
 B1["Attempt 1: empty group"] --> B2["Attempt 2: split into 2"]
 B2 --> B3["Attempt 3: split into 3"]
 B3 --> B4["... thousands of combinations"]
 end
 subgraph Automatons
 A1["One step per character"] --> A2["No backtracking"]
 A2 --> A3["Guaranteed linear time"]
 end

How to test it step by step

To confirm the difference between a backtracking engine and an automaton-based one on your own machine, install RE2 in Python:

pip install google-re2

import re2

patron_seguro = re2.compile(r"(a+)+$")
entrada = "a" * 10000 + "!"
patron_seguro.match(entrada) # linear time, doesn't hang

If you prefer Rust, the regex crate offers the same guarantee:

cargo add regex

use regex::Regex;

fn main() {
 let re = Regex::new(r"(a+)+$").unwrap();
 let texto = "a".repeat(10000) + "!";
 println!("{}", re.is_match(&texto));
}

To verify you’re using the right engine: RE2 and Rust’s regex crate reject backreferences when compiling the pattern (a syntax error instead of accepting it), while PCRE and Python’s re accept them without complaint. You can also measure the time with time.time(): if doubling the input size doubles the execution time, the engine is linear; if it multiplies it by much more, you’re looking at exponential backtracking.

Real-world use cases

• Web Application Firewalls (WAF): they process regex against untrusted traffic, which is why many migrated to automaton-based engines to avoid ReDoS.
• Linters and compilers: they use backtracking because the pattern is written by the project’s own developer, not an external attacker.
• Services that accept user-supplied regex (log search tools, configurable validators): these are the highest-risk case if they use a backtracking engine with no time limit.
• Databases and proxies like those implementing regex-based routing rules: they tend to prefer RE2 for its time guarantee.

Common mistakes and best practices

• Nested quantifiers: patterns like (a+)+, (a*)*, or (a|a)* are the classic signature of ReDoS. Avoid them or rewrite them without nesting the same character twice.
• Relying on timeouts as the only defense: a timeout keeps the server from hanging, but it still burns CPU on every attempt until it expires.
• Not validating regex from external input: if a user can upload their own pattern (for example, in a configurable search tool), that pattern should run on an automaton-based engine, not a backtracking one.
• Assuming greedy and lazy change the complexity: switching + for +? (lazy) doesn’t fix a structural ReDoS, it just changes the order in which alternatives are tried.

💡 Tip: tools like safe-regex or ESLint linters with the no-misleading-character-class rule and similar ones can detect patterns with nested quantifiers before they reach production.

Comparison with alternatives

Engine	Type	Guaranteed complexity	Backreferences / lookaround	When to use it
PCRE (PHP, linting tools)	Backtracking	Exponential worst case	Yes	Fixed pattern, written by your own team
Python re (stdlib)	Backtracking	Exponential worst case	Yes	Scripts and validations with controlled input
JavaScript (V8 Irregexp)	Backtracking with optimizations	Exponential worst case	Yes	Form validation with bounded patterns
RE2 (Google)	Automaton (Thompson NFA + Pike VM)	Linear O(n)	No	Processing untrusted regex or text
Rust’s regex	Automaton (Pike VM)	Linear O(n)	No	Systems where predictable performance is critical
Go regexp (stdlib)	Automaton (based on RE2)	Linear O(n)	No	Backend services that process external input

Going deeper: the Pike virtual machine and the real cost of captures

Rob Pike designed a variant of NFA execution that, besides deciding whether there’s a match, can report where the captured groups start and end, without giving up the linear-time guarantee. This technique, known as the Pike virtual machine, is what both RE2 and Rust’s regex crate use to offer group(1) without backtracking.

The way they achieve this is by simulating all the NFA’s possible states in parallel, one character at a time, instead of trying them one by one like backtracking does. The cost is proportional to the number of automaton states multiplied by the length of the text, never exponential.

💭 Key takeaway: the real reason PCRE, Python, and JavaScript still use backtracking isn’t ignorance of these techniques. It’s that backreferences like (\w+)\1 can’t be expressed with a finite automaton: the problem of recognizing those strings isn’t regular in the formal sense, and there, backtracking (or something worse) is unavoidable.

That’s the underlying trade-off: full expressiveness with the risk of exponential time, or guaranteed linear time at the cost of backreferences and variable-length lookaround. No engine solves both sides without concessions.

📖 Summary on Telegram: View summary

Your next step: take a regex you already use in production, run pip install google-re2, and compile it with re2.compile() to see if the automaton-based engine accepts it without changes.

Frequently Asked Questions

What is ReDoS and how does it affect me

ReDoS is a denial of service caused by a regex pattern that, given certain input, makes the engine try an exponential number of combinations before failing. It affects any service that evaluates regex against input it doesn’t fully control.

Why doesn’t PCRE use automatons if they’re faster in the worst case

Because PCRE offers backreferences and variable-length lookaround, features that can’t be represented with a pure finite automaton. Giving up backtracking would mean giving up those features.

How do I know if my regex is vulnerable to catastrophic backtracking

Look for nested quantifiers over the same set of characters, like (a+)+, (a*)*, or overlapping alternations like (a|a)*. If your pattern has that shape, test it with long inputs and measure the time.

Is RE2 slower than PCRE for simple cases

It can have a small fixed cost when compiling the automaton, but its execution time always grows linearly, while PCRE can be faster in the common case and much slower (or hang) in the worst case.

Do lookahead and lookbehind work in RE2

No. RE2 and Rust’s regex crate reject, at compile time, any pattern with backreferences or variable-length lookaround, precisely because they would break the linear-time guarantee.

Which languages use automaton-based engines by default

Go uses regexp, based on RE2, by default. Rust uses the regex crate, also automaton-based. Python and JavaScript use backtracking by default, though in Python you can install google-re2 as an alternative.

References

• Regular Expression Matching Can Be Simple And Fast, Russ Cox: the article that popularized the comparison between backtracking and automatons.
• RE2 on GitHub: source code and documentation for Google’s engine.
• Official documentation for Python’s re module: reference for the stdlib’s backtracking engine.
• Documentation for Rust’s regex crate: implementation based on the Pike virtual machine.
• MDN: Regular expressions in JavaScript: guide to the syntax supported by V8.

📱 Enjoying this content? Follow @programacion on Telegram for daily tech content in Spanish: quick summaries, fresh content every day.

Imagen destacada: Foto de wesfly en Unsplash