Towards Efficient Matching of Regexes with Backreferences using Register Set Automata (Technical Report)
This paper proposes Register Set Automata (RSAs), a novel automaton model that extends register automata with set-based operations, to enable efficient, deterministic, and robust matching of regular expressions containing backreferences while establishing their theoretical decidability and expressive power.
Original authors:Vojtěch Havlena, Lukáš Holík, Ondřej Lengál, Jan Vašák, Sabína Gulčíková
Original authors: Vojtěch Havlena, Lukáš Holík, Ondřej Lengál, Jan Vašák, Sabína Gulčíková
Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer
The Problem: The "Copy-Paste" Trap
Imagine you are a librarian trying to find a specific book in a massive, chaotic library. You have a search rule: "Find a sentence that starts with 'The', has a word in the middle, and ends with the exact same word that was in the middle."
In computer science, this is called a Regular Expression (Regex) with a Backreference. It's like telling the computer, "Remember what you saw here, and make sure you see it again later."
The Current Crisis: Most computer programs that do this search (like the ones in your web browser or security software) use a method called Backtracking.
The Analogy: Imagine a detective trying to solve a crime by guessing. They guess a suspect, check the alibi, and if it fails, they go back, erase the guess, and try a different suspect.
The Danger: If the rule is complex and the text is long, the detective might have to try millions of combinations. If a hacker sends a specially crafted, long sentence, the detective gets stuck in an infinite loop of guessing. The computer freezes, the website crashes, and the service goes down. This is called a ReDoS attack (Regular Expression Denial of Service).
The Solution: The "Set-Keeping" Robot
The authors of this paper propose a new way to do the search that doesn't involve guessing. They introduce a new type of machine called a Register Set Automaton (RSA).
1. The Old Way vs. The New Way
The Old Machine (Register Automaton): Imagine a robot with a few pockets (registers). It can put one item in a pocket. If it sees a new item, it has to decide: "Do I keep this one, or the old one?" It can't remember everything it has ever seen, only one thing at a time. This makes it hard to handle complex "remember this" rules without guessing.
The New Machine (Register Set Automaton): Imagine a robot with pockets that are actually magic baskets.
Instead of holding just one item, a basket can hold a whole collection of items.
As the robot reads the text, it doesn't have to guess which item to remember. It just drops every new item it sees into the basket.
Later, when it needs to check if a specific item appeared before, it just looks inside the basket. If the item is there, great! If not, it's not there.
2. Why This is a Game-Changer
Because the robot uses "baskets" (sets) instead of single slots, it can be deterministic.
Deterministic means: "There is only one path forward. No guessing, no backtracking."
The Analogy: Instead of a detective guessing and erasing, imagine a conveyor belt where every item is automatically sorted into a bin as it passes. You never have to go back and re-sort anything. The speed is predictable and fast, no matter how long the text is.
The "Magic" of the Paper
The paper does three main things to make this work:
Inventing the Basket (The RSA Model): They formally defined this new machine that can store sets of data. They proved that while these machines are powerful, they are still mathematically solvable (we can tell if they will ever finish a job).
The Translation Guide (Determinization): They created an algorithm that takes a "guessing" machine (the old, slow way) and automatically converts it into a "basket-holding" machine (the new, fast way).
Note: Sometimes the translation fails if the rule is too weird, but for the vast majority of real-world rules, it works perfectly.
The Speed Test: They built a prototype robot (a software tool called rsamatch) and tested it against the best existing tools.
The Result: When faced with the "ReDoS" attacks that crash other systems, their robot didn't even break a sweat. It finished the job in milliseconds, while the others took minutes or hours (or crashed entirely).
Real-World Impact
Why should you care?
Security: Hackers love to use these "copy-paste" rules to crash servers. This new method makes those attacks much harder to pull off.
Speed: Websites and apps can use powerful search features without worrying that a user typing a long sentence will freeze the system.
Reliability: It turns a "maybe it will work, maybe it will crash" situation into a "it will work fast every time" guarantee.
Summary Analogy
The Problem: Trying to find a matching pair of socks in a dark room by picking one, checking the drawer, putting it back, and trying another. If you have 1,000 socks, this takes forever.
The Old Solution: A robot that picks a sock, checks, and if it's wrong, puts it back and tries again. (Slow, prone to getting stuck).
The New Solution (This Paper): A robot that has a magic bag. As it picks up socks, it just drops them all into the bag. When it needs to check if a sock exists, it just looks in the bag. It never has to put anything back or guess. It's fast, reliable, and impossible to trick into getting stuck.
The authors have essentially given computers a "magic bag" to handle complex text searches, making the internet safer and faster.
1. Problem Statement
Regular expression (regex) matching is fundamental to many computing tasks (search, validation, parsing). However, regexes with backreferences (e.g., \1 referring to a previously captured group) pose a significant challenge:
Performance Degradation: Standard matchers (like PCRE2, Python re, Java java.util.regex) typically use backtracking algorithms for backreferences. In the worst case, this leads to exponential time complexity, causing Regular Expression Denial of Service (ReDoS) attacks where a malicious input crashes a server.
Lack of Deterministic Models: Efficient matching usually relies on deterministic automata (DFAs) with linear time complexity. However, standard automata determinization cannot handle backreferences because the resulting languages are often non-regular. Existing fast matchers (RE2, HyperScan) explicitly disable backreferences to maintain performance.
The Gap: There is no known efficient, deterministic automata model that supports backreferences while guaranteeing predictable, near-linear performance.
2. Methodology
The authors propose a novel formal model and a compilation pipeline to bridge this gap.
A. The Core Model: Register Set Automata (RSAs)
The paper introduces Register Set Automata (RSAs), an extension of standard Register Automata (RAs).
Key Difference: In standard RAs, a register holds a single data value. In RSAs, a register holds a set of data values.
Operations: RSAs support:
Adding input values to registers.
Merging registers (union of sets).
Clearing registers.
Testing membership (checking if the current input value is in a register's set).
Deterministic RSAs (DRSAs): The authors focus on deterministic variants. A DRSA processes input in a single pass, maintaining a set of possible values in its registers, allowing for efficient membership testing without backtracking.
B. The Compilation Pipeline
The authors developed a workflow to convert regexes with backreferences into DRSAs:
Regex to Register Automaton (RA): Using Antimirov's partial derivatives, they convert a regex with single-letter capture groups and backreferences into a non-deterministic RA (NRA).
RA to DRSA Determinization: They propose a semi-algorithm (Algorithm 1) to determinize the NRA into a DRSA.
Technique: It uses a subset construction similar to Rabin-Scott but tracks register size classes (0, 1, or ω) to handle disequality guards precisely.
Handling Non-Determinism: It employs "choice collapse" at equality tests to ensure that if a register is tested for equality, the set of possible values collapses to a single value, preventing spurious matches.
Limitations: The algorithm is a semi-algorithm; it may fail (return ⊥) if the input NRA requires more complex interactions than the DRSA model can capture (e.g., certain Cartesian overapproximations).
C. Complexity Analysis
Finite Alphabets: Matching time is linearO(∣w∣) with respect to input length ∣w∣.
Infinite Alphabets: Matching time is quadraticO(∣w∣2).
Theoretical Bounds: The emptiness problem for RSAs is shown to be Fω-complete (Ackermannian), significantly higher than the PSPACE-completeness of standard RAs, reflecting the increased expressive power.
3. Key Contributions
Formal Model (RSAs): Introduction of Register Set Automata, which strictly generalize RAs and are incomparable to Alternating RAs (ARAs) in expressive power.
Determinization Semi-Algorithm: A novel algorithm to convert a large class of NRAs (specifically those derived from single-letter backreference regexes) into DRSAs.
Regex Compilation: A derivative-based construction to compile regexes with backreferences into NRAs, completing the end-to-end pipeline from regex to deterministic automaton.
Theoretical Analysis:
Proof that the emptiness problem for RSAs is decidable (Fω-complete).
Demonstration that RSAs are incomparable to other popular data-word automata models (like Pebble Automata or History-Register Automata).
Proof that language inclusion is decidable for the specific subclass of languages generated by the determinization process.
Prototype Implementation (rsamatch): A Python-based matcher implementing the proposed approach.
4. Experimental Results
The authors evaluated rsamatch against state-of-the-art matchers (PCRE2, Python re, Java, .NET, grep) using a dataset of 12,046 real-world regexes and ReDoS attack vectors generated by the tool Rengar.
ReDoS Resilience:
Standard matchers frequently timed out (>100s) or took tens of seconds on attack vectors, confirming their vulnerability.
rsamatch successfully matched the vast majority of inputs in under 1 second, demonstrating predictable, linear-time performance.
On the 1,246 supported regexes, rsamatch had a median runtime of 0.16s and a standard deviation of 0.30s, whereas competitors had standard deviations in the range of 3.0s to 6.4s.
Coverage:
The determinization algorithm succeeded on 91% of regexes containing only single-letter backreferences.
It failed on regexes with complex multi-letter capture groups or specific structural patterns that exceed the DRSA model's current capabilities.
Trade-off: While the determinization step adds an offline overhead (average 1.15s), this is amortized over many online matching operations, making the approach highly suitable for server-side validation.
5. Significance and Impact
Security: The work provides a practical defense against ReDoS attacks for a significant class of regexes (single-letter backreferences), which are common in real-world applications. It shifts regex matching from an exponential-risk model to a predictable, polynomial-time model.
Theoretical Advancement: It establishes a new hierarchy of automata over infinite alphabets, showing that set-based registers offer a unique balance between expressiveness (handling backreferences) and decidability (determinization and emptiness checking).
Practical Applicability: The prototype demonstrates that it is possible to build robust, high-performance regex engines that support features previously deemed too expensive for deterministic processing. This could lead to safer implementations in web frameworks, intrusion detection systems, and data validation tools.
In conclusion, the paper successfully bridges the gap between the theoretical intractability of backreference matching and the practical need for high-speed, secure regex processing by introducing Register Set Automata and a viable determinization strategy.