一句话：提出 matching NFA，将带前瞻正则转换为标准 ε-NFA，把前瞻感知的 ReDoS 检测归约为 ε-NFA 歧义分析。
带前瞻断言的正则表达式在现代软件中广泛使用，但与回溯引擎交互时可能引发 ReDoS 漏洞。现有静态方法依赖 ε-NFA 歧义分析，无法刻画前瞻求值开销；动态与混合方法则代价高或覆盖不全。本文提出 LARA，一种面向带前瞻正则表达式（REwLA）的静态 ReDoS 检测器。其核心贡献是 matching NFA，将 REwLA 转换为标准 ε-NFA。该自动机与原 REwLA 语言不等价，但作者证明其 match degree 等于原 REwLA 的 la-match degree，因此包含前瞻开销的复杂度上界得以保持，从而把前瞻感知的 ReDoS 检测归约为标准 ε-NFA 歧义分析，使现有检测技术可直接应用。在 42,794 个去重真实 REwLA 上评估，LARA 在多工具共同确认的 5,889 个漏洞中识别 5,871 个，优于所有基线；在来自 177 个真实 CVE 的 400 个确认漏洞正则上召回率 99.50%，并在真实引擎上成功利用 4,468 个漏洞，中位分析时间 0.05 秒、内存 7.67 MB。
Regular expressions (regexes) with lookahead assertions are widely used in modern software, yet their interaction with backtracking engines can cause Regular expression Denial of Service (ReDoS) vulnerabilities. Existing static methods rely on 𝜀-NFA ambiguity analysis, which cannot capture lookahead evaluation cost, while dynamic and hybrid methods incur high cost or incomplete coverage. We present LARA, a static ReDoS detector for regular expressions with lookahead (REwLA), which subsumes standard regexes. Our core contribution is the matching NFA, which transforms a REwLA into a standard 𝜀-NFA. The matching NFA is not language-equivalent to the original REwLA; however, we prove that its match degree equals the la-match degree of the original REwLA, so the same complexity upper bound is preserved, including lookahead overhead. This reduces lookahead-aware ReDoS detection to standard 𝜀-NFA ambiguity analysis, enabling existing detection techniques to be applied directly to the matching NFA. We evaluate LARA on 42,794 deduplicated real-world REwLA. Among 5,889 vulnerabilities jointly confirmed by multiple tools and validated on real backtracking engines, LARA identifies 5,871, outperforming all baselines. On 400 confirmed vulnerable regexes from 177 real-world ReDoS CVEs, LARA achieves 99.50% recall. LARA successfully exploits 4,468 vulnerabilities on real engines, with a median analysis time of 0.05 s and 7.67 MB memory.
@inproceedings{paperbot12507,
title = {LARA: Static ReDoS Detection for Regular Expressions with Lookahead via Matching Automata},
author = {Mengxi Wang and Chengyao Peng and Weihao Su and Guiyi He and Rongchen Li and Hong Huang and Haiming Chen},
booktitle = {ASE},
year = {2026},
doi = {10.1145/3832783.3837475}
}