More Like this

1. How well are regular expressions tested in the wild?

   https://doi.org/10.1145/3236024.3236072  

   Wang, Peipei ; Stolee, Kathryn T. ( January 2018 , Proceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering)

   Developers report testing their regular expressions less than the rest of their code. In this work, we explore how thoroughly tested regular expressions are by examining open source projects. Using standard metrics of coverage, such as line and branch cov- erage, gives an incomplete picture of the test coverage of regular expressions. We adopt graph-based coverage metrics for the DFA representation of regular expressions, providing fine-grained test coverage metrics. Using over 15,000 tested regular expressions in 1,225 Java projects on GitHub, we measure node, edge, and edge-pair coverage. Our results show that only 17% of the regular expressions in the repositories are tested at all. For those that are tested, the median number of test inputs is two. For nearly 42% of the tested regular expressions, only one test input is used. Average node and edge coverage levels on the DFAs for tested regular expressions are 59% and 29%, respectively. Due to the lack of testing of regular expressions, we explore whether a string generation tool for reg- ular expressions, Rex, achieves high coverage levels. With some exceptions, we found that tools such as Rex can be used to write test inputs with similar coverage to the developer tests. 

   more » « less
2. Regexes are Hard: Decision-Making, Difficulties, and Risks in Programming Regular Expressions

   https://doi.org/10.1109/ASE.2019.00047  

   Michael, Louis G. ; Donohue, James ; Davis, James C. ; Lee, Dongyoon ; Servant, Francisco ( November 2019 , Proceedings of the 34th IEEE/ACM International Conference on Automated Software Engineering)
3. SemRegex: A Semantics-Based Approach for Generating Regular Expressions from Natural Language Specifications

   https://doi.org/10.18653/v1/D18-1189  

   Zhong, Zexuan ; Guo, Jiaqi ; Yang, Wei ; Peng, Jian ; Xie, Tao ; Lou, Jian-Guang ; Liu, Ting ; Zhang, Dongmei ( October 2018 , Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing)
4. Optimizing Regular Expressions via Rewrite-Guided Synthesis

   Jedidiah McClurg ; Miles Claver ; Jackson Garner ; Jake Vossen ; Jordan Schmerge ; Belviranli, Mehmet E ( October 2022 , 2022 31st International Conference on Parallel Architectures and Compilation Techniques (PACT))

   Regular expressions are pervasive in modern systems. Many real world regular expressions are inefficient, sometimes to the extent that they are vulnerable to complexity-based attacks, and while much research has focused on detecting inefficient regular expressions or accelerating regular expression matching at the hardware level, we investigate automatically transforming regular expressions to remove inefficiencies. We reduce this problem to general expression optimization, an important task necessary in a variety of domains even beyond compilers, e.g., digital logic design, etc. Syntax-guided synthesis (SyGuS) with a cost function can be used for this purpose, but ordered enumeration through a large space of candidate expressions can be prohibitively expensive. Equality saturation is an alternative approach which allows efficientconstruction and maintenance of expression equivalence classes generated by rewrite rules, but the procedure may not reach saturation, meaning global minimality cannot be confirmed. We present a new approach called rewrite-guided synthesis (ReGiS), in which a unique interplay between SyGuS and equality saturation-based rewriting helps to overcome these problems, resulting in an efficient, scalable framework for expression optimization. 

   more » « less
5. FOREST: An Interactive Multi-tree Synthesizer for Regular Expressions

   https://doi.org/10.1007/978-3-030-72016-2_9  

   Ferreira, Margarida ; Terra-Neves, Miguel ; Ventura, Miguel ; Lynce, Ines ; Martins, Ruben ( March 2021 , Tools and Algorithms for the Construction and Analysis of Systems)

   null (Ed.)