正则表达式回溯导致性能灾难时如何通过重写为确定性有限自动机消除指数级时间复杂度的实践

一、一次线上“卡死”引发的调查

事情发生在一个平平无奇的下午。我的一个后端服务突然大面积超时，监控面板上CPU使用率直接冲到了100%。第一反应是查日志，发现某个接口的请求量并不大，但每个请求都像被什么东西卡住了一样，迟迟不返回。最后通过性能剖析工具定位到，罪魁祸首是一行正则表达式。

那行正则长这样：

// 技术栈：JavaScript（Node.js）
// 一个用来校验“字符串是否由若干个a分组构成”的正则表达式
const regex = /^(a+)+$/;

这个正则本身是为了检查输入是否只包含字母 a，并且至少有一个。看起来人畜无害，可一旦输入是“一连串的a在结尾追加一个b”，比如 aaaaaaaaaaaaaaaaaaaaab，正则引擎就开始疯狂地尝试各种分组方式，耗时随着 a 的数量增加呈指数级上涨。从最初的几十毫秒，到几十秒，再到几分钟，最后直接把服务拖垮。

这种问题在安全领域有个专门的名字，叫“正则表达式拒绝服务攻击”，英文缩写是 ReDoS。很多知名公司都栽在过类似的正则上。今天我就用最通俗的语言，把这件事从头到尾讲清楚，并且告诉大家怎么用“确定性有限自动机”这种硬核又朴素的思路，把性能灾难彻底消灭掉。

二、回溯到底是怎么“爆炸”的

要理解灾难，得先理解回溯。

正则表达式匹配字符串时，引擎会尝试各种可能的路径。比如用 /a*b/ 去匹配 aaaaac，因为 * 是贪婪的，它会先吃掉所有的 a，然后发现下一个字符是 c，不对。于是引擎会退回一格，让出一个 a，再看下一个是不是 b，还不是，再退回一格……这样一直退到字符串开头，最后发现所有排列都不行，匹配失败。这个过程就是“回溯”。

单纯的 a* 回溯次数是线性的，字符串多长就退多少次，问题不大。但一旦规则出现了“嵌套”，麻烦就来了。

(a+)+$ 是什么意思呢？外层括号里的 a+ 表示“至少一个a”，后面再跟一个 +，表示“这个分组可以重复一次或多次”。也就是说，这个正则允许我们把字符串里的a拆分成一组一组。比如“aaaa”，它可以拆成 (a)(a)(a)(a)，也可以拆成 (aa)(aa)，还可以拆成 (aaa)(a)，等等。拆法的数量是惊人的。对于长度为 n 的a串，理论上拆法数量接近 2^(n-1)。

当字符串末尾有一个 b 的时候，正则引擎必须先尝试所有拆法，确定哪一种都匹配不到最后的 $，才肯罢休。于是 2^(n-1) 种拆法全部试一遍。n 是 30 的时候，就是 5 亿多种；n 是 50 的时候，你算算有多少。这就是指数级时间复杂度的来源。

你可以把这种嵌套量词想象成你站在一个迷宫门口，迷宫里面有无数个岔路口，而每个岔路口又分叉成无数个更小的岔路。你要想证明“此路不通”，就得把所有分岔路都走完。字符串稍微长一点，宇宙都等不起你。

三、跑个实验，亲眼看看指数增长

光说不够，咱们直接敲代码验证。用 Node.js 写一个简单的性能测试脚本，分别测试不同长度的输入，看看耗时怎么变化。

// 技术栈：JavaScript（Node.js 18）
// 引入Node.js内置的性能计时模块
const { performance } = require('perf_hooks');

// 这就是那个经典的“灾难正则”
const evilRegex = /^(a+)+$/;

// 构造测试输入：n个a后面加一个b
// 因为b的存在，匹配一定失败
function buildBadInput(n) {
  return 'a'.repeat(n) + 'b';
}

console.log('开始测试正则回溯灾难...');

