Analyzing Catastrophic Backtracking Behavior in Practical Regular Expression Matching
2014 (English)Conference paper (Refereed)
We consider in some detail how regular expression matching happens in Java, as a popular representative of the category of regex-directed matching engines. We extract a slightly idealized algorithm for this scenario. Next we define an automata model which captures all the aspects needed to perform matching, of the Java style, in a formal way. Finally, two types of static analysis, which take a regular expression and tells whether there exists a family of strings which make Java-style matching run in exponential time, are done.
Place, publisher, year, edition, pages
regular expressions, catastrophic backtracking, static analysis
IdentifiersURN: urn:nbn:se:umu:diva-88232OAI: oai:DiVA.org:umu-88232DiVA: diva2:714507
14th International Conference Automata and Formal Languages