ReDoS 正则回溯攻击检测器

ReDoS (Regular Expression Denial of Service) 是一种利用正则表达式灾难性回溯（Catastrophic Backtracking）导致CPU资源耗尽的安全漏洞。当正则引擎尝试匹配一个精心构造的字符串时，回溯次数呈指数级增长，导致服务器响应缓慢甚至完全无响应。

例如，正则 (a+)+ 匹配字符串 aaaaaaaaaaaaaaaaaaaa! 时，引擎会尝试所有可能的分组组合，回溯次数可达数百万次，消耗大量CPU时间。

关键特征：嵌套的量词结构（如 (X+)+、(X*)*）是导致灾难性回溯的主要原因。

以下模式是常见的危险信号：

• 嵌套量词：(a+)+、(a*)*、(a+)* — 量词内部包含另一个量词
• 宽字符类嵌套：(.*)+、(\w+)*、([a-zA-Z]+)+ — 匹配范围广的字符类被量词包裹后再加量词
• 交替分支重叠：(a|aa)+、(ab|a)+ — 多选分支中一个分支是另一个的前缀
• 否定字符类嵌套：([^,]+)* — 否定字符类配合嵌套量词
• 多分支+外层量词：(option1|option2|option3)* 配合特定输入

修复策略：

1. 消除嵌套量词：将 (a+)+ 改为 a+（大多数情况下外层量词是多余的）
2. 使用原子组：在支持的语言中（如PHP的(?>...)），防止回溯进入组内。JS暂不支持，但可用其他方式模拟
3. 使用占有量词：如 a++（JS不支持，但可用更精确的字符类替代）
4. 缩小字符类范围：将 .* 替换为更具体的 [^delimiter]*
5. 添加锚点：使用 ^ 和 $ 限定匹配边界，减少回溯空间
6. 重写正则：避免交替分支重叠，如 (a|aa)+ 改为 a+
7. 设置超时：在使用正则的代码中设置执行超时（如Node.js的re2库或设置超时包装）

是的。JavaScript 使用回溯算法（Backtracking）实现正则匹配，这意味着它天然容易受到 ReDoS 攻击。V8引擎（Chrome/Node.js）虽然有一些优化（如Irregexp引擎的快速路径），但遇到嵌套量词时仍可能触发灾难性回溯。

与一些使用Thompson NFA（如Go的re2、Rust的regex）的引擎不同，JS的正则引擎在理论上可能对某些模式产生指数级时间复杂度。因此，在Node.js服务端应用中，ReDoS是一个需要认真对待的安全问题。

Node.js防护建议：使用 re2 库替代原生RegExp，或使用 vm 模块设置脚本超时。

本工具使用两阶段分析：

1. 静态结构分析：解析正则表达式的抽象结构，检测嵌套量词、交替分支重叠、宽字符类等危险模式。通过状态机扫描正则字符串，正确识别字符类[...]、转义序列、分组结构等。
2. 动态计时测试：使用 performance.now() 对测试字符串进行实际匹配计时。如果匹配时间超过阈值（50ms），则标记为高风险。测试在受控条件下进行，限制字符串长度以避免浏览器卡死。

综合静态分析和动态测试结果，给出五级风险评级（安全/低危/中危/高危/严重）及修复建议。

• Cloudflare (2019)：一个WAF规则中的正则 (?:(?:\"|'|\]|\}|\\|\d|(?:nan|infinity|true|false|null|undefined|symbol|math)|\`|\-|\+)+[)]*;? 导致全球性服务中断约30分钟，影响数百万网站。
• Stack Exchange (2016)：评论中的 [\s\u200b]+$ 加上特定Unicode字符导致严重性能问题。
• Node.js moment.js：日期解析正则中的嵌套量词在某些输入下导致毫秒级的解析变成秒级。

这些案例表明，即使是在经过严格审查的生产代码中，ReDoS漏洞也可能隐藏多年才被触发。