// 从10个a开始，每次增加5个a
for (let n = 10; n <= 30; n += 5) {
  const input = buildBadInput(n);

  const start = performance.now();        // 记录匹配开始时间
  const matched = evilRegex.test(input);  // 执行正则匹配
  const end = performance.now();          // 记录匹配结束时间

  // 打印结果
  console.log(`a的个数: ${n}, 匹配结果: ${matched}, 耗时: ${(end - start).toFixed(2)} 毫秒`);
}

你实际跑的时候，可能因为电脑性能不同而有所差异，但趋势一定是这样：

a的个数: 10, 匹配结果: false, 耗时: 0.06 毫秒
a的个数: 15, 匹配结果: false, 耗时: 0.35 毫秒
a的个数: 20, 匹配结果: false, 耗时: 18.22 毫秒
a的个数: 25, 匹配结果: false, 耗时: 620.48 毫秒
a的个数: 30, 匹配结果: false, 耗时: 14320.16 毫秒

看清楚，从 20 个a到 30 个a，只多了 10 个字符，耗时却从 18 毫秒飙到 14 秒。如果再往后加几个a，直接就是十几分钟、几小时。这不是什么性能抖动，这是彻底炸了。

很多程序员平时不会在意这种写法，毕竟在测试用例里输入都很短，根本看不出问题。一旦放到生产环境，用户传入一个几百字节的恶意字符串，服务就废了。

四、NFA和DFA：两条完全不同的路

要解决这个问题，我们得先搞懂背后两种自动机的区别。

NFA（非确定性有限自动机）的特点是，在同一个状态下，读取同一个字符，可能有好几个“下一状态”可选。正则引擎为了模拟这种多分支，只能一条路一条路地试。试错了就回头换一条，这就是回溯。绝大多数编程语言的正则库核心都是NFA，比如 JavaScript、Python、Java、PHP 等等。

DFA（确定性有限自动机）就不一样了。它要求在任何时刻，读取一个字符之后，下一个状态是唯一的。没有选择，没有分支，当然也就不需要回溯。处理一个长度为 n 的字符串，它只需要把每个字符读一遍，做 n 次状态转移，时间永远是线性的。

用生活化的比喻来说：NFA 像一个开着导航却总在路口犹犹豫豫的司机，走错了还要倒回去重新选路。DFA 则像是已经铺好的铁轨，火车沿着轨道一路飞驰，不管前面有多少条岔路被提前焊死了，永远不必回头。

那么问题来了：我们能不能把正则表达式直接转换成DFA？理论上是完全可以的。编译原理课本里都讲过正则表达式到NFA再到DFA的转换算法。但实际工程里的正则表达式远不止“a、b、括号、星号”这些基础元字符，还有反向引用、环视、贪婪与懒惰匹配等高级特性。这些特性大多无法用DFA来表达。所以语言实现者们干脆选择了回溯方案，好用但危险。

如果我们只处理一个足够简单的正则，比如 (a+)+$，那完全可以自己动手写一个DFA来替换它。性能立刻变得极其稳定。

五、把那个坑爹正则改成DFA

现在开始实战。先别急着写代码，我们思考一下：(a+)+$ 想表达的数学语言到底是什么？

稍微分析一下就能看出来：它要匹配的是“由一个或多个a组成的字符串”，而且要求从头到尾全是a，至少一个。至于怎么分组，那些分组其实都不影响最终结果——反正都是a。所以一个最朴素的优化是直接把它改写成 /^a+$/。这个改法简单有效，在JavaScript里也能跑。

但今天我们要展示的是“确定性有限自动机”的思路，所以我不偷懒，手动建一个真正的DFA出来。

5.1 设计状态

这个DFA只需要三个状态：

• 状态0：初始状态，还没读过任何字符。
• 状态1：接受状态，表示已经读过了至少一个a，并且到目前为止都合法。
• 状态2：陷阱状态，表示已经遇到了不合法字符，永远无法翻身。

