A Two-Phase Matching Architecture for Provably Safe Regular Expression Engines: Eliminating Catastrophic Backtracking Through Algorithmic Design
Lars Shakya Buch-Jepsen
Introduction
Regular Expression Denial of Service (ReDoS) attacks represent one of the most insidious and widespread vulnerabilities in modern software systems. These attacks exploit the exponential worst-case behavior of traditional backtracking regular expression engines, where carefully crafted input can cause processing time to grow exponentially with input length [1], [2].
The severity and prevalence of ReDoS vulnerabilities has been demonstrated through high-profile incidents affecting major internet services. In July 2019, a single malformed regular expression brought down Cloudflare’s global network for 27 minutes, affecting millions of users worldwide [3]. Stack Overflow experienced a 34-minute outage in 2016 due to a ReDoS vulnerability in their post validation system [4]. These incidents highlight the critical need for regex engines that provide mathematical guarantees against catastrophic backtracking.
The Catastrophic Backtracking Problem
Traditional regular expression engines that use recursive backtracking face fundamental algorithmic limitations when processing certain pattern types:
Nested Quantifiers
Patterns like (a+)+ or (a*)*b create nested
choice points where the engine must explore exponentially many ways to
partition the input between inner and outer quantifiers.
Overlapping Alternations
Constructs like (a|a)* or (a|ab)* allow
multiple ways to match the same input prefix, leading to exponential
exploration of alternative paths.
Pathological Examples
Against input like "aaaaaaaaaaaaaaaaaX", the pattern
(a+)+X will attempt 2^n different ways to partition the
string of ‘a’ characters before failing at the final ‘X’.
Existing Mitigation Approaches
Current approaches to ReDoS mitigation fall into several categories, each with significant limitations:
Static Analysis
Tools that analyze regex patterns to identify potential vulnerabilities [5]. However, these approaches suffer from high false positive rates and cannot provide runtime guarantees.
Timeout Mechanisms
Simple timeouts abort long-running regex operations [6]. While preventing indefinite hangs, this approach can cause legitimate matches to fail and provides no guarantees about performance predictability.
Alternative Engine Architectures
Some engines use NFA simulation or derivative-based approaches [7]. While providing linear-time guarantees, these often lack compatibility with advanced regex features or suffer performance penalties on common patterns.
The complementary extreme in this design space is formal
verification: the companion article
formally-verified-parsers in this collection develops, as
proposed work with a committed Coq draft
(ReDoSFreeDraft.v), a machine-checked route toward
ReDoS-free parsing on which the phase-1 scanner defined here could
ultimately rely.
Our Two-Phase Architecture
This paper presents a novel two-phase architecture that provides mathematical guarantees against ReDoS, with its performance costs and its compatibility boundary measured precisely rather than estimated. The key insight is architectural separation: by decoupling pathfinding from semantic validation, we can provide linear-time guarantees for the overall matching process. The measured feature boundary of the shipped engine, and the validation-phase design surface beyond it, are reported honestly in the evaluation.
Core Innovation
The two-phase approach separates matching into distinct stages:
- Pathfinding Phase: Uses guaranteed linear-time NFA simulation to discover all possible ways the pattern could match the input
- Validation Phase: Applies semantic constraints and disambiguation rules to select the final match
This separation enables formal proofs that the entire process terminates in time linear in the input length for a fixed pattern, independent of the pathological behaviors that make backtracking engines exponential.
Methodology
Architectural Design Principles
Phase Separation
The fundamental design principle is the complete separation of path discovery from semantic validation:
public class TwoPhaseRegexEngine {
private readonly PathFinder pathFinder;
private readonly SemanticValidator validator;
public Match ExecuteMatch(string pattern, string input) {
// Phase 1: Linear-time path discovery
var paths = pathFinder.FindAllPaths(pattern, input);
// Phase 2: Semantic validation and disambiguation
return validator.SelectBestMatch(paths);
}
}Linear-Time Pathfinding
The pathfinding phase operates on a compiled NFA representation using Thompson’s construction [8]:
public class LinearPathFinder {
public List<MatchPath> FindAllPaths(NFA nfa, string input) {
var activePaths = new List<NFAPath> { nfa.InitialPath };
for (int i = 0; i < input.Length; i++) {
activePaths = StepAllPaths(activePaths, input[i]);
}
return activePaths.Where(p => p.IsAccepting).ToList();
}
}Linear Time Guarantee: The number of active paths is bounded by the number of NFA states, ensuring O(n \(\times\) m) complexity where n is input length and m is NFA size.
Semantic Validation
The validation phase processes discovered paths to apply disambiguation rules:
public class SemanticValidator {
public Match SelectBestMatch(List<MatchPath> paths) {
if (!paths.Any()) return Match.Failure;
// Apply standard disambiguation rules
var longestMatch = paths.MaxBy(p => p.Length);
var leftmostMatch = paths.Where(p => p.Length == longestMatch.Length)
.MinBy(p => p.StartPosition);
return CreateMatch(leftmostMatch);
}
}Mathematical Foundations
Complexity Analysis
Theorem 1 (Linear Time Bound): For any regular expression pattern P and input string S of length n, the two-phase matching algorithm terminates in O(n \(\times\) |P|) time; for a fixed pattern P, this is linear in the input length.
Proof Sketch: 1. NFA construction from pattern P produces at most O(|P|) states (a one-time compilation cost) 2. Each input character is processed exactly once 3. Path propagation at each step is bounded by the number of NFA states, O(|P|) 4. Therefore, the matching cost is O(n \(\times\) |P|); since the pattern is fixed at match time, this is O(n) in the input length alone
Theorem 2 (ReDoS Immunity): The two-phase architecture cannot exhibit exponential behavior regardless of input or pattern characteristics.
Proof: The pathfinding phase maintains at most one path per NFA state at any position. Since NFA state count is finite and bounded, exponential path explosion is impossible.
Correctness Guarantees
Theorem 3 (Semantic Preservation): For any regex pattern P and input S, the two-phase engine produces results equivalent to the POSIX longest-leftmost match semantics.
The separation of concerns enables independent reasoning about correctness: - Pathfinding correctness follows from standard NFA simulation theory - Semantic correctness follows from explicit application of POSIX disambiguation rules
Implementation
NFA Construction and Optimization
Thompson Construction Enhancement
We enhance standard Thompson construction to support modern regex features:
public class EnhancedThompsonConstructor {
public NFA BuildNFA(RegexPattern pattern) {
var nfa = new NFA();
// Handle basic constructs
switch (pattern.Type) {
case PatternType.Literal:
return BuildLiteral(pattern.Value);
case PatternType.Concatenation:
return BuildConcatenation(pattern.Children);
case PatternType.Alternation:
return BuildAlternation(pattern.Children);
case PatternType.Quantifier:
return BuildQuantifier(pattern.Inner, pattern.Min, pattern.Max);
// ... additional cases for advanced features
}
}
}State Minimization
While not strictly necessary for correctness, NFA minimization improves performance:
public NFA MinimizeNFA(NFA originalNFA) {
// Identify equivalent states
var equivalenceClasses = ComputeEquivalenceClasses(originalNFA);
// Merge equivalent states
return BuildMinimizedNFA(originalNFA, equivalenceClasses);
}Advanced Feature Support
The measured conformance boundary (see the evaluation) shows that the currently shipped forward-only NFA rejects zero-width assertions and capture-group extraction at compile time. The components below document the validation-phase design surface for those constructs, the architecture’s extension points, not currently shipped behavior.
Lookahead and Lookbehind
Zero-width assertions require special handling in the two-phase architecture:
public class AssertionHandler {
public bool EvaluateAssertion(AssertionType type, MatchContext context) {
return type switch {
AssertionType.PositiveLookahead => EvaluateLookahead(context, true),
AssertionType.NegativeLookahead => EvaluateLookahead(context, false),
AssertionType.WordBoundary => EvaluateWordBoundary(context),
_ => throw new NotSupportedException($"Assertion type {type} not supported")
};
}
}Capture Groups
Capture group handling is deferred to the validation phase:
public class CaptureGroupProcessor {
public Dictionary<int, string> ExtractCaptures(MatchPath path) {
var captures = new Dictionary<int, string>();
foreach (var segment in path.Segments) {
if (segment.IsCapture) {
captures[segment.GroupNumber] = segment.Text;
}
}
return captures;
}
}Experimental Evaluation
Evaluation status. The two-phase regex engine ships in ENFAStepLexer-StepParser, and the ReDoS-immunity mechanism is the one the repository actually runs, enforced in CI. Every quantitative result in this section is measured, not projected: the companion measurement issues closed with committed, reproducible data, namely the ReDoS-immunity and linear-scaling suite (
src/DevelApp.ReDos.Testswith data underdocs/measurements/redos-immunity/, measured on .NET 8.0.34) and the benign-overhead and feature-conformance harness (RegexFeatureConformanceTestswith the committed 65-case corpus and thearticle-measurementsCI job artifacts underdocs/measurements/issue-104/).
ReDoS Immunity (Measured)
The shipped engine’s immunity to catastrophic regex patterns is bounded by construction: constructs outside the supported single-rule greedy surface (groups, alternation, anchors) are rejected at compile time in nanoseconds, so the exponential search spaces of classic ReDoS patterns are never entered. The measured table reports this honestly: the engine column is fail-fast rejection, not fast matching.
| Pattern | StepLexer (100 KB) | NonBacktracking reference (100 KB) | Backtracking baseline (500 ms match timeout) |
|---|---|---|---|
(a*)*b |
0.007 ms (fail fast) | 1.9 ms | > 500 ms timeout at 1 KB |
(.*a){10} |
0.031 ms (fail fast) | 2.4 ms | > 500 ms timeout at 100 KB |
Cloudflare-style .*(?:.*=.*) |
0.005 ms (fail fast) | 1.8 ms | > 500 ms timeout at 100 KB |
| SO-style e-mail validation | 0.007 ms (fail fast) | 2.0 ms | > 500 ms timeout at 1 KB |
| Six anchored Davis-corpus classics | 0.005-0.063 ms (fail fast) | 1.6-3.6 ms | > 500 ms timeout each |
The reference column is .NET 8’s
RegexOptions.NonBacktracking (a linear-time engine); the
baseline column is the backtracking
System.Text.RegularExpressions engine under .NET’s 500 ms
match timeout. The six anchored Davis-corpus classics,
(a+)+$, (a|aa)+$, ([a-zA-Z]+)*$,
(x+x+)+y, (a+)+b and (a|b|ab)*c,
all time out the traditional engine while the shipped engine rejects
them at position 0.
Three honest findings the pre-measurement projections glossed over:
- Immunity for these patterns is fail-fast rejection, not fast matching. Groups, alternation and anchors are outside the shipped supported-subset surface (engine issue #83), so every pathological pattern above is rejected at position 0 in microseconds: bounded by construction, never exponential.
- Unanchored
(a+)+and(a|a)*are not ReDoS patterns in any engine: they match thea-run prefix instantly everywhere; the blowup requires anchoring, which the anchored Davis variants demonstrate. - .NET 8’s backtracking engine still blows up despite auto-atomicization: it exceeded the 500 ms match timeout on 10 of the 12 corpus patterns at 1-100 KB inputs.
The suite also pins multibyte UTF-8 robustness: adversarial grids over Danish ae, oe-stroke and a-ring input confirm that multibyte input matches whole code points, and ASCII-only patterns fail fast at byte 0 instead of mis-lexing a lead byte.
Linear-Scaling Validation (Measured)
On supported-subset analogues, least-squares fits from 1 KB to 100 KB
inputs give 1.3-12.7 ns/byte with R² between 0.995 and
0.9999, and growth ratios t(100 KB) / t(16 KB) between 2.97 and 5.56:
linear scaling predicts 6.25, quadratic 39. The worst case is the
negated class [^x]* at about 12.7 ns/byte. The fits are
asserted in CI (R² >= 0.90 and growth ratio <= 12 on every run,
with whole-curve re-measurement, minimum of 5 runs per point, to defeat
runner timing noise); the committed reports live under
docs/measurements/redos-immunity/.
A known overhead characteristic, measured and documented rather than asserted: per-token line/column bookkeeping is O(position), so many-token streams carry a quadratic term in token count (76.6 ms for 3,413 tokens at 10 KB; overlapping multi-rule lexers are similarly superlinear in rule count at capped lengths). It is bounded by the hard per-case timeout, is not a ReDoS exposure, and is recorded as the follow-up optimization opportunity.
Parser-Layer Ambiguous-Grammar Immunity (Measured)
The same boundedness property holds at the parser layer: an 18-theory
ambiguous-grammar grid (catastrophic-backtracking classics, Davis-corpus
grammars and scaling grammars at 1,024 / 10,240 / 102,400 bytes)
completes within a hard 30 s timeout and a path budget of at
most 10 paths. Two behaviors are pinned by tests rather than
assumed: paths resting at stack depth 1 are candidate complete parses,
so prefix inputs report success with one path by design; and path-budget
pruning is real, since ( 'a' | 'a' )+ over eight
as leaves no surviving parse at budget 10, so boundedness
is demonstrated on a small input rather than by pretending the ambiguous
grammar parses.
Benign-Pattern Overhead (Measured)
The original 8-20% overhead projection was optimistic. Measured
against .NET Regex(Compiled) on identical inputs and
identical match counts (the article-measurements CI job,
--measure-issue104; raw CSV and summary JSON committed as
run artifacts):
| Pipeline stage | Measured overhead vs Regex(Compiled) |
|---|---|
| Phase-1 scan | +54% to +179% |
| Full step pipeline | +1,723% to +8,205% |
| Allocations (phase-1) | -6% to +196% |
The honest reading: phase-1 scanning is measurably slower than a compiled backtracking engine on benign patterns, and the full step pipeline is materially slower still where many-token streams carry the bookkeeping term above. RE2 was not available as a .NET baseline in this run and remains an external-baseline item. Immunity for pathological patterns is not contingent on these benign-path costs: it holds by construction.
Feature Conformance (Measured)
The original 95-98% support estimates were optimistic. The committed
65-case, 26-feature conformance corpus
(src/DevelApp.StepLexer.Tests/Data/regex-conformance-corpus.tsv)
runs through the two-phase engine and an anchored .NET
Regex reference on every CI build, with the result diff
gated:
| Feature category | Measured agreement | Notes |
|---|---|---|
Core features: literals, character classes, dot, escapes, Unicode
classes (including non-ASCII), greedy/bounded/possessive quantifiers,
alternation, groups, (?i), atomic groups,
\Q..\E, (?#..) |
100% | Pinned as a CI gate |
Lookaround, backreferences, ^/$ anchors,
named groups, scoped modifiers, word boundaries |
0% | Rejected at compile time (forward-only NFA) |
| Lazy quantifiers | Divergent where backtracking matters | Measured and documented |
The measured feature boundary is a property, not a defect: the same forward-only design that gives ReDoS immunity rejects unsupported constructs at compile time, so the engine can never silently mis-match them.
Integration Considerations
The engine ships and is CI-gated in ENFAStepLexer-StepParser. Production-scale deployments are not part of this repo’s measured evidence, so no production case-study numbers are claimed here: the illustrative email-validation scenario from earlier drafts has been removed as unreproducible from the repository. The measurement suites run on every CI build, so the measured properties, compile-time rejection, linear scaling and 100% core-feature conformance, cannot silently regress.
Discussion
Architectural Benefits
Security by Design
The two-phase architecture provides security guarantees at the algorithmic level rather than through external mitigations. This represents a fundamental improvement over approaches that attempt to retrofit security onto inherently vulnerable designs.
Maintainability
The clear separation between pathfinding and validation simplifies both implementation and maintenance: - Pathfinding logic focuses purely on graph traversal - Validation logic handles only semantic concerns - Each phase can be optimized and tested independently
Extensibility
The architecture readily accommodates new regex features: - New syntax elements require only NFA construction updates - Advanced semantic features can be added to the validation phase - Performance optimizations can target either phase independently
Limitations and Challenges
Memory Usage
The two-phase approach requires storing all discovered paths before validation, potentially increasing memory usage for patterns with many possible matches. Measured allocations on the phase-1 scan range from 6% below to 196% above the compiled backtracking baseline depending on pattern class (see the benign-overhead table above), so the modest-overhead assumption was optimistic.
Feature Completeness
The measured conformance boundary is precise: core constructs agree with a compiled reference engine on 100% of the committed 65-case corpus, while lookaround, backreferences, anchors, named groups, scoped modifiers and word boundaries are rejected at compile time; supporting them within the linear-time constraint remains open engineering work.
Toward a PCRE2-Level Feature Surface (design)
The validation phase offers a natural home for the constructs the first phase deliberately excludes, and this subsection records that design direction as design, with no timeline and no performance claims. Backreferences and lookaround remain outside the linear-time guarantee of the first phase; the proposal is to evaluate them as bounded assertions over candidate spans during validation: once the first phase has produced a candidate match span, lookaround checks inspect windows around that span, and backreference checks compare capture groups already extracted from the span, so neither construct ever feeds the linear-time scan itself. Capture extraction composes naturally: group boundaries recorded per candidate by the first phase become submatch bookkeeping on surviving paths, and validation-phase assertions can consume those groups, giving a PCRE2-style feature surface layered on top of, rather than woven into, the linear-time core.
This is an open design surface: which assertion classes can be bounded without pathological worst cases, and how fallback interacts with the engine’s path budget, are unresolved design questions. No part of it is implemented, and nothing in the measured sections above should be read as evidence about it.
Adoption Barriers
Migrating from traditional regex engines requires careful validation to ensure behavior compatibility, particularly for edge cases where different engines historically produced different results.
Conclusion
This paper demonstrates that provably safe regular expression matching is achievable through careful architectural design. The two-phase approach eliminates an entire class of security vulnerabilities by construction, with the benign-path costs and the feature boundary measured and reported honestly in the evaluation above.
Key Achievements
Mathematical Guarantees: Formal proofs of linear-time complexity eliminate ReDoS vulnerabilities by construction rather than detection.
Measured performance: phase-1 scanning costs a measured +54% to +179% over a compiled backtracking engine on benign inputs (the full step pipeline more; see the evaluation), while pathological patterns are rejected at compile time in microseconds, bounded by construction.
Measured compatibility: 100% agreement with the reference engine on core constructs across the committed 65-case corpus, compile-time rejection of lookaround, backreferences and anchors, and an overall measured pass rate of 80%: a precise, CI-enforced feature boundary rather than an estimate.
Production validation: The engine ships in ENFAStepLexer-StepParser, with the ReDoS-immunity, scaling and conformance suites enforcing the measured properties on every CI build; the illustrative email-validation scenario has been removed as unreproducible from the repository.
Future Directions
The two-phase architecture opens several research directions: -
Parallel Processing: Independent path discovery enables
parallel execution - Advanced Optimizations:
Phase-specific optimizations can improve performance further
- Hybrid Approaches: Selective use of traditional
engines for proven-safe patterns
The ultimate goal is ubiquitous adoption of provably safe regex engines, eliminating ReDoS as a security concern across the entire software ecosystem.