{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,31]],"date-time":"2025-08-31T23:30:52Z","timestamp":1756683052610,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":63,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,10,8]],"date-time":"2022-10-08T00:00:00Z","timestamp":1665187200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2018910, 2124010"],"award-info":[{"award-number":["2018910, 2124010"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,10,8]]},"DOI":"10.1145\/3559009.3569664","type":"proceedings-article","created":{"date-parts":[[2023,1,27]],"date-time":"2023-01-27T14:02:50Z","timestamp":1674828170000},"page":"426-438","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Optimizing Regular Expressions via Rewrite-Guided Synthesis"],"prefix":"10.1145","author":[{"given":"Jedidiah","family":"McClurg","sequence":"first","affiliation":[{"name":"Colorado State University"}]},{"given":"Miles","family":"Claver","sequence":"additional","affiliation":[{"name":"Colorado School of Mines"}]},{"given":"Jackson","family":"Garner","sequence":"additional","affiliation":[{"name":"Colorado School of Mines"}]},{"given":"Jake","family":"Vossen","sequence":"additional","affiliation":[{"name":"Colorado School of Mines"}]},{"given":"Jordan","family":"Schmerge","sequence":"additional","affiliation":[{"name":"Colorado School of Mines"}]},{"given":"Mehmet E.","family":"Belviranli","sequence":"additional","affiliation":[{"name":"Colorado School of Mines"}]}],"member":"320","published-online":{"date-parts":[[2023,1,27]]},"reference":[{"key":"e_1_3_2_1_1_1","article-title":"Testing the Equivalence of Regular Languages","author":"Almeida Marco","year":"2010","unstructured":"Marco Almeida , Nelma Moreira , and Rog\u00e9rio Reis . \" Testing the Equivalence of Regular Languages \". In J. Autom. Lang. Comb. ( 2010 ). Marco Almeida, Nelma Moreira, and Rog\u00e9rio Reis. \"Testing the Equivalence of Regular Languages\". In J. Autom. Lang. Comb. (2010).","journal-title":"J. Autom. Lang. Comb. ("},{"key":"e_1_3_2_1_2_1","first-page":"1","article-title":"Syn-tax-Guided Synthesis","volume":"40","author":"Alur Rajeev","year":"2015","unstructured":"Rajeev Alur , Rastislav Bod\u00edk , Eric Dallal , Dana Fisman , Pranav Garg , Garvit Juniwal , Hadas Kress-Gazit , P. Madhusudan , Milo M. K. Martin , Mukund Raghothaman , Shambwaditya Saha , Sanjit A. Seshia , Rishabh Singh , Armando Solar-Lezama , Emina Torlak , and Abhishek Udupa . \" Syn-tax-Guided Synthesis \". In Dependable Software Systems Eng. Vol. 40 . 2015 , pp. 1 -- 25 . Rajeev Alur, Rastislav Bod\u00edk, Eric Dallal, Dana Fisman, Pranav Garg, Garvit Juniwal, Hadas Kress-Gazit, P. Madhusudan, Milo M. K. Martin, Mukund Raghothaman, Shambwaditya Saha, Sanjit A. Seshia, Rishabh Singh, Armando Solar-Lezama, Emina Torlak, and Abhishek Udupa. \"Syn-tax-Guided Synthesis\". In Dependable Software Systems Eng. Vol. 40. 2015, pp. 1--25.","journal-title":"Dependable Software Systems Eng."},{"key":"e_1_3_2_1_3_1","volume-title":"TACAS.","author":"Alur Rajeev","year":"2017","unstructured":"Rajeev Alur , Arjun Radhakrishna , and Abhishek Udupa . \" Scaling Enumerative Program Synthesis via Divide and Conquer\". In TACAS. 2017 . Rajeev Alur, Arjun Radhakrishna, and Abhishek Udupa. \"Scaling Enumerative Program Synthesis via Divide and Conquer\". In TACAS. 2017."},{"key":"e_1_3_2_1_4_1","volume-title":"AFL. EPTCS.","author":"Berglund Martin","year":"2014","unstructured":"Martin Berglund , Frank Drewes , and Brink van der Merwe . \" Analyzing Catastrophic Backtracking Behavior in Practical Regular Expression Matching\". In AFL. EPTCS. 2014 . Martin Berglund, Frank Drewes, and Brink van der Merwe. \"Analyzing Catastrophic Backtracking Behavior in Practical Regular Expression Matching\". In AFL. EPTCS. 2014."},{"key":"e_1_3_2_1_5_1","volume-title":"Comput. Sci.","author":"Berry G\u00e9rard","year":"1992","unstructured":"G\u00e9rard Berry and G\u00e9rard Boudol . \" The Chemical Abstract Machine\". In Theor . Comput. Sci. ( 1992 ). G\u00e9rard Berry and G\u00e9rard Boudol. \"The Chemical Abstract Machine\". In Theor. Comput. Sci. (1992)."},{"key":"e_1_3_2_1_6_1","volume-title":"POPL.","author":"Bonchi Filippo","year":"2013","unstructured":"Filippo Bonchi and Damien Pous . \" Checking NFA equivalence with bisimulations up to congruence\". In POPL. 2013 . Filippo Bonchi and Damien Pous. \"Checking NFA equivalence with bisimulations up to congruence\". In POPL. 2013."},{"key":"e_1_3_2_1_7_1","first-page":"775","article-title":"Optimizing synthesis with metasketches","author":"Bornholt James","year":"2016","unstructured":"James Bornholt , Emina Torlak , Dan Grossman , and Luis Ceze . \" Optimizing synthesis with metasketches \". In POPL. ACM , 2016 , pp. 775 -- 788 . James Bornholt, Emina Torlak, Dan Grossman, and Luis Ceze. \"Optimizing synthesis with metasketches\". In POPL. ACM, 2016, pp. 775--788.","journal-title":"POPL. ACM"},{"key":"e_1_3_2_1_8_1","volume-title":"Computer","author":"Brooks Frederick P.","year":"1987","unstructured":"Frederick P. Brooks . \" No Silver Bullet - Essence and Accidents of Software Engineering\". In Computer ( 1987 ). Frederick P. Brooks. \"No Silver Bullet - Essence and Accidents of Software Engineering\". In Computer (1987)."},{"key":"e_1_3_2_1_9_1","volume-title":"PACT.","author":"Cameron Robert D.","year":"2014","unstructured":"Robert D. Cameron , Thomas C. Shermer , Arrvindh Shriraman , Kenneth S. Herdy , Dan Lin , Benjamin R. Hull , and Meng Lin . \" Bitwise data parallelism in regular expression matching\". In PACT. 2014 . Robert D. Cameron, Thomas C. Shermer, Arrvindh Shriraman, Kenneth S. Herdy, Dan Lin, Benjamin R. Hull, and Meng Lin. \"Bitwise data parallelism in regular expression matching\". In PACT. 2014."},{"key":"e_1_3_2_1_10_1","volume-title":"DCFS.","author":"C\u00e2mpeanu Cezar","year":"2015","unstructured":"Cezar C\u00e2mpeanu and Kai Salomaa . \" Nondeterministic Tree Width of Regular Languages\". In DCFS. 2015 . Cezar C\u00e2mpeanu and Kai Salomaa. \"Nondeterministic Tree Width of Regular Languages\". In DCFS. 2015."},{"key":"e_1_3_2_1_11_1","volume-title":"CAV.","author":"Cardelli Luca","year":"2017","unstructured":"Luca Cardelli , Milan Ceska , Martin Fr\u00e4nzle , Marta Z. Kwiatkowska , Luca Laurenti , Nicola Paoletti , and Max Whitby . \" Syntax-Guided Optimal Synthesis for Chemical Reaction Networks\". In CAV. 2017 . Luca Cardelli, Milan Ceska, Martin Fr\u00e4nzle, Marta Z. Kwiatkowska, Luca Laurenti, Nicola Paoletti, and Max Whitby. \"Syntax-Guided Optimal Synthesis for Chemical Reaction Networks\". In CAV. 2017."},{"key":"e_1_3_2_1_12_1","volume-title":"CAV.","author":"Cern\u00fd Pavol","year":"2013","unstructured":"Pavol Cern\u00fd , Thomas A. Henzinger , Arjun Radhakrishna , Leonid Ryzhyk , and Thorsten Tarrach . \" Efficient Synthesis for Concurrency by Semantics-Preserving Transformations\". In CAV. 2013 . Pavol Cern\u00fd, Thomas A. Henzinger, Arjun Radhakrishna, Leonid Ryzhyk, and Thorsten Tarrach. \"Efficient Synthesis for Concurrency by Semantics-Preserving Transformations\". In CAV. 2013."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.4204\/EPTCS.229.3"},{"key":"e_1_3_2_1_14_1","volume-title":"PLDI.","author":"Chen Qiaochu","year":"2020","unstructured":"Qiaochu Chen , Xinyu Wang , Xi Ye , Greg Durrett , and Isil Dillig . \"Multi-modal synthesis of regular expressions\". In PLDI. 2020 . Qiaochu Chen, Xinyu Wang, Xi Ye, Greg Durrett, and Isil Dillig. \"Multi-modal synthesis of regular expressions\". In PLDI. 2020."},{"key":"e_1_3_2_1_15_1","volume-title":"by Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d'Alch\u00e9-Buc, Emily B. Fox, and Roman Garnett.","author":"Chen Xinyun","year":"2019","unstructured":"Xinyun Chen and Yuandong Tian . \" Learning to Perform Local Rewriting for Combinatorial Optimization\". In NeurIPS. Ed. by Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d'Alch\u00e9-Buc, Emily B. Fox, and Roman Garnett. 2019 . Xinyun Chen and Yuandong Tian. \"Learning to Perform Local Rewriting for Combinatorial Optimization\". In NeurIPS. Ed. by Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d'Alch\u00e9-Buc, Emily B. Fox, and Roman Garnett. 2019."},{"key":"e_1_3_2_1_16_1","unstructured":"Russ Cox. Regular Expression Matching Can Be Simple And Fast (but is slow in Java Perl PHP Python Ruby ...) https:\/\/swtch.com\/~rsc\/regexp\/regexp1.html.  Russ Cox. Regular Expression Matching Can Be Simple And Fast (but is slow in Java Perl PHP Python Ruby ...) https:\/\/swtch.com\/~rsc\/regexp\/regexp1.html."},{"key":"e_1_3_2_1_17_1","volume-title":"USENIX Security Symposium.","author":"Scott","year":"2003","unstructured":"Scott A. Crosby and Dan S. Wallach. \"Denial of Service via Algorithmic Complexity Attacks \". In USENIX Security Symposium. 2003 . Scott A. Crosby and Dan S. Wallach. \"Denial of Service via Algorithmic Complexity Attacks\". In USENIX Security Symposium. 2003."},{"key":"e_1_3_2_1_18_1","volume-title":"ESEC\/SIGSOFT FSE.","author":"Davis James C.","year":"2019","unstructured":"James C. Davis . \" Rethinking Regex engines to address ReDoS\". In ESEC\/SIGSOFT FSE. 2019 . James C. Davis. \"Rethinking Regex engines to address ReDoS\". In ESEC\/SIGSOFT FSE. 2019."},{"key":"e_1_3_2_1_19_1","volume-title":"FSE.","author":"Davis James C.","year":"2018","unstructured":"James C. Davis , Christy A. Coghlan , Francisco Servant , and Dongyoon Lee . \" The impact of regular expression denial of service (ReDoS) in practice : an empirical study at the ecosystem scale \". In FSE. 2018 . James C. Davis, Christy A. Coghlan, Francisco Servant, and Dongyoon Lee. \"The impact of regular expression denial of service (ReDoS) in practice: an empirical study at the ecosystem scale\". In FSE. 2018."},{"key":"e_1_3_2_1_20_1","volume-title":"SETTA.","author":"Fu Chen","year":"2017","unstructured":"Chen Fu , Yuxin Deng , David N. Jansen , and Lijun Zhang . \" On Equivalence Checking of Nondeterministic Finite Automata\". In SETTA. 2017 . Chen Fu, Yuxin Deng, David N. Jansen, and Lijun Zhang. \"On Equivalence Checking of Nondeterministic Finite Automata\". In SETTA. 2017."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.2016.7783747"},{"key":"e_1_3_2_1_22_1","unstructured":"Jan Goyvaerts. Runaway Regular Expressions: Catastrophic Backtracking. https:\/\/www.regular-expressions.info\/catastrophic.html.  Jan Goyvaerts. Runaway Regular Expressions: Catastrophic Backtracking. https:\/\/www.regular-expressions.info\/catastrophic.html."},{"key":"e_1_3_2_1_23_1","volume-title":"Information and Computation","author":"Hromkovic Juraj","year":"2002","unstructured":"Juraj Hromkovic , Sebastian Seibert , Juhani Karhum\u00e4ki , Hartmut Klauck , and Georg Schnitger . \" Communication Complexity Method for Measuring Nondeterminism in Finite Automata\". In Information and Computation ( 2002 ). Juraj Hromkovic, Sebastian Seibert, Juhani Karhum\u00e4ki, Hartmut Klauck, and Georg Schnitger. \"Communication Complexity Method for Measuring Nondeterminism in Finite Automata\". In Information and Computation (2002)."},{"key":"e_1_3_2_1_24_1","volume-title":"PLDI.","author":"Huang Kangjing","year":"2020","unstructured":"Kangjing Huang , Xiaokang Qiu , Peiyuan Shen , and Yanjun Wang . \" Reconciling enumerative and deductive program synthesis\". In PLDI. 2020 . Kangjing Huang, Xiaokang Qiu, Peiyuan Shen, and Yanjun Wang. \"Reconciling enumerative and deductive program synthesis\". In PLDI. 2020."},{"key":"e_1_3_2_1_25_1","volume-title":"CAV.","author":"Jeon Jinseong","year":"2015","unstructured":"Jinseong Jeon , Xiaokang Qiu , Armando Solar-Lezama , and Jeffrey Foster . \" Adaptive Concretization for Parallel Program Synthesis\". In CAV. 2015 . Jinseong Jeon, Xiaokang Qiu, Armando Solar-Lezama, and Jeffrey Foster. \"Adaptive Concretization for Parallel Program Synthesis\". In CAV. 2015."},{"key":"e_1_3_2_1_26_1","volume-title":"NSS.","author":"Kirrage James","year":"2013","unstructured":"James Kirrage , Asiri Rathnayake , and Hayo Thielecke . \" Static Analysis for Regular Expression Denial-of- Service Attacks\". In NSS. 2013 . James Kirrage, Asiri Rathnayake, and Hayo Thielecke. \"Static Analysis for Regular Expression Denial-of-Service Attacks\". In NSS. 2013."},{"key":"e_1_3_2_1_27_1","unstructured":"Dan Kogai. Regexp::Optimizer. https:\/\/metacpan.org\/pod\/release\/DANKOGAI\/Regexp-Optimizer-0.15\/lib\/Regexp\/Optimizer.pm.  Dan Kogai. Regexp::Optimizer. https:\/\/metacpan.org\/pod\/release\/DANKOGAI\/Regexp-Optimizer-0.15\/lib\/Regexp\/Optimizer.pm."},{"key":"e_1_3_2_1_28_1","volume-title":"LICS.","author":"Kozen Dexter","year":"1991","unstructured":"Dexter Kozen . \" A Completeness Theorem for Kleene Algebras and the Algebra of Regular Events\". In LICS. 1991 . Dexter Kozen. \"A Completeness Theorem for Kleene Algebras and the Algebra of Regular Events\". In LICS. 1991."},{"key":"e_1_3_2_1_29_1","volume-title":"PLDI.","author":"Lee DongKwon","year":"2020","unstructured":"DongKwon Lee , Woosuk Lee , Hakjoo Oh , and Kwangkeun Yi. \"Optimizing homomorphic evaluation circuits by program synthesis and term rewriting\". In PLDI. 2020 . DongKwon Lee, Woosuk Lee, Hakjoo Oh, and Kwangkeun Yi. \"Optimizing homomorphic evaluation circuits by program synthesis and term rewriting\". In PLDI. 2020."},{"key":"e_1_3_2_1_30_1","volume-title":"ICSE.","author":"Loncaric Calvin","year":"2018","unstructured":"Calvin Loncaric , Michael D. Ernst , and Emina Torlak . \" Generalized data structure synthesis\". In ICSE. 2018 . Calvin Loncaric, Michael D. Ernst, and Emina Torlak. \"Generalized data structure synthesis\". In ICSE. 2018."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2908080.2908122"},{"key":"e_1_3_2_1_32_1","volume-title":"MICRO.","author":"van Lunteren Jan","year":"2012","unstructured":"Jan van Lunteren , Christoph Hagleitner , Timothy Heil , Giora Biran , Uzi Shvadron , and Kubilay Atasu . \" Designing a Programmable Wire-Speed Regular-Expression Matching Accelerator\". In MICRO. 2012 . Jan van Lunteren, Christoph Hagleitner, Timothy Heil, Giora Biran, Uzi Shvadron, and Kubilay Atasu. \"Designing a Programmable Wire-Speed Regular-Expression Matching Accelerator\". In MICRO. 2012."},{"key":"e_1_3_2_1_33_1","volume-title":"PLDI.","author":"Mamouras Konstantinos","year":"2022","unstructured":"Konstantinos Mamouras , Kaiyuan Yang , Lingkun Kong , Qixuan Yu , Agnishom Chattopadhyay , Alexis Le Glaunec, and Yi Huang. \"Software-Hardware Codesign for Efficient In-Memory Regular Pattern Matching \". In PLDI. 2022 . Konstantinos Mamouras, Kaiyuan Yang, Lingkun Kong, Qixuan Yu, Agnishom Chattopadhyay, Alexis Le Glaunec, and Yi Huang. \"Software-Hardware Codesign for Efficient In-Memory Regular Pattern Matching\". In PLDI. 2022."},{"key":"e_1_3_2_1_34_1","volume-title":"POPL.","author":"Mayr Richard","year":"2013","unstructured":"Richard Mayr and Lorenzo Clemente . \" Advanced automata minimization\". In POPL. 2013 . Richard Mayr and Lorenzo Clemente. \"Advanced automata minimization\". In POPL. 2013."},{"key":"e_1_3_2_1_35_1","volume-title":"CAV.","author":"McClurg Jedidiah","year":"2017","unstructured":"Jedidiah McClurg , Hossein Hojjat , and Pavol Cern\u00fd . \" Synchronization Synthesis for Network Programs\". In CAV. 2017 . Jedidiah McClurg, Hossein Hojjat, and Pavol Cern\u00fd. \"Synchronization Synthesis for Network Programs\". In CAV. 2017."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78800-3_24"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2010.5462149"},{"key":"e_1_3_2_1_38_1","volume-title":"PLDI.","author":"Nandi Chandrakana","year":"2020","unstructured":"Chandrakana Nandi , Max Willsey , Adam Anderson , James R. Wilcox , Eva Darulova , Dan Grossman , and Zachary Tatlock . \" Synthesizing structured CAD models with equality saturation and inverse transformations\". In PLDI. 2020 . Chandrakana Nandi, Max Willsey, Adam Anderson, James R. Wilcox, Eva Darulova, Dan Grossman, and Zachary Tatlock. \"Synthesizing structured CAD models with equality saturation and inverse transformations\". In PLDI. 2020."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1217856.1217859"},{"key":"e_1_3_2_1_40_1","volume-title":"SAT.","author":"N\u00f6tzli Andres","year":"2019","unstructured":"Andres N\u00f6tzli , Andrew Reynolds , Haniel Barbosa , Aina Niemetz , Mathias Preiner , Clark W. Barrett , and Cesare Tinelli . \" Syntax-Guided Rewrite Rule Enumeration for SMT Solvers\". In SAT. 2019 . Andres N\u00f6tzli, Andrew Reynolds, Haniel Barbosa, Aina Niemetz, Mathias Preiner, Clark W. Barrett, and Cesare Tinelli. \"Syntax-Guided Rewrite Rule Enumeration for SMT Solvers\". In SAT. 2019."},{"key":"e_1_3_2_1_41_1","article-title":"Quantifying nondeterminism in finite automata","author":"Palioudakis Alexandros","year":"2015","unstructured":"Alexandros Palioudakis , Kai Salomaa , and Selim G Akl . \" Quantifying nondeterminism in finite automata \". In Annals of the U. of Bucharest ( 2015 ). Alexandros Palioudakis, Kai Salomaa, and Selim G Akl. \"Quantifying nondeterminism in finite automata\". In Annals of the U. of Bucharest (2015).","journal-title":"Annals of the U. of Bucharest ("},{"key":"e_1_3_2_1_42_1","volume-title":"OOPSLA","author":"Pan Rong","year":"2019","unstructured":"Rong Pan , Qinheping Hu , Gaowei Xu , and Loris D'Antoni . \" Automatic Repair of Regular Expressions\". In OOPSLA ( 2019 ). Rong Pan, Qinheping Hu, Gaowei Xu, and Loris D'Antoni. \"Automatic Repair of Regular Expressions\". In OOPSLA (2019)."},{"key":"e_1_3_2_1_43_1","volume-title":"Christian Pilato, and Marco D. Santambrogio. \"CICERO: A Domain-Specific Architecture for Efficient Regular Expression Matching\". In ACM Trans. Embed. Comput. Syst.","author":"Parravicini Daniele","year":"2021","unstructured":"Daniele Parravicini , Davide Conficconi , Emanuele Del Sozzo , Christian Pilato, and Marco D. Santambrogio. \"CICERO: A Domain-Specific Architecture for Efficient Regular Expression Matching\". In ACM Trans. Embed. Comput. Syst. ( 2021 ). Daniele Parravicini, Davide Conficconi, Emanuele Del Sozzo, Christian Pilato, and Marco D. Santambrogio. \"CICERO: A Domain-Specific Architecture for Efficient Regular Expression Matching\". In ACM Trans. Embed. Comput. Syst. (2021)."},{"key":"e_1_3_2_1_44_1","volume-title":"ASPLOS.","author":"Phothilimthana Phitchaya Mangpo","year":"2016","unstructured":"Phitchaya Mangpo Phothilimthana , Aditya Thakur , Rastislav Bod\u00edk , and Dinakar Dhurjati . \" Scaling up Superoptimization\". In ASPLOS. 2016 . Phitchaya Mangpo Phothilimthana, Aditya Thakur, Rastislav Bod\u00edk, and Dinakar Dhurjati. \"Scaling up Superoptimization\". In ASPLOS. 2016."},{"key":"e_1_3_2_1_45_1","volume-title":"CoRR abs\/1405.7058","author":"Rathnayake Asiri","year":"2014","unstructured":"Asiri Rathnayake and Hayo Thielecke . \" Static Analysis for Regular Expression Exponential Runtime via Substructural Logics\". In CoRR abs\/1405.7058 ( 2014 ). Asiri Rathnayake and Hayo Thielecke. \"Static Analysis for Regular Expression Exponential Runtime via Substructural Logics\". In CoRR abs\/1405.7058 (2014)."},{"key":"e_1_3_2_1_46_1","unstructured":"Alex Roichman and Adar Weidman. Regular Expression Denial of Service. https:\/\/www.checkmarx.com\/wp-content\/uploads\/2015\/03\/ReDoS-Attacks.pdf.  Alex Roichman and Adar Weidman. Regular Expression Denial of Service. https:\/\/www.checkmarx.com\/wp-content\/uploads\/2015\/03\/ReDoS-Attacks.pdf."},{"key":"e_1_3_2_1_47_1","volume-title":"ASPLOS.","author":"Schkufza Eric","year":"2013","unstructured":"Eric Schkufza , Rahul Sharma , and Alex Aiken . \" Stochastic superoptimization\". In ASPLOS. 2013 . Eric Schkufza, Rahul Sharma, and Alex Aiken. \"Stochastic superoptimization\". In ASPLOS. 2013."},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3238147.3238159"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/FMCAD.2016.7886678"},{"key":"e_1_3_2_1_50_1","first-page":"04826","article-title":"Theory Exploration Powered By Deductive Synthesis","author":"Singher Eytan","year":"2009","unstructured":"Eytan Singher and Shachar Itzhaky . \" Theory Exploration Powered By Deductive Synthesis \". In CoRR abs\/ 2009 . 04826 (2020). Eytan Singher and Shachar Itzhaky. \"Theory Exploration Powered By Deductive Synthesis\". In CoRR abs\/2009.04826 (2020).","journal-title":"CoRR abs\/"},{"key":"e_1_3_2_1_51_1","volume-title":"VMCAI.","author":"Smith Calvin","year":"2019","unstructured":"Calvin Smith and Aws Albarghouthi . \" Program Synthesis with Equivalence Reduction\". In VMCAI. 2019 . Calvin Smith and Aws Albarghouthi. \"Program Synthesis with Equivalence Reduction\". In VMCAI. 2019."},{"key":"e_1_3_2_1_52_1","volume-title":"ACSAC.","author":"Smith Randy","year":"2006","unstructured":"Randy Smith , Cristian Estan , and Somesh Jha . \" Backtracking Algorithmic Complexity Attacks against a NIDS\". In ACSAC. 2006 . Randy Smith, Cristian Estan, and Somesh Jha. \"Backtracking Algorithmic Complexity Attacks against a NIDS\". In ACSAC. 2006."},{"key":"e_1_3_2_1_53_1","first-page":"361","volume-title":"USENIX Security Symposium. USENIX Association","author":"Staicu Cristian-Alexandru","year":"2018","unstructured":"Cristian-Alexandru Staicu and Michael Pradel . \" Freezing the Web : A Study of ReDoS Vulnerabilities in JavaScript-based Web Servers \". In USENIX Security Symposium. USENIX Association , 2018 , pp. 361 -- 376 . Cristian-Alexandru Staicu and Michael Pradel. \"Freezing the Web: A Study of ReDoS Vulnerabilities in JavaScript-based Web Servers\". In USENIX Security Symposium. USENIX Association, 2018, pp. 361--376."},{"key":"e_1_3_2_1_54_1","unstructured":"Bryan Sullivan. Regular Expression Denial of Service Attacks and Defenses. https:\/\/docs.microsoft.com\/en-us\/archive\/msdn-magazine\/2010\/may\/security-briefs-regular-expression-denial-of-service-attacks-and-defenses.  Bryan Sullivan. Regular Expression Denial of Service Attacks and Defenses. https:\/\/docs.microsoft.com\/en-us\/archive\/msdn-magazine\/2010\/may\/security-briefs-regular-expression-denial-of-service-attacks-and-defenses."},{"key":"e_1_3_2_1_55_1","volume-title":"LMCS","author":"Tate Ross","year":"2011","unstructured":"Ross Tate , Michael Stepp , Zachary Tatlock , and Sorin Lerner . \" Equality Saturation : A New Approach to Optimization \". In LMCS ( 2011 ). Ross Tate, Michael Stepp, Zachary Tatlock, and Sorin Lerner. \"Equality Saturation: A New Approach to Optimization\". In LMCS (2011)."},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/363347.363387"},{"key":"e_1_3_2_1_57_1","first-page":"287","article-title":"TRANSIT: specifying protocols with concolic snippets","author":"Udupa Abhishek","year":"2013","unstructured":"Abhishek Udupa , Arun Raghavan , Jyotirmoy V. Deshmukh , Sela Mador-Haim , Milo M. K. Martin , and Rajeev Alur . \" TRANSIT: specifying protocols with concolic snippets \". In PLDI. ACM , 2013 , pp. 287 -- 296 . Abhishek Udupa, Arun Raghavan, Jyotirmoy V. Deshmukh, Sela Mador-Haim, Milo M. K. Martin, and Rajeev Alur. \"TRANSIT: specifying protocols with concolic snippets\". In PLDI. ACM, 2013, pp. 287--296.","journal-title":"PLDI. ACM"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-40946-7_27"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3434304"},{"key":"e_1_3_2_1_60_1","volume-title":"TACAS.","author":"W\u00fcstholz Valentin","year":"2017","unstructured":"Valentin W\u00fcstholz , Oswaldo Olivo , Marijn J. H. Heule , and Isil Dillig . \" Static Detection of DoS Vulnerabilities in Programs that Use Regular Expressions\". In TACAS. 2017 . Valentin W\u00fcstholz, Oswaldo Olivo, Marijn J. H. Heule, and Isil Dillig. \"Static Detection of DoS Vulnerabilities in Programs that Use Regular Expressions\". In TACAS. 2017."},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2011.73"},{"key":"e_1_3_2_1_62_1","unstructured":"Joel Yliluoma. Perl-compatible regular expression optimizer. https:\/\/bisqwit.iki.fi\/source\/regexopt.html.  Joel Yliluoma. Perl-compatible regular expression optimizer. https:\/\/bisqwit.iki.fi\/source\/regexopt.html."},{"key":"e_1_3_2_1_63_1","unstructured":"Ivan Zuzak and Vedrana Jankovic. Regular Expression Gym (Noam). http:\/\/ivanzuzak.info\/noam\/webapps\/regex_simplifier\/.  Ivan Zuzak and Vedrana Jankovic. Regular Expression Gym (Noam). http:\/\/ivanzuzak.info\/noam\/webapps\/regex_simplifier\/."}],"event":{"name":"PACT '22: International Conference on Parallel Architectures and Compilation Techniques","sponsor":["SIGARCH ACM Special Interest Group on Computer Architecture","IFIP WG 10.3 IFIP WG 10.3","IEEE CS"],"location":"Chicago Illinois","acronym":"PACT '22"},"container-title":["Proceedings of the International Conference on Parallel Architectures and Compilation Techniques"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3559009.3569664","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3559009.3569664","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:02:38Z","timestamp":1750186958000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3559009.3569664"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,8]]},"references-count":63,"alternative-id":["10.1145\/3559009.3569664","10.1145\/3559009"],"URL":"https:\/\/doi.org\/10.1145\/3559009.3569664","relation":{},"subject":[],"published":{"date-parts":[[2022,10,8]]},"assertion":[{"value":"2023-01-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}