状态转移规则也很简单：

• 从状态0读到 a，进入状态1。
• 从状态0读到非 a，进入状态2。
• 从状态1读到 a，继续留在状态1。
• 从状态1读到非 a，进入状态2。
• 状态2读到什么字符，都留在状态2。

如果处理完整个字符串后，我们停在状态1，那就说明匹配成功。否则失败。

5.2 用JavaScript实现DFA

下面是完整的实现，包含详细注释，方便你照着理解：

// 技术栈：JavaScript（Node.js 18）
// 手写一个DFA，用来替代灾难正则 /^(a+)+$/
function isAllA(input) {
  // 定义状态常量，用数字表示，可读性更强
  const START = 0;   // 初始状态
  const ACCEPT = 1;  // 接受状态
  const TRAP = 2;    // 陷阱状态

  // 一开始处于初始状态
  let state = START;

  // 逐个字符处理，每个字符只处理一次
  for (let i = 0; i < input.length; i++) {
    const ch = input[i]; // 拿到当前字符

    if (state === START) {
      // 初始状态下，只能接受字符'a'
      if (ch === 'a') {
        state = ACCEPT;
      } else {
        state = TRAP; // 第一个字符就不是a，直接失败
      }
    } else if (state === ACCEPT) {
      // 接受状态下，遇到a就继续留在接受状态
      if (ch === 'a') {
        // 状态保持不变
        state = ACCEPT;
      } else {
        // 遇到非a，进入陷阱
        state = TRAP;
      }
    } else {
      // 陷阱状态，不管来什么字符都保持陷阱
      state = TRAP;
    }
  }

  // 只有最终状态是ACCEPT，才算匹配成功
  return state === ACCEPT;
}

// 引入性能计时模块来对比结果
const { performance } = require('perf_hooks');

// 测试函数：生成n个a加一个b的输入
function makeBadInput(n) {
  return 'a'.repeat(n) + 'b';
}

console.log('开始测试手写DFA...');

// 即使n很大，耗时也几乎为零
for (let n = 10; n <= 100; n += 30) {
  const input = makeBadInput(n);
  const start = performance.now();   // 开始时间
  const result = isAllA(input);      // 执行DFA，结果一定是false
  const end = performance.now();     // 结束时间

  // 把耗时换算成微秒，更能看出微小的变化
  const costMicro = (end - start) * 1000;
  console.log(`输入长度: ${n}, 匹配结果: ${result}, DFA耗时: ${costMicro.toFixed(3)} 微秒`);
}

这段代码的时间复杂度是 O(n)，空间复杂度是 O(1)。输入一万个字符，也只需要循环一万次。没有回溯，没有指数爆炸，一切尽在掌控之中。

也许有读者会说：“这跟直接写 ^a+$ 有什么没区别？” 本质上等价，但DFA的意义在于：当你的表达式复杂到不能简单改写，自己设计状态机反而是一个可控的选择。你可以把每个状态都画出来，测试用例覆盖每一条转移边，心里特别踏实。

六、工程上的一些安全替代方案

有人可能会问：难道每次遇到危险正则，都要手写状态机吗？那太累了。确实，所以工程上也有现成的库可以帮我们。

比如 Node.js 的第三方包 re2，它的底层就是一个基于DFA思想的线性时间正则引擎。使用起来跟原生正则几乎一样，但它不会因为回溯而爆炸。要安装它，只需要在你项目目录下执行：

# 技术栈：Node.js 包管理器
# 安装 re2 库
npm install re2

不过 re2 不支持反向引用（比如 \1）和一些环视断言（lookaround）。所以在替换之前，你需要先确认业务正则里没有用到这些特性。如果用了，就得换方案。

另外一个思路是使用支持“原子组”的正则引擎。原子组 (?>...) 会扔掉所有备选状态，匹配一旦成功就不再回溯。比如在 PCRE、Java、Python 的 regex 模块里，可以把 (a+)+$ 写成 ^(?>a+)+$。但 JavaScript 原生不支持原子组，所以这条路在纯前端和后端Node环境里走不通。

