Towards an Effective Method of ReDoS Detection for Non-backtracking Engines

Towards an Effective Method of ReDoS Detection for Non-backtracking Engines

Speakers: Weihao Su, Haiming Chen, Tingjian Ge (University of Michigan; Chinese Academy of Sciences)

Conference: USENIX Security '24

YouTube: https://www.youtube.com/watch?v=-SL7RJAH_CU

Overview

Regular expression Denial of Service (ReDoS) attacks represent a significant threat to applications that rely on regular expressions for pattern matching, often leading to severe performance degradation or complete service unavailability. This talk, presented by Tingjian Ge from the University of Michigan, delves into a critical, yet often overlooked, vulnerability vector in modern regular expression engines: those that employ non-backtracking algorithms. Traditionally, non-backtracking engines were heralded as a safer and faster alternative to their backtracking counterparts, largely due to their perceived linear time complexity. However, this research challenges that assumption, demonstrating that these engines are far from immune to ReDoS, exhibiting super-linear performance in specific, crafted scenarios.

The presentation introduces EvilStringGen, a novel tool and methodology designed to effectively detect ReDoS vulnerabilities in non-backtracking regular expression engines. EvilStringGen leverages a deep understanding of the underlying automaton theory and computational complexities that govern these engines. By systematically generating "evil strings" — inputs specifically engineered to trigger worst-case performance — the researchers expose the latent vulnerabilities that existing tools often miss. This work is pivotal for the security community, offering a new perspective on ReDoS risks and providing actionable insights for developers and defenders to fortify their systems against these subtle yet potent attacks.

Background

▶ Watch: Introduction to ReDoS and non-backtracking engines (0:00)

Regular expressions are a ubiquitous tool in computer science, integral to tasks ranging from network security and database queries to programming language parsing and data validation. The core functionality involves pattern matching, where an input string is evaluated against a defined regular expression. This can involve full matching (does the entire string match the pattern?) or partial matching (does the pattern appear as a substring?). Despite their widespread utility, regular expression matching is a computationally intensive problem, known to be NL-complete or NP-complete in its general forms, depending on the specific variant and features used.

Historically, regular expression engines have primarily fallen into two categories: backtracking engines and non-backtracking engines. Backtracking engines, common in languages like Python and Perl, operate by recursively exploring different matching paths. If a path fails, the engine "backtracks" to a previous state and tries an alternative route. While powerful, this mechanism is notoriously susceptible to ReDoS when certain patterns (e.g., nested quantifiers, overlapping alternatives) are combined with specific "catastrophic backtracking" input strings, leading to exponential time complexity.

In response to the inherent dangers of backtracking, non-backtracking engines emerged as a more robust alternative. These engines, exemplified by Google's re2, are primarily based on automaton theory, typically constructing Deterministic Finite Automata (DFA) or Nondeterministic Finite Automata (NFA). The promise of non-backtracking engines was their perceived safety and speed, often touted as offering linear time complexity with respect to the input string length (O(N)). This assumption led to their increasing adoption in security-sensitive applications and modern programming environments. However, as this research highlights, the linear time complexity claim is not universally true; the actual performance can also depend on the size and complexity of the regular expression itself, particularly when expanded into an automaton. Previous work, such as GadgetCA (presented at a prior USENIX conference), began to explore ReDoS vulnerabilities in non-backtracking engines, primarily focusing on specific "counting structures" within regular expressions. This talk extends that foundational work, identifying broader categories of vulnerabilities and developing a more comprehensive detection methodology.

Key Findings

▶ Watch: Introducing 'evil string gen' tool and its results (3:30)

The central finding of this research is that non-backtracking regular expression engines, despite their design to avoid catastrophic backtracking, are indeed vulnerable to ReDoS attacks. This vulnerability stems not from the traditional backtracking mechanism but from what the researchers term "descriptional complexity" and the inherent computational challenges in constructing and traversing the underlying automata.

Specifically, the key findings include:

