String Generation for Testing Regular Expressions

摘要

Regular expressions have been widely studied due to their expressiveness and flexibility for various applications. A common yet challenging way to ensure the quality of regular expressions is regular expression testing. In this work, we study coverage criteria-based string generation for testing regular expressions. First, we propose a notion of pairwise coverage criterion for regular expressions and analyze the subsumption relationships with existing coverage criteria for both regular grammars and finite automata. Second, we design an algorithm that given as an input a regular expression, outputs a small set of strings that satisfies the pairwise coverage criterion. Third, we extend the coverage criterion and the generation algorithm to further deal with regular operators counting and interleaving. Fourth, we experimentally demonstrate the effectiveness and efficiency of our algorithms by testing element-type definitions of real-world XML schemas. Finally, we identify more applications of pairwise coverage and its corresponding generation algorithm and show that they can be used to generate characteristic samples for certain regular expression learning algorithms that follow Gold's learning paradigm of learning (identification) in the limit. These results are not only theoretically meaningful but also useful for practical applications involved with regular expressions.