Static Detection of DoS Vulnerabilities in Programs that use Regular Expressions (Extended Version)
This addresses security vulnerabilities in web applications for developers and users, but it is incremental as it builds on existing static analysis methods for ReDoS detection.
The paper tackles the problem of detecting regular expression denial-of-service (ReDoS) vulnerabilities in programs by proposing an automated technique that identifies vulnerable regular expressions and determines if malicious inputs can trigger worst-case behavior, resulting in the discovery of 41 exploitable security vulnerabilities in Java web applications.
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.