Generating Evil Test Strings for Regular Expressions
Eric B. Larson, Anna Kirk · 2016
Regular expressions are a powerful string processing tool. However, they are error-prone and receive little error checking from the compiler as most regular expressions are syntactically correct. This paper describes EGRET, a tool for generating evil test strings for regular expressions. EGRET focuses on common mistakes made by developers when creating regular expressions and develops test strings that expose these errors. EGRET has found errors in 284 out of 791 regular expressions. Prior approaches to test string generation have traversed all possible paths in the equivalent nondeterministic finite state automaton leading to the generation of too many strings. EGRET keeps the set of test strings to a manageable number: Fewer than 100 test strings were generated for 96% of the regular expressions, a manageable 307 test strings were generated for the most complex regular expression.