Search papers, labs, and topics across Lattice.
This paper introduces PUFFERDOS, a novel attack string generator specifically designed to exploit Regular Expression Denial of Service (ReDoS) vulnerabilities effectively and efficiently. By addressing the limitations of existing methods, PUFFERDOS synthesizes attack inputs that adhere to realistic length constraints while ensuring their effectiveness through program-level validation. The key result demonstrates that PUFFERDOS can generate practical attack strings that successfully trigger vulnerable regex patterns in real-world applications, significantly enhancing the utility of ReDoS detection techniques.
Attack strings generated by PUFFERDOS not only fit realistic input lengths but also guarantee exploitability in real-world regex engines, unlike previous methods.
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.
