  In an algorithmic complexity attack, a malicious party takes advantage of the
worst-case behavior of an algorithm to cause denial-of-service. A prominent
algorithmic complexity attack is regular expression denial-of-service (ReDoS),
in which the attacker exploits a vulnerable regular expression by providing a
carefully-crafted input string that triggers worst-case behavior of the
matching algorithm. This paper proposes a technique for automatically finding
ReDoS vulnerabilities in programs. Specifically, our approach automatically
identifies vulnerable regular expressions in the program and determines whether
an "evil" input string can be matched against a vulnerable regular expression.
We have implemented our proposed approach in a tool called REXPLOITER and found
41 exploitable security vulnerabilities in Java web applications.
