为什么我的正则这么慢？灾难性回溯与 ReDoS

你有一个正则，它能用。你丢给它的每个测试都通过了，上线，接下来好几周风平浪静，没人觉出哪里不对。直到某天来了一个稍微长一点的输入——一段粘贴进来的文字、一个畸形的 URL、一行拖着长长一串空格的日志——标签页就卡死了。CPU 直接顶到 100%。要是在服务端，整个 Node.js 进程干脆不再响应任何请求。没有任何报错；这个正则在技术上依然是“对”的。它只是永远跑不完。

先说清楚这是哪一种“慢”，因为不是所有慢正则都是同一种东西。有些只是多项式级的慢——比如二次方，输入翻倍、耗时大约变四倍，烦人但扛得住；有些纯粹是因为输入本身巨大，或者你在一个热循环里反复调用它。这篇文章不谈那些，那些是普通的性能优化。它谈的是更凶险的一类：输入只长了一点点，耗时却直接爆炸——工作量呈指数级增长，多喂几个字符，就能把微秒变成分钟、再变成永远跑不完。这有个名字，叫灾难性回溯（catastrophic backtracking）；当有人故意构造这样的输入来把你的服务打垮时，它就叫 ReDoS（正则表达式拒绝服务）攻击。

好消息是，这一点都不玄。它就是从回溯式引擎的工作方式里长出来的——本系列的第一篇已经把那台引擎从头讲透了。只要你记住引擎贪心地吃、卡住了就回溯，灾难性回溯不过是同一套机制失了控。这篇正好从那里接上：是什么让工作量爆炸、怎么一眼认出危险的形状、它们藏在真实代码的哪些角落，以及——既然 JavaScript 几乎不给你任何护栏——怎么靠重写把自己救出来。

爆炸从哪来

把第一篇的引擎模型压缩成一句话：回溯式引擎在贪婪量词无法凑齐整个匹配时，会倒回去换一种拆法——把吃进去的字符吐回来、另找一条出路，直到试遍每一种可能才肯认输。灾难性回溯，就是“每一种可能”变成一个天文数字的时候。

教科书级的触发器是嵌套量词——一个会重复的组，自己又被重复一遍：

(a+)+$

照字面读，它是冗余的。“一到多个（由一到多个 a 组成的段），并锚定到字符串结尾”，描述的其实和一个朴素的 a+$ 是同一批字符串。但引擎并不知道这两者等价，而正是这份冗余要了它的命：内层 a+ 和外层 + 都能来争同一批 a，于是一串 a 能被切成组的方式就不止一种——引擎觉得自己有义务把每一种都试过，才肯罢休。

拿只有四个字符的 aaaX 看它怎么走。引擎的开局是贪婪的：内层 a+ 一口气把三个 a 全吞成一组 (aaa)。这时它想要 $，可光标正停在 X 上——失败。于是回溯。内层 a+ 吐回一个 a，剩下 (aa)；外层 + 抓住机会开了第二组，内层 a+ 把剩下那个 a 捡走，凑成 (aa)(a)；再试 $，还是 X，失败。再回溯：(a)(aa)，失败；(a)(a)(a)，失败。把三个 a 的全部四种分组都试过、也全都失败之后，引擎才被允许放弃这个起始位置——然后往右挪一格，把整场折磨从头再来一遍。

三个 a 对应四种分组绝非偶然：n 个 a 有 2ⁿ⁻¹ 种切成有序分组的方式，而那个致命的 $——在 X 前面永远无法成立——逼着引擎在认输前把每一种都走一遍。10 个 a 是 512 次尝试，20 个是五十多万次，30 个就超过五亿次。所以这种卡死不是慢慢变卡，而是骤然失控：每多一个 a，工作量大致翻一倍。它不是慢，是指数级——而指数曲线在真正竖起来之前，看着一直是平的。

