做前端或 Node.js 开发时，大家基本每天都要写正则。但很多人初学时常把正则当成简单的“字符串查找助手”，直到某天线上 Node.js 服务突然 CPU 100%、或者前端页面敲入一个长字符串直接全页冻结弹窗，才头一次听说 ReDoS（正则表达式拒绝服务）。

当写出带有嵌套量词或重叠分支的正则，又碰巧遇上精心构造的边界输入时，底层的 NFA（非确定有限状态自动机）引擎会在后台开启指数级甚至阶乘级的灾难性回溯（Catastrophic Backtracking）。在单线程的 JavaScript 环境里，这意味着整个 Event Loop 被瞬间锁死。

这篇文章我们从编译原理的状态机聊起，拆解 ReDoS 的几何级数成因，并分享本站正则表达式测试器是用怎样的 Web Worker 沙箱 + 看门狗定时器 防卡死架构，把恶性回溯牢牢封印在后台线程里的。

1. DFA vs NFA：为什么主流引擎会产生回溯？

正则表达式引擎主要分为两大流派：DFA（确定有限状态自动机） 与 NFA（非确定有限状态自动机）。

维度 DFA 引擎（如 RE2, Rust regex） NFA 引擎（如 JavaScript V8, Python re, PCRE）
状态确定性 任一输入字符只能转移到唯一确定的下一个状态 允许 ε\varepsilon-转移（空转移），可同时存在多个分支路径
匹配时间复杂度 严格的线性时间 O(n)O(n)，与文本长度成正比 最优 O(n)O(n)，最坏情况可能退化为指数级 O(2n)O(2^n)
功能支持 不支持捕获组反向引用（Backreference）、环视断言（Lookaround） 完整支持反向引用、正反向零宽断言、贪婪/非贪婪控制
内存与预编译 状态空间转换可能发生状态爆炸（O(2m)O(2^m) 状态膨胀） 状态机规模与正则式长度呈线性关系 O(m)O(m)

JavaScript 的 V8 引擎（Irregexp 引擎）以及几乎所有现代高级语言默认都采用 NFA 引擎，原因在于 NFA 能够灵活支持高级语法特性（如 /(a+)\1/ 捕获组反向引用）。

然而，NFA 在面对多个可能的匹配分支时，其工作策略是：

  1. 深度优先搜索（DFS）：挑选第一个可能的路径向前推进；
  2. 记录检查点（Checkpoint）：保存当前分支状态与文本游标；
  3. 失败回退（Backtracking）：若后续字符不匹配，沿着检查点倒退，尝试下一个可能的备选路径。

正是这个“深度优先搜索 + 失败回退”的机制，为灾难性回溯埋下了祸根。

2. 经典 ReDoS 漏洞模式与数学推导

灾难性回溯的核心特征是：匹配失败比匹配成功耗时长数万倍。当输入文本几乎与模式匹配、仅在最后一个字符失败时，引擎被迫遍历整个庞大的搜索树。

模式一：嵌套量词的指数级爆炸 O(2^n)

最经典的灾难性模式莫过于嵌套贪婪量词：

^(a+)+$

当输入为 aaaaaaaaaaaaaaaa!（nn 个 a，末尾追加一个非 a 字符 !）时：

  • 外层 ()+ 和内层 a+ 都可以消费 a；
  • 对于长度为 nn 的连续序列，将 nn 个元素分割成若干个非空子集的方式，对应数学上的整数拆分或排列数；
  • 状态转移树的分支因子为 2，总回溯步数约为 2n2^n。
n = 10  → 约 1,024 步（耗时 < 1ms）
n = 20  → 约 1,048,576 步（耗时约 5ms）
n = 30  → 约 1,073,741,824 步（耗时约 5 秒）
n = 40  → 约 1.1 × 10¹² 步（耗时约 1.5 小时，完全卡死单核 CPU）

只要输入长度增加 10 个字符，耗时便直接扩大 1000 倍！

模式二：重叠分支的组合爆炸

