Abstract machine semantics of regular expression matching

Add to your list(s) Download to your calendar using vCal

• Asiri Rathnayake
• Tuesday 19 June 2012, 12:00-13:00
• CS 217.

If you have a question about this talk, please contact Dan Ghica.

Regular languages have been studied in computer science for decades. However, most practical implementations of regular expression matchers have deviated from the well-understood algorithms into a naive backtracking algorithm. This backtracking approach has broght along with it a class of deficiencies that can be exploited to create denial-of-service style attacks (ReDoS). We employ tools in theoretical computer science (operational semantics and abstract machines) to formalize this backtracking approach to regular expression matching and prove its correctness. We also show that our model can be used to formally prove the exponential blow-up of certain regular expressions. Finally, we’ll highlight various research directions that can be explored using our framework.

This talk is part of the Lab Lunch series.

This talk is included in these lists:

• CS 217
• Computer Science Departmental Series
• Computer Science Distinguished Seminars
• Lab Lunch
• Theoretical computer science seminar
• computer sience

Note that ex-directory lists are not shown.