Static analysis for regular expression denial of service attacks
In brief, the analysis computes successive derivatives of regular expressions inside Kleene stars. If there are two or more different paths through such an expression, the matching becomes so nondeterministic that there is an exponential blowup of the search tree. The tool constructs possible malicious inputs, so that programmers can test their regular expressions for ReDoS vulnerabilities.
The tool and some example data are available for download.
PhD students
Asiri Rathnayake's PhD thesis will be largely in this area.
Relevant papers
-
Hayo Thielecke
On the Semantics of Parsing Actions
Science of Computer Programming, special issue for PPDP'12. Elsevier -
James Kirrage, Asiri Rathnayake, and Hayo Thielecke
Static Analysis for Regular Expression Denial-of-Service Attacks
International Conference on Network and System Security (NSS 2013)
The paper won the NSS 2013 best paper award. -
Hayo Thielecke
Functional Semantics of Parsing Actions, and Left Recursion Elimination as Continuation Passing
14th International ACM SIGPLAN Symposium on Principles and Practice of Declarative Programming (PPDP 2012)
Slides for the talk -
Asiri Rathnayake and Hayo Thielecke
Regular Expression Matching and Operational Semantics
Sructural Operational Sematics 2011
Slides for Southampton talk in PDF - Lecture notes on operational semantics and abstract machines, taught in 2011 and 2012