正则回溯爆炸：一个能卡死服务器的表达式

一个 31 个字符的输入，跑了 8 秒

先把结论摆在前面，剩下的部分都是在解释它。下面这个表达式没有任何看起来危险的地方，长度不到十个字符：

/^(a+)+$/

用它去匹配一串 a 后面跟一个 X——因为有 X，匹配注定失败。a 的个数从 20 递增到 30（连 X 一起算，输入总长是 21 到 31 个字符），记录 test() 返回所花的时间：

const re = /^(a+)+$/;
for (let i = 0; i < 200; i++) re.test('a'.repeat(12) + 'X'); // 预热，理由见文末
for (let n = 20; n <= 30; n++) {
  const s = 'a'.repeat(n) + 'X';
  const t0 = performance.now();
  re.test(s);
  console.log(n, (performance.now() - t0).toFixed(1) + ' ms');
}

这是在 Node v22.17.1 / Apple M1 Pro / macOS 26.5.2 上跑出来的实测结果，每个长度跑三次取最小值：

每多一个 a，耗时翻一倍。这条规律的可怕之处在于它不会自己停下来：按同样的倍率往下推，40 个 a 大约要 2.3 小时（8101.1 毫秒 × 2¹⁰），50 个 a 大约要 98 天（× 2²⁰）。后面这两个数字是外推出来的，我没有真的等——但外推的依据就是上表里那一列稳定在 2.0 附近的比值。

一个用户在表单里多打十个字母，就足够把一个请求变成一场事故。

为什么正好是翻倍

先把大前提摆明：JavaScript 用的是回溯式引擎（Java、Python、Ruby、PCRE 也都是这一路），它靠「试一条路，走不通就退回来换一条」来实现匹配——这与下文会提到的 RE2 是两种不同的实现路线，后者不回溯。回溯式引擎在处理 ^(a+)+$ 时，要在两层量词之间分配这些 a：内层的 a+ 每轮吃掉一段，外层的 + 决定分成几轮。把 n 个 a 切成若干个非空段，方案数就是 n 的有序拆分数，正好是 2 的 n-1 次方。20 个 a 有 52 万多种切法，30 个有 5.3 亿多种。

如果字符串能匹配，引擎试到第一种可行的切法就收工了；但结尾那个 X 让 $ 永远对不上，于是每一种切法都会被推进到最后一步再被否掉。引擎必须把 5 亿多种可能全部试完，才有资格说「不匹配」。 上表里那个 2.0 的倍率，就是 2 的 n-1 次方在时间轴上的投影——理论值和实测值对得上，这不是巧合。

真正致命的是「失败」，不是「成功」

这是这类问题最反直觉、也最值得记住的一点。同一个 ^(a+)+$，喂给它能匹配的输入：

• 30 个 a（匹配成功）：0.000037 毫秒
• 1000 个 a（匹配成功）：0.000401 毫秒
• 10000 个 a（匹配成功）：0.003198 毫秒

三档用的是同一种测法：预热之后取多次平均，只有迭代次数不同（前两档各 20 万次，最后一档 2 万次——档位本身越慢，取够稳定所需的次数越少）。这里必须统一测法，也必须留足有效数字——单次测量的抖动和四舍五入都会大到足以让下面这些倍数关系失真。

成功路径的开销大致随长度线性增长：后两档长度从 1000 涨到 10000（10 倍），耗时从 0.000401 涨到 0.003198（8.0 倍）；最短那一档的绝对耗时当然是三档里最小的，但按每个字符摊算反而最贵——30 个 a 的真实匹配成本已经小到被固定的调用开销盖住了。三档的绝对值全都停在微秒量级，因为贪婪量词第一次尝试就一路吃到底、直接匹配成功，根本没有回溯发生。

真正该对比的是失败路径，而且要拿长度只差一个字符的输入来比：30 个 a 匹配成功是 0.000037 毫秒，末尾只多一个 X（31 个字符）就是 8101 毫秒。两个输入只差一个字符，耗时差了 2.2 亿倍，八个数量级。（失败那一档取的是上面第一张表的实测值，测法与成功路径不同；但两者差着八个数量级，测法带来的差异根本不在同一个尺度上。）

这意味着这个 bug 不会出现在你的测试里。测试用例通常长这样：一条合法的样本（走成功路径，快），一条明显不合法的样本（比如空字符串或几个字符，快）。真正会引爆它的输入形状很特别：一段很长的、几乎能匹配的合法前缀，末尾跟一个破坏匹配的字符。这种输入不会出现在你手写的用例里，但一定会出现在生产环境——用户会粘贴一段没写完的日志，攻击者会专门构造它。

所以灾难性回溯几乎总是在生产环境第一次现身，而且第一次现身时通常就是全站级别的。

三种形态，以及它们各自有多快爆炸

认出危险模式靠的是形状，不是经验。下面三种覆盖了绝大多数成因，我把每一种的实测增长阶也附上——因为「会爆炸」不是一个二值判断，爆炸的速度差别很大。

