浅析正则表达式性能问题

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

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

正则引擎原理

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

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

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

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

Cloudflare 的正则分析

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


Cloudflare WAF 简化正则之后的出问题的其实是 .*.*=.* 这个模式。这个模式看起来并不是很复杂，要求正则引擎匹配任何值 = 任何值，但是这会导致非常严重的回溯问题。

在正则表达式中 . 表示匹配单个字符，而 .* 表示尽可能多的匹配字符（贪婪匹配，可以是零个字符），在使用贪婪匹配或者惰性匹配或者或匹配进入到匹配路径选择的时候，遇到失败的匹配路径，尝试走另外一个匹配路径的这种行为，称作回溯。因此 .*.*=.* 表示匹配零个或多个字符，然后匹配零个或多个字符，然后匹配一个 = 字符，然后匹配零个或多个字符。

我们使用 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 才能得到匹配失败的结果。

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

PCRE2 为 a(n) = (n^2 - 3\*n + 6)/2，n = b + 5
backtraking 为 a(n) = n^2 + n + 3，n = b + 3


图为 b = 15 时的匹配动画

如果稍微修改一下正则表达式，情况就会更糟，比如修改它为 .*.*=.*;（在表达式末尾增加一个分号），PCRE2 引擎的匹配次数会小幅增加到 304 次, 而 backtraking 则会暴涨至 5353 次。更极端的情况下，使用 X(.+)+X 去匹配字符串 ==XX==================== 会引发回溯失控，正则引擎会在第 119989 步终止，并返回匹配失败。

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

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

正则表达式为 .*.*=.*;，测试文本为 a=bb…bb（100 个 b），进行多次测试。

PHP（PCRE），耗时 0.7ms-1ms

Javascript 速度较快，0.4ms-0.6ms

Python 耗时 0.7ms-0.8ms

Golang 最慢，耗时大于 165ms

Java 耗时大于 5ms

注：Javascript 在 Chrome Console 中使用表达式 X(.+)+X 的测试耗时超过 20s，而在 Regex 的测试中耗时约为 200ms ，可能是对 Javascript 的实现不同导致的。从 Chrome 88 开始，Chrome 新增了一项实验性非回溯 RegExp 引擎，它可以保证在字符串长度变大的情况下保持线性的时间变化，可以在添加启动参数 --enable-experimental-regexp_engine-on-excessive-backtracks 在过多的回溯上启用对非回溯引擎的回退（NFA 与 DFA 混用）。

优化建议

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

例如要匹配 ; 之前并且包括该字符的文本，不要使用模式 .*;，此模式将匹配文本中最后一个 ; 字符之前的文本，其中包括匹配的文本中前面的所有 ;，使用 [^;]*; 则可以避免很多无效的匹配。

同样的，.* 模式会强制匹配到文本的末端并开始查找最佳匹配导致性能较差，除非要匹配到所有剩余数据。

具有冗余嵌套重复的表达式，如 ([a-z0-9]+)* 会导致查找最佳匹配时进行多次搜索，尽可能使用精准匹配条件来使表达式保持简单。

使用取反 ^ 代替 . 进行精准匹配也是不错的选择，如匹配字符串

总结

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