2019 年七月初，Cloudflare 曾经全球中断服务，原因是为了改进内联 JavaScript 屏蔽，部署了一条正则表达式组成的 WAF 防御规则，耗尽了 CPU 资源。

Cloudflare WAF 的引擎还是 backtraking，所以导致错误的正则写法产生回溯问题，最终 ReDos（正则表达式拒绝服务攻击）。它会导致计算量急剧的放大，使大量网站访问出现了 502。

正则引擎原理

提到正则表达式引擎，首先需要涉及到一个概念：有限状态自动机

有限状态自动机（FSM "finite state machine" 或者FSA "finite state automaton" ）是为研究有限内存的计算过程和某些语言类而抽象出的一种计算模型。有限状态自动机拥有有限数量的状态，每个状态可以迁移到零个或多个状态，输入字串决定执行哪个状态的迁移。

传统正则表达式引擎分为两类，分别是 NFA（非确定性有限状态自动机）和 DFA（确定性有限状态自动机）。

最直观的区别就是 NFA 在语法解析的时候，构造出的一个有向图。然后通过深搜的方式，去一条路径一条路径的递归尝试，因此速度较慢，不过实现的功能更丰富，对正则编写功底较高，否则容易因为回溯造成性能问题。DFA 会把正则表达式转换成一个图的邻接表，然后通过跳表的形式判断一个字符串是否匹配该正则，因此匹配速度较快，但是不支持捕获组和断言等功能。

Cloudflare 的正则分析

.*.*=.*
.*

我们使用 a=b 来作为测试文本，正则引擎为 PCRE2（PHP>=7.3）。

  1. 第一个 .* 贪婪匹配 0 个字符
  2. 第二个 .* 贪婪匹配剩余全部字符
  3. = 尝试匹配，由于没有更多字符可以匹配了，匹配失败
  4. 引擎向前回溯
  5. 第二个 .* 贪婪匹配到字符 a=
  6. = 尝试匹配字符 b，匹配失败
  7. 引擎向前回溯
  8. 第二个 .* 贪婪匹配到字符 a
  9. = 尝试匹配字符 b, 匹配失败
  10. = 尝试向前匹配 =，匹配成功
  11. 第三个 .* 贪婪匹配 0 个字符
  12. 第三个 .* 贪婪匹配剩余全部字符，正则完成全部字符匹配


12 次匹配只为了匹配三个字符的字符串（Cloudflare 使用的正则引擎为 backtraking，匹配次数为 23 次），如果测试字符串从 a=b 变为 a=bb，完全匹配需要 17 次，a=bbb 需要 23 次，当 b 的个数为 20 时，次数达到了 278 次。如果 a= 缺少了，那需要匹配次数会增加到 2023 才能得到匹配失败的结果。


随着字符数量的增加，匹配需要的时间也相应的增加

图为 b = 15 时的匹配动画


.*.*=.*;X(.+)+X==XX====================

不同语言自带的正则性能比较

避免此类问题的方法就是尽可能使用高效的正则表达式引擎，比如 RE2、Rust、PCRE 等，不同的引擎之间有着较大的性能差异，这里使用 Regex 进行测试，测试仅供横向对比参考，不同的表达式在不同的引擎上各有优劣，实际速度与计算机性能相关。

.*.*=.*;a=bb…bb
X(.+)+X--enable-experimental-regexp_engine-on-excessive-backtracks

优化建议

某些格式的正则表达式可能涉及大量查找最佳匹配工作，会导致性能的降低，甚至产生预期之外的结果。正则表达式的很多优化技巧都是围绕着减少回溯这样一个原则进行优化的。

;.*;;;[^;]*;
.*
([a-z0-9]+)*
^.
123456
]+>[^<]+<\/div>.*?<\/div>

总结

造成 Cloudflare 这次事件的原因是使用了性能较差的正则引擎以及有问题的正则表达式，造成了灾难性的回溯（然而大部分语言的正则引擎都是使用NFA）。使用 DFA 或许是个好办法，但是不支持断言等功能使会易用性降低。平时写正则的时候尽可能少用模糊匹配可以有效缓解回溯问题。关于 NFA 与 DFA 原理更详细的解释可以参考这篇文章 DFA和NFA。