regex 总览待审核
catastrophic backtracking · ReDoS

灾难性回溯:一条正则如何耗尽 CPU

有些正则在匹配失败时会卡死——不是写错了,而是回溯引擎要尝试指数级的组合。 典型成因是嵌套量词((a+)+、(a|a)*):同一段文本能被拆成无数种方式, 一旦末尾对不上,引擎就把每一种拆法都试一遍。下面实测它每加一个字符、步数翻一倍—— 这就是 ReDoS(Regular-expression Denial of Service)的根。

为什么会指数爆炸? 拿 (a+)+b 去匹配 "aaaa…a"(没有结尾的 b)。 外层 + 要把这串 a 切成若干段、每段交给内层 a+——n 个 a 有 2n-1 种切法。因为整串注定匹配不上(缺 b),引擎被迫把所有切法都尝试一遍, 于是步数 ≈ 2n。
24 输入 = "a"×n(故意不放结尾字符 → 匹配失败 → 触发全回溯)

回溯步数随 n 增长(纵轴对数刻度;红 = 超出预算上限)

同一条 regex,换成线性引擎的表现

上面那条爆炸曲线是回溯引擎的病。基于 NFA/DFA 的线性引擎(本仓库的 Pike VM、Google RE2) 同时跟踪「所有可能状态」,从不回溯,所以同一条 (a+)+b 是 O(n)——根本不存在指数爆炸。 点下面用本仓库 @vega/parsing 的两条真引擎实测耗时对比(回溯故意强制开启)。

回溯一栏到 n≈22 就要数百 ms、再大直接卡死——这正是为什么默认引擎 auto 会自动躲开它选 Pike。

点上面按钮开跑。

如何避免? 前三种思路都是「消除歧义、不给引擎回溯的余地」:
其一,精确化、消歧义:(.*?,){11} → ([^,\r\n]*,){11},去掉嵌套量词的重叠区。
其二,原子组 (?>…):整组匹配完就「提交」,绝不回溯进去。
其三,占有量词 a*+ / a++:吃掉就不吐。
根本解决:换线性引擎(RE2 / Pike VM)。Cloudflare 2019 年那次全球宕机,正是一条 .*.*=.* 类的正则在 WAF 里灾难性回溯占满 CPU——后来迁到了 RE2。 原生 JS 也能就地换引擎。 上面的换线性引擎在本仓库是 { engine: 'pike' };在浏览器 / Node 的原生 RegExp 上,V8 也内置了一个非回溯的线性引擎,用实验性的 l flag 开启 (/(a+)+$/l,l = linear)。但它至今默认关闭、需启动时带 --enable-experimental-regexp-engine,且和 RE2 一样不支持 lookaround / 反向引用 ——思路与权衡都跟本仓库 engine:'pike' 一模一样。Safari 的 JSC 则是另一路:回溯超过约一百万次就直接返回 false(快,但结果可能是错的)。

🔗 相关链接