淺析正則表達式性能問題

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]+)* 會導致查找最佳匹配時進行多次搜索，盡可能使用精準匹配條件來使表達式保持簡單。

使用取反 ^ 代替 . 進行精準匹配也是不錯的選擇，如匹配字符串

123456

，表達式 ]+>[^<]+<\/div> 只用了 14 次匹配，而表達式.*?<\/div> 的匹配次數達到了 39 次。總結

造成 Cloudflare 這次事件的原因是使用了性能較差的正則引擎以及有問題的正則表達式，造成了災難性的回溯（然而大部分語言的正則引擎都是使用NFA）。使用 DFA 或許是個好辦法，但是不支持斷言等功能使會易用性降低。平時寫正則的時候盡可能少用模糊匹配可以有效緩解回溯問題。關于 NFA 與 DFA 原理更詳細的解釋可以參考這篇文章 DFA和NFA（https://www.iteye.com/blog/hooopo-548087）

=END=