淺析正則表達(dá)式性能問題
2019 年七月初，Cloudflare 曾經(jīng)全球中斷服務(wù)，原因是為了改進(jìn)內(nèi)聯(lián) JavaScript 屏蔽，部署了一條正則表達(dá)式組成的 WAF 防御規(guī)則，耗盡了 CPU 資源。
Cloudflare WAF 的引擎還是 backtraking，所以導(dǎo)致錯誤的正則寫法產(chǎn)生回溯問題，最終 ReDos（正則表達(dá)式拒絕服務(wù)攻擊）。它會導(dǎo)致計算量急劇的放大，使大量網(wǎng)站訪問出現(xiàn)了 502。
正則引擎原理
提到正則表達(dá)式引擎，首先需要涉及到一個概念：有限狀態(tài)自動機
有限狀態(tài)自動機（FSM "finite state machine" 或者FSA "finite state automaton" ）是為研究有限內(nèi)存的計算過程和某些語言類而抽象出的一種計算模型。有限狀態(tài)自動機擁有有限數(shù)量的狀態(tài)，每個狀態(tài)可以遷移到零個或多個狀態(tài)，輸入字串決定執(zhí)行哪個狀態(tài)的遷移。
傳統(tǒng)正則表達(dá)式引擎分為兩類，分別是 NFA（非確定性有限狀態(tài)自動機）和 DFA（確定性有限狀態(tài)自動機）。
最直觀的區(qū)別就是 NFA 在語法解析的時候，構(gòu)造出的一個有向圖。然后通過深搜的方式，去一條路徑一條路徑的遞歸嘗試，因此速度較慢，不過實現(xiàn)的功能更豐富，對正則編寫功底較高，否則容易因為回溯造成性能問題。DFA 會把正則表達(dá)式轉(zhuǎn)換成一個圖的鄰接表，然后通過跳表的形式判斷一個字符串是否匹配該正則，因此匹配速度較快，但是不支持捕獲組和斷言等功能。
Cloudflare的正則分析
(?:(?:\"|'|\]|\}|\\|\d|(?:nan|infinity|true|false|null|undefined|symbol|math)|\`|\-|\+)+[)]*;?((?:\s|-|~|!|{}|\|\||\+)*.*(?:.*=.*)))
Cloudflare WAF 簡化正則之后的出問題的其實是 .*.*=.* 這個模式。這個模式看起來并不是很復(fù)雜，要求正則引擎匹配任何值 = 任何值，但是這會導(dǎo)致非常嚴(yán)重的回溯問題。
在正則表達(dá)式中 . 表示匹配單個字符，而 .* 表示盡可能多的匹配字符（貪婪匹配，可以是零個字符），在使用貪婪匹配或者惰性匹配或者或匹配進(jìn)入到匹配路徑選擇的時候，遇到失敗的匹配路徑，嘗試走另外一個匹配路徑的這種行為，稱作回溯。因此 ?.*.*=.* 表示匹配零個或多個字符，然后匹配零個或多個字符，然后匹配一個 = 字符，然后匹配零個或多個字符。
我們使用 a=b 來作為測試文本，正則引擎為 PCRE2（PHP>=7.3）。
第一個 .* 貪婪匹配 0 個字符
第二個 .* 貪婪匹配剩余全部字符
= 嘗試匹配，由于沒有更多字符可以匹配了，匹配失敗
引擎向前回溯
第二個 .* 貪婪匹配到字符 a=
= 嘗試匹配字符 b，匹配失敗
引擎向前回溯
第二個 .* 貪婪匹配到字符 a
= 嘗試匹配字符 b, 匹配失敗
= 嘗試向前匹配 =，匹配成功
第三個 .* 貪婪匹配 0 個字符
第三個 .* 貪婪匹配剩余全部字符，正則完成全部字符匹配
12 次匹配只為了匹配三個字符的字符串（Cloudflare 使用的正則引擎為 backtraking，匹配次數(shù)為 23 次），如果測試字符串從 a=b 變?yōu)?a=bb，完全匹配需要 17 次，a=bbb 需要 23 次，當(dāng) b 的個數(shù)為 20 時，次數(shù)達(dá)到了 278 次。如果 a= 缺少了，那需要匹配次數(shù)會增加到 2023 才能得到匹配失敗的結(jié)果。
隨著字符數(shù)量的增加，匹配需要的時間也相應(yīng)的增加
PCRE2 為 a(n) = (n^2 - 3\*n + 6)/2，n = b + 5
backtraking 為 a(n) = n^2 + n + 3，n = b + 3
圖為 b = 15 時的匹配動畫
如果稍微修改一下正則表達(dá)式，情況就會更糟，比如修改它為 .*.*=.*;（在表達(dá)式末尾增加一個分號），PCRE2 引擎的匹配次數(shù)會小幅增加到 304 次, 而 backtraking 則會暴漲至 5353 次。更極端的情況下，使用 X(.+)+X 去匹配字符串 ==XX==================== 會引發(fā)回溯失控，正則引擎會在第 119989 步終止，并返回匹配失敗。
不同語言自帶的正則性能比較
避免此類問題的方法就是盡可能使用高效的正則表達(dá)式引擎，比如 RE2、Rust、PCRE 等，不同的引擎之間有著較大的性能差異，這里使用 Regex 進(jìn)行測試，測試僅供橫向?qū)Ρ葏⒖?，不同的表達(dá)式在不同的引擎上各有優(yōu)劣，實際速度與計算機性能相關(guān)。
正則表達(dá)式為 .*.*=.*;，測試文本為 a=bb…bb（100 個 b），進(jìn)行多次測試。
PHP（PCRE），耗時 0.7ms-1ms
JavaScript 速度較快，0.4ms-0.6ms
Python 耗時 0.7ms-0.8ms
Golang 最慢，耗時大于 165ms
Java 耗時大于 5ms
注：JavaScript 在 Chrome Console 中使用表達(dá)式
X(.+)+X的測試耗時超過 20s，而在 Regex 的測試中耗時約為 200ms ，可能是對 JavaScript 的實現(xiàn)不同導(dǎo)致的。從 Chrome 88 開始，Chrome 新增了一項實驗性非回溯 RegExp 引擎，它可以保證在字符串長度變大的情況下保持線性的時間變化，可以在添加啟動參數(shù)--enable-experimental-regexp_engine-on-excessive-backtracks在過多的回溯上啟用對非回溯引擎的回退（NFA 與 DFA 混用）。
優(yōu)化建議
某些格式的正則表達(dá)式可能涉及大量查找最佳匹配工作，會導(dǎo)致性能的降低，甚至產(chǎn)生預(yù)期之外的結(jié)果。正則表達(dá)式的很多優(yōu)化技巧都是圍繞著減少回溯這樣一個原則進(jìn)行優(yōu)化的。
例如要匹配 ; 之前并且包括該字符的文本，不要使用模式 .*;，此模式將匹配文本中最后一個 ; 字符之前的文本，其中包括匹配的文本中前面的所有 ;，使用 [^;]*; 則可以避免很多無效的匹配。
同樣的，.* 模式會強制匹配到文本的末端并開始查找最佳匹配導(dǎo)致性能較差，除非要匹配到所有剩余數(shù)據(jù)。
具有冗余嵌套重復(fù)的表達(dá)式，如 ([a-z0-9]+)* 會導(dǎo)致查找最佳匹配時進(jìn)行多次搜索，盡可能使用精準(zhǔn)匹配條件來使表達(dá)式保持簡單。
使用取反 ^ 代替 . 進(jìn)行精準(zhǔn)匹配也是不錯的選擇，如匹配字符串
總結(jié)
造成 Cloudflare 這次事件的原因是使用了性能較差的正則引擎以及有問題的正則表達(dá)式，造成了災(zāi)難性的回溯（然而大部分語言的正則引擎都是使用NFA）。使用 DFA 或許是個好辦法，但是不支持?jǐn)嘌缘裙δ苁箷子眯越档?。平時寫正則的時候盡可能少用模糊匹配可以有效緩解回溯問題。關(guān)于 NFA 與 DFA 原理更詳細(xì)的解釋可以參考這篇文章 DFA和NFA（https://www.iteye.com/blog/hooopo-548087）
=END=