小心 ReDoS 攻击！写错正则表达式导致 CPU 100% 爆表的原因与防范

一、问题概述：灾难性回溯与 ReDoS 拒绝服务漏洞

传统正则表达式引擎（如 V8、Python、Java 默认的 NFA 引擎）采用回溯机制搜索匹配路径。当正则表达式中包含重叠或嵌套的量词（例如 (a+)+$、(a|a)+$）且目标输入文本在末尾匹配失败时，NFA 引擎会尝试指数级数量的可能组合（时间复杂度达到 O(2^N) 或 O(N^k)），导致单次匹配耗时数分钟甚至数小时，彻底卡死单线程事件循环。

二、最小复现：导致 CPU 100% 爆表的嵌套量词代码

下面的例子示范了触发灾难性回溯的经典 ReDoS 模式以及 CPU 爆表效果：

/* 经典 ReDoS 触发模式: 嵌套量词 (a+)+$ */

const unsafeRegex = /^(a+)+$/;
const maliciousInput = "aaaaaaaaaaaaaaaaaaaaaaaaaaaa!"; // 28 个 'a' 加一个无法匹配的字符 '!'

console.time("ReDoS Test");
// 下面这行代码会导致 V8 引擎产生上亿次无效回溯，严重阻塞 CPU！
const isMatched = unsafeRegex.test(maliciousInput);
console.timeEnd("ReDoS Test");

三、根因分析：回溯决策树与非确定性路径搜索

1. 分支试错：回溯型正则引擎面对 (a+)+$ 时，每个字符 a 都可被分配给不同层级的重复。2. 指数级组合：对于长度为 N 的连续 a，失败后可能探索接近 2^{N-1} 条分割路径。3. 事件循环饥饿：Node.js 在事件循环线程同步执行这类匹配时，其他请求无法及时被调度；这属于线程被占用，不是数据库意义上的“死锁”。

四、推荐方案：正则安全改写、输入长度限制与 Worker 超时隔离

1. 重构歧义嵌套和重叠分支。2. 在匹配前按业务契约限制输入长度。3. 不可信或动态正则放进可终止的 Web Worker / Node.js worker_threads。4. 高风险路径评估 RE2 类线性时间引擎，但先确认其受限语法能覆盖现有模式。静态扫描和单一长度阈值都只能作为纵深防御。

五、完整代码：真正可中断的浏览器 Worker 正则匹配

同步匹配完成后再记录耗时无法中断灾难性回溯。下面的浏览器代码把匹配放进独立 Worker，并在超时时直接终止 Worker；输入长度上限仍是第一道防线。Node.js 服务端应使用 worker_threads 或 RE2 类线性时间实现。

function regexMatchWithTimeout(
  pattern: RegExp,
  input: string,
  maxLength = 500,
  timeoutMs = 100,
): Promise<boolean> {
  if (input.length > maxLength) {
    return Promise.reject(new RangeError("输入文本超过安全长度上限"));
  }

  const source = [
    "self.onmessage = (event) => {",
    "  const { source, flags, input } = event.data;",
    "  try {",
    "    self.postMessage({ matched: new RegExp(source, flags).test(input) });",
    "  } catch (error) {",
    "    self.postMessage({ error: error instanceof Error ? error.message : String(error) });",
    "  }",
    "};",
  ].join("\n");
  const url = URL.createObjectURL(new Blob([source], { type: "text/javascript" }));
  const worker = new Worker(url);

  return new Promise((resolve, reject) => {
    let timer = 0;
    const cleanup = () => {
      window.clearTimeout(timer);
      worker.terminate();
      URL.revokeObjectURL(url);
    };

    timer = window.setTimeout(() => {
      cleanup();
      reject(new Error("正则匹配超时，Worker 已终止"));
    }, timeoutMs);
    worker.onmessage = (event) => {
      cleanup();
      if (event.data.error) reject(new Error(event.data.error));
      else resolve(Boolean(event.data.matched));
    };
    worker.onerror = (event) => {
      cleanup();
      reject(new Error(event.message || "正则 Worker 执行失败"));
    };
    worker.postMessage({ source: pattern.source, flags: pattern.flags, input });
  });
}

console.log(await regexMatchWithTimeout(/^a+$/, "aaaaaaaa!")); // false

六、常见错误方案

误以为懒惰量词 +? 能彻底解决 ReDoS（懒惰量词在末尾字符匹配失败时依然会进行全力回溯）；在没有输入长度限制的情况下向服务端暴露自定义用户正则校验功能。

七、边界条件：引擎能力、CSP 与 Worker 成本

V8 与 Node.js 原生 RegExp 支持反向引用和环视等高级能力，部分模式会出现灾难性回溯。Google RE2 通过有限自动机策略和受限语法换取与输入长度线性相关的执行时间。浏览器 Blob Worker 还受站点 worker-src CSP 控制；高频短匹配不宜每次创建 Worker，可复用受控 Worker 池，但超时后必须丢弃被卡住的实例。

八、如何检测与评估正则表达式安全风险

使用在线 Safe Regex 工具扫描模式中是否存在 (a+)+ 或 (a|b)+ 结构；在 CI/CD 中加入 ReDoS 模糊测试 (Fuzzing)；在监控系统中跟踪 RegExp 相关的 CPU 线程消耗。

九、FAQ

问：为什么在 Node.js 中一条 ReDoS 正则能带崩整个服务？答：因为 Node.js 是单线程事件循环架构，同步的 CPU 密集回溯计算会占用整个 CPU 核心，导致后续所有 HTTP 请求无法被事件循环调度。

问：所有正则表达式都存在 ReDoS 风险吗？答：不是。只有包含了“重叠量词”或“歧义交叠分支”且作用于无法匹配的末尾文本时，才会触发灾难性回溯。

问：如何修改 (a+)+$ 使其变得安全？答：直接改写为单层量词 ^a+$，完全消除了分配路径歧义，执行时间缩短为毫秒级。

十、总结

ReDoS 攻击是利用正则引擎物理算法缺陷的拒绝服务漏洞。工程实践中应避免嵌套重叠量词、严格校验输入文本长度，并在高危场景下引入 Worker 超时隔离或 DFA 引擎。