别去纠结到底多长的输入会把它压垮，那随浏览器、硬件和引擎实现而变。真正要记住的是曲线的形状——还有一条让它从性能小毛病升级成武器的性质：会出事的恰恰是失败的那次匹配。 这样的模式在测试里跑得飞快，因为你拿去测的输入都能很快、很省地匹配上。真正把引擎拖进完整指数搜索的，是那些差一点点就成了的输入——几乎一路匹配到底、却在最后一步失败。攻击者深谙此道，所以一个 ReDoS 载荷总是被精心构造成“险些匹配”的样子：一长串 a，末尾再补上那个让它功亏一篑的字符。

危险的形状，一眼认出

你不必每次都在脑子里跑一遍引擎——危险模式的轮廓就那么几种。但值得把“有多危险”分清楚，因为有两条截然不同的耗时曲线被一股脑塞进了“ReDoS”这个词，而真正的炸弹只有一种。

指数级的形状——真正的炸弹。 就是那种每多一个字符、耗时大致翻倍的，跟上面追踪过的一模一样。它的标志是重复叠着重复，而且两层都能匹配同一批字符，于是同一段字符可以被切成指数级多种分法：

(a+)+$       (a*)*$       (\w+)*$       ([\w.]+)+@

量词底下的重叠分支是同一种病换了张皮：当两个分支能匹配同一段文本，每个字符就有不止一条匹配路径，外面的量词再把它们乘起来。

(a|a)*$      (\w|\d)*$

\d 是 \w 的子集，所以 (\w|\d)* 有两条路匹配同一个数字——面对一长串最终会失败的数字，那就是 2ⁿ 条路径。（分支必须在同一批字符上重叠才算。(a|ab)* 的两个分支吃掉的长度不同，那是更微妙、通常只是多项式级的情况，不是必然的炸弹。）

多项式级的形状——慢，但偶尔才可利用。 相邻的无界量词，或是一个宽泛的 .* 到处去找一个根本不存在的东西，不会指数级引爆——但它们照样能烧掉 O(n²) 甚至更多，在足够大的输入上把页面拖死：

.*.*=        \s*.*\s*$        a.*b.*c

这些也该修，但它们是另一个严重级别。分清这条线，你就不会一看到 .* 就喊“指数级”。

改成懒惰，这些一个都拆不掉。 “把贪婪换成懒惰”常被当成性能修法四处流传；它不是。懒惰只是把引擎尝试各种拆法的顺序倒过来——先试短的而不是先试长的——而在一次失败的匹配里，它照样要把所有拆法都走一遍。(a+?)+$ 和 (a+)+$ 一样是指数级的。别把 *? 当成安全特性。

有一点对这两个级别都适用：危险的形状只在失败的匹配上才真正咬人。 它到底能不能被利用，取决于是否存在一个能逼出完整搜索的输入——通常是一长串会重复的前缀，后面跟一个能破坏锚点或必需后缀的字符——以及攻击者能把这个输入拉多长。形状告诉你风险存在，失败路径和输入长度才决定它有多糟。

想亲身感受这中间的差别，把它们丢进正则测试工具，让它的 ReDoS 分析来替你判断——它在后台运行，会标出有风险的形状。你不该做的，是粘一段很长的攻击串进去、只为看页面卡住：匹配是跑在浏览器主线程上的，你这么干唯一的成果，就是把自己的标签页挂死，去印证一个分析器早就替你得出的结论。

它到底藏在哪

没人会在生产代码里故意写 (a+)+$。灾难性回溯之所以被带上线，是因为它藏在那些看起来毫无破绽的模式里——尤其藏在校验器里，也就是我们对着不可信用户输入去跑的那些正则，而那恰恰是最不该出事的地方。

