Analyzing Catastrophic Backtracking Behavior in Practical Regular Expression Matching
arXiv:1405.5599 · doi:10.4204/EPTCS.151.7
Abstract
We develop a formal perspective on how regular expression matching works in Java, a popular representative 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.
In Proceedings AFL 2014, arXiv:1405.5272