灾难性回溯：正则表达式为什么会卡死
一个 7 个字符的正则，在 30 个字符的输入上可能要跑好几秒，在 40 个字符的输入上可能要跑几个小时。本文讲解回溯的原理、(a+)+ 这类嵌套量词为什么会爆炸、它在 Stack Overflow 和 Cloudflare 引发的故障，以及让正则变安全的改写方法。
· 阅读约 4 分钟
/^key=[^=]*$/
抓住
- key=value
- key=
- key=42
- key=on
放过
- key=a=b
- key
- value
- k=v
大多数正则表达式几微秒就能跑完。但有少数正则遇到不对的输入，会跑上几秒、几分钟甚至更久，全程占满一个 CPU 核心。这叫做灾难性回溯（catastrophic backtracking），它曾让真实的网站宕机。
好消息是，危险的正则有一眼就能认出的形状，修复通常也很小。本文会展示这种形状、具体数字和改写方法。
01回溯的原理
JavaScript、Python、Java、PHP 和大多数其他语言用的都是回溯引擎。当正则里有选择（一个 + 吃掉几个字符、| 先试哪一边）时，引擎先选一个继续往下走。如果后面匹配失败，它就退回来，换下一个选择再试。
拿 ^a+$ 去匹配 aaaa!，可试的不多：a+ 吃掉全部四个 a，$ 在 ! 处失败，引擎每次吐回一个 a，每次尝试都很快失败。几步之后，结果是“不匹配”。
02会爆炸的形状
现在把一个量词放进另一个量词里：
(a+)+ 的意思是“一个或多个分组，每组是一个或多个 a”。四个 a 有八种分组方式：aaaa、aaa|a、a|aaa、aa|aa、aa|a|a，等等。当 ! 让匹配失败时，引擎会把每一种分法都试一遍才放弃。每多一个 a，分法就翻一倍。
下面是在一台普通笔记本上用 Node 23 测的结果，输入是一串 a 后面跟一个 !：
| 长度 | ^(a+)+$ |
^a+$ |
|---|---|---|
| 24 个 a | 0.12 秒 | 不到 0.01 毫秒 |
| 26 个 a | 0.5 秒 | 不到 0.01 毫秒 |
| 28 个 a | 2 秒 | 不到 0.01 毫秒 |
| 40 个 a | 超过两小时（估算） | 不到 0.01 毫秒 |
匹配的字符串相同，代价却天差地别。危险总是出在失败的匹配上：输入能匹配时，第一条路径通常就走通了。
要警惕的一般形状是：一个被重复的分组，其内部能用不止一种方式匹配同一段文本：
- 嵌套量词：
(a+)+、(\w+)*、(\d*)+ - 相互重叠的分支，再加重复：
(a|a)+、(\w|\d)+、(.*,)* - 同一段文本上连续好几个
.*：.*=.*=.*
03生产环境里真的发生过
Stack Overflow，2016 年 7 月。一篇帖子的某一行中间有大约 20,000 个连续的空白字符。一个用来去掉行尾空白的正则，大致就是 \s+$，从这些空格中的每一个开始尝试匹配。每次尝试都一路跑到空白的尽头，发现后面还有文本而不是行尾，于是失败。这是平方级的工作量，大约 2 亿步，让网站宕机了 34 分钟。
Cloudflare，2019 年 7 月。一条新的防火墙规则里有一个包含 .*(?:.*=.*) 的正则。所有运行这条规则的服务器 CPU 都飙到 100%，Cloudflare 的网络在全球范围内丢弃流量约 27 分钟。
这两个正则乍一看都不危险，在正常输入上也都没问题。
04修复 1：让选择互斥
最干净的修复是写出每个字符只能用一种方式匹配的正则。去掉嵌套：
一个真实的例子：逗号分隔的数字。有风险的写法在另一个量词外面套了一个重复分组，还让逗号可有可无，于是一串数字可以有很多种拆法：
/^(\d+,?)+$/安全的写法要求元素之间必须有逗号，这样每个数字只属于唯一的位置：
05修复 2：写明不能出现什么
.* 常常是罪魁祸首，因为它什么都能匹配，包括下一部分需要的文本。否定字符类天生就是互斥的：
06修复 3：原子组和占有量词
原子组 (?>…) 只匹配一次，绝不吐回任何字符。占有量词（a++、\d*+）对单个量词做同样的事。两者都会去掉引擎原本要重试的那些备选路径。
Python 从 3.11 起两者都支持。Java、PCRE 和 PHP 也都有。JavaScript 两个都没有，但先行断言加反向引用的效果相当于原子组：(?=(a+))\1 一次性匹配这些 a，无法再拆分。
07修复 4：限制输入，或者换引擎
- 匹配前限制输入长度。很多会爆炸的正则在 200 个字符上是无害的。
- 对不可信的输入使用线性时间引擎。Google 的 RE2（有 Node、Python、Go 等语言的绑定）和 Rust 的
regexcrate 从不回溯，所以不会爆炸。代价是它们不支持反向引用和环视。 - 平台支持时设置超时。.NET 的
Regex可以传入matchTimeout。
08试一试
写出逗号分隔数字列表的安全版本：
抓住逗号分隔的数字，比如 1,22,333（没有空格，没有空项）。
目标 · 抓住 0/5
- 1目标
- 42目标
- 1,2目标
- 10,200,3000目标
- 7,7,7目标
无辜词 · 误抓 0
- ,1无辜
- 1,无辜
- 1,,2无辜
- a,b无辜
- 1, 2无辜
- ,无辜
输入正则——棋盘会实时更新。