{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,22]],"date-time":"2026-09-22T11:07:54Z","timestamp":1790075274660,"version":"4.0.1"},"reference-count":76,"publisher":"Association for Computing Machinery (ACM)","issue":"PLDI","license":[{"start":{"date-parts":[[2026,6,8]],"date-time":"2026-06-08T00:00:00Z","timestamp":1780876800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2026,6,8]]},"abstract":"<jats:p>\n                    Matching regexes (regular expressions) is a common problem in many areas of computer science, with requirements on high speed and robust performance. Regexes with backreferences allow one to express certain patterns (even beyond regular) concisely, however, since the matching is usually done by backtracking, the matching speed can degrade to a degree that constitutes a service failure or a security threat. To facilitate highspeed matching of such regexes, we propose\n                    <jats:italic toggle=\"yes\">register set automata<\/jats:italic>\n                    (RSAs), an extension of register automata where registers can contain\n                    <jats:italic toggle=\"yes\">sets<\/jats:italic>\n                    of symbols (from a potentially infinite alphabet) and the following operations are supported: adding input values to registers, merging or clearing registers, and testing whether a register contains a value. We show that a large class of\n                    <jats:italic toggle=\"yes\">register automata<\/jats:italic>\n                    can be transformed into\n                    <jats:italic toggle=\"yes\">deterministic<\/jats:italic>\n                    RSAs, which can serve as a basis for fast matching of a family of regexes with single-letter capture groups and backreferences. We also give a derivative-based algorithm for transforming a large class of regexes with backreferences to register automata and show that the time complexity of matching is linear and quadratic to the length of the input for finite and infinite alphabets respectively. Our prototype implementation of a regex matcher shows that our approach can significantly improve the robustness of state-of-the-art regex matchers on regexes with backreferences. We also study the theoretical properties of the model and show that the emptiness problem for RSAs is decidable and complete for the\n                    <jats:bold>F<\/jats:bold>\n                    <jats:sub>\n                      <jats:italic toggle=\"yes\">\u03c9<\/jats:italic>\n                    <\/jats:sub>\n                    class and that RSAs are incomparable in expressive power to other popular automata models over data words.\n                  <\/jats:p>","DOI":"10.1145\/3808281","type":"journal-article","created":{"date-parts":[[2026,6,8]],"date-time":"2026-06-08T18:04:09Z","timestamp":1780941849000},"page":"855-880","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Towards Efficient Matching of Regexes with Backreferences using Register Set Automata"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4375-7954","authenticated-orcid":false,"given":"Vojt\u011bch","family":"Havlena","sequence":"first","affiliation":[{"name":"Brno University of Technology, Brno, Czech Republic"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6957-1651","authenticated-orcid":false,"given":"Luk\u00e1\u0161","family":"Hol\u00edk","sequence":"additional","affiliation":[{"name":"Brno University of Technology, Brno, Czech Republic"},{"name":"Aalborg University, Aalborg, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3038-5875","authenticated-orcid":false,"given":"Ond\u0159ej","family":"Leng\u00e1l","sequence":"additional","affiliation":[{"name":"Brno University of Technology, Brno, Czech Republic"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-4410-0398","authenticated-orcid":false,"given":"Jan","family":"Va\u0161\u00e1k","sequence":"additional","affiliation":[{"name":"Brno University of Technology, Brno, Czech Republic"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-1783-9390","authenticated-orcid":false,"given":"Sab\u00edna","family":"Gul\u010d\u00edkov\u00e1","sequence":"additional","affiliation":[{"name":"Brno University of Technology, Brno, Czech Republic"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,8]]},"reference":[{"key":"e_1_3_1_2_2","unstructured":"Adar Weidman. 2025. Regular expression Denial of Service \u2013 ReDoS. https:\/\/owasp.org\/www-community\/attacks\/Regular_expression_Denial_of_Service_-_ReDoS. [Online; accessed 25-March-2025]."},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-444-88071-0.50010-2"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00182-4"},{"key":"e_1_3_1_5_2","unstructured":"Adam Baldwin. 2016. Regular Expression Denial of Service affecting Express.js. https:\/\/medium.com\/node-security\/regular-expression-denial-of-service-affecting-express-js-9c397c164c43. [Online; accessed 25-March-2025]."},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-33264-7_4"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3510003.3510047"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3656431"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/1544012.1544037"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/3708821.3733912"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38771-5_12"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/FCCM.2019.00025"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-64437-6_18"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1587\/TRANSINF.2022EDP7098"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/2535838.2535849"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3338906.3342509"},{"key":"e_1_3_1_17_2","volume-title":"On the Impact and Defeat of Regular Expression Denial of Service","author":"Davis James C.","year":"2020","unstructured":"James C. Davis. 2020. On the Impact and Defeat of Regular Expression Denial of Service. Ph. D. Dissertation. Virginia Tech, Blacksburg, VA, USA. http:\/\/hdl.handle.net\/10919\/98593"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3338906.3338909"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/1507244.1507246"},{"key":"e_1_3_1_20_2","unstructured":"V8 JavaScript Engine. 2024. V8 regular expression source code. Online. Available: https:\/\/github.com\/v8\/v8\/tree\/main\/src\/regexp [Accessed: 2024-11-17]."},{"key":"e_1_3_1_21_2","volume-title":"Automata Theory: An Algorithmic Approach","author":"Esparza Javier","year":"2023","unstructured":"Javier Esparza and Michael Blondin. 2023. Automata Theory: An Algorithmic Approach. MIT Press."},{"key":"e_1_3_1_22_2","unstructured":"M. Haertel et al. 2022. GNU grep. Online. Available: https:\/\/www.gnu.org\/software\/grep\/ [Accessed: 2024-11-17]."},{"key":"e_1_3_1_23_2","unstructured":"Stack Exchange. 2016. Outage Postmortem. http:\/\/stackstatus.net\/post\/147710624694\/outage-postmortem-july-202016."},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-8(1:22)2012"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/S00224-012-9389-0"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2019.04.001"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-63461-2_2"},{"key":"e_1_3_1_28_2","unstructured":"Google. 2022. RE2 Issue Tracker: Feature request #101: Add backreference support. https:\/\/github.com\/google\/re2\/issues\/101"},{"key":"e_1_3_1_29_2","unstructured":"Google. 2025. RE2. https:\/\/github.com\/google\/re2"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/SP46215.2023.10179442"},{"key":"e_1_3_1_31_2","unstructured":"Vojt\u011bch Havlena Luk\u00e1\u0161 Hol\u00edk Ond\u0159ej Leng\u00e1l Jan Va\u0161\u00e1k and Sab\u00edna Gul\u010d\u00edkov\u00e1. 2026. Towards Efficient Matching of Regexes with Backreferences using Register Set Automata (Technical Report). CoRR 2205.12114 (2026). arXiv:2205.12114 https:\/\/arxiv.org\/abs\/2205.12114"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","unstructured":"Vojt\u011bch Havlena Luk\u00e1\u0161 Hol\u00edk Jan Va\u0161\u00e1k Ond\u0159ej Leng\u00e1l and Sab\u00edna Gul\u010d\u00edkov\u00e1. 2026. Artifact for the PLDI\u201926 paper \u201cTowards Efficient Matching of Regexes with Backreferences using Register Set Automata\u201d. doi:10.5281\/zenodo.19223981","DOI":"10.5281\/zenodo.19223981"},{"key":"e_1_3_1_33_2","unstructured":"P. Hazel. 2024. Perl-compatible Regular Expressions. Online. Available: https:\/\/www.pcre.org\/ [Accessed: 2024-11-17]."},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-34175-6_24"},{"key":"e_1_3_1_35_2","unstructured":"Intel. 2022. HyperScan manual unsupported features. https:\/\/intel.github.io\/hyperscan\/dev-reference\/compilation.html#unsupported-constructs"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-25543-5_3"},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-013-5419-7"},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90242-9"},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38631-2_11"},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519939.3523456"},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1109\/SP40001.2021.00062"},{"key":"e_1_3_1_42_2","unstructured":"F. Lundh and A. M. Kuchling. 2023. Python Standard Library: re module. Online. Available: https:\/\/docs.python.org\/3\/library\/re.html [Accessed: 2024-11-17]."},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","DOI":"10.1109\/FCCM.2018.00048"},{"key":"e_1_3_1_44_2","first-page":"4219","volume-title":"31st USENIX Security Symposium, USENIX Security 2022, Boston, MA, USA, August 10-12, 2022","author":"McLaughlin Robert","year":"2022","unstructured":"Robert McLaughlin, Fabio Pagani, Noah Spahn, Christopher Kruegel, and Giovanni Vigna. 2022. Regulator: Dynamic Analysis to Detect ReDoS. In 31st USENIX Security Symposium, USENIX Security 2022, Boston, MA, USA, August 10-12, 2022, Kevin R. B. Butler and Kurt Thomas (Eds.). USENIX Association, 4219\u20134235. https:\/\/www.usenix.org\/conference\/usenixsecurity22\/presentation\/mclaughlin"},{"key":"e_1_3_1_45_2","unstructured":"Microsoft. 2024. .NET 8.0.110 regular expressions in System.Text.RegularExpressions. Online. Available: https:\/\/learn.microsoft.com\/en-us\/dotnet\/api\/system.text.regularexpressions?view=net-8.0 [Accessed: 2024-11-17]."},{"key":"e_1_3_1_46_2","doi-asserted-by":"publisher","DOI":"10.2307\/1970290"},{"key":"e_1_3_1_47_2","doi-asserted-by":"publisher","unstructured":"Andrzej S. Murawski Steven J. Ramsay and Nikos Tzevelekos. 2018. Polynomial-Time Equivalence Testing for Deterministic Fresh-Register Automata. (2018) 14 pages. doi:10.4230\/LIPICS.MFCS.2018.72","DOI":"10.4230\/LIPICS.MFCS.2018.72"},{"key":"e_1_3_1_48_2","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2010.5462149"},{"key":"e_1_3_1_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/1013560.1013562"},{"key":"e_1_3_1_50_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.MFCS.2025.81"},{"key":"e_1_3_1_51_2","unstructured":"OpenJDK. 2024. JDK 17 API Documentation: Regular Expressions. Online. Available: https:\/\/docs.oracle.com\/en\/java\/javase\/17\/docs\/api\/java.base\/java\/util\/regex\/package-summary.html [Accessed: 2024-11-17]."},{"key":"e_1_3_1_52_2","doi-asserted-by":"publisher","unstructured":"Francesco Parolini and Antoine Min\u00e9. 2022. Sound Static Analysis of Regular Expressions for Vulnerabilities to Denial of Service Attacks. In Theoretical Aspects of Software Engineering - 16th International Symposium TASE 2022 Cluj-Napoca Romania July 8-10 2022 Proceedings (Lecture Notes in Computer Science Vol. 13299) Yamine A\u00eft Ameur and Florin Craciun (Eds.). Springer 73\u201391. doi:10.1007\/978-3-031-10363-6_6","DOI":"10.1007\/978-3-031-10363-6_6"},{"key":"e_1_3_1_53_2","doi-asserted-by":"publisher","DOI":"10.1147\/rd.32.0114"},{"key":"e_1_3_1_54_2","unstructured":"Regex101.com. 2025. https:\/\/regex101.com. [Online; accessed 25-March-2025]."},{"key":"e_1_3_1_55_2","volume-title":"Snort: A Network Intrusion Detection and Prevention System","author":"Roesch M.","year":"2022","unstructured":"M. Roesch et al. 2022. Snort: A Network Intrusion Detection and Prevention System,. Cisco. http:\/\/www.snort.org"},{"key":"e_1_3_1_56_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00105-X"},{"key":"e_1_3_1_57_2","doi-asserted-by":"publisher","unstructured":"Markus L Schmid. 2016. Characterising REGEX Languages by Regular Languages Equipped with Factor-Referencing. 249 (Aug. 2016) 1\u201317. doi:10.1016\/j.ic.2016.02.003","DOI":"10.1016\/j.ic.2016.02.003"},{"key":"e_1_3_1_58_2","doi-asserted-by":"publisher","DOI":"10.1145\/2858784"},{"key":"e_1_3_1_59_2","unstructured":"Sylvain Schmitz. 2017. Algorithmic Complexity of Well-Quasi-Orders. Habilitation \u00e0 diriger des recherches. \u00c9cole normale sup\u00e9rieure Paris-Saclay. https:\/\/tel.archives-ouvertes.fr\/tel-01663266"},{"key":"e_1_3_1_60_2","unstructured":"Sylvain Schmitz and Philippe Schnoebelen. 2012. Algorithmic Aspects of WQO Theory. (Aug. 2012). https:\/\/cel.archives-ouvertes.fr\/cel-00727025"},{"key":"e_1_3_1_61_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40184-8_2"},{"key":"e_1_3_1_62_2","doi-asserted-by":"publisher","DOI":"10.1007\/11874683_3"},{"key":"e_1_3_1_63_2","doi-asserted-by":"publisher","DOI":"10.1145\/3238147.3238159"},{"key":"e_1_3_1_64_2","volume-title":"33rd USENIX Security Symposium, USENIX Security 2024, Philadelphia, PA, USA, August 14-16, 2024","author":"Su Weihao","year":"2024","unstructured":"Weihao Su, Hong Huang, Rongchen Li, Haiming Chen, and Tingjian Ge. 2024. Towards an Effective Method of ReDoS Detection for Non-backtracking Engines. In 33rd USENIX Security Symposium, USENIX Security 2024, Philadelphia, PA, USA, August 14-16, 2024, Davide Balzarotti and Wenyuan Xu (Eds.). USENIX Association. https:\/\/www.usenix.org\/conference\/usenixsecurity24\/presentation\/su-weihao"},{"key":"e_1_3_1_65_2","unstructured":"Nvidia Mellanox team. 2021. Personal communication."},{"key":"e_1_3_1_66_2","doi-asserted-by":"publisher","DOI":"10.1109\/CSF64896.2025.00011"},{"key":"e_1_3_1_67_2","doi-asserted-by":"publisher","DOI":"10.1145\/363347.363387"},{"key":"e_1_3_1_68_2","doi-asserted-by":"publisher","DOI":"10.1145\/335168.335171"},{"key":"e_1_3_1_69_2","first-page":"4165","volume-title":"31st USENIX Security Symposium, USENIX Security 2022, Boston, MA, USA, August 10-12, 2022","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 2022, Boston, MA, USA, August 10-12, 2022, Kevin R. B. Butler and Kurt Thomas (Eds.). USENIX Association, 4165\u20134182. https:\/\/www.usenix.org\/conference\/usenixsecurity22\/presentation\/turonova"},{"key":"e_1_3_1_70_2","doi-asserted-by":"publisher","DOI":"10.1145\/3428286"},{"key":"e_1_3_1_71_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-37075-5_2"},{"key":"e_1_3_1_72_2","doi-asserted-by":"publisher","DOI":"10.1145\/3704837"},{"key":"e_1_3_1_73_2","unstructured":"Jan Va\u0161\u00e1k. 2026. rsamatch. https:\/\/github.com\/VeriFIT\/RegisterSetAutomata"},{"key":"e_1_3_1_74_2","first-page":"631","volume-title":"NSDI\u201919","author":"Wang Xiang","year":"2019","unstructured":"Xiang Wang, Yang Hong, Harry Chang, KyoungSoo Park, Geoff Langdale, Jiayu Hu, and Heqing Zhu. 2019. Hyperscan: A Fast Multi-pattern Regex Matcher for Modern CPUs. In NSDI\u201919, Jay R. Lorch and Minlan Yu (Eds.). USENIX Association, 631\u2013648. https:\/\/www.usenix.org\/conference\/nsdi19\/presentation\/wang-xiang"},{"key":"e_1_3_1_75_2","doi-asserted-by":"publisher","unstructured":"Xinyi Wang Cen Zhang Yeting Li Zhiwu Xu Shuailin Huang Yi Liu Yican Yao Yang Xiao Yanyan Zou Yang Liu and Wei Huo. 2023. Effective ReDoS Detection by Principled Vulnerability Modeling and Exploit Generation. In 2023 IEEE Symposium on Security and Privacy (SP). 2427\u20132443. doi:10.1109\/SP46215.2023.10179328","DOI":"10.1109\/SP46215.2023.10179328"},{"key":"e_1_3_1_76_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-40946-7_27"},{"key":"e_1_3_1_77_2","doi-asserted-by":"publisher","unstructured":"Valentin W\u00fcstholz Oswaldo Olivo Marijn J. H. Heule and Isil Dillig. 2017. Static Detection of DoS Vulnerabilities in Programs that Use Regular Expressions. In Tools and Algorithms for the Construction and Analysis of Systems - 23rd International Conference TACAS 2017 Held as Part of the European Foint Conferences on Theory and Practice of Software ETAPS 2017 Uppsala Sweden April 22-29 2017 Proceedings Part II (Lecture Notes in Computer Science Vol. 10206) Axel Legay and Tiziana Margaria (Eds.). 3\u201320. doi:10.1007\/978-3-662-54580-5_1","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\/pdf\/10.1145\/3808281","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,9,22]],"date-time":"2026-09-22T10:50:35Z","timestamp":1790074235000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3808281"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,8]]},"references-count":76,"journal-issue":{"issue":"PLDI","published-print":{"date-parts":[[2026,6,8]]}},"alternative-id":["10.1145\/3808281"],"URL":"https:\/\/doi.org\/10.1145\/3808281","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,6,8]]},"assertion":[{"value":"2025-11-14","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-04-03","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-06-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}