邮箱与 URL 校验。 手写的地址校验器背后拖着一长串真实的 ReDoS CVE，而出问题的那些都共享同一种形状：一个会重复的组，它的内容和外面包着的重复相互重叠。看一个写成 ^([a-zA-Z0-9]+[._-]?)+@ 的本地部分校验。它读起来挺讲究——“字母数字，加一个可选的分隔符，重复若干次”。但喂给它一长串没有分隔符、也没有 @ 的字母，那个可选的 [._-]? 每一轮都匹配空，整个东西就坍缩成 ([a-zA-Z0-9]+)+——上面那个指数级形状，只是套了层伪装。（要注意，那个故意长得人畜无害的 ^([a-zA-Z0-9]+\.)+[a-zA-Z]{2,}$ 并不是这个 bug：它的内层字符类匹配不了 .，而每一次外层重复都必须吃掉一个字面的 .，所以根本没办法把同一批字符重新切分。要命的是重叠，不是“有个嵌套的 +”这件事本身。）

重复空白类的模式。 这里值得放慢脚步，因为一个看着吓人的 trim 其实往往没事。日常那句 ^\s+|\s+$ 不是 ReDoS 风险——它就是两段简单的、锚定好的连续空白，没有嵌套也没有重叠，放心继续用。危险的是嵌套形态：(\s+)+、(\s*)*，或者外面再套一个量词的 (\s|\t)+，这才把重叠又请了回来。由于空白规整化往往对着用户提交的一切内容跑，一个嵌套版本就是个上等靶子——但别一慌之下把正常的 trim 都删了。

任何带 (.*,)* 或重复组的模式——解析逗号分隔的列表、一串键值对、重复的 HTML 属性、带重复段的路径。只要你写下“一到多个（本身又含一到多个的东西）”，就停下来查这个决定性的问题：内层和外层能不能吃到同一批字符？如果每次重复都被钉在各自的分隔符上，或者输入长不起来，最坏也不过是个值得测一测的性能开销——不是炸弹。只有当重叠是真的、而且存在一个长的失败输入时，它才算真正的 ReDoS 候选。

藏在模式背后的规律是：最可能藏着回溯炸弹的正则，恰恰就是你拿去跑不可信输入的那些，因为嵌套量词天然就在校验器里冒出来。“有漏洞的形状”和“攻击者可控的输入”这两者的重合，就是 ReDoS 威胁的全部。

怎么修：只能重写，因为 JavaScript 不会救你

有些正则引擎给你一个直接关掉回溯的开关。原子组 (?>...) 告诉引擎“这段一旦匹配上，就再也别吐回去”，占有量词 a++、a*+ 对单个量词做同样的事。把它们对准有歧义的那一段，指数搜索就从源头被锁死了。

这里有条值得刻进脑子的硬限制：JavaScript 两样都没有。 没有原子组，没有占有量词，直到今天。（Java、PCRE、Ruby、.NET 全都有；JS 是那个显眼的例外。）所以在 JavaScript 里，你手上唯一的杠杆，就是把模式重写成歧义根本不存在的样子——把重叠去掉，就没有什么可回溯的了。下面是这套工具箱，大致按“它是正解”的频率排序：

1. 用取反字符类，别用 .* 或 .*?。 这是性价比最高的一招，也正是第一篇一直在给你埋的伏笔。[^"]* 跨不过一个引号，所以当你写 "[^"]*" 时，匹配中间那段的方式有且只有一种——不会来回试探。对比一下 ".*"（贪得过头：.* 会把结束引号也吃掉、再不得不吐回来——这只是一点线性的回溯，单独看并不是灾难）和 "[^"]*"（无歧义，硬边界）。单看这一处，好处是更精确、更正确；而对本文来说真正的收益在于：一道硬边界不会形成那种一旦被嵌进另一个量词就会指数化的重叠。只要你能说出是哪个字符给一段收尾，就去匹配“除它以外的任意字符”，而不是“任意字符，懒惰地来”。

".*?"    →    "[^"]*"
\w+@.*   →    \w+@[^\s@]+

