Analyzing Catastrophic Backtracking Behavior in Practical Regular Expression Matching

Martin Berglund
Frank Drewes
Brink van der Merwe

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 Zoltán Ésik and Zoltán Fülöp: Proceedings 14th International Conference on Automata and Formal Languages (AFL 2014), Szeged, Hungary, May 27-29, 2014, Electronic Proceedings in Theoretical Computer Science 151, pp. 109–123.
Published: 21st May 2014.

ArXived at: https://dx.doi.org/10.4204/EPTCS.151.7 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org