  Regular expressions are a concise yet expressive language for expressing
patterns. For instance, in networked software, they are used for input
validation and intrusion detection. Yet some widely deployed regular expression
matchers based on backtracking are themselves vulnerable to denial-of-service
attacks, since their runtime can be exponential for certain input strings. This
paper presents a static analysis for detecting such vulnerable regular
expressions. The running time of the analysis compares favourably with tools
based on fuzzing, that is, randomly generating inputs and measuring how long
matching them takes. Unlike fuzzers, the analysis pinpoints the source of the
vulnerability and generates possible malicious inputs for programmers to use in
security testing. Moreover, the analysis has a firm theoretical foundation in
abstract machines. Testing the analysis on two large repositories of regular
expressions shows that the analysis is able to find significant numbers of
vulnerable regular expressions in a matter of seconds.
