Research · v1.0.1

A Two-Phase Matching Architecture for Provably Safe Regular Expression Engines: Eliminating Catastrophic Backtracking Through Algorithmic Design

Lars Shakya Buch-Jepsen

v1.0.1Latest stable release: 2026-11-21

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:

  1. Pathfinding Phase: Uses guaranteed linear-time NFA simulation to discover all possible ways the pattern could match the input
  2. 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.Tests with data under docs/measurements/redos-immunity/, measured on .NET 8.0.34) and the benign-overhead and feature-conformance harness (RegexFeatureConformanceTests with the committed 65-case corpus and the article-measurements CI job artifacts under docs/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.

ReDoS Vulnerability Test Results, measured on .NET 8.0.34 (committed suite, hard 10 s per-case timeout, CI-enforced)
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:

  1. 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.
  2. Unanchored (a+)+ and (a|a)* are not ReDoS patterns in any engine: they match the a-run prefix instantly everywhere; the blowup requires anchoring, which the anchored Davis variants demonstrate.
  3. .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):

Performance Comparison on Benign Inputs (measured)
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 Compatibility Analysis (measured; overall pass rate 80%, 52 of 65 corpus cases; alternation takes the longest match, measured and documented)
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.

References

[1]
S. A. Crosby and D. S. Wallach, “Denial of service via algorithmic complexity attacks,” in Proceedings of the 12th USENIX security symposium, 2003.
[2]
J. C. Davis, C. A. Coghlan, S. Kriebel, and L. G. Michael IV, “The impact of regular expression denial of service (ReDoS) in the wild,” in 2018 IEEE european symposium on security and privacy workshops (EuroS&PW), 2018.
[3]
Cloudflare, “Details of the cloudflare outage on 2 july 2019.” Cloudflare Blog, 2019. Available: https://blog.cloudflare.com/details-of-the-cloudflare-outage-on-2-july-2019/
[4]
N. Craver, “Outage postmortem — july 20, 2016.” Stack Exchange / nickcraver.com, 2016.
[5]
V. Wüstholz and A. O. Olivo, “Static detection of DoS vulnerabilities in programs that use regular expressions,” in European symposium on programming (ESOP), in LNCS, vol. 10201. 2017.
[6]
T. Rathnayake, “Detection of ReDoS vulnerabilities in web applications,” 2016.
[7]
R. Cox, “Regular expression matching can be simple and fast (but is slow in java, perl, PHP, python, ruby, ...).” swtch.com, 2007. Available: https://swtch.com/~rsc/regexp/regexp1.html
[8]
K. Thompson, “Programming techniques: Regular expression search algorithm,” Communications of the ACM, vol. 11, no. 6, pp. 419–422, 1968.