{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T08:45:25Z","timestamp":1780994725531,"version":"3.54.1"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"PLDI","license":[{"start":{"date-parts":[[2024,6,20]],"date-time":"2024-06-20T00:00:00Z","timestamp":1718841600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2024,6,20]]},"abstract":"<jats:p>Modern regex languages have strayed far from well-understood traditional regular expressions: they include features that fundamentally transform the matching problem. In exchange for these features, modern regex engines at times suffer from exponential complexity blowups, a frequent source of denial-of-service vulnerabilities in JavaScript applications. Worse, regex semantics differ across languages, and the impact of these divergences on algorithmic design and worst-case matching complexity has seldom been investigated.<\/jats:p>\n          <jats:p>This paper provides a novel perspective on JavaScript\u2019s regex semantics by identifying a larger-than-previously-understood subset of the language that can be matched with linear time guarantees. In the process, we discover several cases where state-of-the-art algorithms were either wrong (semantically incorrect), inefficient (suffering from superlinear complexity) or excessively restrictive (assuming certain features could not be matched linearly). We introduce novel algorithms to restore correctness and linear complexity. We further advance the state-of-the-art in linear regex matching by presenting the first nonbacktracking algorithms for matching lookarounds in linear time: one supporting captureless lookbehinds in any regex language, and another leveraging a JavaScript property to support unrestricted lookaheads and lookbehinds. Finally, we describe new time and space complexity tradeoffs for regex engines. All of our algorithms are practical: we validated them in a prototype implementation, and some have also been merged in the V8 JavaScript implementation used in Chrome and Node.js.<\/jats:p>","DOI":"10.1145\/3656431","type":"journal-article","created":{"date-parts":[[2024,6,20]],"date-time":"2024-06-20T16:27:20Z","timestamp":1718900840000},"page":"1336-1360","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Linear Matching of JavaScript Regular Expressions"],"prefix":"10.1145","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7297-2170","authenticated-orcid":false,"given":"Aur\u00e8le","family":"Barri\u00e8re","sequence":"first","affiliation":[{"name":"EPFL, Lausanne, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1900-3901","authenticated-orcid":false,"given":"Cl\u00e9ment","family":"Pit-Claudel","sequence":"additional","affiliation":[{"name":"EPFL, Lausanne, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,6,20]]},"reference":[{"key":"e_1_3_2_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-444-88071-0.50010-2"},{"key":"e_1_3_2_2_1","doi-asserted-by":"publisher","unstructured":"Aur\u00e8le Barri\u00e8re and Cl\u00e9ment Pit-Claudel. 2024. Artifact for \"Linear Matching of JavaScript Regular Expressions\" at PLDI 2024. https:\/\/doi.org\/10.5281\/ZENODO.10806044 10.5281\/ZENODO.10806044","DOI":"10.5281\/ZENODO.10806044"},{"key":"e_1_3_2_3_1","first-page":"30","volume-title":"Proceedings of the Prague Stringology Conference 2017, Prague, Czech Republic, August 28-30, 2017","author":"Berglund Martin","year":"2017","unstructured":"Martin Berglund and Brink van der Merwe. 2017. Regular Expressions with Backreferences Re-examined. In Proceedings of the Prague Stringology Conference 2017, Prague, Czech Republic, August 28-30, 2017. Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague, 30\u201341. http:\/\/www.stringology.org\/event\/2017\/p04.html"},{"key":"e_1_3_2_4_1","doi-asserted-by":"publisher","DOI":"10.3897\/jucs.66330"},{"key":"e_1_3_2_5_1","doi-asserted-by":"publisher","DOI":"10.1002\/SPE.2881"},{"key":"e_1_3_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2931037.2931073"},{"key":"e_1_3_2_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP46214.2022.9833597"},{"key":"e_1_3_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3591287"},{"key":"e_1_3_2_9_1","unstructured":"Chromium. 2009. Irregexp Google Chrome\u2019s New Regexp Implementation. https:\/\/blog.chromium.org\/2009\/02\/irregexp-google-chromes-new-regexp.html."},{"key":"e_1_3_2_10_1","unstructured":"Cloudflare. 2019. Details of the Cloudflare outage. https:\/\/blog.cloudflare.com\/details-of-the-cloudflare-outage-on-july-2-2019\/."},{"key":"e_1_3_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1292535.1292541"},{"key":"e_1_3_2_12_1","unstructured":"Russ Cox. 2007. Regular Expression Matching Can Be Simple And Fast. https:\/\/swtch.com\/~rsc\/regexp\/regexp1.html."},{"key":"e_1_3_2_13_1","unstructured":"Russ Cox. 2009. Regular Expression Matching: the Virtual Machine Approach. https:\/\/swtch.com\/~rsc\/regexp\/regexp2.html."},{"key":"e_1_3_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3236024.3236027"},{"key":"e_1_3_2_15_1","doi-asserted-by":"publisher","unstructured":"James C. Davis Louis G. Michael IV Christy A. Coghlan Francisco Servant and Dongyoon Lee. 2019. Why aren\u2019t regular expressions a lingua franca? an empirical study on the re-use and portability of regular expressions. In Proceedings of the ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering ESEC\/SIGSOFT FSE 2019 Marlon Dumas Dietmar Pfahl Sven Apel and Alessandra Russo (Eds.). ACM 443\u2013454. https:\/\/doi.org\/10.1145\/3338906.3338909 10.1145\/3338906.3338909","DOI":"10.1145\/3338906.3338909"},{"key":"e_1_3_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP40001.2021.00032"},{"key":"e_1_3_2_17_1","unstructured":"Mark Jason Dominus. 2000. Perl Regular Expression Matching is NP-Hard. https:\/\/perl.plover.com\/NPC\/NPC-3SAT.html."},{"key":"e_1_3_2_18_1","unstructured":"DukTape. 2013. DukTape Regular Expressions. https:\/\/github.com\/svaarala\/duktape\/blob\/master\/doc\/regexp.rst."},{"key":"e_1_3_2_19_1","unstructured":"ECMA-262. 2024. RegExp (Regular Expression) Objects. https:\/\/262.ecma-international.org\/13.0\/#sec-regexp-regular-expression-objects."},{"key":"e_1_3_2_20_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:FORM.0000017718.28096.48"},{"key":"e_1_3_2_21_1","unstructured":"Andrew Gallant. 2014. Crate regex: An implementation of regular expressions for Rust. https:\/\/docs.rs\/regex\/latest\/regex\/."},{"key":"e_1_3_2_22_1","unstructured":"Andrew Gallant. 2023. Regex engine internals as a library. https:\/\/blog.burntsushi.net\/regex-internals\/."},{"key":"e_1_3_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2071368.2071372"},{"key":"e_1_3_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3586044"},{"issue":"5","key":"e_1_3_2_25_1","first-page":"3","article-title":"Abstract theory of automata","volume":"16","author":"Glu\u0161kov V. M.","year":"1961","unstructured":"V. M. Glu\u0161kov. 1961. Abstract theory of automata. Uspehi Mat. Nauk 16, 5(101) (1961), 3\u201362.","journal-title":"Uspehi Mat. Nauk"},{"key":"e_1_3_2_26_1","unstructured":"Google. 2022. RE2: A fast safe thread-friendly alternative to backtracking regular expression engines like those used in PCRE Perl and Python. https:\/\/github.com\/google\/re2."},{"key":"e_1_3_2_27_1","unstructured":"Google. 2023. RE2 Wiki. https:\/\/github.com\/google\/re2\/wiki\/Glossary."},{"key":"e_1_3_2_28_1","unstructured":"Hermes. 2022. Hermes Regex Engine. https:\/\/hermesengine.dev\/docs\/regexp\/."},{"key":"e_1_3_2_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-30829-1_19"},{"key":"e_1_3_2_30_1","unstructured":"Iain Ireland. 2020. A New RegExp Engine in SpiderMonkey. https:\/\/hacks.mozilla.org\/2020\/06\/a-new-regexp-engine-in-spidermonkey\/."},{"key":"e_1_3_2_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38631-2_11"},{"key":"e_1_3_2_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/SPIRE.2000.878194"},{"key":"e_1_3_2_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP40001.2021.00062"},{"key":"e_1_3_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3632934"},{"key":"e_1_3_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3591262"},{"key":"e_1_3_2_36_1","unstructured":"MuJS. 2014. MuJS Regex Engine. https:\/\/github.com\/ccxvii\/mujs\/blob\/master\/regexp.c."},{"key":"e_1_3_2_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-10363-6_6"},{"key":"e_1_3_2_38_1","unstructured":"Rob Pike. 1987. The text editor sam. http:\/\/doc.cat-v.org\/plan_9\/4th_edition\/papers\/sam\/."},{"key":"e_1_3_2_39_1","unstructured":"QuickJS. 2020. QuickJS Regex Engine. https:\/\/github.com\/bellard\/quickjs\/blob\/master\/libregexp.c."},{"key":"e_1_3_2_40_1","unstructured":"RE2. 2017. GitHub Issue: Please Support Negative Lookahead. https:\/\/github.com\/google\/re2\/issues\/156."},{"key":"e_1_3_2_41_1","unstructured":"Markus L. Schmid. 2019. Regular Expressions with Backreferences: Polynomial-Time Matching Techniques. (2019). https:\/\/arxiv.org\/abs\/1903.05896"},{"key":"e_1_3_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3238147.3238159"},{"key":"e_1_3_2_43_1","unstructured":"Stack Exchange. 2016. Outage Postmortem. https:\/\/stackstatus.tumblr.com\/post\/147710624694\/outage-postmortem-july-20-2016."},{"key":"e_1_3_2_44_1","first-page":"361","volume-title":"27th USENIX Security Symposium, USENIX Security 2018","author":"Staicu Cristian-Alexandru","year":"2018","unstructured":"Cristian-Alexandru Staicu and Michael Pradel. 2018. Freezing the Web: A Study of ReDoS Vulnerabilities in JavaScriptbased Web Servers. In 27th USENIX Security Symposium, USENIX Security 2018. USENIX Association, 361\u2013376. https:\/\/www.usenix.org\/conference\/usenixsecurity18\/presentation\/staicu"},{"key":"e_1_3_2_45_1","unstructured":"TC39. 2010. test262. https:\/\/github.com\/tc39\/test262"},{"key":"e_1_3_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/363347.363387"},{"key":"e_1_3_2_47_1","unstructured":"TIOBE. 2023. Programming Community Index for April 2023. https:\/\/www.tiobe.com\/tiobe-index\/."},{"key":"e_1_3_2_48_1","article-title":"Regular Expression Improvements","author":"Toub Stephen","year":"2022","unstructured":"Stephen Toub. 2022. Regular Expression Improvements in .NET 7. https:\/\/devblogs.microsoft.com\/dotnet\/regular-expression-improvements-in-dotnet-7.","journal-title":"NET 7"},{"key":"e_1_3_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428286"},{"key":"e_1_3_2_50_1","unstructured":"V8. 2021. An Additional Non-backtracking RegExp Engine. https:\/\/v8.dev\/blog\/non-backtracking-regexp."},{"key":"e_1_3_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3129416.3129440"},{"key":"e_1_3_2_52_1","unstructured":"WebKit. 2018. JavaScriptCore RegExp Processing. https:\/\/trac.webkit.org\/wiki\/JSCRegExpProcessingAndJSCGoals."},{"key":"e_1_3_2_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-40946-7_27"},{"key":"e_1_3_2_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-54580-5_1"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3656431","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3656431","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T20:39:33Z","timestamp":1751661573000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3656431"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,20]]},"references-count":54,"journal-issue":{"issue":"PLDI","published-print":{"date-parts":[[2024,6,20]]}},"alternative-id":["10.1145\/3656431"],"URL":"https:\/\/doi.org\/10.1145\/3656431","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,6,20]]},"assertion":[{"value":"2024-06-20","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}