一句话：结合过程间污点分析、SMT 求解与 LLM 智能体，自动判定并生成可触发 ReDoS 的可执行 PoC。
现有 ReDoS 检测只判断正则是否超线性匹配，不判定能否在程序上下文中由外部输入触发，分诊成本高。ReSEDA 面向 JavaScript，结合 IFDS 过程间污点分析、SMT 路径可行性与 ReDoS 约束求解，并用 LLM 智能体与 MCP 工具生成可执行 PoC。在 86 个高星 JS 项目中，637 个被报脆弱正则仅 63 个可经外部接口触发，ReSEDA 自动识别并为 61 个生成 PoC；分析工时减少 8.78 倍，单漏洞成本 2.01 美元，本地 LLM 下减少 7.86 倍；发现 27 个 CVE，其中 8 个完全自动披露。
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.
@inproceedings{paperbot12286,
title = {ReSEDA: Automatic and Precise Program-Level ReDoS Triage via Interprocedural Taint Analysis and Agentic Exploit Generation},
author = {Rongchen Li and Weihao Su and Chengyao Peng and Hong Huang and Haiming Chen and Guiyi He},
booktitle = {ASE},
year = {2026},
doi = {10.1145/3832783.3837545}
}