Analyzing Catastrophic Backtracking Behavior in Practical Regular Expression Matching
Martin Berglund, Frank Drewes, Brink van der Merwe · 2016
We develop a formal perspective on how regular expression matching works in Java1, a popular rep-resentative of the category of regex-directed matching engines. In particular, we define an automata model which captures all the aspects needed to study such matching engines in a formal way. Based on this, we propose two types of static analysis, which take a regular expression and tell whether there exists a family of strings which makes Java-style matching run in exponential time. 1