ReSEDA: Automatic and Precise Program-Level ReDoS Triage via Interprocedural Taint Analysis and Agentic Exploit Generation

Abstract

Regular expressions (regexes) are widely used in computer science, particularly in web services. However, Regular Expression Denial-of-Service (ReDoS) has become a growing security threat. ReDoS is an asymmetric Denial-of-Service attack that exploits the super-linear runtime behavior of regex engines. However, existing ReDoS detection tools only report whether regexes cause the super-linear matching behavior, instead of considering whether the behavior can be triggered in the program context. As a result, triaging such findings remains expensive for developers in practice. We present ReSEDA, an automatic and precise workflow that triages ReDoS alerts and generates executable proofs of concept (PoCs) for vulnerable JavaScript programs. The workflow employs (i) Interprocedural Finite Distributive Subset (IFDS) taint analysis, (ii) Satisfiability Modulo Theories (SMT) solving for supported path-feasibility and ReDoS constraints, and (iii) Large Language Model (LLM) agents for PoC construction with Model Context Protocol (MCP) tools that provide static evidence. From 86 most starred JavaScript projects in GitHub, we confirm that among 637 regexes reported to be vulnerable, there are only 63 regexes which can be exploited by injection through external interfaces, where ReSEDA is able to identify and generate PoCs for 61 of them automatically. We also discover that the assistance of ReSEDA reduces analyst-hours by 8.78× using $2.01 per vulnerability, or by 7.86× for free in a local-LLM setting. Furthermore, ReSEDA uncovered 27 impactful ReDoS vulnerabilities with assigned CVE IDs, including 8 disclosed fully automatically.