PufferDoS: Efficient and Effective Attack String Generation for Regular Expression Denial of Service Vulnerabilities

Regular Expression Denial-of-Service (ReDoS) attacks constitute a critical class of resource-exhaustion vulnerabilities. In such attacks, adversaries exploit the pathological worst-case execution behavior of regular expression (regex) engines to induce highly asymmetric computational workloads, ultimately exhausting system resources and degrading service availability. To protect systems against ReDoS attacks, numerous detection techniques have been proposed that simulate the attack process by generating attack strings to proactively exploit ReDoS vulnerabilities at the early development stage and facilitate remediation. Existing techniques broadly fall into two classes: static analyses that search for pathological regex structures, and dynamic exploration methods that synthesize candidate attack strings. However, the generated attack strings are often impractical for real-world exploitation because they usually assume unrealistic input-length budgets and do not validate the effectiveness and efficiency of the attack at the program level. Therefore, many generated strings fail to trigger vulnerable regexes when applied to real-world programs, further limiting the practical utility.

To address these shortcomings, we introduce an effective and efficient attack string generator, PUFFERDOS, designed to synthesize attack inputs that are both feasible within realistic length budgets and validated at the program level, enabling effective exploitation of ReDoS vulnerabilities in real-world programs. Specifically, we first define three vulnerable patterns based on our observation and formal verification. According to the patterns, PUFFERDOS conducts a synthesis technique to generate attack strings, and then refines and validates the strings with ReDoS-specific compositional concolic execution to guarantee real-world exploitability. We evaluated PUFFERDOS on a baseline corpus of 17,962 real-world vulnerable regexes. Compared to state-of-the-art tool RENGAR, PUFFERDOS produced attack strings that achieve efficiency gains ranging from 97.2× to 3872.4×, thereby significantly enhancing practical exploitability assessment in real-world contexts. PUFFERDOS also discovered 59 exploitable ReDoS instances across 12 1. S. Ma is partially funded by the Australian Research Council (ARC) Future Fellowship (FT -250100652) popular projects, which is 25 more than RENGAR.