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 def…