University of Birmingham > Talks@bham > Lab Lunch > Abstract machine semantics of regular expression matching

Abstract machine semantics of regular expression matching

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

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


Talks@bham, University of Birmingham. Contact Us | Help and Documentation | Privacy and Publicity.
talks@bham is based on from the University of Cambridge.