手写DFA看着原始，反而是最通用的降维打击方式。

七、五个能救命的写正则习惯

除了遇到问题再补救，更重要的是平时写正则时避开雷区。这里分享五个我非常受用的习惯。

第一，绝不写嵌套量词。像 (a+)+、(\w*\d*)*、(a|aa)* 这种形式，尽量避开。如果非写不可，就用原子组或者DFA。

第二，坚持“最小匹配原则”。能用字符类 [a-z] 就不要用括号+量词。括号会引入分组，分组会产生额外分支。^[a-z]+$ 永远比 ^([a-z]+)+$ 安全。

第三，给正则加上“锚定”。如果业务允许，在正则开头加上 ^，结尾加上 $。这样可以告诉引擎匹配的边界，减少很多无谓的试探。

第四，限制输入长度。很多 ReDoS 攻击只有在输入足够长的时候才能造成伤害。如果你的业务逻辑允许，把用户输入长度限制在 100 个字符以内，就算正则有点小坑，爆炸威力也有限。

第五，给正则写性能测试。把那些“失败匹配”的用例加入自动化测试，比如 aaaaaaaaab 这种结构。如果将来有人改正则改出了隐患，CI 一跑就能发现。我们这次线上事故就是因为缺少这种防线。

八、应用场景和注意事项

那手写DFA最适合用在哪里呢？我总结几个典型场景：

1. 用户输入要经过复杂正则校验，而且有被恶意攻击的风险。
2. 正则表达式里嵌套量词无法重构，现有引擎又不支持原子组。
3. 接口对真实耗时有严格限制，哪怕是几十毫秒的抖动都不能接受。
4. 团队希望把关键校验逻辑做得可测试、可审查。DFA状态一目了然，比天书一样的正则强多了。

这个方法也有自己的优缺点。

优点是性能稳如磐石，无论输入多长，耗时线性增长；状态转移逻辑几乎没有歧义，代码很容易写单元测试；也完全消除了 ReDoS 威胁。

缺点是状态机的表达能力有限。正则表达式里的捕获组、反向引用、前瞻断言、贪婪与非贪婪模式，这些高级特性的语义用DFA很难全部保留。并且状态多了之后，画图、维护、扩展都变得麻烦，代码量往往比一行正则大得多。

所以我的建议是：优先尝试简化正则，改不了再用DFA。不要把DFA当成万能药，它适合解决“特定场景下的特定危险正则”。如果业务正则特别复杂，还是考虑成熟的正则库比如 re2，或者干脆换一种验证方案，比如逐字符解析，本质上也是一个手写的DFA。

另外要记得，写DFA时状态命名别用魔法数字。像代码里的 START、ACCEPT、TRAP 这种常量就让可读性提高了一个档次。还有，处理输入时可以考虑提前终止：一旦进入陷阱状态，就可以直接 break 出来，没必要继续读后面的字符。上面的代码为了展示完整没有提前退出，实际工程中可以加上这个优化。

九、总结

一次线上事故教会我：正则表达式不是银弹。它强大、简洁，但背后隐藏着回溯的无底洞。(a+)+$ 这种看起来微不足道的写法，可以在一瞬间耗尽整个CPU。

通过把危险的正则重写成确定性有限自动机，我们获得了完全可控的线性时间匹配。没有回溯的取舍，没有状态爆炸的焦虑，只有老老实实地逐个字符读一遍，稳稳地得出结论。虽然状态机不能取代所有正则功能，但在那些“高性能、高安全、低复杂度”的校验场景里，它是一个值得信赖的伙伴。

希望这篇文章能帮你避开正则回溯的坑。下次再碰到莫名卡死的接口，别急着重启，先低头看看你的正则有没有偷偷在“拆a组”吧。