Research · v1.0.0

Formally Verified Parsers for Provable Security: A Coq-Based Approach to Certified ReDoS-Free Regular Expression Engines

Lars Shakya Buch-Jepsen

v1.0.0Latest stable release: 2026-11-15

Introduction

The security of modern software systems fundamentally depends on the correctness of their parsing infrastructure. Compilers, interpreters, web servers, and countless other applications rely on parsers to process input data safely and accurately. However, parsing systems are notoriously complex and error-prone, making them attractive targets for attackers seeking to exploit subtle implementation flaws [1], [2].

Among the most insidious parsing vulnerabilities are Regular Expression Denial of Service (ReDoS) attacks, where maliciously crafted input can cause exponential-time behavior in regex engines, leading to application freezes and service outages [3], [4]. High-profile incidents at Cloudflare, Stack Overflow, and other major services have demonstrated the real-world impact of these vulnerabilities [5].

The ReDoS Vulnerability Landscape

Traditional regular expression engines that use Nondeterministic Finite Automaton (NFA) simulation with backtracking are particularly susceptible to catastrophic performance degradation. The vulnerability arises from a combination of factors:

  1. Nested quantifiers: Patterns like (a+)+ or (a*)*b create exponential search spaces
  2. Alternation overlap: Constructs like (a|a)* allow multiple ways to match the same input
  3. Backtracking explosion: Failed matches trigger exponential exploration of alternative paths

The severity of this problem extends beyond individual applications. Modern software supply chains mean that vulnerable regex engines can affect thousands of downstream systems, creating systemic security risks [6].

Two Generations of ReDoS-Free Architecture

The architectural separation this paper builds on exists in two shipped generations.

The original generation is the two-layer regex engine: a single engine whose matching is split into a linear pathfinding scan (Phase 1) that treats capture groups, lookarounds and backreferences as non-consuming markers, and a bounded grouping and content resolution pass (Phase 2) that walks the scan’s potential-match records to finalize captures and validate the non-regular constructs. No implementation of the original engine survived; it has been recreated as a fully tested, runnable showcase [7], which also carries the committed measurement dataset reported in this paper.

The evolved generation is the ENFAStepLexer-StepParser system [8], which distributes the same protection across the lexer/parser boundary: the StepLexer is a forward-only matcher over compiled rule tables with no backtracking machinery at all, while structural work moves to the StepParser layer under a hard active-path budget. Section Architecture lineage traces this evolution; the evaluation section reports measured ReDoS tests against both generations.

Formal Verification as a Solution

Formal verification offers a principled approach to eliminating these vulnerabilities by providing mathematical proofs of program correctness [9]. Unlike testing, which can only demonstrate the presence of bugs, formal verification can prove their absence within the specified model.

The key insight of our work is that the architectural design choices in parsing systems dramatically affect the tractability of formal verification. The two-phase approach, which separates pathfinding from semantic validation, creates natural boundaries that align with formal verification techniques [10].

Research Contributions

This paper makes several key contributions:

  1. Formal Framework: We outline a formal model of the two-phase regex architecture in Coq, state the four proof obligations the development must discharge, and commit a concrete draft of the development alongside the article (Section Proposed Coq development).

  2. Linear Time Guarantees: We target a machine-checked proof that the scan performs at most \(m \cdot n\) elementary operations — \(m\) the automaton size, \(n\) the input length — eliminating ReDoS vulnerabilities by construction.

  3. Compositional Verification: We show how the architectural separation is designed to enable independent verification of lexical and syntactic components, making formal verification tractable for complex parsers.

  4. Measured Security Across Two Generations: We report committed measurements for both engine generations — the original two-layer engine and the evolved lexer/parser split — running the same adversarial ReDoS catalog on the same runtime, against the same .NET baselines. The tabulated figures are published benchmarks; the raw data is committed in the two engine repositories.

  5. Practical Tool Chain: We provide a complete tool chain from formal specifications to executable, verified parser code, enabling practical adoption of formal methods in parser development.

