2019年7月2日，一个普通的周二下午，全球数十万网站突然无法访问。Cloudflare的全球服务中断了27分钟，受影响的网站包括Discord、Omegale、Buffer等知名服务。这不是黑客攻击，不是硬件故障，也不是配置错误。罪魁祸首是一行正则表达式。
更准确地说，是一个看起来无害的正则表达式片段：.*(?:.*=.*)。
这27分钟的技术调查揭示了一个困扰软件开发领域超过五十年的问题：正则表达式引擎的回溯灾难（ReDoS，Regular Expression Denial of Service）。这个问题曾在2016年让Stack Overflow瘫痪34分钟，影响过无数生产系统，至今仍是OWASP Top 10中不可忽视的安全风险。
一行代码的蝴蝶效应
Cloudflare的这次事故起源于一个看似平凡的变更。WAF（Web Application Firewall）团队的一名工程师正在更新XSS攻击检测规则。为了应对不断演进的Web安全威胁，Cloudflare的WAF规则平均每三小时就要更新一次。这次更新与其他数百次更新一样：代码审核通过，CI/CD流水线绿灯，测试套件全部通过。
问题出在那个正则表达式本身。
完整的正则表达式是这样的：
(?:(?:\"|'|\]|\}|\\|\d|(?:nan|infinity|true|false|null|undefined|symbol|math)|\`|\-|\+)+[)]*;?((?:\s|-|~|!|{}|\|\||\+)*.*(?:.*=.*)))
这个正则表达式用于检测XSS攻击模式，其设计目的是识别类似foo=bar这样的赋值表达式。问题出在核心部分.*(?:.*=.*)。当这个正则遇到特定结构的输入时，它不会立即匹配或失败，而是会尝试所有可能的匹配路径。
以最简单的例子来说明：假设输入是x=x，这个正则需要执行23次匹配操作。如果输入是x=xx，需要33步。x=xxx需要45步。x=xxxxxxxxxxxxxxxxxxxx（等号后20个x）需要555步。而如果输入只是20个x没有等号——完全匹配失败的场景——正则引擎需要执行惊人的4067步才能确认"匹配失败"。
这不是线性增长。这是超线性甚至指数级的复杂度爆炸。
gantt
title Cloudflare 2019年事故时间线
dateFormat HH:mm
axisFormat %H:%M
section 部署
代码合并到主分支 : 13:31, 6m
CI构建和测试通过 : 13:37, 5m
全球部署开始 : 13:42, 1m
section 故障
第一个警报触发 : milestone, 13:45, 0m
CPU全球飙升至100% : 13:45, 22m
工程师定位WAF问题 : 14:00, 2m
section 恢复
执行全局WAF终止 : 14:07, 2m
流量恢复正常 : 14:09, 43m
WAF重新启用 : 14:52, 0m
当Cloudflare的WAF遇到精心构造的恶意请求时，每个请求都会触发这种疯狂的回溯。由于正则引擎没有超时保护机制，CPU核心被完全占满。全球180多个数据中心的HTTP/HTTPS处理进程全部卡死。用户看到的是502 Bad Gateway，而Cloudflare的工程师看到的是CPU使用率飙升到100%的监控图表。
回溯：一个被误解了五十年的"特性"
要理解回溯灾难，需要先理解正则表达式引擎的工作方式。
1968年，Ken Thompson在Communications of the ACM上发表了一篇题为"Regular Expression Search Algorithm"的论文。这篇仅四页的文章介绍了将正则表达式转换为NFA（非确定性有限自动机）并在线性时间内完成匹配的算法。Thompson的方法优雅而高效：对于长度为n的输入字符串，匹配时间总是O(n)。
但大多数现代编程语言没有采用Thompson的方法。
Perl的出现改变了一切。Larry Wall在1987年设计Perl时，引入了许多方便的正则表达式扩展功能：反向引用、前瞻断言、非贪婪匹配等。这些扩展让正则表达式更加强大和易用，但也带来了一个代价——它们无法用传统的有限自动机实现。
为了支持这些高级特性，Perl使用了回溯算法。
回溯算法的基本思想是"尝试一切可能"。当正则引擎遇到一个可以匹配多种情况的结构时（比如.*可以匹配零个、一个、或多个字符），它会选择一条路径继续匹配。如果后续匹配失败，引擎会"回退"到选择点，尝试另一条路径。
这种"深度优先搜索"的策略在大多数情况下工作良好。但某些正则模式与某些输入的组合会触发指数级的路径探索。这就是回溯灾难的本质。
flowchart TB
subgraph 回溯引擎工作流程
A[开始匹配] --> B{当前字符匹配?}
B -->|是| C[前进到下一字符]
B -->|否| D{有其他选择?}
D -->|是| E[回退到选择点]
E --> B
D -->|否| F[匹配失败]
C --> G{还有字符?}
G -->|是| B
G -->|否| H[匹配成功]
end
style A fill:#e1f5fe
style H fill:#c8e6c9
style F fill:#ffcdd2
style E fill:#fff3e0
以.*.*=.*为例，三个.*意味着三个独立的"匹配零个或多个字符"的选择点。对于长度为n的输入，这三个选择点的组合数量是O(n³)级别。如果正则中存在更多嵌套的量词，复杂度会进一步指数化。
更糟糕的是，回溯引擎在匹配失败时比匹配成功时更慢。因为匹配成功意味着引擎可以提前终止，而匹配失败意味着必须探索所有可能的路径才能确认"确实无法匹配"。这就是为什么恶意攻击者通常会发送不匹配正则模式的输入——这样能让服务器付出最大的计算代价。
NFA与DFA：一场被遗忘的技术抉择
为什么大多数编程语言选择了回溯引擎？答案涉及历史、功能和性能的权衡。
DFA（确定性有限自动机）引擎的工作方式是"文本驱动"。它预先将正则表达式编译成一个状态机，然后对输入文本进行单次扫描。每个输入字符只触发一次状态转移，因此匹配时间严格线性于输入长度。
NFA（非确定性有限自动机）引擎的工作方式是"正则驱动"。它在匹配过程中可能同时处于多个状态，需要追踪所有可能的匹配路径。Thompson的算法巧妙地使用状态列表来模拟NFA，保持了线性时间复杂度。但为了支持反向引用等高级特性，许多实现放弃了这种做法，转而使用回溯。
flowchart LR
subgraph 正则表达式引擎分类
A[正则引擎] --> B[DFA引擎]
A --> C[NFA引擎]
C --> D[Thompson NFA<br/>线性时间]
C --> E[回溯NFA<br/>指数时间最坏情况]
end
B --> F[特点: 文本驱动<br/>O(n)时间保证<br/>不支持反向引用]
D --> G[特点: 正则驱动<br/>O(nm)时间保证<br/>有限高级特性]
E --> H[特点: 正则驱动<br/>支持所有高级特性<br/>最坏情况O(2^n)]
style B fill:#c8e6c9
style D fill:#fff9c4
style E fill:#ffcdd2
回溯NFA的优势在于功能强大。反向引用允许你匹配重复的文本（比如\1匹配第一个捕获组的内容），前瞻断言允许你在不消耗输入的情况下检查后续内容，非贪婪匹配允许你匹配"尽可能少"而不是"尽可能多"。这些特性在实际开发中非常实用，但它们无法用传统的有限自动机实现。
代价是性能的不确定性。一个回溯引擎在最坏情况下可能需要O(2ⁿ)的时间复杂度，其中n是输入长度。对于长输入，这会导致CPU被完全占满，系统响应变得极其缓慢。
Russ Cox在2007年发表的经典文章"Regular Expression Matching Can Be Simple And Fast"中，用图表展示了两种引擎的性能差异。对于同一个正则表达式(a?){n}a{n}，当n=29时，Perl需要超过60秒才能匹配成功，而使用Thompson NFA的实现只需要不到200微秒。这是30万倍的差距。
Cloudflare宕机事件的技术解剖
回到2019年的Cloudflare事故。事后分析揭示了多个防御层同时失效的过程。
flowchart TB
subgraph 防御层级失效分析
A[第一层: CPU保护机制] --> A1[重构时被移除]
B[第二层: 测试套件] --> B1[未测试性能边界]
C[第三层: 灰度发布] --> C1[WAF规则可直接全球发布]
D[第四层: 监控告警] --> D1[警报指向功能而非性能]
E[第五层: 快速恢复] --> E1[访问控制系统依赖自身服务]
end
A1 --> F[所有防线同时失效]
B1 --> F
C1 --> F
D1 --> F
E1 --> F
F --> G[全球服务中断27分钟]
style A fill:#ffcdd2
style B fill:#ffcdd2
style C fill:#ffcdd2
style D fill:#ffcdd2
style E fill:#ffcdd2
style G fill:#b71c1c,color:#fff
第一道防线应该是一个CPU使用率保护机制。在WAF的一次重构中，工程师移除了这个保护，目的是"让WAF使用更少CPU"。这个重构在测试中没有暴露问题，因为测试没有考虑到极端的CPU消耗场景。
第二道防线是测试套件。Cloudflare的WAF测试覆盖了数百种攻击模式和正常请求，确保规则不会误报或漏报。但测试没有测量每个规则的处理时间，一个正则可以在功能上完全正确，同时在性能上是灾难性的。
第三道防线是部署流程。通常软件更新会经过DOG（内部员工使用）、PIG（少量免费客户）、Canary（全球小范围测试）三个阶段的灰度发布。但WAF规则为了应对紧急威胁，被设计为可以直接全球发布。这个设计决策在紧急情况下很有价值，但也放大了一次错误的影响范围。
第四道防线是监控系统。第一个警报在部署三分钟后触发，但警报指向的是WAF功能测试失败，而不是CPU异常。工程师花了更多时间才定位到根本原因。
第五道防线是快速恢复能力。Cloudflare有一个"全局终止"机制可以一键禁用WAF。但由于Cloudflare自己的访问控制系统也依赖于Cloudflare服务，工程师们无法登录内部面板。他们不得不使用一个不常用的旁路机制才能执行恢复操作。
每一道防线的失效都有其合理性，但当它们同时失效时，系统就失去了最后的保护。
Stack Overflow 2016年的事故有着相似的模式。一个用于Markdown解析的正则表达式遇到了精心构造的输入，导致整个网站无法响应。那个正则表达式的问题同样是嵌套的量词导致的回溯爆炸。
回溯的数学本质：从组合爆炸到指数灾难
回溯灾难的数学本质是组合优化中的搜索空间爆炸。
考虑正则表达式(a+)+b。外层的+表示内层模式a+可以匹配一次或多次，内层的+表示a可以出现一次或多次。对于输入aaa...ac（n个a后面跟一个c），正则引擎需要尝试所有可能的分割方式：
a+aa...ac（第一组匹配1个a，剩余交给第二组）aa+a...ac（第一组匹配2个a，剩余交给第二组）aaa+...ac（第一组匹配3个a，剩余交给第二组）- …
每次第一组选择不同的a数量，第二组又会面临类似的选择。这个选择过程形成一棵决策树，树的深度与输入长度成正比，分支因子与正则中的量词数量成正比。
当最终发现无法匹配b时，引擎必须回溯，探索这棵树的每一个分支。分支数量是指数级的：对于n个a，可能的分割方式约为2ⁿ种。
graph TD
A[输入: aaaaac] --> B{第一组匹配?}
B -->|1个a| C[剩余: aaaac]
B -->|2个a| D[剩余: aaac]
B -->|3个a| E[剩余: aac]
B -->|4个a| F[剩余: ac]
C --> G{第二组匹配?}
D --> H{第二组匹配?}
E --> I{第二组匹配?}
F --> J{第二组匹配?}
G -->|继续...| K[...]
H -->|继续...| L[...]
I -->|继续...| M[...]
J -->|失败| N[c不匹配b]
K --> O[最终失败]
L --> O
M --> O
N --> O
这种组合爆炸不仅存在于正则表达式，也出现在许多其他计算问题中：SAT问题、旅行商问题、背包问题。这些问题共同的特点是：最坏情况下需要指数时间，但大多数实际输入不会触发最坏情况。
正则表达式的特殊之处在于，触发最坏情况的输入可以很容易地构造。攻击者只需要了解目标系统使用的正则模式，就能生成让服务器陷入死循环的输入。
xychart-beta
title "回溯步数随输入长度指数增长"
x-axis ["x=x", "x=xx", "x=xxx", "x=xxxx", "x=xxxxx", "x=xxxxxx"]
y-axis "匹配步数" 0 --> 500
bar [23, 33, 45, 59, 75, 93]
line [23, 33, 45, 59, 75, 93]
真实世界的回溯灾难
除了Cloudflare和Stack Overflow的著名案例，回溯灾难在软件开发历史上留下了许多伤痕。
2016年，一个正则表达式漏洞影响了多个JavaScript验证库，包括validator.js。用于验证电子邮件地址的正则表达式在某些输入下会触发严重回溯，导致Node.js的事件循环被阻塞。由于Node.js是单线程的，一个请求的阻塞会影响所有请求。
2020年，Python标准库urllib.request被发现存在ReDoS漏洞（CVE-2020-8492）。解析URL的正则表达式在处理特定格式的输入时会产生性能问题。这个漏洞影响广泛，因为urllib是Python的标准库，几乎所有Python Web应用都直接或间接使用它。
同一时期，Jinja2模板引擎也被发现存在ReDoS漏洞（CVE-2020-28393）。模板渲染过程中的一个正则表达式在特定输入下会导致服务拒绝。考虑到Jinja2是Flask等流行Web框架的默认模板引擎，这个漏洞的影响面同样广泛。
timeline
title ReDoS重大事件时间线
2016 : Stack Overflow宕机34分钟
: JavaScript验证库漏洞披露
2019 : Cloudflare全球服务中断27分钟
2020 : Python urllib CVE-2020-8492
: Jinja2 CVE-2020-28393
2024 : 持续有新CVE披露
研究显示，ReDoS是服务器端第四大常见的安全漏洞类型。一项对超过130,000个JavaScript项目的分析发现，约有10%的项目使用了可能触发回溯灾难的正则表达式。
更令人担忧的是，许多开发者不了解这个风险。正则表达式被视为"简单的文本匹配工具"，很少有人在代码审查时关注正则的性能特性。测试通常只覆盖功能性，不覆盖极端输入下的性能表现。
检测与防御：在效率与安全之间寻找平衡
防止回溯灾难需要多层次的防御策略。
flowchart TB
subgraph 防御策略选择
A[ReDoS防御策略] --> B{能否更换引擎?}
B -->|是| C[使用线性时间引擎<br/>RE2 / Rust regex]
B -->|否| D{能否设置超时?}
D -->|是| E[添加匹配超时保护]
D -->|否| F[依赖其他防御层]
F --> G[静态分析工具检测]
G --> H[输入验证与清洗]
H --> I[监控与告警]
end
C --> J[最彻底的解决方案]
E --> K[缓解措施<br/>需谨慎设置阈值]
I --> L[最后一道防线]
style C fill:#c8e6c9
style E fill:#fff9c4
style J fill:#2e7d32,color:#fff
使用线性时间引擎
最彻底的解决方案是使用保证线性时间复杂度的正则引擎。Google的RE2库和Rust的regex库是两个著名的例子。
RE2由Russ Cox设计，采用Thompson NFA算法，保证所有匹配操作在O(nm)时间内完成，其中n是输入长度，m是正则表达式长度。RE2不支持反向引用和某些高级特性，但对于大多数文本处理场景，这些特性并非必需。
Rust的regex库同样采用有限自动机方法，并且经过精心优化，在许多常见场景下甚至比RE2更快。它的设计哲学是"默认安全"：所有正则表达式都保证线性时间，不支持可能导致超线性复杂度的特性。
Cloudflare在2019年事故后迅速切换到了RE2引擎。这个决定意味着放弃一些高级特性，但换来了可预测的性能。
输入验证与超时保护
如果必须使用回溯引擎，设置匹配超时是必要的防护措施。.NET的正则引擎提供了RegexMatchTimeoutException，可以在指定时间内强制终止匹配。Java 9+也有类似的超时机制。
但超时只是缓解措施，不是根本解决方案。超时设置太短会误杀正常的复杂匹配，设置太长又无法有效防御攻击。而且，超时机制在多线程环境中可能引入竞态条件。
静态分析工具
多种静态分析工具可以检测潜在危险的.regex模式。regexploit、safe-regex等工具可以扫描代码库，识别可能导致回溯爆炸的正则表达式。
Semgrep和CodeQL等通用静态分析工具也提供了ReDoS检测规则。这些工具能识别常见的危险模式，如嵌套量词、重叠匹配等。
但静态分析有局限性。一个正则表达式是否危险，取决于输入数据的分布特征。某些正则在特定输入下安全，在其他输入下危险。静态分析无法预测运行时的输入特征。
正则表达式设计最佳实践
开发层面的防御包括：
-
避免嵌套量词：
(a+)+这种模式是回溯灾难的经典触发器。如果需要匹配重复字符，使用a*而不是(a+)*。 -
避免重叠匹配：
.*.*这样的模式中，两个.*可以匹配相同的字符，导致大量重复探索。如果需要匹配多个部分，使用更精确的模式。 -
优先使用非贪婪匹配：
.*?在某些情况下可以减少回溯，但不是万能解决方案。非贪婪匹配同样可能触发回溯爆炸。 -
锚定正则表达式：使用
^和$限制匹配范围，避免引擎尝试所有可能的起始位置。 -
简化正则表达式：复杂的正则往往是设计问题的信号。考虑将匹配逻辑拆分成多个简单的正则，或使用专门的解析器。
线性时间引擎的工作原理
Thompson NFA算法的核心思想是将正则表达式转换为一个可以同时处于多个状态的自动机。
传统NFA在任何时刻只处于一个状态，遇到分支选择时需要回溯。Thompson的方法是让自动机同时"记住"所有可能的状态。每当读取一个字符，引擎将当前所有状态并行转移到所有可能的新状态。
stateDiagram-v2
[*] --> S0
S0 --> S1: ε
S0 --> S2: ε
S1 --> S1: a
S2 --> S2: b
S1 --> S3: ε
S2 --> S3: ε
S3 --> [*]
note right of S0 : 初始状态同时进入S1和S2
note right of S3 : 任一路径到达即成功
这种方法的空间复杂度是O(m)，其中m是正则表达式的长度。时间复杂度是O(nm)，其中n是输入长度。无论正则表达式多么复杂，无论输入构造得多么恶意，时间始终是可预测的线性关系。
flowchart LR
subgraph Thompson NFA执行过程
A[初始: 状态集={S0}] --> B[读取字符a]
B --> C[状态集={S1,S2}]
C --> D[读取字符b]
D --> E[状态集={S1,S2,S3}]
E --> F{S3在接受集中?}
F -->|是| G[匹配成功]
F -->|否| H[继续处理]
end
style G fill:#c8e6c9
为什么这种算法没有成为主流？功能限制是主要原因。Thompson NFA无法支持反向引用，因为反向引用需要"记住"之前的匹配内容，这与自动机的无状态特性冲突。前瞻断言同样难以实现，因为它需要在不消耗输入的情况下检查未来内容。
但反思一下，这些高级特性真的必不可少吗？大多数正则表达式用于简单的模式匹配——验证邮箱格式、提取日期、分割字符串。这些任务不需要反向引用。对于确实需要复杂解析的场景，使用专门的解析器往往是更好的选择。
从历史中学习
正则表达式的历史可以追溯到1956年，数学家Stephen Kleene提出了正则语言的概念，用于描述神经网络的激活模式。十年后，Ken Thompson将这一理论付诸实践，在QED文本编辑器中实现了第一个正则表达式搜索工具。
Thompson的实现是高效的，但也是简陋的。它只支持最基本的正则特性：字符匹配、连接、选择（|）、重复（*）。没有捕获组，没有反向引用，没有前瞻断言。
timeline
title 正则表达式技术演进史
1956 : Kleene提出正则语言理论
1968 : Thompson实现第一个高效算法
1987 : Perl引入回溯引擎和高级特性
2007 : Cox发文揭示性能问题
2010 : Google开源RE2
2015 : Rust regex发布
2019 : Cloudflare事故引发关注
1987年，Perl的出现改变了正则表达式的命运。Larry Wall将正则表达式深度集成到语言中，引入了大量方便但实现复杂的新特性。其他语言纷纷效仿，正则表达式成为了程序员的标准工具。
但Perl的实现选择了回溯算法，这个技术决策影响了此后三十多年的编程语言生态。JavaScript、Python、Ruby、Java——几乎所有主流语言的正则引擎都是回溯型的。性能问题被当作"罕见边界情况"忽视，直到生产事故将其推到聚光灯下。
2007年，Russ Cox发表了"Regular Expression Matching Can Be Simple And Fast"，详细解释了Thompson算法的原理，并批评了回溯引擎的设计选择。这篇文章在编程社区引发了广泛讨论，但改变语言的默认正则引擎是一个巨大的工程决策，需要权衡兼容性、功能和性能。
2010年，Google开源了RE2。这个库证明了高效正则引擎可以在生产环境中使用，尽管需要放弃一些高级特性。RE2被广泛用于安全敏感场景，如Cloudflare的WAF、各种输入验证系统。
近年来，新语言做出了不同的选择。Rust的regex库从一开始就设计为线性时间实现。Go标准库的regexp包使用RE2语法。这些语言从历史中学到了教训。
未完的故事
回溯灾难的故事没有完美结局。
旧语言无法轻易改变默认正则引擎，因为有数百万行现有代码依赖反向引用等特性。JavaScript、Python、Java的用户不得不在方便与安全之间做出选择。
新语言和新库正在推动变化，但迁移需要时间。RE2和Rust regex的优秀表现展示了"正确设计"的价值，但许多开发者仍然不了解这些替代方案。
云服务提供商开始关注这个问题。Cloudflare、Akamai等公司在安全产品中采用了线性时间引擎，但应用代码层面的问题仍然存在。
安全社区将ReDoS列为需要关注的风险，但它在知名度上仍不及SQL注入、XSS等更"直观"的漏洞。一个正则表达式的性能问题容易被忽视，直到它造成实际损害。
1968年，Ken Thompson用四页论文展示了正则匹配可以简单而快速。五十七年过去了，我们仍然在为他人的"简单"选择付出代价。也许真正的教训是：在系统设计中，性能不是可以事后优化的次要属性，而是与正确性同等重要的核心约束。
当一行代码可以让全球互联网瘫痪27分钟时，我们看到的不是一个简单的bug，而是一个技术选择在几十年间累积的系统性风险。回溯灾难提醒我们：便利性常常有隐藏的成本，而某些成本，只有在系统崩溃的那一刻才会显现。
参考文献
-
Thompson, K. (1968). Regular expression search algorithm. Communications of the ACM, 11(6), 419-422.
-
Cox, R. (2007). Regular Expression Matching Can Be Simple And Fast. https://swtch.com/~rsc/regexp/regexp1.html
-
Cloudflare. (2019). Details of the Cloudflare outage on July 2, 2019. https://blog.cloudflare.com/details-of-the-cloudflare-outage-on-july-2-2019/
-
Davis, J., Coghlan, C., Servant, F., & Lee, D. (2018). The Impact of Regular Expression Denial of Service (ReDoS) in Practice. ESEC/FSE 2018.
-
Weideman, N., van der Merwe, B., van der Merwe, M., & Visser, W. (2024). SoK: Demystifying Regular Expression Denial of Service. IEEE Symposium on Security and Privacy.
-
Laurikari, V. (2000). NFAs with Tagged Transitions, their Conversion to Deterministic Automata and Application to Regular Expressions. SPIRE 2000.
-
Rabin, M. O., & Scott, D. (1959). Finite automata and their decision problems. IBM Journal of Research and Development, 3(2), 114-125.
-
OWASP. (2023). Regular Expression Denial of Service. OWASP Cheat Sheet Series.
-
Snyk. (2017). Regular Expression Denial of Service (ReDoS) and Catastrophic Backtracking. https://snyk.io/blog/redos-and-catastrophic-backtracking/
-
Google. (2010). RE2: an efficient, principled regular expression library. https://github.com/google/re2
-
Rust regex crate documentation. https://docs.rs/regex/latest/regex/
-
CVE-2020-8492. Python urllib.request ReDoS vulnerability. NIST National Vulnerability Database.
-
CVE-2020-28393. Jinja2 ReDoS vulnerability. NIST National Vulnerability Database.
-
Stack Overflow Meta. (2016). Why does Stack Overflow use a backtracking regex implementation? https://meta.stackoverflow.com/questions/328376/
-
Davis, J. (2020). On the Impact and Defeat of Regular Expression Denial of Service. Virginia Tech Dissertation.