即使没有显式的嵌套括号，多分支交叠同样会引发指数灾难：

^(a|a)+$
或
^(a|ab)+$

在匹配 aaaa...a! 时，每个字符位置既可以走分支 1，也可以走分支 2，回溯搜索树深度与序列长度呈完全二叉树结构，同样是 O(2n)O(2^n) 复杂度。

模式三：多项式级回溯 O(n^2) 或 O(n^3)

并非只有 O(2n)O(2^n) 才是 ReDoS，多项式级回溯在长文本处理中同样致命：

a+.*b

当文本包含 100,000 个字符的连续 a 且末尾没有 b 时，外层循环每次推进一位，内层 .* 都会从当前位置吞噬至文本末尾，再逐字回退尝试匹配 b。总比较次数为：

∑i=1n(n−i)=n(n−1)2≈O(n2)\sum_{i=1}^{n} (n - i) = \frac{n(n - 1)}{2} \approx O(n^2)

对于 10 万字符的文本，n2/2≈5×109n^2 / 2 \approx 5 \times 10^9 次运算，在现代 CPU 上足以让进程停滞 10 秒以上。

3. 真实世界中的 ReDoS 生产事故

ReDoS 绝非学术象牙塔里的理论假设，它是真实发生过数次重特大互联网故障的元凶：

  1. Cloudflare 2019 年 7 月全球宕机事故：
    • 原因：WAF 规则库中部署了一条包含 .*.*=.* 的不严谨正则，试图检测跨站脚本攻击；
    • 结果：全球各边缘机房 CPU 使用率瞬时飙升至 100%，导致全网流量丢弃，持续 27 分钟。
  2. 知名 npm 库历史漏洞：
    • 包含早期的 moment（CVE-2016-4055）、semver（CVE-2015-8855）、validator.js（CVE-2014-8882）以及 ms 等基础库，因日期解析、语义化版本或邮箱验证正则缺乏边界约束，攻击者只需发送几百字节的特定恶意字符串即可发动 DoS 攻击。

4. 浏览器端架构设计：如何构建零卡顿的正则测试器？

在开发前端正则表达式测试器时，我们面临一个核心冲突：

  • 功能需求：必须使用 JavaScript 原生引擎（因为用户需要测试的就是 JS 环境下的正则行为，包括各种捕获组、标志位 d/g/i/m/s/u/y/v）；
  • 安全性挑战：用户可以任意输入正则和长文本。如果直接在 DOM 绑定的 input 事件回调中调用 regex.exec(text)，一旦遇到 ReDoS 模式，浏览器主线程事件循环将彻底锁死，UI 失去响应。

方案对比

解决方案 优势 缺陷 适用性
AST 静态检测（分析正则是否存在 ReDoS 模式） 提前阻断 存在误报与漏报；无法处理复杂交叉引用的边界情况 辅助预警
改用 WASM RE2 引擎 绝对安全（线性时间） 丢失 JS 原生特性（不支持后瞻断言、反向引用等），与宿主环境行为脱节 无法替代 JS 测试
Web Worker 线程隔离 + 看门狗超时熔断 100% 保持 JS 原生语义，即使死循环也完全不影响 UI 渲染与交互 需要管理 Worker 生命周期与消息序列号 最佳工程方案

生产级架构落地：Worker 隔离与看门狗机制

我们最终采用的架构由三个核心部分组成：

主线程 (UI Controller)          看门狗 (Watchdog)          工作线程 (Regex Worker)
       |                              |                            |
       |--- postMessage(reqId, reg) ->|                            |
       |------------------------------|--- postMessage(task) ----->|
       |                              |                      [正则回溯计算]
       |                              |                            |
       |<-- (若超时 800ms) 强行中断 ----|                            |
       |    worker.terminate()        |                            |
       |    重新创建 Worker 实例        |                            |

关键源码实现

在主线程管理器中，不能简单只用一个 setTimeout，必须管理请求的版本序列号（Request ID），防止历史慢查询在超时被杀前“回光返照”覆盖新结果：

