2019年7月2日，保护着全球约20%互联网流量的Cloudflare遭遇了一次持续27分钟的全球性宕机。原因令人意外：一个正则表达式。

更准确地说，是这个正则表达式：

(?:(?:\"|'|\]|\}|\\|\d|(?:nan|infinity|true|false|null|undefined|symbol|math)|\`|\-|\+)+[)]*;?((?:\s|-|~|!|{}|\|\||\+)*.*(?:.*=.*)))

这个模式被用于WAF（Web应用防火墙）中检测XSS攻击。当它遇到特定的请求时，CPU利用率瞬间飙升到100%，全球各地的服务器相继瘫痪。这不是黑客攻击，没有恶意流量——仅仅是一个正则表达式在处理某个HTTP请求时触发了灾难性回溯。

这不是孤例。2016年，Stack Overflow因类似原因宕机34分钟。2024年9月，Express.js核心依赖path-to-regexp被披露存在ReDoS漏洞，影响数百万Node.js应用。

正则表达式是程序员工具箱中最常用的工具之一，但很少有人意识到它可能成为系统中最危险的攻击面。本文将深入分析正则表达式回溯灾难的技术本质，揭示为什么大多数主流语言的正则引擎都存在这个致命弱点，以及如何从根本上规避这一风险。

回溯：一个优雅但危险的算法

要理解问题，必须先理解正则表达式引擎是如何工作的。

现代编程语言中的正则引擎几乎都采用**回溯NFA（Nondeterministic Finite Automaton）**算法。NFA是一种非确定性有限状态自动机——听起来很学术，但核心思想很简单：当引擎遇到多种可能的匹配路径时，它会选择一条路径尝试，如果失败就"回溯"到上一个决策点，尝试其他路径。

考虑一个简单的例子：正则表达式 ^(a+)+$ 匹配由一个或多个a组成的字符串。看起来无害，对吧？

但当我们用这个表达式去匹配 aaaaaaaaaaaaaaaaaaaaX（20个a后面跟一个X）时，问题出现了。

表达式无法匹配（因为有X），但引擎不会立即给出结果。它需要穷尽所有可能的路径才能确定"无匹配"。让我们看看有多少种路径：

  • 外层的 + 表示整个组 (a+) 可以重复1次、2次、3次……
  • 内层的 + 表示每组中的 a 可以有1个、2个、3个……
  • 对于20个a，可能的分配方式数量是指数级的

具体计算：对于n个a，内层a+可能的取值组合数大约是2^n级别。当n=20时，需要尝试超过一百万次回溯；当n=30时，超过十亿次；当n=40时，计算时间超过宇宙年龄。

这不是夸张——这是算法复杂度理论的基本结论。

一个具体的回溯过程

让我们用更小的例子来演示。正则表达式 (x+x+)+y 匹配字符串 xxxxxxxxxxy：

  1. 第一个 x+ 匹配所有10个x
  2. 第二个 x+ 失败（没有剩余字符）
  3. 第一个 x+ 回溯到9个x
  4. 第二个 x+ 匹配剩余1个x
  5. 外层 + 尝试第二次重复，失败
  6. 匹配y成功

总共几十步，一切正常。

但如果字符串是 xxxxxxxxxxxx（没有y），引擎就会疯狂回溯：

  • 第一个x+从10→9→8→…→1，每次都要尝试内层x+的各种组合
  • 每次外层迭代失败，都要重新排列内层
  • 步数呈指数增长

实测数据：

字符串长度 回溯步数
10个x 2,557步
11个x 5,117步
12个x 10,237步
19个x 超过100万步

复杂度为O(2^n)，每增加一个字符，步数翻倍。

为什么主流语言都用了"错误"的算法？

既然回溯算法有如此严重的问题，为什么Java、Python、JavaScript、Perl、PHP、Ruby等所有主流语言都采用它？

答案在于一个关键的权衡：功能丰富度。

回溯引擎虽然最坏情况下是指数复杂度，但它支持一些非常方便的特性：

反向引用（Backreferences）：\1、\2等可以引用之前捕获组的内容。例如 (cat|dog)\1 匹配"catcat"或"dogdog"，但不匹配"catdog"。这在处理HTML标签匹配、引号配对等场景非常有用。

前瞻和后瞻（Lookaround）：(?=...)、(?!...)等可以检查某个位置后面/前面是否有特定模式，但不消耗字符。

原子组和占有量词：虽然这些特性可以用来防止回溯，但它们本身也需要回溯引擎的支持。

问题是：这些特性使得正则表达式不再是"正则"的——它们超越了正则语言的表达能力。理论上，真正的正则表达式都可以转换为DFA（确定性有限自动机），在线性时间内完成匹配。但反向引用等特性使得DFA转换不再可行。

Russ Cox在2007年的经典文章《Regular Expression Matching Can Be Simple And Fast》中指出：Perl的正则引擎处理一个29字符的字符串需要60秒，而Ken Thompson的NFA算法只需要20微秒——相差一百万倍。

1968年的解法：Thompson NFA

1968年，Ken Thompson在发表在CACM上的论文《Programming Techniques: Regular Expression Search Algorithm》中描述了一种方法：将正则表达式编译成NFA，然后用一种特殊的模拟方式执行，保证线性时间。

关键区别在于如何处理非确定性。

回溯方法：遇到分支时，选择一条路径尝试；失败则回退，尝试另一条。这需要保存大量的回溯状态。

Thompson方法：同时跟踪所有可能的状态。在每一步，引擎维护一个"当前可能处于的所有状态"的集合。读取下一个字符后，计算所有可能的新状态集合。

用一个简单的例子说明。正则表达式 abab|abbb 匹配字符串 abbb：

回溯方式：

  1. 尝试 abab 路径，在第三个字符失败
  2. 回溯，尝试 abbb 路径
  3. 成功

Thompson方式：

  1. 初始状态集：{开始状态, a分支起点, b分支起点}
  2. 读取’a’后：{状态2, 状态5}
  3. 读取’b’后：{状态3, 状态6}
  4. 读取’b’后：{状态4, 状态7}
  5. 读取’b’后：{匹配状态}

每一步只做常量工作，总时间是线性的。

Thompson方法的核心洞察：NFA虽然有多个可能的状态，但状态总数是固定的（等于正则表达式的长度）。因此在任意时刻，可能状态的集合大小是有界的。这消除了指数爆炸的可能。

为什么Thompson NFA不能完全替代回溯引擎？

Thompson NFA完美解决了性能问题，但它有一个根本限制：无法支持反向引用。

反向引用需要"记住"之前匹配的具体内容，这与NFA的状态转移语义不兼容。NFA只关心"我可能处于哪些状态"，而不关心"我是怎么到达这些状态的"。

这就是为什么大多数语言选择了回溯引擎：开发者需要反向引用等功能，而Thompson NFA无法提供。

Evil Regex：危险的代码模式

OWASP将可能导致ReDoS的正则表达式称为"Evil Regex"。它们通常具有以下特征：

  1. 分组嵌套重复：如 (a+)+、([a-z]+)*
  2. 分组内交替重叠：如 (a|aa)+、(a|a?)+
  3. 连续的贪婪通配符：如 .*.*=.*

典型示例：

(a+)+$              # 最经典的例子
([a-zA-Z]+)*$       # 邮箱验证中常见
(a|aa)+$            # 交替重叠
(a|a?)+$            # 可选字符造成重叠
.*.*=.*             # 连续贪婪通配

所有这些模式都有一个共同点：同一字符可以被多种方式"归属"到不同的子模式中。当匹配失败时，引擎必须尝试所有可能的归属方式。

真实世界中的Evil Regex

Cloudflare事件中的正则表达式简化后核心是 .*.*=.*。问题出在这一部分：

.*.*=.*/

三个连续的 .*。当匹配一个长字符串如 x=xxxxxxx...xxx 时：

  1. 第一个 .* 尝试匹配所有内容
  2. 第二个 .* 匹配空
  3. = 找不到匹配，回溯
  4. 第一个 .* 释放一个字符
  5. 第二个 .* 尝试匹配…
  6. 无限循环

Cloudflare的工程师在事后分析中计算：匹配 x=x 需要23步，匹配 x=xx 需要33步，匹配 x=xxxxxxxxxxxxxxxxxxxx（20个x）需要555步。而如果末尾再加一个分号变成 .*.*=.*;，匹配20个x需要5,353步——仍然是指数增长。

真实攻击案例

Cloudflare 2019年宕机

时间线（UTC）：

  • 13:42 - 工程师部署WAF规则更新，自动通过CI/CD测试
  • 13:45 - 第一个告警触发，显示WAF功能异常
  • 随后 - 大量502错误报告，全球CPU利用率飙升至100%
  • 14:00 - 确认WAF是问题源头
  • 14:07 - 执行全局WAF终止命令
  • 14:09 - 流量和CPU恢复正常

根本原因分析揭示了一个令人警醒的事实：

  1. 正则表达式由工程师手写，可以产生巨大回溯
  2. 几周前的一次重构意外移除了CPU使用率保护
  3. 正则引擎（Lua的PCRE）没有复杂度保证
  4. 测试套件没有检测CPU消耗异常
  5. SOP允许非紧急规则直接全球部署
  6. 回滚流程需要完整构建两次WAF，耗时过长

更重要的是，Cloudflare使用自己的产品。当服务宕机时，他们无法访问自己的控制面板——因为控制面板也托管在Cloudflare上。团队不得不使用很少训练过的绕过机制。

Stack Overflow 2016年宕机

2016年7月，Stack Overflow因一个格式错误的帖子触发了正则表达式回溯。帖子本身无害，但它包含了某种特殊字符序列，导致处理帖子的正则表达式进入无限回溯。

这次宕机持续了34分钟，暴露了一个有趣的问题：Python的GIL（全局解释器锁）阻止了一个线程中断另一个正在执行正则匹配的线程。即使有超时机制，也无法停止已经卡住的匹配操作。

path-to-regexp 2024年漏洞

2024年9月，Express.js的核心依赖path-to-regexp被披露存在ReDoS漏洞，分配编号CVE-2024-45296。

path-to-regexp是一个将路径字符串转换为正则表达式的库，广泛用于Express.js、Next.js等框架的路由系统。问题出在路径参数的处理上。

例如，路由 /flights/:from-:to 会生成正则表达式：

/^\/flights\/([^\/]+?)-([^\/]+?)\/?$/i

看起来正常？但如果我们匹配一个恶意构造的路径：/flights/ + 16000个- + /x

匹配时间超过300毫秒。正常的正则匹配应该在1毫秒内完成。

原因分析：当匹配失败时（因为有/x后缀），引擎必须尝试 :from 和 :to 参数之间所有可能的字符分配方式。第一个参数 ([^\/]+?) 可以匹配任意数量的 -，第二个参数也是。当有n个字符需要在两个参数之间分配时，有O(n)种方式；如果有更多参数，组合数会进一步增加。

修复方案很直接：在第二个参数中排除分隔符 -，改为 ([^\/-]+?)。匹配时间从300毫秒降到0.07毫秒。

语言实现对比：谁更安全？

不同编程语言对ReDoS的防护措施差异很大：

高风险：回溯引擎

Python (re模块)：标准实现使用回溯NFA。Python 3.11引入了占有量词和原子分组，可以手动防止回溯，但需要开发者主动使用。

# 危险
re.match(r'(a+)+$', 'aaaaaaaaaaaaaaaaaaaaX')

# 安全（Python 3.11+）
re.match(r'(a++)++$', 'aaaaaaaaaaaaaaaaaaaaX')  # 占有量词
re.match(r'(?>(a+)+)$', 'aaaaaaaaaaaaaaaaaaaaX')  # 原子分组

JavaScript：所有主流引擎（V8、SpiderMonkey、JavaScriptCore）都使用回溯NFA。不支持占有量词或原子分组。唯一的防护是手动限制输入长度或使用替代引擎。

// 危险
/(a+)+$/.test('aaaaaaaaaaaaaaaaaaaaX')

// 只能手动防护
function safeMatch(pattern, text, maxLength = 1000) {
    if (text.length > maxLength) return false;
    return pattern.test(text);
}

Java：java.util.regex使用回溯NFA。有趣的是，Java的接口设计实际上要求回溯实现，因为它允许在匹配路径中执行任意Java代码。

Perl/PCRE：作为回溯引擎的"鼻祖"，Perl 5.10之后的版本会在栈溢出时崩溃（而不是无限循环），但这只是把DoS变成了另一种DoS。

低风险：有限自动机引擎

Go (regexp包)：使用RE2语法，基于有限自动机，保证O(n)匹配时间。不支持反向引用。

// 安全 - 线性时间保证
regexp.MustCompile(`^(a+)+$`).MatchString("aaaaaaaaaaaaaaaaaaaaX")

Rust (regex crate)：同样使用有限自动机，保证线性时间。由BurntSushi（Andrew Gallant）开发，内部实现了多种策略的动态组合。

RE2 (C++)：Google开发的正则引擎，专门为安全而设计。它的设计哲学是：宁可不支持某些功能，也要保证性能可预测。

// RE2保证线性时间
RE2 pattern("(a+)+$");
RE2::FullMatch("aaaaaaaaaaaaaaaaaaaaX", pattern);  // O(n) 时间

混合策略

.NET：使用回溯引擎，但提供了RegexOptions.NonBacktracking选项（.NET 7+）可以在需要时切换到非回溯模式。

Node.js生态：可以通过第三方库如re2绑定Google RE2，获得线性时间保证。但需要显式选择使用。

防护策略

1. 使用占有量词和原子分组

如果语言支持，这是最直接的防护方式。

占有量词：a++、a*+、a?+

匹配后不释放已匹配的字符，阻止回溯。

// 危险
(a+)+$

// 安全
(a++)+$

原子分组：(?>pattern)

将整个组视为原子单位，一旦匹配完成，不再回溯进入组内。

// 危险
^(.*?,){11}P

// 安全
^(?>(.*?,){11})P

2. 避免嵌套量词

最安全的做法是完全避免在重复组内使用重复量词。

// 危险：嵌套量词
(x+x+)+y

// 安全：简化表达式
xx+y

3. 使用互斥替代

当必须使用交替时，确保各选项互斥——没有一个字符能被多个选项匹配。

// 危险：'a'可以被两个选项匹配
(a|aa)+

// 安全：选项互斥
(ab|aa)+

4. 限制输入长度

简单但有效的防御措施：

import re

def safe_match(pattern, text, max_length=1000):
    if len(text) > max_length:
        raise ValueError("Input too long")
    return re.match(pattern, text)

5. 使用安全引擎

对于处理不可信输入的场景，考虑使用RE2或Rust regex：

// Node.js + re2
const RE2 = require('re2');
const pattern = new RE2('(a+)+$');
pattern.test('aaaaaaaaaaaaaaaaaaaaX');  // 线性时间

6. 静态检测工具

一些工具可以自动检测Evil Regex：

  • safe-regex (JavaScript)
  • ReDoSHunter (研究工具)
  • SonarQube规则

但这些工具无法100%覆盖，仍需人工审查。

总结：理论、实践与权衡

正则表达式的回溯问题是一个完美的案例，展示了理论计算机科学如何指导工程实践。

Ken Thompson在1968年提出的算法保证了线性时间匹配。但几十年来，这个算法被主流语言抛弃，取而代之的是更容易实现、功能更丰富、但在某些情况下性能灾难性的回溯引擎。

这不是一个错误的决定——反向引用等功能对实际开发非常重要。问题是大多数开发者不知道这个权衡，不知道他们每天都在使用一个可能爆炸的工具。

安全使用正则表达式需要：

  1. 理解工具的本质：知道你使用的引擎是什么类型，有什么限制
  2. 审查关键模式：对处理用户输入的正则表达式进行专门审查
  3. 采用防御性编码：使用占有量词、原子分组、输入限制
  4. 考虑替代方案：在安全敏感场景，选择RE2、Rust regex等安全引擎

Cloudflare在事故后做了一系列改进：重新引入CPU保护、审查所有3868条WAF规则、将测试套件中加入性能分析、最终将引擎从PCRE迁移到Rust实现的RE2。

他们吸取了教训。你呢？

参考资料

  1. Cox, R. (2007). Regular Expression Matching Can Be Simple And Fast. https://swtch.com/~rsc/regexp/regexp1.html
  2. Thompson, K. (1968). Programming Techniques: Regular Expression Search Algorithm. CACM 11(6), 419-422.
  3. Cloudflare. (2019). Details of the Cloudflare outage on July 2, 2019. https://blog.cloudflare.com/details-of-the-cloudflare-outage-on-july-2-2019/
  4. OWASP. Regular expression Denial of Service - ReDoS. https://owasp.org/www-community/attacks/Regular_expression_Denial_of_Service_-_ReDoS
  5. Embrey, B. (2024). ReDoS the web. https://blakeembrey.com/posts/2024-09-web-redos/
  6. Gallant, A. (2023). Regex engine internals as a library. https://blog.burntsushi.net/regex-internals/
  7. Google. RE2: a fast, safe, thread-friendly alternative to backtracking regular expression engines. https://github.com/google/re2
  8. Goyvaerts, J. Runaway Regular Expressions: Catastrophic Backtracking. https://www.regular-expressions.info/catastrophic.html
  9. Li, Y. et al. (2021). ReDoSHunter: A Combined Static and Dynamic Approach for Regular Expression DoS Detection. USENIX Security.
  10. Davis, J. et al. (2018). The Impact of Regular Expression Denial of Service (ReDoS) in Practice. ESEC/FSE.