圖1 表示電話號碼的正則表達式字符串

表1 正則表達式基礎語法

圖1中，第一個[0-9]表示數(shù)字0到9中的一個字符，緊接著的{2,3}表示重復出現(xiàn)兩次或三次的字符串，短橫杠字符后是[0-9]{4}-[0-9]{4}，表示電話號碼的“中間4位數(shù)-后4位數(shù)”的正則表達式。

正則表達式的語法有很多種，本文內容基于Python語言編寫，所以筆者使用Python中使用的正則表達式語法來進行解釋。

基于以上正則表達式可以寫一個簡單的匹配電話號碼的Python程序：

也就是，正則表達式會在字符串匹配中嘗試所有可能的匹配，直到匹配失敗。而當正則中出現(xiàn)類似{}、+、*這類表示匹配數(shù)量的含義時會發(fā)生回溯（backtracking），如果正則表達式在匹配字符串的時候發(fā)生數(shù)量巨大的回溯，便會導致災難性回溯（catastrophic backtracking），從而消耗程序大量的計算資源，造成拒絕服務攻擊（Denial of Service）。同時也說明，相同匹配規(guī)則的正則表達式用不同的寫法有不同的匹配次數(shù)，良好的正則表達式可以降低匹配次數(shù)，提升匹配效率，比如相比上述正則的一種更差寫法a(b|bb|bbb)c。

下圖中的代碼是利用回溯消耗計算資源的一個示例。由于正則解釋器是不同的開發(fā)語言內置的，因此選擇不同開發(fā)語言做正則匹配的效率也不同，下圖中代碼如果用Python 2.*運行，可能需要將近一個小時才能完成這個匹配。

圖3 通過控制“回溯”數(shù)量來控制匹配時間

圖4 通過控制“*”數(shù)量來控制回溯數(shù)量來增加匹配時長

圖5 通過HTTP響應代碼中的WWW-Authenticate值驗證用戶身份

圖6 構造一個虛假的請求頭信息，在其中添加正則匹配的部分

該請求可以讓正在運行的Python服務中的urllib.request去校驗登錄請求，從而對其請求頭信息進行正則匹配，造成無限制的正則表達式的回溯匹配，達到拒絕服務的效果。

另外，某些應用在用戶登錄功能邏輯中，會在后端檢測用戶口令中是否有包含用戶名，從而檢測口令的強度。

圖7 登錄過程中判斷口令是否包含賬戶名

圖8 CPU占用率在程序執(zhí)行后上升到15%

正則表達式的“解釋正則表達式字符串”和“判斷輸入字符串是否匹配的部分”是利用有限狀態(tài)機來實現(xiàn)的。

有限狀態(tài)機（FSM，F(xiàn)inite State Automaton）是指對于給定的一系列輸入序列，內部狀態(tài)根據(jù)其輸入轉換，并根據(jù)輸入結束時的狀態(tài)(接受還是拒絕)輸出(確定)的數(shù)學模型。有限狀態(tài)機的特征之一是它內部定義的狀態(tài)數(shù)，顧名思義，限定為有限的狀態(tài)。

比如，要查看二進制數(shù)中是否有偶數(shù)數(shù)量的0，則可以使用有限狀態(tài)機。下方的圖9用狀態(tài)轉換圖表示確定是否有偶數(shù)數(shù)量0的有限狀態(tài)機。

圖9 二進制中檢測0的數(shù)量是否為偶數(shù)的有限狀態(tài)機的狀態(tài)轉換圖

狀態(tài)轉換圖中每個圓圈表示一種狀態(tài)，圓圈中的“q0(偶數(shù))”和“q1(奇數(shù))”表示這些狀態(tài)中的一種。粗箭頭所指的圓圈是開始時的狀態(tài)，雙圈表示“受理”的狀態(tài)（本例中受理狀態(tài)是指偶數(shù)個0的狀態(tài)）。然后，從每個圓圈延伸出來的細箭頭上的數(shù)字表示每個輸入，箭頭指向的方向是與該輸入相對應的轉換目標的狀態(tài)（本例中輸入是0和1）。

如果輸入是1010，從左到右讀取字符，第一個輸入字符是1，它從q0指向q0，下一個輸入是0，狀態(tài)機從q0指向q1。接下來是1，從q1指向q1，最后一個輸入是0，從 q1指向q0。

開始狀態(tài)q0→q0→q1→q1→q0（結束: 接受結果，偶數(shù)個0）

最終結果如上所述，用雙圈表示的q0成為此次處理的受理狀態(tài)（偶數(shù)），因此判定“1010中有偶數(shù)個0”。

圖10 事件發(fā)生的半個小時內，CPU占用率飆升至100%

產生的后果是，包括Cloudflare公司在內的所有使用Cloudflare域名解析服務的網(wǎng)站訪問頁面都是502 Bad Gateway。而在此之前，Cloudflare已經6年未發(fā)生過全球性事故了，對于公司的品牌和聲譽影響可見一斑。

事故是當天的13:42一名工程師提交的WAF規(guī)則變更導致，由于WAF規(guī)則更新的及時性特性，WAF規(guī)則更新無需經過灰度發(fā)布，且集成測試中也無關于CPU性能的測試，故導致錯誤的規(guī)則被發(fā)布上線。事故處理時Cloudflare一度將全球的WAF功能停用，最終在14:52修復問題并恢復WAF。其中涉及的正則表達式如下：

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

問題出自該正則中非捕獲分組（non-capturing group）.*(?:.*=.*)，簡化之后事.*.*=.*，上文說過在諸如*出沒的正則中要注意回溯的問題，這里的連續(xù)三個.*表達式，意味著字符串越長，回溯的次數(shù)越多，正則匹配需要花費的時間越長。比如下圖中的匹配時間對比。

圖11 x=x字符串的匹配步驟是16步，耗時0.1ms

圖12 更換字符串之后匹配步驟是5566步，耗時0.5ms

圖13 x的數(shù)量與執(zhí)行步驟之間的關系

輸入驗證和消毒（sanitization）：確保用戶輸入在用于生成正則表達式之前經過驗證和消毒。

• 輸入長度限制：實施輸入長度限制，限制可處理的用戶輸入長度。

• 利用超時設置：使用超時值來限制單個正則表達式匹配所能花費的時間。

• 檢查正則表達式：檢查正則表達式設計的合理性和災難性回溯問題。

• 使用安全的庫：使用維護良好、文檔齊全的最新安全正則表達式庫。

• 更換安全的正則匹配引擎：如Cloudflare事后更換了re2或Rust正則引擎。

以下是基于上文開頭示例代碼修改的ReDoS攻擊防御代碼，該代碼會在正則表達式匹配超過1秒時候停止執(zhí)行：

圖14 函數(shù)校驗正字符串產出ReDoS后停止