Formally Verified Parsers for Provable Security: A Coq-Based Approach to Certified ReDoS-Free Regular Expression Engines
Lars Shakya Buch-Jepsen
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:
- Nested quantifiers: Patterns like
(a+)+or(a*)*bcreate exponential search spaces - Alternation overlap: Constructs like
(a|a)*allow multiple ways to match the same input - 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:
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).
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.
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.
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.
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 ascoq/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:
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.Positions, not strings, in the hot path. The scan operates on
(state : nat, pos : nat)pairs with alive sets aslist natcarrying aNoDupinvariant, and avisited : list (nat * nat)accumulator. The visited-set monotonicity is the entire complexity argument, and it needs only decidable equality — no heavy set libraries.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.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:
Scan.vinvariants (NoDuppreservation, bounded alive sets) — routine inductions.- T1 — the visited-monotonicity counting argument; the hardest single insight, but a bounded one.
- T2 — simulation between
scanand NFA reachability. - T3 — immediate from the fuel structure; its value is pinning the honest budget contract.
- 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.
| 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:
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.
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.The two-layer engine trades constant factors for the polynomial bound. Per case it is 10-600x slower than the production-grade
NonBacktrackingengine — 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.
| 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
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.