export class SafeRegexRunner {
  private worker: Worker | null = null;
  private currentRequestId = 0;
  private timeoutTimer: number | null = null;
  private readonly TIMEOUT_MS = 1000; // 1秒熔断阈值

  constructor(private workerScriptUrl: string) {
    this.initWorker();
  }

  private initWorker() {
    if (this.worker) {
      this.worker.terminate();
    }
    this.worker = new Worker(this.workerScriptUrl);
    this.worker.onmessage = (e) => this.handleMessage(e.data);
  }

  public test(pattern: string, flags: string, text: string): Promise<MatchResult> {
    return new Promise((resolve, reject) => {
      const requestId = ++this.currentRequestId;

      if (this.timeoutTimer) {
        clearTimeout(this.timeoutTimer);
      }

      // 看门狗：一旦 Worker 超时，立即硬杀并不阻塞主线程
      this.timeoutTimer = window.setTimeout(() => {
        if (this.currentRequestId === requestId) {
          this.initWorker(); // 强杀并重建 Worker
          reject(new Error('EXECUTION_TIMEOUT: 正则执行超过 1000ms，已触发防回溯熔断保护。'));
        }
      }, this.TIMEOUT_MS);

      this.pendingResolve = (res) => {
        if (this.currentRequestId === requestId) {
          clearTimeout(this.timeoutTimer!);
          resolve(res);
        }
      };

      this.worker?.postMessage({ requestId, pattern, flags, text });
    });
  }
}

在 Worker 内部，执行精准的单步匹配：

self.onmessage = (e) => {
  const { requestId, pattern, flags, text } = e.data;
  try {
    const reg = new RegExp(pattern, flags);
    const matches: Array<{ index: number; match: string; groups: string[] }> = [];

    let match: RegExpExecArray | null;
    let stepCount = 0;
    const MAX_STEPS = 10000; // 限制全局匹配的最大循环步数

    if (flags.includes('g')) {
      while ((match = reg.exec(text)) !== null) {
        matches.push({
          index: match.index,
          match: match[0],
          groups: match.slice(1),
        });

        // 避免零宽断言导致的死循环（如 /(?=a)/g）
        if (match.index === reg.lastIndex) {
          reg.lastIndex++;
        }

        if (++stepCount > MAX_STEPS) {
          throw new Error('TOO_MANY_MATCHES: 匹配结果过多，已自动截断');
        }
      }
    } else {
      match = reg.exec(text);
      if (match) {
        matches.push({
          index: match.index,
          match: match[0],
          groups: match.slice(1),
        });
      }
    }

    self.postMessage({ requestId, success: true, matches });
  } catch (err: any) {
    self.postMessage({ requestId, success: false, error: err.message });
  }
};

5. 日常编写高性能正则的五条铁律

  1. 避免双重量词嵌套：严禁写出形如 (a+)+、(.*)*、([a-zA-Z]+)* 的模式，改为扁平化的单层量词。
  2. 限定通配符范围：尽量不用 .*，用具体的非集合代替。例如提取双引号内容，写 "[^"]*" 而不是 ".*?"。虽然非贪婪模式不会直接引发回溯爆炸，但在长文本失败场景下依然会发生前向全量扫描。
  3. 消除分支交集：在 (A|B) 分支中，确保 A 和 B 之间前缀互斥。例如 (integer|int) 应写成 int(eger)?。
  4. 尽早失败锚定：充分利用 ^、$ 或单词边界 \b。如果模式必须匹配整行，明确加上两端锚点，避免引擎在文本每一个偏移位置逐个启动失败回溯。
  5. 善用原子组与占有量词（Possessive Quantifiers）：在支持的语言（如 Java、PCRE）中，优先使用 ++ 或 (?>...) 剥离回溯检查点；在 JavaScript 中，可以通过正向零宽预查 (?=(...))\1 技巧模拟原子组，强行锁定匹配结果，禁止引擎回退。