1. Super-Linear Performance in Non-Backtracking Engines: The talk demonstrates concrete examples where non-backtracking engines like re2 exhibit significantly degraded performance (e.g., almost two seconds for a specific input string) compared to backtracking engines (e.g., one millisecond for the same string in Python). This directly contradicts the common assumption of linear time complexity for all inputs in non-backtracking contexts.
2. Determinization Blow-up as a Root Cause: A primary factor contributing to ReDoS in these engines is the phenomenon of determinization blow-up. When an NFA is converted to its equivalent DFA, the number of states in the DFA can grow exponentially with respect to the number of states in the NFA. This exponential growth in states directly translates to increased computational overhead, especially when dealing with complex regular expression structures.
3. Impact of Counting Structures and Unicode Encoding: While GadgetCA previously identified counting structures (e.g., (a{1,5}){1,5}) as a source of vulnerability, this research further highlights the impact of Unicode encoding, specifically UTF-8. UTF-8, being a variable-length encoding, can dramatically increase the number of DFA states required to process even simple patterns (e.g., \w/\d repeated five times). An example shows that ASCII encoding might yield no problem, but UTF-8 can lead to "many, many more states," exacerbating the determinization blow-up.
4. The "Simple String" Problem and its Hardness: The researchers define a novel concept called a simple string. This is an input string designed to traverse as many distinct DFA states as possible, analogous to finding the longest path in a graph without repeating nodes – a known NP-hard problem. They further define the K-simple string problem (determining if a simple string of length at least K exists) and formally prove that it is exponential space hard, indicating an even higher computational complexity than NP-hard problems. This theoretical finding underpins the difficulty and necessity of their heuristic-based approach.
5. EvilStringGen's Superiority: The developed tool, EvilStringGen, significantly outperforms existing baselines, including GadgetCA, in generating ReDoS-inducing strings for non-backtracking engines. EvilStringGen successfully identifies vulnerable regular expressions and generates strings that lead to processing times orders of magnitude longer than strings generated by other tools. For instance, in comparative tests, EvilStringGen consistently produces strings that cause delays of several seconds, whereas GadgetCA might only achieve milliseconds.
6. Real-World Vulnerabilities: A case study involving open-source projects revealed that EvilStringGen identified vulnerabilities in 85 projects and pinpointed 34 problematic regular expressions, including one in unknown/SLC, demonstrating the practical applicability and impact of their method.

Technical Deep Dive

▶ Watch: Analyzing root causes: DFA state blow-up and Unicode (4:30)

The technical foundation of this research lies in understanding the internal workings and computational complexities of non-backtracking regular expression engines. While these engines strive for linear time performance, their reliance on automata can introduce vulnerabilities under specific conditions.

Non-backtracking engines, such as re2, primarily operate by constructing a DFA from the given regular expression. A DFA is a finite state machine where for each state and input symbol, there is exactly one transition to another state. This deterministic nature is what typically leads to efficient, linear-time matching. However, constructing a DFA directly from a regular expression can be computationally expensive. Often, an engine first builds an NFA (Nondeterministic Finite Automaton), which allows for multiple transitions from a state on the same input symbol, or transitions without consuming input (epsilon transitions). The NFA is then converted into a DFA through a process called determinization.

The core of the ReDoS problem in non-backtracking engines, as identified by this work, stems from the descriptional complexity inherent in this NFA-to-DFA conversion. This complexity manifests in several ways:

1. Determinization Blow-up: The process of converting an NFA to a DFA can, in the worst case, lead to an exponential increase in the number of states. If an NFA has n states, its equivalent DFA can have up to 2^n states. This state explosion means that even for moderately complex regular expressions, the resulting DFA can become astronomically large. When the engine has to construct and manage such a vast number of states, performance degrades significantly. The talk points out that the computational complexity, if it hits the worst case, could be "more than linear" for DFA-based processing.
2. Fallback Mechanisms: While DFA is the primary mechanism, non-backtracking engines often incorporate fallback strategies. If a DFA state cannot be efficiently constructed or becomes too large, the engine might fall back to an NFA-based matching. If NFA matching also proves problematic, some engines may even resort to a backtracking approach as a last resort. Each of these fallbacks can introduce its own performance pitfalls, with NFA matching still potentially leading to super-linear complexity.
3. Counting Structures: As highlighted by previous work like GadgetCA, regular expressions with repeated counting structures (e.g., (a{1,5}){1,5}) are particularly prone to determinization blow-up. These patterns can create a combinatorial explosion of possible states in the NFA, which then translates into a massive DFA.
4. Unicode Encoding (UTF-8) Impact: A significant novel contribution of this work is identifying variable-length Unicode encodings, specifically UTF-8, as a major exacerbating factor. Regular expressions that handle Unicode character classes (e.g., \w for word characters, \d for digits) can generate many more DFA states when processed with UTF-8 compared to fixed-length encodings like ASCII. The example \w/\d repeated five times ((\w|\d){5}) demonstrates this: while it might pose no problem with ASCII, UTF-8 processing can lead to a drastic increase in DFA states, thereby increasing the processing time. This is because a single logical character can be represented by multiple bytes in UTF-8, and the engine must account for all possible byte sequences that form a valid character within the character class, leading to a much larger state space.