Verification status. The two-phase architecture described in this paper is shipped software in two generations: the original two-layer regex engine, recreated as the runnable showcase of [7], and the ENFAStepLexer-StepParser system [8] that evolved from it. Since v0.2.0, the performance figures in the evaluation section are measured: both engines run the identical adversarial ReDoS catalog with the raw data committed under docs/measurements/ in their repositories, and both test suites re-enforce the immunity properties continuously in CI. Since v0.3.0, the Coq formalization is drafted but not yet machine-checked: a concrete development plan and a ~260-line Coq draft (definitions, invariant structure, theorem statements, one completed proof) is committed alongside the article as coq/ReDoSFreeDraft.v. It has not been compiled; no machine-checked proof exists yet, and nothing in this paper should be read as a completed verification.

Methodology

Architectural Foundation for Verification

The key insight enabling our verification approach is the architectural separation inherent in the two-phase systems. This separation creates natural boundaries that align with formal verification techniques.

Two-Phase Architecture Analysis

The system’s two-phase approach provides several verification advantages. Phase 1 (pathfinding) operates purely on automaton structure: a breadth-first simulation over the product of automaton states and input positions, in which each (state, position) pair is expanded at most once. Phase 2 (semantic validation) is a fuel-bounded walk over the records the scan produced. The two phases have sharply different proof obligations: the scan carries the complexity guarantee, the resolution carries the capture semantics, and neither depends on the other’s internals.

Architecture Lineage: From the Two-Layer Engine to the Lexer/Parser Split

The two-phase separation was born in the original two-layer regex engine and was then carried forward, with the responsibilities redistributed across the lexer/parser boundary, into the ENFAStepLexer-StepParser system. Both generations are shipped, tested software, and both are measured in this paper’s evaluation.

Two-layer engine (original)     ENFAStepLexer-StepParser
------------------------------  --------------------------
Phase 1: pathfinding scan       StepLexer: forward-only
  - Thompson-NFA simulation    scanning over compiled rule
    over all alive (state,     tables; no backtracking
    position) pairs, each      machinery exists to attack
    visited once               StepParser: structural work
  - O(m*n) guaranteed;         under a hard active-path
    non-regular constructs     budget
    become markers             Immunity: unsupported
Phase 2: grouping & content    constructs are rejected at
  resolution: bounded          position 0 (fail-fast)
  post-scan walk; captures,
  lookaround sub-scans,
  backrefs; memoized,
  budgeted
Immunity: the linear scan
  itself evaluates the full
  pattern

The two generations answer the same threat with different mechanisms, and the difference matters for both verification and measurement:

  • The two-layer engine supports the non-regular constructs (groups, alternation, anchors, lookarounds, backreferences) and must therefore evaluate a hostile pattern against a hostile input. Its immunity is that the evaluation cannot blow up: Phase 1 visits each (state, position) pair at most once, so a structurally hopeless attack input costs exactly one linear pass, and Phase 2 runs only when the scan found a structural accept, bounded by memoization and a hard step budget. Because lookarounds are validated as bounded sub-scans rather than compiled into the search, the engine even accepts variable-length lookbehind, which classical engines reject outright.

  • The evolved system moves the boundary earlier. The StepLexer’s regular subset is compiled to forward-only rule tables; constructs outside the subset — including every pattern in the adversarial catalog below — are rejected at position 0 in microseconds. There is no backtracking machinery to attack. The structural remainder is handled by the StepParser layer under a hard active-path budget, so the polynomial bound is enforced by construction at both layers rather than by a post-scan resolution phase.

For the proposed Coq development, this lineage is the verification target: the same invariant — no phase, layer, or component may revisit or fork on an input position — is what the linear-time theorem must capture, whether it is stated over the two-layer engine’s scan/resolution pair or over the lexer/parser split.

Measurement Parity

Both engines are measured against the identical pattern catalog and adversarial inputs (the corpus of the two-phase architecture articles plus the catastrophic-backtracking patterns identified empirically by [2]), on the same runtime (.NET 8.0.34, Debian GNU/Linux 13) and against the same baselines: the .NET 8 backtracking engine under a 500 ms match timeout, and the in-box linear-time RegexOptions.NonBacktracking engine. One methodological difference is inherent to the engines and is stated openly: the two-layer engine is measured through its anchored full-input evaluation (MatchExact, the entry point carrying the complete O(m·n) guarantee), while the StepLexer is measured through tokenization, its only entry point. The raw data for both is committed: the two-layer dataset in the showcase repository [7] and the StepLexer dataset in the ENFA repository [8], both under docs/measurements/redos-immunity/.

