# 它不逐字扫：一行正则也能挂死服务器 ## 导语：你以为的正则，可能只是它的"皮" 写代码的人几乎没有不碰正则的。一段 `/ab*c/`，或者更花哨的邮箱、手机号校验，往代码里一贴，好像就解决了字符串匹配问题。但绝大多数人对正则的理解，停留在"一种神奇的模式语法"——它从哪来、按下回车后引擎到底做了什么、为什么同样的写法有时候飞快、有时候却把 CPU 直接打满，很少有人追究。 Computerphile 频道里 Prof. Brailsford 那期《Regular Expressions》之所以值得看，恰恰在于它把正则从"工具语法"拉回了它的本源：一门有 70 年历史的形式语言。顺着这条线往下挖，你会发现一个被很多教程跳过的关键事实——**正则不是被"逐字符扫描"匹配的，它先被编译成一台状态机**。而正是这台状态机"怎么跑"，决定了你的正则是秒回，还是把整台服务器拖进指数级的深渊。2019 年 Cloudflare 那场波及半个互联网、持续约 27 分钟的全球级宕机，肇事的就是一行完全合法、谁也看不出毛病的正则。这篇文章就借这期视频，把正则引擎从"编译"到"爆炸"的完整链路拆给你看。 ## 视频背景卡片 | 项目 | 内容 | |------|------| | 视频标题 | Regular Expressions（正则表达式） | | 频道 | Computerphile（诺丁汉大学出品的计算机科学频道，订阅数百万） | | 主讲 | Prof. David Brailsford（形式语言与文档检索方向学者） | | 时长 | 约 14 分钟 | | 播放量 | 约 27 万（截至检索时） | | 核心主题 | 正则表达式的语法起源，以及它和形式语言、有限自动机的内在联系 | ## 核心内容拆解 ### 1. 正则的本来面目：一门诞生于 1956 年的数学语言 很多人以为正则是程序员为了方便发明的"模式字符串"，其实它是一门正儿八经的数学语言。1956 年，美国数学家 Stephen Cole Kleene 发表论文《Representation of Events in Nerve Nets and Finite Automata》，用"正则集合（regular sets）"来描述有限自动机能够识别的事件类。你现在天天敲的那个 `*`（匹配零次或多次），名字就叫 **Kleene star**，正是以他命名。 所以在数学上，你写的每一行正则，本质上都是在描述一个**正则语言（regular language）**——一类能被有限状态机识别的字符串集合。在 Chomsky 文法层级里，它处于最底层的 Type-3，表达能力最弱，但也正因为弱，它才有"线性时间可判定"这种珍贵性质。Computerphile 这期视频最有价值的点，就是 Brailsford 没有把正则当成一组需要背诵的符号，而是从这条理论根基讲起，让你明白：正则不是魔法，而是一套被严格定义的语言。这一节是**视频原话层面的核心立意**。 ### 2. 模式不是模式：它被编译成一台状态机 理解了正则是一门语言，下一个关键认知就水到渠成：当你写 `/ab*c/`，引擎**不是用肉眼去字符串里逐个字符找**。它在匹配开始之前，会先做一次"编译"——把你写的文本模式，翻译成一台**有限自动机（finite automaton）**，也就是一组状态和带条件的转移边。 这个"编译"思想的源头同样赫赫有名。1968 年，Unix 共同发明人、图灵奖得主、后来又设计了 Go 语言的 **Ken Thompson**，在《Communications of the ACM》上发表了正则搜索算法，给出第一套把正则高效编译成 NFA（非确定性有限自动机）并在文本里搜索的方案。这就是所谓的 **Thompson 构造法（Thompson construction）**，他当时把它用进了 QED 文本编辑器——后来的 grep、sed、vi 里的正则，全是这条血脉的后代。 > 这一条延伸出一个非常实用的工程结论：正则存在"编译成本"。当你在一个循环里反复使用同一段正则时，应该**预编译**它——Python 的 `re.compile()`、Java 的 `Pattern.compile()` 都是这个道理。**（本段为延伸分析，非视频原话）** ### 3. NFA 与 DFA：通往"线性时间"的两条路 编译出来的 NFA 有个特点：它在某个时刻可能"同时"处在好几个状态里（非确定性）。要在一段文本上真正跑起来，工程上有两条都能保证基本线性的路： - **Thompson 模拟法**：每读入一个字符，就同步推进"所有当前可能状态"的集合。因为状态总数有上限，整个过程耗时约 O(n·m)（n 为文本长度，m 为模式长度），相对文本几乎线性。 - **子集构造（subset construction）**：把 NFA 进一步转成 DFA（确定性有限自动机），任何时刻只处于一个状态，匹配变成纯粹的 O(n)。代价是 DFA 的状态数在最坏情况下会指数膨胀（最坏 2^m），但一旦构造好，匹配极快。 Russ Cox 在 2007 年那篇被奉为经典的《Regular Expression Matching Can Be Simple And Fast》里，实测对比了 Thompson NFA 引擎和当时主流的回溯引擎：前者面对再复杂的模式、再长的文本，耗时曲线都是一条平缓的直线；后者却画出一条陡峭得吓人的指数曲线。这恰恰是问题的分水岭——**正则本来是可以很快的**。 ### 4. 回溯：大多数引擎"抄的近路"埋下了雷 既然线性时间这么好，为什么不是所有引擎都用自动机？因为另一条路——**回溯（backtracking）**——实现起来简单得多，而且能做线性自动机做不到的事：**反向引用（backreferences，如 `\1`）、前后查找（lookahead / lookbehind）、捕获组**这些高级特性。 回溯的工作方式像走迷宫：遇到一个有多条岔路的状态，先走一条，走不通就**退回来**换另一条试。在简单的模式上，它和自动机几乎一样快。但麻烦出在**嵌套量词**上。当你写出 `(a+)+`、`(a*)*` 这类结构，再喂给它一长串 `aaaaaa...`（结尾恰好缺少该有的字符），引擎会去尝试 2ⁿ 种"这些 a 到底怎么分配给内外两层量词"的组合，而几乎所有组合最终都会失败。 于是本该瞬间完成的匹配，退化成了**指数级**的计算。这就是"灾难性回溯（catastrophic backtracking）"，业界更广为人知的名字叫 **ReDoS——Regular expression Denial of Service（正则表达式拒绝服务）**。注意，这条雷不是你写错了模式，模式本身完全合法、完全"正确"。 ### 5. ReDoS 不是理论：一行正则放倒半个互联网 这不是教科书里的思想实验。**2019 年 7 月 2 日**，Cloudflare 用于 WAF（Web 应用防火墙）的一段正则表达式触发了灾难性回溯，导致全球大量网站——其中包括 Discord、Stripe 等知名服务——集体不可用约 **27 分钟**。肇事模式形如 `(?:(?:\"|'|\]|\}|\\|\d|...)+)+`，内层一堆"或"选项外面又套了一层 `+` 量词，在特定输入下完美踩中指数回溯，把 CPU 瞬间打满。 更要命的是，这段正则部署在**每一个 HTTP 请求**的关键路径上，于是单条规则的崩溃被瞬间放大成全网级事故。Cloudflare 事后专门发布技术复盘，并很快上线了自动检测危险正则的工具。除此之外，Stack Exchange 等大型平台历史上也踩过同类坑，CVE 漏洞数据库里登记的 ReDoS 条目数量可观，OWASP 已经把 ReDoS 正式列入需要关注的攻击面。 > 一句话点破这件事的荒诞：**攻击者甚至不需要构造复杂 payload，只要发一段精心选择的普通文本，就能让你那行"用来防御的正则"反过来打死你自己。** ### 6. 为什么大家明知危险，还要用回溯 这是个很自然的疑问。答案是：**因为回溯引擎能做的事，线性自动机做不了**。反向引用——也就是"把前面匹配到的内容，后面再拿出来用"——在数学上会让这门语言**超出正则语言的范畴**，纯 DFA 根本表达不了。为了这些丰富特性，PCRE、Perl、Python `re`、Java、JavaScript、.NET 这些主流引擎，普遍选择了回溯（或带各种优化的回溯）。 反过来，**Google 的 RE2、Rust 的 regex、Go 的 regexp** 则故意把反向引用这类特性砍掉，换回线性时间的硬保证——它们基于 Thompson NFA / DFA，**从设计上就不会 ReDoS**。这是一条被刻意做出的工程取舍：**功能 vs 安全**。Rust 的 `regex` 文档里甚至明文写着自己拒绝支持反向引用，原因正是 ReDoS。**（本段为延伸分析）** ### 7. 怎么不被自己的正则反噬 知道原理，防御就有了章法。几条可以落地的实践： 1. **凡是处理用户输入或外部数据的正则，优先用 RE2 / rust-regex 这类有线性保证的引擎。** Go 和 Rust 标准库自带；Python 可装 `google-re2`；JavaScript 有 RE2 的绑定。这是釜底抽薪。 2. **警惕嵌套量词。** `(x+)+`、`(x*)*`、`(.*a){n}` 都是高危信号，code review 时应当重点关注。 3. **善用占有量词和原子分组。** 比如 `a++`（possessive，占有量词）和 `(?>...)`（atomic group，原子分组），它们明确告诉引擎"这条岔路不回头"，能直接掐断指数级回溯。可惜 JavaScript 原生正则目前还不支持，PCRE / Java / .NET 支持。 4. **给匹配设超时。** Java 的 `java.util.regex` 支持带超时的匹配，RE2 系天然可控；把正则放在可中断的沙箱里跑，是最后一道闸。 5. **上线前给正则做"体检"。** `regex101` 的 debugger、JS 生态的 `safe-regex` 等静态工具，能在部署前就识别出潜在的危险模式。 ## 知识结构图 ```mermaid flowchart TD A["正则表达式 pattern"] -->|"编译"| B["NFA 有限自动机\nThompson 1968"] B --> C{"执行引擎怎么跑"} C -->|"路线A 自动机"| D["Thompson NFA / 子集构造 DFA"] D --> E["匹配时间 O(n) 线性"] E --> F["代表：RE2 / rust-regex / Go"] C -->|"路线B 回溯"| G["递归回溯匹配"] G --> H["最坏 O(2^n) 指数"] H --> I["代表：PCRE / Python / Java / JS / Perl"] I --> J["危险：ReDoS 灾难性回溯"] J --> K["真实事故：Cloudflare 2019\n宕机约27分钟"] L["工程防御"] --> M["换用 RE2 / rust-regex"] L --> N["设超时 / 锚定 / 原子分组"] L --> O["静态体检 safe-regex 等"] J -.->|"靠这些消除"| L ``` ## 实战启示 看完这期视频再结合引擎原理，最该升级的一个认知是：**写正则的时候，脑子里要装一台状态机。** 你遇到的绝大多数正则性能问题，根子都不在"模式写得长不长"，而在"你对引擎工作模型的假设是错的"。 落到工程实践上，我建议团队做三件事。**第一，把正则纳入 code review 的正式检查项**，尤其是那些部署在请求热路径、处理用户输入的正则——它们和 SQL 语句一样，是会被攻击面利用的"代码"，必须可测试、可超时、可替换。**第二，建立简单的选型决策树**：只需要普通匹配（绝大多数场景）→ 一律上 RE2 系引擎；确实需要反向引用、复杂查找 → 用回溯引擎，但务必设超时并对输入长度做限制。**第三，把"正则也会爆炸"写进新人文档**，附上 `(a+)+` 这类最经典的反面案例和一个本地复现脚本，让人亲眼看到一行"正确的正则"把进程卡死。 更深一层，这件事其实揭示了一个普遍的工程教训：**"能跑通"和"安全"是两回事**。一个合法的正则、一段正确的 SQL、一个没报错的递归，都可能在边界输入下露出指数级的獠牙。养成"想一想最坏情况复杂度"的反射，比背再多语法都值。 ## 延伸学习路径 1. **Russ Cox《Regular Expression Matching Can Be Simple And Fast》（2007）** —— 理解正则引擎分水岭的必读经典，实测曲线一目了然。 2. **Russ Cox 正则系列后续篇（regexp2 ~ regexp4）** —— 深入 DFA、子集构造与 lazy DFA 的实现细节。 3. **《Beautiful Code》第一章，Brian Kernighan 著** —— 用不到 30 行 C 实现一个线性正则匹配器，极好的源码级教材。 4. **RE2 官方文档与 syntax 说明（github.com/google/re2）** —— 看一个"刻意阉割功能换安全"的工业级引擎是怎么设计的。 5. **Cloudflare 2019 宕机复盘博客 + OWASP ReDoS 攻击页** —— 从真实事故和攻防视角，理解为什么这是必须重视的工程问题。 ## 一句话总结 正则不是魔法字符串，而是一台被编译出来的状态机；选错了引擎，一行"完全正确"的模式，就足以把整台服务器拖进指数级的泥潭。 ## 参考来源 1. [Regular Expressions — Computerphile](https://www.youtube.com/watch?v=528Jc3q86F8) — 本文解读的核心视频（Prof. Brailsford 主讲） 2. [Russ Cox: Regular Expression Matching Can Be Simple And Fast](https://swtch.com/~rsc/regexp/regexp1.html) — 正则引擎线性 vs 回溯的经典技术分析 3. [Cloudflare: Details of the Cloudflare outage on July 2, 2019](https://blog.cloudflare.com/details-of-the-cloudflare-outage-on-july-2-2019/) — ReDoS 真实事故复盘 4. [OWASP: Regular expression Denial of Service - ReDoS](https://owasp.org/www-community/attacks/Regular_expression_Denial_of_Service_-_ReDoS) — ReDoS 攻防与防御指引 5. [RE2 — Google](https://github.com/google/re2) — 线性时间正则引擎的代表实现与设计说明 > 本文由「51学通信」技术团队出品。51学通信由通信行业18年老兵**爱卫生**（微信ID: gprshome201101）维护，聚焦5G/6G核心网、3GPP标准解读、通信前沿技术深度分析。 > 出版作品有《5G核心网原理与实践》《IMS原理与实践》等4本通信专业书籍。知识星球「51学通信」提供深度技术答疑和行业洞察。 ### 完成摘要（What was done） ### 下一步计划（What's next） 1. **优先级高**：建议人工复核视频卡片的"时长/播放量"两项——因 IP 限流无法取到精确元数据，"约14分钟/约27万播放"为搜索页快照读取值，可酌情微调。 2. **优先级中**：如需更"近期热门"的视频，可在 7 月 18 日限流解除后，用 WebSearch 补一个近 7 天的 ReDoS/正则引擎相关新视频替换锚点。 3. **优先级低**：若希望配可视化演示，可后续用 `knowledge-card-pro` 或 `content-to-video` 技能把"灾难性回溯的指数曲线"做成短视频卡片。 ### 注意事项（If applicable） - 全文未杜撰视频逐字原话；凡涉及视频内容的描述（如 Brailsford 从理论根基讲起）均为概括，延伸分析（Thompson 构造、ReDoS、RE2 取舍等）已明确标注为延伸，便于读者区分。 - Cloudflare 2019 事故、Russ Cox 2007 文章、Kleene/Thompson 时间线均为可公开核实的史实；CVE 数量用模糊表述避免不精确数字。 > [!tip] 51学通信知识星球 > **星主：爱卫生**（微信：gprshome201101）——公众号「51学通信」创办者，19 年通信行业运维与讲师经验，著有《GPRS网络信令实例详解》《EPC原理与实践》《5G核心网原理与实践》三本纸质书（各大电商平台有售）。 > **星球定位**：深耕 5G 核心网、IMS、NFV/AI、云原生等 ICT 领域，主打运维岗位与信令分析。 > **当前规模**：5200 篇主题 / 990 个回答，198 元/年。 > **加入福利**：加入星球后请加爱卫生微信，拉您进知识星球年度陪伴与答疑群——不限量回复您的各种问题，另有群内分享。 > **AI 加持**：51学通信知识星球已作为 skill 接入 WorkBuddy，使用 deepseek-4-flash 在海量星球帖子中精准找贴、找视频、找 FAQ 和案例，做总结、找文档和 PPT 等场景全覆盖。