上面第二个例子并不是无脑等价——\w+@.* 和 \w+@[^\s@]+ 匹配的东西并不一样。[^\s@]+ 是刻意把结尾收窄成“一段不含空格、也不含第二个 @ 的域名部分”，而这通常正是你本来想要的。选哪个取反集合，要贴合你真正的意图，而不只是为了躲开回溯。

2. 让分支互斥。 如果你的几个分支相互重叠，就重组它们，让每个字符恰好只有一个分支能匹配。(\w|\d)* 直接变成 \w*（反正 \d 本来就在 \w 里）。重叠是敌人，消灭它。

3. 加锚点、砍掉起始位置——但要知道它的边界。 在合适的位置加 ^/$，或在重复组之间放一个明确的分隔符，能拦住引擎在每一个起始位置重试整场匹配，这消掉的是外层那个线性或多项式的因子。它做不到的，是拆掉内层的指数级爆炸——(a+)+$ 本来就带着锚点，而那个 $ 恰恰就是逼出指数级失败的元凶。加锚点帮的是多项式那一档；对嵌套重叠的炸弹，它不是解药。

4. 限制输入，作为纵深防御，而不是修复本身。 在业务层设一道硬性长度上限——在正则见到输入之前就把超过 n 个字符的拒掉——是实打实值得做的，而 {1,64} 代替 + 也给嵌套深度封了个顶。但别把“设了上限”错当成“漏洞没了”：{1,64} 仍然允许多达 2⁶⁴ 条路径，那是个天文数字，根本跑不完。上限控制的是爆炸半径；真正拆掉炸弹的，是消除重叠。

5. 干脆别用正则。 有些活儿——嵌套结构、任何像样的语法、解析 HTML 或 JSON——根本不是正则语言，硬拿正则去套，正是你一开始造出这些怪物的原因。一个手写的字符串循环、传字符串分隔符的 String.split（而不是 split(/正则/)——那仍然会跑正则），或者一个真正的解析器，往往更简单、更快，而且对这一整类 bug 免疫。

每次重写之后，确认两件事：它仍然能匹配上所有该匹配的（回归特别爱藏在“更安全”的重写里），以及它不再触发 ReDoS 检查。这两件事在正则测试工具里都是一粘即得——把旧模式和新模式并排放着，喂同一个“险些匹配”的输入。

安全视角：为什么这是 DoS，而不只是个 bug

值得把话挑明：为什么灾难性回溯会从“性能烦恼”晋升成“安全漏洞”——因为这一跃迁和服务器的运行方式是绑死的。

Node.js 在单线程上执行 JavaScript。当一个正则陷入灾难性回溯，那条线程就被彻底占住了——它不让出、不处理别的请求，只是在正则引擎里空转。于是一个精心构造的输入，拖慢的不只是承载它的那一个请求，而是把整个进程为它服务的所有用户一起冻住。而且这里有根刺：你用 setTimeout 设的请求超时救不了你，因为定时器回调只能等事件循环空下来才触发——而那个失控的正则，恰恰就是霸着事件循环不放的元凶。Node 没法中断一个正在跑的同步正则；被占住的线程就一直被占着，直到匹配自己跑完，而那可能约等于永远。

这场爆炸波及多远，取决于你的部署：单进程的服务器会彻底黑掉，而多进程或 worker 线程、一道把连接掐掉的网关超时、外加限流，都会把半径缩小。但那条核心的不对称在这一切之后依然成立——攻击的代价微不足道，吸收的代价却极不成比例——这正是 ReDoS 频繁出现在各种流行库 CVE 报告里的原因。

这也顺带解开了第一篇留下的一个谜：为什么同一个危险模式在 ripgrep 里瞬间跑完，搬到 Node 却卡死。 像 ripgrep（Rust 的 regex crate）和 Go 的 regexp 这类工具建立在有限自动机之上，那是另一种引擎架构，把匹配变成一次没有任何回溯的线性扫描。它们从构造上就对灾难性回溯免疫——代价是放弃了反向引用这类本质上需要回溯的特性。你跑在哪一类引擎上，决定了这个威胁对你成不成立。在回溯类引擎上——JavaScript、Python、PCRE、Java——它成立得很。