一、嵌套量词：(x+)+、(x*)*、(x+)*。 就是上文那个例子，指数级，底数为 2。特征是一个带量词的组，外面又套了一个量词。

二、量词作用在可交替的分支上：(a|a)*、(a|aa)+。 危险的不是「有交替」，而是分支之间有重叠：同一段文本能被不同的分支组合拼出来，于是一个字符串有多种拆法。(a|a)* 的两个分支干脆完全相同；(a|aa)+ 的两个分支并不相同，但一串 a 既可以一个一个地切、也可以两个两个地切，拆法照样不止一种——两者都会让引擎在失败时把所有拼法试一遍。反过来，(a|ab)+ 同样是「量词套着交替」，却不会爆炸：a 与 ab 的结尾字符不同，串里每个 b 的位置就钉死了 ab 只能切在那儿，拆法唯一，也就没有可搜索的空间——我拿一万个 a 加一个 X（同样是失败路径）喂给它，2000 次平均只要 0.04 毫秒。回到会爆的那个，实测 ^(a|aa)+$ 匹配 n 个 a 加一个 X：

同样是指数，但底数变了：用 1 和 2 去拆分 n 的方案数是斐波那契数，增长率是黄金比例 1.618 的 n 次方，每多两个 a 就是 1.618 的平方即 2.618 倍。实测那一列除了最短的一档（0.7 毫秒，绝对值太小、噪声占比高）以外稳定在 2.62——和理论值对到小数点后两位。底数更小意味着它更阴险：40 个 a 还只要 1.6 秒，看着像「有点慢」而不像「坏了」；而按同一倍率外推，60 个 a 就是将近 7 小时（4247.5 毫秒 × 2.618⁹）。

三、相邻的贪婪通配：.*.*、.*.*=.*。 这一种和前两种有本质区别，实测 /.*.*=.*/ 匹配 n 个 x（串里没有等号，注定失败）：

长度翻倍，耗时变八倍——这是三次方，多项式，不是指数。8000 字符按此推算约 4.3 分钟（32703.4 毫秒 × 7.96），我没有跑完就中止了它。

多项式听起来比指数温和，但请看清楚横轴的单位：前两种在几十个字符上就出事，这一种要到几千字节才出事。而几千字节是一个 HTTP 请求头或请求体再普通不过的尺寸。能造成大规模事故的往往不是最凶的那种，而是最容易被真实流量喂到临界点的那种。

Cloudflare 2019 年 7 月 2 日

上一节最后那句话有一个教科书级的例子。2019 年 7 月 2 日，Cloudflare 全球边缘节点大面积返回 502，持续不到半小时，起因是一次 WAF 托管规则的更新。

事故报告里点名的正是相邻贪婪通配这种形状——报告用来说明问题的简化形式写作 .*.*=.*。我不在这里抄写那条规则的完整表达式：凭记忆抄一条正则，抄错一个字符就是在传播错误信息，要看原文请直接读官方报告。规则本身的意图是拦截内联 JavaScript 的 XSS，逻辑上没有错，错在它的形状。

技术上有两点值得记住。第一，当时的 WAF 建在 Lua 加 PCRE 上，PCRE 是回溯引擎，一条规则一旦跑飞就能把一个 CPU 核吃满，而那套部署里没有哪一层会在这时候把它掐掉。第二，这条规则跳过了灰度，一次性推到全球所有机器，于是所有机器同时开始烧 CPU，止血手段最终只剩下全局关掉 WAF。

把这两点和上一节的量级放在一起看就很清楚了：三次方的回溯，配上全球规模、内容完全由外部决定的请求，根本不需要指数级就能烧穿一个全球网络。官方事后报告在这里：https://blog.cloudflare.com/details-of-the-cloudflare-outage-on-july-2-2019/

怎么修，按可行性从高到低

改写表达式，消除歧义。 这是唯一的根治手段。所谓歧义，就是同一段输入存在多种被同一个模式接受的拆法。^(a+)+$ 的等价安全写法就是把外层量词删掉：

/^a+$/

两者接受的字符串集合完全相同——都是「一个或多个 a」，外面那层 + 从一开始就没有增加任何表达力，只贡献了指数级的切分方式。实测这个写法匹配 100000 个 a 加一个 X：0.294 毫秒。十万个字符，比原式跑那三十一个字符还快了约 2.8 万倍，四个多数量级。