Proposed Coq Development: Suggestion and Draft

This section is the concrete suggestion for the Coq formalization: what to prove, in which order, with which representations — and a committed draft. The draft (coq/ReDoSFreeDraft.v, in this article’s repository) is written in final-form Coq notation, carries the complete definition structure and one completed proof, and is honestly labeled not yet machine-checked: it has not been compiled, and the remaining proofs are open goals with a stated attack order.

Proof obligations

The development targets four theorems, in increasing order of difficulty:

  • T1 — Scan work bound (the ReDoS-freedom theorem). The scan performs at most \(m \cdot n + O(m + n)\) elementary operations. This is the paper’s central security claim, and it is provable with ordinary Coq tooling: the argument is a monotonicity invariant on a visited set of (state, position) pairs, not a deep dependent-type construction.

  • T2 — Scan correctness. The scan reports “accept alive” if and only if the marker-NFA’s accepting state is reachable from a start position. A standard simulation/reachability argument over the product automaton.

  • T3 — Resolution termination and budget honesty. The Phase 2 interpreter is fuel-recursive (termination by construction), and fuel exhaustion is reported — the engine may answer “budget exceeded”, never a wrong match and never a hang.

  • T4 — Resolution soundness under capture semantics. A match reported by Phase 2 satisfies the declarative semantics of the pattern: group spans are consistent, lookarounds reduce to sub-scan lemmas (this is where variable-length lookbehind becomes a theorem instead of an implementation trick), and backreferences compare by string equality. This is the research-grade obligation; the draft restricts the full semantics to the regular fragment and states the capture extension as the explicit final goal.

Representation choices (and why)

The suggestion rests on four choices, each made to keep proofs tractable rather than to maximize cleverness:

  1. Cost-instrumented semantics. “Time” is formalized as a step counter threaded through the functional definitions, in the style of verified-complexity developments. We prove the concrete bound steps <= m * n + c, not an asymptotic O-notation, because concrete bounds are what a reviewer can check against an implementation.

  2. Positions, not strings, in the hot path. The scan operates on (state : nat, pos : nat) pairs with alive sets as list nat carrying a NoDup invariant, and a visited : list (nat * nat) accumulator. The visited-set monotonicity is the entire complexity argument, and it needs only decidable equality — no heavy set libraries.

  3. Markers as data, not as control flow. Capture groups, anchors, lookarounds and backreferences are edges of the NFA (constructor marker), non-consuming for the scan. Phase 1 is then a pure NFA simulation whose proof obligations are classical, and all non-regular reasoning is quarantined in the Phase 2 soundness obligation (T4). This is precisely the architectural property the article claims makes verification tractable, turned into a proof decomposition.

  4. Plain stdlib first. Coq.Lists.List, Coq.Arith, Nat.eq_dec-based decision procedures. MathComp/SSReflect is an optional later refinement for the finite-cardinality bookkeeping; nothing in the roadmap needs it, and a first complete stdlib development is worth more than an elegant half-development.

Module structure

Regex.v         AST of the supported subset; declarative
                semantics (Inductive accepts)
Nfa.v           marker NFA record; compile : regex -> nfa
Scan.v          eclose/scan, step counter, visited-set
                invariant lemmas
Complexity.v    T1 scan_work_bound (the main theorem)
Resolve.v       fuel-bounded Phase 2 interpreter (T3)
Soundness.v     T2 + T4: scan correctness, capture soundness
Main.v          composition: Theorem matchexact_redos_free

Key definitions from the draft

The AST mirrors the showcase’s supported subset, characters as nat to keep the draft friction-free:

Inductive regex : Type :=
| RChar (c : nat) | RAny | RClass (cs : list nat) (neg : bool)
| RSeq (r1 r2 : regex) | RAlt (r1 r2 : regex)
| RStar (r : regex)
| RGroup (i : nat) (r : regex)          (* capture group i *)
| RAnchor (a : anchor)                  (* ^ or $ *)
| RLookB (r : regex) | RLookA (r : regex)
| RBackref (i : nat).

The marker NFA makes the scan regular; every non-regular construct is an annotation the scan carries without interpreting:

