{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T03:33:53Z","timestamp":1767929633453,"version":"3.49.0"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"PLDI","license":[{"start":{"date-parts":[[2023,6,6]],"date-time":"2023-06-06T00:00:00Z","timestamp":1686009600000},"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":[[2023,6,6]]},"abstract":"<jats:p>We develop a new derivative based theory and algorithm for nonbacktracking regex matching that supports anchors and counting, preserves backtracking semantics, and can be extended with lookarounds. The algorithm has been implemented as a new regex backend in .NET and was extensively tested as part of the formal release process of .NET7. We present a formal proof of the correctness of the algorithm, which we believe to be the first of its kind concerning industrial implementations of regex matchers. The paper describes the complete foundation, the matching algorithm, and key aspects of the implementation involving a regex rewrite system, as well as a comprehensive evaluation over industrial case studies and other regex engines.<\/jats:p>","DOI":"10.1145\/3591262","type":"journal-article","created":{"date-parts":[[2023,6,6]],"date-time":"2023-06-06T20:06:24Z","timestamp":1686081984000},"page":"1026-1049","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Derivative Based Nonbacktracking Real-World Regex Matching with Backtracking Semantics"],"prefix":"10.1145","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0009-0007-0144-9722","authenticated-orcid":false,"given":"Dan","family":"Moseley","sequence":"first","affiliation":[{"name":"Microsoft, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-9879-4282","authenticated-orcid":false,"given":"Mario","family":"Nishio","sequence":"additional","affiliation":[{"name":"Microsoft, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-6989-0555","authenticated-orcid":false,"given":"Jose","family":"Perez Rodriguez","sequence":"additional","affiliation":[{"name":"Microsoft, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7596-4734","authenticated-orcid":false,"given":"Olli","family":"Saarikivi","sequence":"additional","affiliation":[{"name":"Microsoft, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-5833-1311","authenticated-orcid":false,"given":"Stephen","family":"Toub","sequence":"additional","affiliation":[{"name":"Microsoft, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-8427-7977","authenticated-orcid":false,"given":"Margus","family":"Veanes","sequence":"additional","affiliation":[{"name":"Microsoft, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-1429-7679","authenticated-orcid":false,"given":"Tiki","family":"Wan","sequence":"additional","affiliation":[{"name":"Microsoft, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-8206-4908","authenticated-orcid":false,"given":"Eric","family":"Xu","sequence":"additional","affiliation":[{"name":"Microsoft, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,6,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-59042-0_96"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-43144-4_5"},{"key":"e_1_2_1_3_1","unstructured":"Adam Baldwin. 2016. Regular Expression Denial of Service affecting Express.js.  http:\/\/web.archive.org\/web\/20170116160113\/https:\/\/medium.com\/node-security\/regular-expression-denial-of-service-affecting-express-js-9c397c164c43 \t\t\t\t  Adam Baldwin. 2016. Regular Expression Denial of Service affecting Express.js.  http:\/\/web.archive.org\/web\/20170116160113\/https:\/\/medium.com\/node-security\/regular-expression-denial-of-service-affecting-express-js-9c397c164c43"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2021.01.010"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/176454.176484"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/321239.321249"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/D18-1547"},{"key":"e_1_2_1_8_1","unstructured":"Russ Cox. 2010. Regular Expression Matching in the Wild. https:\/\/swtch.com\/~rsc\/regexp\/regexp3.html \t\t\t\t  Russ Cox. 2010. Regular Expression Matching in the Wild. https:\/\/swtch.com\/~rsc\/regexp\/regexp3.html"},{"key":"e_1_2_1_9_1","unstructured":"CVC4. 2020.  https:\/\/github.com\/CVC4\/CVC4 \t\t\t\t  CVC4. 2020.  https:\/\/github.com\/CVC4\/CVC4"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535838.2535849"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3338906.3342509"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3236024.3236027"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78800-3_24"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1863543.1863594"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27836-8_53"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1070\/RM1961v016n05ABEH004112"},{"key":"e_1_2_1_17_1","unstructured":"GNU. 2020. grep.  https:\/\/www.gnu.org\/software\/grep\/ \t\t\t\t  GNU. 2020. grep.  https:\/\/www.gnu.org\/software\/grep\/"},{"key":"e_1_2_1_18_1","unstructured":"Google. 2021. RE2.  https:\/\/github.com\/google\/re2 \t\t\t\t  Google. 2021. RE2.  https:\/\/github.com\/google\/re2"},{"key":"e_1_2_1_19_1","volume-title":"Details of the Cloudflare outage on","author":"Graham-Cumming John","year":"2019","unstructured":"John Graham-Cumming . 2019. Details of the Cloudflare outage on July 2, 2019 . https:\/\/blog.cloudflare.com\/details-of-the-cloudflare-outage-on-july-2-2019\/ John Graham-Cumming. 2019. Details of the Cloudflare outage on July 2, 2019. https:\/\/blog.cloudflare.com\/details-of-the-cloudflare-outage-on-july-2-2019\/"},{"key":"e_1_2_1_20_1","unstructured":"Zoltan Herczeg. 2015. Performance comparison of regular expression engines.  https:\/\/zherczeg.github.io\/sljit\/regex_perf.html \t\t\t\t  Zoltan Herczeg. 2015. Performance comparison of regular expression engines.  https:\/\/zherczeg.github.io\/sljit\/regex_perf.html"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-18275-4_18"},{"key":"e_1_2_1_22_1","unstructured":"Intel Co. 2021. Hyperscan. https:\/\/github.com\/intel\/ \t\t\t\t  Intel Co. 2021. Hyperscan. https:\/\/github.com\/intel\/"},{"key":"e_1_2_1_23_1","unstructured":"Mario Ju\u00e1rez. 2020. Languages Regex Benchmark.  https:\/\/github.com\/mariomka\/regex-benchmark \t\t\t\t  Mario Ju\u00e1rez. 2020. Languages Regex Benchmark.  https:\/\/github.com\/mariomka\/regex-benchmark"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.FSTTCS.2014.175"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/256167.256195"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/SPIRE.2000.878194"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-24246-0_9"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314645"},{"key":"e_1_2_1_29_1","unstructured":"Microsoft. 2021. CredScan.  https:\/\/secdevtools.azurewebsites.net\/helpcredscan.html \t\t\t\t  Microsoft. 2021. CredScan.  https:\/\/secdevtools.azurewebsites.net\/helpcredscan.html"},{"key":"e_1_2_1_30_1","unstructured":"Microsoft. 2021. .NET Performance.  https:\/\/github.com\/dotnet\/performance \t\t\t\t  Microsoft. 2021. .NET Performance.  https:\/\/github.com\/dotnet\/performance"},{"key":"e_1_2_1_31_1","unstructured":"Microsoft. 2021. Regular Expression Language - Quick Reference.  https:\/\/docs.microsoft.com\/en-us\/dotnet\/standard\/base-types\/regular-expression-language-quick-reference \t\t\t\t  Microsoft. 2021. Regular Expression Language - Quick Reference.  https:\/\/docs.microsoft.com\/en-us\/dotnet\/standard\/base-types\/regular-expression-language-quick-reference"},{"key":"e_1_2_1_32_1","unstructured":"Microsoft. 2022. .NET Regular Expressions.  https:\/\/github.com\/dotnet\/runtime\/tree\/main\/src\/libraries\/System.Text.RegularExpressions \t\t\t\t  Microsoft. 2022. .NET Regular Expressions.  https:\/\/github.com\/dotnet\/runtime\/tree\/main\/src\/libraries\/System.Text.RegularExpressions"},{"key":"e_1_2_1_33_1","volume-title":"Olli Saarikivi, Stephen Toub, Margus Veanes, Tiki Wan, and Eric Xu.","author":"Moseley Dan","year":"2023","unstructured":"Dan Moseley , Mario Nishio , Jose Perez Rodriguez , Olli Saarikivi, Stephen Toub, Margus Veanes, Tiki Wan, and Eric Xu. 2023 . Derivative Based Nonbacktracking Real-World Regex Matching with Backtracking Semantics. Microsoft Research . https:\/\/www.microsoft.com\/en-us\/research\/publication\/derivative-based-nonbacktracking-real-world-regex-matching-with-backtracking-semantics\/ Dan Moseley, Mario Nishio, Jose Perez Rodriguez, Olli Saarikivi, Stephen Toub, Margus Veanes, Tiki Wan, and Eric Xu. 2023. Derivative Based Nonbacktracking Real-World Regex Matching with Backtracking Semantics. Microsoft Research. https:\/\/www.microsoft.com\/en-us\/research\/publication\/derivative-based-nonbacktracking-real-world-regex-matching-with-backtracking-semantics\/"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.7709500"},{"key":"e_1_2_1_35_1","unstructured":"OWASP. 2020. Regular expression Denial of Service - ReDoS. https:\/\/owasp.org\/www-community\/attacks\/Regular_expression_Denial_of_Service_-_ReDoS \t\t\t\t  OWASP. 2020. Regular expression Denial of Service - ReDoS. https:\/\/owasp.org\/www-community\/attacks\/Regular_expression_Denial_of_Service_-_ReDoS"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796808007090"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2775051.2677007"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17462-0_24"},{"key":"e_1_2_1_39_1","volume-title":"Software Solutions in C","author":"Spencer Henry","year":"1846","unstructured":"Henry Spencer . 1994. Software Solutions in C . Academic Press Professional, Inc. , San Diego, CA, USA . 35\u201371. isbn:012-632-3607 http:\/\/dl.acm.org\/citation.cfm?id=156626. 1846 89 Henry Spencer. 1994. Software Solutions in C. Academic Press Professional, Inc., San Diego, CA, USA. 35\u201371. isbn:012-632-3607 http:\/\/dl.acm.org\/citation.cfm?id=156626.184689"},{"key":"e_1_2_1_40_1","unstructured":"Stack Exchange. 2016. Outage Postmortem.  http:\/\/stackstatus.net\/post\/147710624694\/outage-postmortem-july-20-2016 \t\t\t\t  Stack Exchange. 2016. Outage Postmortem.  http:\/\/stackstatus.net\/post\/147710624694\/outage-postmortem-july-20-2016"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454066"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/800125.804029"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2370776.2370788"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/363347.363387"},{"key":"e_1_2_1_45_1","volume-title":"Counting in Regexes Considered Harmful: Exposing ReDoS Vulnerability of Nonbacktracking Matchers. In 31st USENIX Security Symposium (USENIX Security 22)","author":"Turo\u0148ov\u00e1 Lenka","year":"2022","unstructured":"Lenka Turo\u0148ov\u00e1 , Luk\u00e1\u0161 Hol\u00edk , Ivan Homoliak , Ond\u0159ej Leng\u00e1l , Margus Veanes , and Tom\u00e1\u0161 Vojnar . 2022 . Counting in Regexes Considered Harmful: Exposing ReDoS Vulnerability of Nonbacktracking Matchers. In 31st USENIX Security Symposium (USENIX Security 22) . USENIX Association, Boston, MA. 4165\u20134182. https:\/\/www.usenix.org\/conference\/usenixsecurity22\/presentation\/turonova Lenka Turo\u0148ov\u00e1, Luk\u00e1\u0161 Hol\u00edk, Ivan Homoliak, Ond\u0159ej Leng\u00e1l, Margus Veanes, and Tom\u00e1\u0161 Vojnar. 2022. Counting in Regexes Considered Harmful: Exposing ReDoS Vulnerability of Nonbacktracking Matchers. In 31st USENIX Security Symposium (USENIX Security 22). USENIX Association, Boston, MA. 4165\u20134182. https:\/\/www.usenix.org\/conference\/usenixsecurity22\/presentation\/turonova"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428286"},{"key":"#cr-split#-e_1_2_1_47_1.1","unstructured":"Ola Wingbrant. 2019. Regular languages derivatives and finite automata. https:\/\/doi.org\/10.48550\/ARXIV.1907.13577 10.48550\/ARXIV.1907.13577"},{"key":"#cr-split#-e_1_2_1_47_1.2","unstructured":"Ola Wingbrant. 2019. Regular languages derivatives and finite automata. https:\/\/doi.org\/10.48550\/ARXIV.1907.13577"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3591262","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3591262","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:20Z","timestamp":1750178840000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3591262"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,6]]},"references-count":48,"journal-issue":{"issue":"PLDI","published-print":{"date-parts":[[2023,6,6]]}},"alternative-id":["10.1145\/3591262"],"URL":"https:\/\/doi.org\/10.1145\/3591262","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,6]]},"assertion":[{"value":"2023-06-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}