To tackle the challenge of finding ReDoS-inducing strings for these complex scenarios, the researchers defined the concept of a simple string. A simple string is one that maximizes the number of distinct DFA states visited during the matching process. This is fundamentally analogous to the longest path problem in graph theory, which is known to be NP-hard. The researchers formalized this into the K-simple string problem (does a simple string of length at least K exist?) and proved its computational complexity to be exponential space hard. This theoretical hardness necessitates a heuristic-based approach for practical string generation.

EvilStringGen employs two primary heuristics to navigate this complex search space and generate effective simple strings:

1. Maximizing Nondeterminism: This heuristic aims to guide the DFA generation process towards states that exhibit a higher degree of nondeterminism. Intuitively, more nondeterminism makes it harder for the DFA engine to make a definitive transition, potentially forcing it to explore more states or engage in more complex state-merging operations, thereby increasing computational load. The goal is to reach states where the engine faces more choices or ambiguity, pushing it towards its worst-case behavior.
2. Maximizing Lexicographical Order (Distance from Final States): The second heuristic focuses on reaching states that are "far away" from the final states (also known as accepting states). Once a final state is reached, the matching process typically concludes successfully. By prioritizing paths that lead to states distant from any final state, EvilStringGen attempts to prolong the matching process, forcing the engine to generate and explore a larger portion of the DFA before either accepting or rejecting the input. This effectively maximizes the "work" the engine must perform.

The EvilStringGen algorithm leverages these heuristics during an "on-the-fly" DFA generation process. It dynamically explores the state space, making choices based on these heuristics to construct input strings that are likely to push the engine into its worst-case performance scenarios. The specific algorithm details are elaborated in their full paper, but the essence lies in this intelligent, heuristic-driven exploration of the automaton's state space to exploit its descriptional complexity.

Demo / Proof of Concept

▶ Watch: Formalizing the attack problem: 'simple string' complexity (6:30)

The practical efficacy of EvilStringGen was demonstrated through comprehensive experimental evaluations, comparing its performance against several baselines, including the state-of-the-art GadgetCA, across a wide range of regular expressions and engines. The evaluation focused on two key metrics: machine-dependent running time (processing time for the input string) and machine-independent number of DFA states generated.

The results unequivocally showcased EvilStringGen's superior capability in generating ReDoS-inducing strings. In a table presenting main results, EvilStringGen (referred to as "all tool evil string gen" with various strategy combinations) consistently generated strings that resulted in significantly longer processing times compared to baselines. For example, for a particular vulnerable regular expression, EvilStringGen could cause processing delays of several seconds, while GadgetCA might only induce delays in the order of milliseconds. An ablation study further confirmed that the combination of all strategies within EvilStringGen yielded the most potent attack strings. While the primary focus was on non-backtracking engines, EvilStringGen also showed effectiveness against some backtracking engines, though one baseline performed slightly better for Perl and PHP.

A specific scatter plot comparison against GadgetCA visually reinforced EvilStringGen's advantage, illustrating its ability to generate strings that not only took much longer to process but also forced the engines to generate a substantially higher number of DFA states. This directly validated the underlying hypothesis that EvilStringGen effectively exploits the determinization blow-up and descriptional complexity.

Beyond benchmark comparisons, the research included compelling case studies on real-world open-source projects. EvilStringGen was deployed to analyze regular expressions used in widely adopted systems. This practical application led to the discovery of problematic regular expressions in 85 different open-source projects. A specific instance highlighted was a vulnerable regular expression found in unknown/SLC, a widely used component. In total, 34 distinct regular expressions were identified as vulnerable to ReDoS when processed by non-backtracking engines using EvilStringGen's crafted inputs. These findings underscore that the identified vulnerabilities are not merely theoretical but represent tangible security risks in actively maintained software, providing concrete proof of concept for the tool's effectiveness in identifying real-world ReDoS attack vectors.

