Formal Verification for JavaScript Regular Expressions: a Proven Semantics and its Applications Conference: ; ; ISBN: 978-1-4503-XXXX-X/2018/06
Aurèle Barrière, Victor Deng, Clément Pit-Claudel · 2025
Read Formal Verification for JavaScript Regular Expressions: a Proven Semantics and its Applications Conference: ; ; ISBN: 978-1-4503-XXXX-X/2018/06 by Aurèle Barrière, Victor Deng, Clément Pit-Claudel (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-13091.txt.
Introduction
Aurèle Barrière, Victor Deng, and Clément Pit-Claudel give the first fully proven meaning for JavaScript regular expressions, the pattern language built into web code. Regular expressions with backtracking are subtle: a failed path is retried in a set order, and the official spec spells that out line by line in prose. Their version is short, complete, and proven equal to that spec.
Two uses show its worth. A new notion of when two patterns act alike lets them prove or refute rewrites drawn from past work. They also prove correct a fast matching engine used in real tools. Unlike past work, their version records the full tree of possible matches, not just the winner. All proofs were machine-checked.
Catalog record
| CREATOR | Aurèle Barrière, Victor Deng, Clément Pit-Claudel |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 142 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-13091
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Formal Verification for JavaScript Regular Expressions: a Proven Semantics and its Applications Conference: ; ; ISBN: 978-1-4503-XXXX-X/2018/06 Aurèle Barrière, Victor Deng, Clément Pit-Claudel Abstract . We present the first mechanized, succinct, practical, complete, and proven-faithful semantics for a modern regular expression language with backtracking semantics. We ensure its faithfulness by proving it equivalent to a preexisting line-by-line embedding of the official ECMAScript specification of JavaScript regular expressions. We demonstrate its practicality by presenting two real-world applications. First, a new notion of contextual equivalence for modern regular expressions, which we use to prove or disprove rewrites drawn from previous work. Second, the first formal proof of the PikeVM algorithm used in many real-world engines. In contrast with the specification and other formalization work, our semantics captures not only the top-priority match, but a full backtracking tree recording all possible matches and their respective priority. All our definitions and results have been mechanized in the Rocq proof assistant. 1. Introduction Despite sharing a name and some features, the modern regular expressions found in many programming languages and libraries are fundamentally different from traditional regular expressions. For one, with the addition of new features such as backreferences, modern regular expressions (which we call regexes in the rest of this paper) no longer correspond to regular languages, nor even to context-free languages ( Nogami and Terauchi 2023 ) . More importantly, with features such as capture groups, the matching problem changes. It no longer amounts to a recognition problem (checking that a string belongs to the language of a regular expression), but instead to a segmentation problem (extracting parts of a string that match individual subexpressions of a regex). For instance, matching the regex a(b) on string "abc" in JavaScript returns that the whole regex matched substring "ab" , and that the subexpression in parentheses matched substring "b" . From these features arises a new problem: when there are several ways to match a regex, which substring should be returned? One possible answer is given by the POSIX standard, favoring the leftmost-longest match of the regex. Another more popular answer is to prioritize the match that would be found by a backtracking algorithm. Many modern regex languages, such as the ones of Perl, JavaScript, Python, Go, Rust, Java, or .NET follow that disambiguation policy, called backtracking semantics (sometimes also called leftmost-greedy, or PCRE semantics). Between the new features and this disambiguation policy, the semantics of these modern regexes has become surprisingly large and complex. ECMAScript ( ECMA 2025 ) , the official JavaScript standard, dedicates more than 30 pages to the semantics of JavaScript regexes. This specification is so complex that semantics bugs are still regularly found in regex engines ( V8 2023 ; V8 2025 ) ; that the JavaScript implementation used in Firefox gave up on writing a regex engine and uses Google Chrome’s instead ( Ireland 2020 ) ; and in this work we exhibit semantics errors in the optimizer of a real-world JavaScript regex processor, regexp-tree ( Soshnikov 2025 ) . In this work, we present a new formal semantics for JavaScript regexes, that is mechanized, succinct, complete, practical, and proven to be correct. Despite decades of modern regexes being in wide use (including in more than 30% of JavaScript and Python packages ( Davis et al. 2018 ) ), and multiple previous formalization efforts ( Loring et al. 2019 ; Chida and Terauchi 2023 ; Chida and Terauchi 2024 ; Chen et al. 2022 ; Zhuchko et al. 2024 ; Chattopadhyay et al. 2025 ; De Santo et al. 2024 ) , this is the first time that a semantics enables practical mechanized verification for a real-world modern regex language. Our semantics is mechanized in the Rocq proof assistant (formerly known as Coq). It is proven to be faithful to the JavaScript semantics with a verified equivalence to Warblre ( De Santo et al. 2024 ) , an existing line-by-line embedding of the ECMAScript regex specification into Rocq that is easily auditable but verbose and impractical. It is succinct : the core rules of matching fit in a single page. It is complete : it supports all regex features of the 14 th edition of ECMAScript. Finally, it is practical for formal verification. We demonstrate this with two applications: a new formalized definition of contextual equivalence for regexes with backtracking semantics, and the first formal verification of a widely used matching algorithm. Interestingly, beyond the usual considerations of mechanized semantics design (convenient induction principles, strict positive occurrences etc.), we find that a key ingredient for a practical regex backtracking semantics is to not follow a backtracking algorithm. Instead, we formalize not only the one match returned by a backtracking algorithm, but instead all possible matches, ordered by priority. We claim the following novel contributions: • A new succinct, complete, practical formal semantics , mechanized in Rocq. • Evidence that this semantics is faithful to the ECMAScript regex standard, by proving it equivalent to the Warblre embedding ( De Santo et al. 2024 ) . • A new formal definition of equivalence for JavaScript regexes. We use it to prove the correctness of regex equations from the literature, as well as prove and disprove optimizations used in a real-world JavaScript regex processor. • The first formal verification of the PikeVM algorithm , a linear-time regex matching algorithm used in many real-world regex engines. This is the first time that NFA simulation with capture groups and backtracking semantics comes with a formal proof. The theorem relating our semantics model to the official ECMAScript standard makes this the first formal verification work directly connected to a real-world regex specification. Section 2 informally introduces JavaScript regexes. Section 3 presents our new inductive semantics and its properties. Section 4 shows its faithfulness by proving it equivalent to the Warblre embedding. We then present two formally verified applications. First, Section 5 defines our new regex equivalence and our case studies of correct and incorrect regex rewrites. Second, Section 6 presents our formal verification of the PikeVM algorithm. Finally, Section 7 discusses adapting and extending our work to other languages and applications, as well as related and future work. Our Rocq development, consisting of over 15k lines of definitions and proofs, is available as supplementary material. Appendix A links each individual paper definition to its Rocq counterpart. Some definitions have been simplified in the paper for presentation purposes. 2. Background on JavaScript Regexes 2.1. Syntax The abstract syntax of JavaScript regexes we use in this work is summarized on Figure 1 , with some modifications from concrete JavaScript syntax for presentation and convenience purposes. These differences are as follows. We use {\mathrm{\varepsilon}} instead of no string at all for the empty regex. In concrete JavaScript syntax, capture groups are pairs of parentheses that are implicitly associated with an index depending on their position in the regex. Here, we directly annotate each group with its index, \mathit{g} . For instance, (a(b)) in JavaScript syntax corresponds to {\mathrm{(_{1}\mskip 1.5mua(_{2}\mskip 1.5mub))}} . JavaScript also uses syntactic sugar (?< \mathit{name} > {\mathrm{\mathit{r}}} ) ( named group ) and \k< \mathit{name} > ( named backreference ) to refer to groups using names instead of indices. Group names can refer to one