把通配收窄。 .* 是回溯的燃料。如果你要匹配的是等号前的内容，写 [^=]* 而不是 .*；要匹配一行内的内容，写 [^\n]*；要匹配引号里的内容，写 [^"]*。收窄之后引擎在错误的分支上会立刻失败，而不是先吃光整行再一个字符一个字符地吐回来。加锚点同理，但要分清两者的作用：^ 砍掉的是「换个起始位置再试一遍」这一整维尝试；$ 不减少起始位置，它的作用是让长度对不上的分支提早被否掉，而不必等到把后面的模式全试一遍。

换一个不回溯的实现。 Go 的 regexp（RE2）和 Rust 的 regex crate 保证线性时间，代价是不支持反向引用和前后瞻——这个交换在服务端几乎总是划算的。只要你的正则有任何一部分来自用户输入或外部配置，就不应该用回溯引擎。

用原子组或占有量词。 PCRE 与 Java 两者都支持——(?>...) 是原子组，a++ 是占有量词；.NET 支持原子组。它们的语义都是「这一段一旦匹配完就不许再回退」，等于直接把回溯点删掉。

JavaScript 没有原子组，但可以模拟。 用前瞻加反向引用能得到等价效果：(?=(a+))\1 相当于 (?>a+)。前瞻先贪婪地量出最长的一段并捕获，反向引用再把这一段原样吃掉，中间没有留下任何可回退的分叉。实测 /^(?:(?=(a+))\1)+$/ 对 10000 个 a 加 X 只要 0.010 毫秒，且对 aaaa（真）与 aaaaX（假）的判定与原式完全一致。代价是凭空多出一个捕获组，后面所有编号组都要顺移，而且没有注释的话下一个人根本读不懂——所以能改写成 ^a+$ 时就不要用这招。

兜底只剩两条：限制输入长度，以及把匹配放进一个能被杀掉的执行单元里。 前者是有效的，因为指数增长的另一面是：只要把上限压得够低，2 的 n 次方就大不到哪里去。后者是本站的做法，下一节说。

为什么必须是 Web Worker，而不是 setTimeout

本站的正则测试工具把匹配放在 Web Worker 里跑，主线程设一个 1500 毫秒的定时器，到点就 terminate() 掉整个 Worker。

这里最容易被想当然的是：为什么不直接在主线程上跑，然后用 setTimeout 做超时？答案是那样写出来的超时逻辑一次都不会生效。JavaScript 是单线程的，setTimeout 的回调只是被放进任务队列，它要等当前这段同步代码彻底跑完、执行权交还给事件循环之后才有机会执行。而正则匹配是同步的：引擎在回溯的那 8 秒里，主线程一步都没有离开过 test() 这个调用。等到定时器终于被触发时，匹配早就结束了，超时检查只会看到一个已经完成的结果。AbortController 同样管不着——它能取消的是异步操作，对一段同步执行的代码毫无办法。

也没有别的口子可以钻：JavaScript 的正则没有超时参数，没有步数上限，没有取消令牌，正在回溯的匹配无法从外部中断，也无法自己停下来。唯一可靠的止损手段是杀掉整个执行单元。 而在浏览器里，唯一能被杀掉且不牵连页面的执行单元就是 Worker。

具体到实现（src/tools/regex-tester/index.vue），有几个细节是踩出来的：

• 每次运行都新建 Worker。 terminate() 之后的 Worker 不能复用，所以超时路径和正常路径都要负责把它收掉，组件卸载时也要收。
• Worker 的源码是用 collectMatches.toString() 注入的，不是另写一份。 这样单元测试覆盖的就是线上真正在跑的那段代码，而不是它的一个副本——副本迟早会和本体不一致。
• 输入变化后有 200 毫秒防抖。 边打字边起 Worker 会创建一大堆短命线程，而其中每一个都可能正在跑一个半成品的、形状恰好危险的表达式。
• 界面上那个「有风险」提示是形状层面的启发式，说白了就是用正则去匹配正则，找 (x+)+ 和 (a|b)+ 这两类形状。它刻意只提示、不拦截：一个表达式会不会爆炸取决于具体输入，静态地严格判定这件事在一般情况下不可判定。提示告诉你该往哪儿看，真正保护你的是超时。

也要把这套方案的边界说清楚，它不是万能的：Worker 被杀掉之前的那 1.5 秒，它确实在实打实地跑满一个 CPU 核，只是没有跑在主线程上，所以页面还能滚动、还能编辑；启发式提示既有漏报也有误报；超时用的是墙钟时间，在慢设备上，一个合法的大输入也可能被误杀。这套做法解决的是「页面被冻死、除了关标签页别无他法」这一个具体问题，仅此而已。

自己测的时候会踩的一个坑

如果你照着本文开头那段代码自己跑，很可能第一次拿到的数据是乱的。我第一次跑（没有预热）拿到的是：20 个 a 时 35.1 毫秒，21 个 a 时 13.5 毫秒——字符更多反而更快，曲线一开头就是反的。

原因是第一次调用要付正则的编译成本和 JIT 预热成本，这笔固定开销比 20 个 a 那一档的真实耗时还大，把最短的那几行完全淹没了。加上一轮短输入预热、每个长度跑三次取最小值之后，曲线才干净成上面那个稳定翻倍的样子。这个坑对任何微基准测试都成立：当你要测的量本身很小的时候，测量方法本身的开销就是最大的噪声源。