Revealer: Detecting and Exploiting Regular Expression Denial-of-Service Vulnerabilities

Regular expression Denial-of-Service (ReDoS) is a class of algorithmic complexity attacks. Attackers can craft particular strings to trigger the worst-case super-linear matching time of some vulnerable regular expressions (regex) with extended features that are commonly supported by popular programming languages. ReDoS attacks can severely degrade the performance of web applications, which extensively employ regexes in their server-side logic. Nevertheless, the characteristics of vulnerable regexes with extended features remain understudied, making it difficult to mitigate or even detect such vulnerabilities. In this paper, we aim to model vulnerable regex patterns generated by popular regex engines and craft attack strings accordingly. Our characterization fully supports the analysis of regexes with any extended feature. We develop REVEALER to detect vulnerable structures presented in any given regex and generate attack strings to exploit the corresponding vulnerabilities. REVEALER takes a hybrid approach. It first statically locates potential vulnerable structures of a regex, then dynamically verifies whether the vulnerabilities can be triggered or not, and finally crafts attack strings that can lead to recursive backtracking. By combining both static analysis and dynamic analysis, REVEALER can accurately and efficiently generate exploits in a limited amount of time. It can further offer mitigation suggestions based on the structural information it identifies. We implemented a prototype of REVEALER for Java. We evaluated REVEALER over a dataset with 29,088 regexes, and compared it with three state-of-the-art tools. The evaluation shows that REVEALER considerably outperformed all the existing tools-REVEALER can detect all 237 vulnerabilities that can be detected by any other tool, find 213 new vulnerabilities, and beat the best tool by 140.64%. We further demonstrate that REVEALER successfully detected 45 vulnerable regexes in popular real-world applications. Our evaluation demonstrates that REVEALER is both effective and efficient in detecting and exploiting ReDoS vulnerabilities.