算法与数据结构 / regex · Unicode 字符模型与一个自研引擎 / 灾难性回溯：一条正则耗尽 CPU 待审核 36 / 36
catastrophic backtracking · ReDoS

灾难性回溯：一条正则耗尽 CPU

有些正则在匹配失败时会卡死——不是写错了，而是回溯引擎要尝试指数级的组合。典型成因是嵌套量词：(a+)+b 去匹配一串没有结尾 b 的 a，外层 + 要把这串 a 切成若干段交给内层，n 个 a 有 2 的 n−1 次方种切法；因为整串注定匹配不上，引擎被迫把所有切法都试一遍，步数随即指数增长。这就是 ReDoS 的根。

1 · 步数随 n 翻倍

拿一个会计步的玩具回溯解释器跑在自研引擎的 AST 上，逐个 n 数出步数。纵轴取对数：安全的 a+b 是一条平缓的线，几条带嵌套量词的则一路顶到预算上限。

图 1-1 · 五条 pattern 在长度 1 到 n 的输入上的回溯步数（纵轴对数），超预算的柱标红。可换 pattern 或拖动 n。

2 · 换成线性引擎

上面那条爆炸曲线是回溯引擎的病。基于 NFA 的线性引擎——本仓库的 Pike VM、Google 的 RE2——同时跟踪所有可能状态、从不回溯，所以同一条 (a+)+b 是线性的。下面用两条真引擎实测耗时。

图 2-1 · 同一条 pattern 在回溯与 Pike 两条真引擎上的耗时对照，回溯超过阈值即停测防卡。可换 pattern。

建议 · 前三种思路都是消除歧义、不给引擎回溯的余地：把 (.*?,){11} 精确化成 ([^,\r\n]*,){11}，去掉嵌套量词的重叠区；用原子组 (?>…)，整组匹配完就提交、绝不回溯进去；用占有量词 a*+，吃掉就不吐。根本解决是换线性引擎。Cloudflare 2019 年那次全球宕机，正是一条 .*.*=.* 类的正则在 WAF 里灾难性回溯占满 CPU，后来迁到了 RE2。

注 · 原生 JS 也能就地换引擎：V8 内置了一个非回溯的线性引擎，用实验性的 l 标志开启，但至今默认关闭、需启动时带 --enable-experimental-regexp-engine，且与 RE2 一样不支持环视与反向引用（核对于 2026-08）。Safari 的 JSC 走另一路：回溯超过约一百万次就直接返回假，快，但结果可能是错的。思路与权衡都跟本仓库的 engine: 'pike' 一致，见 自研引擎。

3 · 参考文献

  1. Cloudflare. Details of the Cloudflare outage on July 2, 2019. 一条正则引发全球宕机的事故报告，本页建议一节的出处。blog.cloudflare.com
  2. Google. RE2 Syntax. 线性时间引擎的能力边界：不支持环视与反向引用，换来最坏情况的线性保证。github.com
  3. V8. An additional non-backtracking RegExp engine. V8 线性引擎的设计与限制，实验性 l 标志的来历。v8.dev
  4. OWASP. Regular expression Denial of Service. ReDoS 的成因分类与防御清单。owasp.org