Parsing and regular expressions research

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