正则表达式拒绝服务（ReDoS）漏洞与防护

1. 漏洞描述
正则表达式拒绝服务（ReDoS）是一种通过构造特定输入触发正则表达式引擎进入极端回溯状态，导致CPU资源耗尽的服务拒绝攻击。其根源在于某些正则表达式模式存在“指数级时间复杂度”的匹配路径，恶意输入可使匹配过程陷入大量无效计算。

2. 漏洞原理
2.1 正则表达式引擎的工作机制

• NFA（非确定性有限自动机）引擎（如PCRE、Java、JavaScript等常用引擎）采用回溯算法进行匹配：当某个分支匹配失败时，引擎会退回之前的分支尝试其他可能性。
• 回溯场景示例：正则表达式 (a+)+b 匹配字符串 "aaaaac"：
  • 第一个 a+ 匹配所有 a，剩余 "c" 无法匹配 b，回溯减少一个 a 再尝试；
  • 重复此过程直到所有可能性耗尽，导致大量计算。

2.2 危险模式特征

• 嵌套量词：如 (a+)+、(a*)*，内层和外层量词均存在多种匹配可能。
• 重叠选择分支：如 (a|a)+，分支存在重叠时回溯路径激增。
• 冗余匹配：如 .*.*x，多个通配符连续使用。

3. 攻击示例分析
3.1 典型漏洞代码（Node.js）

const regex = /^(\w+)+$/; // 危险模式：嵌套量词
const input = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!"; // 末尾的!故意不匹配
if (regex.test(input)) { // 触发回溯爆炸
    console.log("匹配成功");
}

3.2 回溯过程模拟
输入字符串长度为 n 时，回溯路径数为 O(2ⁿ)：

• 每个字符可能被内层 \w+ 匹配后，又被外层 + 重新分配；
• 例如 "abc" 的匹配路径包括：(abc)、(a)(bc)、(ab)(c)、(a)(b)(c) 等。

4. 检测方法
4.1 静态代码分析工具

• 使用 SonarQube、CodeQL 等工具扫描危险模式（如 /(a+)+b/）。
• 示例CodeQL查询（JavaScript）：

from RegExpExpr r where r.getRegex().matches("(.*)*") select r

4.2 动态测试工具

• redos-detector（Node.js工具）：

  npx redos-detector "^(\\w+)+$"
  

• 输出结果示例：

  检测到危险模式：回溯复杂度指数级
  最坏情况输入：\w后跟非\w字符（如"a!"）
  

5. 防护方案
5.1 优化正则表达式设计

• 避免嵌套量词：将 (a+)+ 改为 a+。
• 使用非回溯子表达式（占有量词）：
  • PCRE支持 (a++)+ 防止回溯（但JavaScript不支持）。
• 明确边界：用 ^$ 限定匹配范围，减少不确定性。

5.2 引擎配置与超时机制

• Node.js：设置匹配超时：

  const { timeout } = require("async");
  timeout(regex.test, 1000)(input); // 1秒超时
  

• Java：使用 java.util.regex 的 Matcher.usePattern() 并限制输入长度。

5.3 替换方案

• 复杂逻辑改用字符串处理函数（如 split()、indexOf()）替代正则表达式。
• 示例：检查字母数字字符串的安全方式：

  function isAlphanumeric(str) {
    for (let char of str) {
      if (!/[a-zA-Z0-9]/.test(char)) return false;
    }
    return true;
  }
  

6. 进阶实战：自动化检测工具原理

• 正则表达式静态分析：通过解析正则表达式的抽象语法树（AST），识别嵌套量词、重叠分支等模式。
• 模糊测试：生成逐步增长的测试字符串，监控匹配时间突增点，定位危险输入模式。

通过以上步骤，可系统理解ReDoS的成因、检测方法与防护策略，避免在开发中引入此类漏洞。