Inductive marker : Type :=
| MGroupS (i : nat) | MGroupE (i : nat)
| MAnchor (a : anchor)
| MLookB (r : regex) | MLookA (r : regex)
| MBackref (i : nat).

Record nfa : Type := {
  n_Q : nat;                    (* states 0 .. n_Q-1 *)
  n_start, n_accept : nat;
  n_eps  : nat -> list nat;     (* epsilon successors *)
  n_char : nat -> nat -> list nat;   (* successors on input char *)
  n_mark : nat -> list (marker * nat) (* non-consuming marker edges *)
}.

The scan is fuel-recursive over the input, threading the cost counter; its invariant is that the alive set stays NoDup and bounded by the state count:

Fixpoint scan (a : nfa) (input : list nat) (alive : list nat)
              (pos : nat) : result * nat :=
  match input with
  | [] => (decide_accept a alive pos, 0)
  | c :: rest =>
      let alive' := dedup (flat_map (fun q => n_char a q c) alive) in
      let (res, st) := scan a rest alive' (S pos) in
      (res, S st + length alive')
  end.

And the theorem the whole development exists for:

(* T1 - the ReDoS-freedom theorem *)
Theorem scan_work_bound :
  forall (a : nfa) (input : list nat),
    steps (scan a input (eclose a [n_start a]) 0)
      <= n_Q a * length input + n_Q a + 1.

The visited-pair monotonicity behind it is stated as two small lemmas in the draft — dedup_nodup and alive_bounded — with dedup_incl already proven:

Lemma dedup_incl : forall (l : list nat), incl (dedup l) l.
Proof.
  induction l as [|x t IH].
  - intros a Ha. exact Ha.
  - simpl. destruct (in_dec Nat.eq_dec x (dedup t)) as [Hx|Hx].
    + intros a Ha. right. apply IH. exact Ha.
    + intros a [Ha|Ha].
      * left. exact Ha.
      * right. apply IH. exact Ha.
Qed.

Proof order and honest status

The attack order, chosen so that each step unlocks a claim this article can then make without hedging:

  1. Scan.v invariants (NoDup preservation, bounded alive sets) — routine inductions.
  2. T1 — the visited-monotonicity counting argument; the hardest single insight, but a bounded one.
  3. T2 — simulation between scan and NFA reachability.
  4. T3 — immediate from the fuel structure; its value is pinning the honest budget contract.
  5. T4 — capture soundness; the long tail. Restrict first to the regular fragment plus groups, defer lookaround/backref lemmas.

A reasonable outcome is a certified Phase 1 (T1-T3, the security core) in the near term, with T4 following incrementally — mirroring how the measured engines already ship: the polynomial bound is enforced today, the semantic certification is the road ahead.

Implementation

Verified Parser Generator Architecture

Our implementation consists of several interconnected components that work together to produce verified parsers from high-level grammar specifications.

Code Generation Pipeline

The verified parser generator follows a multi-stage pipeline. Each stage maintains verification invariants: grammar-to-NFA preserves acceptance; NFA optimization maintains equivalence; code generation preserves semantic correctness; proof-and-extraction produces executable code carrying its proofs:

Definition generate_parser (grammar : Grammar) : VerifiedParser :=
  let nfa := grammar_to_nfa grammar in
  let optimized_nfa := optimize_nfa nfa in
  let parser_code := nfa_to_code optimized_nfa in
  prove_and_extract parser_code.

Each stage maintains verification invariants: 1. Grammar to NFA: Preserves language acceptance properties 2. NFA Optimization: Maintains equivalence while improving performance 3. Code Generation: Preserves semantic correctness 4. Proof and Extraction: Generates executable code with proofs

Experimental Evaluation

Evaluation status. All figures in this section are measured, not projected: they come from the committed datasets of the two engine repositories ([7], [8], raw data under each repository’s measurement directory), both generated on .NET 8.0.34, Debian GNU/Linux 13, and both re-enforced by CI test suites on every build. The measured engines are the shipped, unmodified showcase implementations; no figure in this section is a design target. What remains proposed — and is labeled as such throughout — is the Coq formalization.

ReDoS Attack Resistance: Measured on Both Generations

Table 1 reports the adversarial catalog: fourteen catastrophic-backtracking patterns (the article patterns plus the Davis et al. corpus [2]), each against its crafted adversarial input of 100 KB. The .NET backtracking baseline was given a 500 ms match timeout; twelve of the fourteen patterns exceed it. The two exceptions, the unanchored (a+)+ and (a|a)*, are not ReDoS patterns in any engine: they match the a-run prefix instantly, which is itself the demonstration that the blowup requires anchoring.

Measured ReDoS immunity of both engine generations, 100 KB adversarial inputs, .NET 8.0.34, Debian GNU/Linux 13. Times are the complete operation at \(n = 102{,}400\) (legend below).
Pattern Input .NET backtracking .NET NonBacktracking Two-layer StepLexer
(a+)+ \(a^{n-1}!\) 0.02 ms @ 1 KB, prefix 0.028 ms 109.7 ms, no 0.006 ms, ff
(a*)*b \(a^{n}\) TO @ 1 KB 1.846 ms 54.4 ms, no 0.006 ms, ff
(a|a)* \(a^{n-1}!\) 0.08 ms @ 1 KB, prefix 0.007 ms 78.6 ms, no 0.022 ms, ff
(.*a){10} \(b^{n-9}a^{9}\) TO @ 100 KB 2.166 ms 21.3 ms, no 0.015 ms, ff
.*(?:.*=.*) \(h^{n}\) TO @ 100 KB 1.562 ms 52.5 ms, no 0.005 ms, ff
^([\w\-.]+)*@([\w\-.]+)$ \(a^{n-1}!\) TO @ 1 KB 1.926 ms 72.8 ms, no 0.011 ms, ff
(a+)+$ \(a^{n}\) TO @ 1 KB 3.220 ms 313.1 ms, yes 0.011 ms, ff
(a|aa)+$ \(a^{n}\) TO @ 1 KB 3.045 ms 1084.7 ms, yes 0.005 ms, ff
([a-zA-Z]+)*$ \(a^{n}\) TO @ 1 KB 3.184 ms 274.7 ms, yes 0.009 ms, ff
(x+x+)+y \(x^{n}\) TO @ 1 KB 1.581 ms 178.4 ms, no 0.020 ms, ff
(a+)+b \(a^{n}\) TO @ 1 KB 1.605 ms 103.1 ms, no 0.010 ms, ff
(a|b|ab)*c \(a^{n}\) TO @ 100 KB 1.534 ms 84.3 ms, no 0.007 ms, ff
(a+)*$ \(a^{n}\) TO @ 1 KB 3.139 ms 453.2 ms, yes 0.005 ms, ff
(\w+\s?)*$ \(a^{n}\) TO @ 1 KB 3.103 ms 275.9 ms, yes 0.009 ms, ff

Legend (Table 1): TO = exceeded the 500 ms match timeout at the smallest input size shown; prefix = matches the a-run prefix at 1 KB (not a ReDoS case); no / yes = full-input rejection or confirmed match; ff = fail-fast rejection at position 0 (groups, alternation and anchors are outside the StepLexer’s forward-only subset). The two-layer column is the anchored full-input evaluation (MatchExact); the StepLexer column is full tokenization. Raw data in both repositories’ docs/measurements/redos-immunity/.

Three observations follow directly from the measured data:

  1. Both generations are immune, by two different mechanisms. The two-layer engine’s immunity is actual linear evaluation: it supports every construct in the catalog, scans the whole attack input once, proves the accepting state unreachable (or reachable, for the matching rows), and finishes in 21.3-178.4 ms for rejections and 274.7-1084.7 ms for the matching runs, with the bounded Phase 2 walk included. The StepLexer’s immunity is fail-fast: it rejects the pattern at position 0 in 5-63 microseconds because there is no backtracking machinery to attack.

  2. The matching rows cost more than the rejections, and honestly so. The five Davis patterns whose adversarial input does match require the two-layer engine to run Phase 2 over the whole potential-match DAG. The walk is bounded (memoized failures, in-progress cycle pruning, a 2,000,000-step budget) but its constant is dominated by per-frame capture snapshots: roughly 1-2 microseconds per input character, with (a|aa)+$ the worst case at about 1.1 s. No case exhausted the step budget, and every verdict was correct.

  3. The two-layer engine trades constant factors for the polynomial bound. Per case it is 10-600x slower than the production-grade NonBacktracking engine — an unoptimized showcase implementation against a tuned engine. The security claim is not speed but the absence of blowup: every case stays polynomial where the backtracking baseline exceeds a 500 ms timeout on twelve of fourteen patterns.

Execution Time Analysis: Linear Scaling, Measured

Table 2 fits evaluation time against input length over the scaling ladder {1, 4, 16, 32, 64, 100} KB (minimum of five repetitions per length, least-squares fit). For both engines the growth ratio \(t(100\,\mathrm{KB})/t(16\,\mathrm{KB})\) is compared against the linear prediction of 6.25; a quadratic regression would show 39.

Measured linear scaling, 1 KB -> 100 KB ladder, both engines (notes below).
Case Two-layer slope Two-layer R² / growth StepLexer slope StepLexer R² / growth
[a]+ full run 1951 ns/char 0.92 / 12.0 1.1 ns/byte 0.97 / 3.0
[a]*b full-scan no-match 353 ns/char 1.00 / 6.2 1.1 ns/byte 1.00 / 2.9
[ab]* full run 1946 ns/char 0.98 / 8.4 1.5 ns/byte 1.00 / 3.0
[^x]* negated full run 1802 ns/char 0.98 / 6.9 11.5 ns/byte 1.00 / 5.3
.*b dot full-scan no-match 441 ns/char 1.00 / 6.2 2.0 ns/byte 0.96 / 5.5
[a-zæøå]+ Danish run 1440 ns/char 0.99 / 8.0 2.4 ns/byte 0.98 / 2.9
[^x]* negated Danish run 1473 ns/char 0.98 / 10.0 8.4 ns/byte 1.00 / 5.7
^(a+)+$ evil no-match 885 ns/char 1.00 / 6.2 rejected at position 0 —
^(a*)*b$ evil no-match 467 ns/char 1.00 / 6.2 rejected at position 0 —
^([\w\-.]+)*@([\w\-.]+)$ evil no-match 618 ns/char 1.00 / 6.5 rejected at position 0 —

Notes (Table 2): the two-layer engine is measured per input character (UTF-16 code unit), the StepLexer per byte. R² is the coefficient of determination of the least-squares linear fit; growth is the measured ratio \(t(100\,\mathrm{KB})/t(16\,\mathrm{KB})\) against the linear prediction of 6.25.

The rejection runs of the two-layer engine (Phase 1 alone) sit at growth 6.2-10.0 with R² >= 0.98 — cleanly linear. The matching runs grow 8.4-12.0 with R² >= 0.92, still inside the linear envelope, with the excess attributable to allocation pressure of the per-frame capture snapshots noted above rather than to search complexity. The StepLexer’s supported-subset runs are linear at 1.1-11.5 ns/byte (the Unicode-property and case-folding ladder entries of the ENFA dataset have no two-layer counterpart: the showcase parser does not support \p{...} classes or inline flags, so those entries are skipped rather than approximated).

Known Characteristics, Measured and Pinned

Both datasets also pin their engines’ known characteristics at capped lengths, in the same honest spirit. The two-layer engine’s unanchored leftmost search runs one Phase 1 scan per candidate start position, so a pattern with a dense candidate set (for example a+b over an a-run, measured at 33.7 ms at 512 chars to 391.6 ms at 2 KB, approximately quadratic as documented) degrades to the \(O(m \cdot n^2)\) worst case; each individual scan stays linear, and the anchored entry points carry the full guarantee. The ENFA dataset analogously pins the superlinear path bookkeeping of overlapping multi-rule lexers (about 3.4 s at 16 KB, bounded by the parser layer’s active-path budget) and the quadratic per-token line/column cost. Neither characteristic is a ReDoS exposure; both are measured, asserted in CI at capped lengths, and recorded as follow-up optimization targets in their repositories.

Conclusion

This paper presents an architectural approach to formally verified parser generation for security-critical applications. By leveraging the architectural separation inherent in the two-phase systems, it outlines a strategy for making formal verification of complex parsing systems tractable.

Key Achievements

Security by architecture, measured on both generations: the original two-layer engine and the evolved lexer/parser split both complete the adversarial ReDoS catalog in bounded time — by linear evaluation and by fail-fast rejection respectively — with committed raw data and continuously enforced CI properties. Machine-checked Coq proofs of these properties remain proposed future work with a committed draft (see the Verification status note): the security core (T1-T3) is ordinary Coq tooling away, the capture soundness (T4) is the research-grade tail.

Practical performance (measured): the two-phase engines stay inside the linear scaling envelope on every measured case while the backtracking baseline times out on twelve of fourteen catalog patterns; the two-layer engine’s constant factors (1-2 microseconds per character on matching runs) are an honest showcase-grade cost of the polynomial bound, not a projection.

Scalable verification (proposed, drafted): the compositional verification strategy is designed to scale to real-world grammars; the committed draft fixes the module structure, the four proof obligations, and the attack order.

The convergence of advanced proof assistants, improved automation, and verification-aware system design suggests a future where formal correctness guarantees become routine rather than exceptional. Our work on verified parsers represents one step toward this vision of trustworthy computing infrastructure.

References

[1]
P.-H. Kamp, “You don’t know jack about software security,” ACM Queue, vol. 11, no. 4, pp. 1–8, 2013.
[2]
J. C. Davis, C. A. Coghlan, F. Servant, and D. Lee, “The impact of regular expression denial of service (ReDoS) in practice: An empirical study at the ecosystem scale,” Proceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, pp. 246–256, 2018.
[3]
S. A. Crosby and D. S. Wallach, “Denial of service via algorithmic complexity attacks,” 12th USENIX Security Symposium, pp. 29–44, 2003.
[4]
A. Rathnayake and R. Ragel, “Security vulnerabilities in regex,” ACM Computing Surveys, vol. 49, no. 2, pp. 1–31, 2016.
[5]
Cloudflare Inc., “Details of the cloudflare outage on july 2, 2019.” https://blog.cloudflare.com/details-of-the-cloudflare-outage-on-july-2-2019/, 2019.
[6]
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
[7]
L. S. Buch-Jepsen, “OriginalTwoLayerRegexArchitecture: A runnable showcase of the two-layer regex architecture.” https://github.com/DevelApp-ai/OriginalTwoLayerRegexArchitecture, 2026.
[8]
L. S. Buch-Jepsen, “ENFAStepLexer-StepParser.” https://github.com/DevelApp-ai/ENFAStepLexer-StepParser, 2026.
[9]
X. Leroy, “Formal verification of a realistic compiler,” Communications of the ACM, vol. 52, no. 7, pp. 107–115, 2009.
[10]
E. M. Clarke, J. M. Wing, et al., “Formal methods: State of the art and future directions,” ACM Computing Surveys, vol. 28, no. 4, pp. 626–643, 1996, doi: 10.1145/234988.234990.

Appendix

A. The Committed Coq Draft

The full draft lives in the article repository as coq/ReDoSFreeDraft.v. It contains, in order: the regex AST of the showcase’s supported subset; the declarative semantics (Inductive accepts) for the regular fragment; the marker NFA record and the Thompson compilation signature; the fuel-recursive epsilon closure and scan with the threaded step counter; the alive-set and visited-set invariant lemmas (including the completed dedup_incl proof); the fuel-bounded Phase 2 interpreter with its honest-budget contract; and the four target theorems T1-T4 stated with Admitted placeholders and a proof roadmap in comments.

Its two composition-level statements are reproduced here. The security core:

(* T1 - the ReDoS-freedom theorem (draft, admitted) *)
Theorem scan_work_bound :
  forall (a : nfa) (input : list nat),
    steps (scan a input (eclose a [n_start a]) 0)
      <= n_Q a * length input + n_Q a + 1.

and the end-to-end contract of MatchExact — bounded scan work, honest budget, no silent blowup:

Theorem matchexact_redos_free :
  forall (r : regex) (input : list nat),
    let (res, st) := matchexact (compile r) input in
      st <= n_Q (compile r) * length input + n_Q (compile r) + resolve_budget
      /\ (res = RMatch _ \/ res = RNoMatch \/ res = RBudget).

Both are Admitted in the draft; the roadmap comment in the file records the attack order of Section Proposed Coq development and which article claim each discharged obligation unlocks.