这里还有一个专门针对 Node 的可操作推论。当一个模式实在没法安全重写——或者你干脆信不过自己能把每一个都手工改对——你可以让它跑在一个线性引擎上，而不是内置的那个。Google 的 RE2 就是这样一台有限自动机引擎，带着那份线性保证，而 re2 这个 npm 绑定在 Node 里近乎是 RegExp 的原样替代。代价是那些本质上依赖回溯的特性：RE2 完全不支持环视——前瞻、后顾一个都没有——也不支持反向引用。 作为交换，匹配耗时随输入长度线性增长（模式更复杂，无非是常数因子更大），永远不会指数级，无论攻击者喂给它什么。对一个必须跑在不可信数据上的正则，这往往是笔划算的买卖。

上线前就把它拦下

抓一个回溯炸弹的最佳时机，是在它进入生产之前，而你不必用肉眼一个个去盯每个模式。本站的正则测试工具会对你的模式异步跑一遍 ReDoS 分析：把正则粘进去，它就在后台检查有没有存在漏洞的结构。发现问题时，它会给你一个具体的攻击串——真能把这个模式炸掉的那个输入——让你亲眼看到失败，而不是凭空信它。而当分析拿不出确定结论时，它也会照实、干脆地告诉你，而不是假装一切都好。一切都在你的浏览器本地运行，模式不会离开这个页面。

把它当烟雾报警器，别当合格证书。结果干净是个好兆头，但它不是安全的证明；一次在你真实输入规模下做的性能测试，仍然是最终裁决。这道检查替你换来的，是那份便宜的、趁早的拦截——让你在 ([a-zA-Z0-9]+[._-]?)+@ 还没去守着生产环境里的登录框之前，就认出它是个炸弹。

一份能照着走的清单

当一个正则卡死了，或者在你放行一个会碰用户输入的正则之前，走这一遍：

1. 一跑就卡、CPU 顶满？ 那是灾难性回溯，不是普通的慢。别绕着它做优化——这个模式是指数级的，得重写。
2. 先扫指数级的形状。 (a+)+、(\w+)*、([\w.]+)+、(a|a)*——重复叠着重复，或者重叠的分支，两层都在抢同一批字符。这些才是真炸弹。
3. 再扫多项式的那些。 .*.*、\s*.*\s*——相邻的无界量词。比它该有的样子慢，偶尔可被利用，但不是同一级别的急症。
4. 别指望懒惰。 (a+?)+ 和 (a+)+ 一样危险；*? 改的是搜索的顺序，不是它的规模。
5. 盯死你的校验器。 邮箱、URL、重复空白这些模式，既是重叠爱藏的地方，也是不可信输入落地的地方。确认你担心的那个 trim 确实是嵌套的（(\s+)+），而不是无害的 ^\s+|\s+$。
6. 靠消除重叠来修，别在外围打补丁。 优先用取反字符类（[^"]*）替代 .*?；让分支互斥；活儿本来就不是正则语言时，改用解析器。加锚点、限输入能帮着控制损失，却拆不掉一个嵌套的炸弹——而 JavaScript 没有原子组、也没有占有量词，所以重写就是全部戏份。实在没法重写时，让它跑在 RE2 上。
7. 先验证重写后仍能匹配，再复查 ReDoS。 新旧模式并排，喂那个“险些匹配”的输入。

灾难性回溯像是正则里一个阴森的角落，直到你看清它其实就是第一篇里那台回溯引擎在做它一贯做的事——只是做了太多太多次。一旦“贪心地吃、卡住就回溯”长进了你的骨头里，危险的形状就会自己在眼前亮起来，而修法几乎永远是同一个安静的动作：把边界明明白白画出来，让引擎没有任何东西可以反复犹豫。