Defensive Implications

▶ Watch: Proposed heuristics for generating challenging attack strings (8:00)

The findings presented in this talk have profound implications for developers, security engineers, and anyone relying on regular expressions in their applications. The notion that non-backtracking engines are inherently immune to ReDoS is clearly debunked, necessitating a re-evaluation of existing security postures.

Here are key defensive implications:

1. Re-evaluate Regular Expression Usage: Developers should no longer assume that using a non-backtracking engine like re2 automatically safeguards against ReDoS. All regular expressions, regardless of the engine type, should be considered potential attack vectors and undergo rigorous security review.
2. Avoid Complex Counting and Nested Quantifiers: While traditionally associated with backtracking ReDoS, complex counting structures (e.g., (a{1,N}){1,M}) and deeply nested quantifiers can still trigger determinization blow-up in non-backtracking engines. Developers should simplify such patterns or ensure they are tightly bounded.
3. Be Wary of Unicode and Variable-Length Encodings: The research highlights the significant impact of UTF-8 encoding on DFA state explosion. When designing regular expressions that handle international characters or character classes (\w, \d), developers must be acutely aware that UTF-8 can drastically increase the attack surface. Where possible, consider constraining character sets or using more explicit patterns that don't rely on broad Unicode properties if performance is critical.
4. Adopt ReDoS Detection Tools for Non-Backtracking Engines: Traditional ReDoS detection tools often focus solely on backtracking vulnerabilities. The emergence of tools like EvilStringGen provides a critical capability for identifying vulnerabilities specific to non-backtracking engines. Organizations should integrate such tools into their CI/CD pipelines and regular security audits to proactively test their regexes against these new attack vectors.
5. Understand Engine Fallback Mechanisms: Developers should be aware of how their chosen regular expression engine handles complex patterns or resource exhaustion (e.g., falling back from DFA to NFA or even backtracking). Understanding these internal mechanisms can help in diagnosing and mitigating performance bottlenecks or ReDoS attempts.
6. Implement Timeouts and Resource Limits: As a last line of defense, all applications processing user-supplied or untrusted regular expressions (or input strings against known regexes) should implement strict timeouts and resource limits. This prevents a single malicious input from monopolizing CPU cycles and causing a full Denial of Service. While not preventing the attack, it limits its impact.
7. Stay Updated on Research and Best Practices: The landscape of ReDoS vulnerabilities is evolving. Developers and security teams must stay informed about new research, tools, and best practices to adapt their defenses accordingly.

Key Takeaways

• Non-backtracking regular expression engines, widely considered safer and faster, are demonstrably vulnerable to ReDoS attacks.
• The primary cause of ReDoS in these engines is descriptional complexity, specifically determinization blow-up during NFA-to-DFA conversion.
• Complex counting structures and the use of UTF-8 (variable-length Unicode encoding) significantly exacerbate the determinization blow-up problem, leading to a massive increase in DFA states and processing time.
• The "simple string" problem, which aims to find input strings that traverse the maximum number of distinct DFA states, is exponential space hard, necessitating heuristic-based attack generation.
• EvilStringGen, a novel tool, effectively generates these "evil strings" by employing heuristics that maximize nondeterminism and guide state exploration away from final states, significantly outperforming existing detection methods.
• EvilStringGen successfully identified ReDoS vulnerabilities in 85 real-world open-source projects, involving 34 distinct regular expressions, highlighting the practical threat.
• Defenders must update their understanding of ReDoS, integrate specialized tools like EvilStringGen into their security practices, and exercise caution with complex regex patterns, especially those involving Unicode, even when using non-backtracking engines.

About the Speaker(s)

The talk was presented by Tingjian Ge, who is affiliated with the University of Michigan. The research is a collaborative effort with his colleagues, Weihao Su and Haiming Chen, from the Chinese Academy of Sciences. Their collective work focuses on advancing the understanding and detection of vulnerabilities related to regular expressions, particularly in the context of modern engine architectures.