如何徹底避免正則表示式的災難性回溯？
題圖：negative space from pexels
正則表示式的災難性回溯（Catastrophic Backtracking）是指，正則在匹配的時候回溯過多，造成 CPU 100%，正常服務被阻塞。
背景
這裡有一篇文章詳細的描述了一次正則回溯導致 CPU 100% 的發現和解決過程，原文比較長，我之前也在 OpenResty 的開發中遇到過兩次類似的問題。
這裡簡單歸納下，你就可以不用花費時間去了解背景了：
-
大部分開發語言的正則引擎是用基於回溯的 NFA 來實現（而不是基於 Thompson’s NFA）；
-
如果回溯次數過多，就會導致災難性回溯，CPU 100%；
-
需要用 gdb 分析 dump，或者 systemtap 分析線上環境來定位；
-
這種問題很難在程式碼上線前發現，需要逐個 review 正則表示式；
站在開發的角度，修復完有問題的正則表示式，就告一段落了。最多再加上一個保險機制，限制下回溯的次數，比如在 OpenResty 中這樣設定：
lua_regex_match_limit 100000;
這樣即使出現災難性回溯，也會被限制住，不會跑滿 CPU。
嗯，看上去已經很完美了嗎？讓我們來跳出開發的層面，用不同的維度來看待這個問題。
攻擊者
只用一臺機器，傳送一個請求，就可以打跨對方的伺服器，這簡直就是黑客夢寐以求的核武器。與之相比，什麼 DDoS 弱爆了，動靜大還花錢多。
這種攻擊也有自己的名字： ReDoS (RegEx Denial of Service) 。
由於正則表示式應用非常廣泛，幾乎存在於後端服務的各個部分，所以只要找到其中一個漏洞，就有機可趁。
試想一個場景，黑客發現了 WAF 中存在 ReDoS 漏洞，傳送一個請求打垮了 WAF；你無法在短時間內定位這個問題， 甚至意識不到這是一次攻擊 ；為了保證業務的正常，你選擇重啟或者暫時關閉 WAF；在 WAF 失效期間，黑客利用 SQL 注入，拖走了你的資料庫。而你，可能還完全矇在鼓裡。
由於開源軟體和雲服務的廣泛使用，只保證自己寫的正則表示式沒有漏洞，也是不夠的 。這是另外一個話題了，我們這裡先只討論自己可控範圍內的正則。
如何發現這類正則表示式？
解決問題的第一步，就是發現問題，而且要儘量發現所有問題，也就是所謂安全的發現能力。
指望人工 code review 來發現有問題的正則，自然是靠不住的。大部分開發者是沒有這方面安全意識的，就算有意去找，人也不可能從複雜的正則表示式中找到問題所在。
這正是自動化工具大顯身手的時候。
我們有以下兩種自動化的方法來解決：
-
靜態檢測
這類工具可以掃描程式碼中正則表示式，根據一定的演算法，從中找出有災難性回溯的正則。
比如 RXXR2 （http://www.cs.bham.ac.uk/%7Ehxt/research/rxxr2/），它是基於一篇 paper 中的演算法來實現，把正則轉換為ε-NFA，然後再進行搜尋，但並不支援正則表示式的擴充套件語法，所以會有漏報。
-
動態 fuzzing
fuzz 測試是一種通用的軟體測試方法，通過長時間輸入大量隨機的資料，來檢測軟體是否有崩潰、記憶體洩漏等問題。
同樣的，在正則的測試中我們也可以用到這種方法。我們可以根據已有的正則表示式來生成測試資料，也可以完全隨機生成。
SlowFuzz 是其中一個開源的工具，也是基於一篇 paper 的演算法實現，本文最後會列出 paper，它是一個通用的工具，並沒有針對正則的結構做處理，所以會有漏報。
SDLFuzzer 是幾年前微軟開發的一個專門的 ReDoS 檢測工具，但已經不再維護了。
這方面的工具可選擇的不多，而且關注度不高。不過讓我興奮的是，在搜尋資料的過程中，發現了南京大學幾位老師和博士關於 ReDoS 的一篇paper，並且和 paper 一起開源了 ReScue 這個工具： https://2bdenny.github.io/ReScue/。這個工具已經找出了幾個開源專案中的 ReDoS 漏洞。
下面是 paper 中對比測試的結果：
可否一勞永逸？
即使我們用了這類工具，有難免會有誤報和漏報，那麼有沒有一勞永逸的方式來解決 ReDoS 呢？
那麼我們就要回到 問題產生的根源 去尋找答案： 正則引擎使用了回溯的方式來匹配。
如果我們棄用這種方法，是不是就可以了呢？沒錯，已經有不少其他的正則引擎的實現，都可以一勞永逸的來解決。他們都 放棄了回溯，用 NFA/DFA 自動機的方法來實現 ，優點是適合流式匹配，也更加安全，缺點不支援很多正則的擴充套件語法，比如 backreferences，好在這些一般也用不到。
-
Google RE2
谷歌的 RE2 是其中完成度比較高開源專案。它支援 PCRE 的大部分語法，而且有 Go、Python、Perl、Node.js 等多種開發語言的庫實現，上手和替換成本很低。
我們以 Perl 為例，看下 RE2 是否可以避免災難性回溯問題。
我們先來看下這個結果對比圖：
來自Russ Cox 所寫的 Regular Expression Matching Can Be Simple And Fast
程式碼如下，感興趣的可以自己試試看：
time perl -e 'if ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" =~ /a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa/) {print("hit");}'
40.80s user 0.00s system 99% cpu 40.800 total
需要 40.8 秒才能跑完這個正則，期間 CPU 99%。
採用 RE2 之後，對比非常明顯：
time perl -e 'use re::engine::RE2; if ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" =~ /a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa/) {print(" hit");}'
perl -e 0.00s user 0.00s system 34% cpu 0.011 total
-
Intel Hyperscan
Intel Hyperscan 也是類似 RE2 的正則引擎，也有Perl、Python 等語言的庫，上手難度不大。
只不過按照 Intel 的慣例，多了平臺的繫結，只能跑在 x86 中。
如果非要說有什麼獨特的好處，可能是能夠和 Intel 的指令集還有硬體更好的配合，有效能的提升，比如結合下自家的 DPDK。
開源的網路入侵檢測工具 Snort，也用 Hyperscan 替換了之前的正則引擎，熟悉 Snort 的同學可以試試看。
-
OpenResty Sregex
最後提下自家開源的正則引擎： OpenResty Sregex，原理和上面兩個類似，都沒有回溯，適合做流式處理和大量正則的匹配。
Sregex 的文件是這幾個中最詳細的，歡迎感興趣的同學參與。
擴充套件
這裡有幾篇正則表示式方面的 paper，感興趣的可以作為擴充套件閱讀。
-
SlowFuzz: Automated Domain-Independent Detection of Algorithmic Complexity Vulnerabilities： https://arxiv.org/pdf/1708.08437.pdf
-
Static Analysis for Regular Expression Exponential Runtime via Substructural Logics：http://www.cs.bham.ac.uk/%7Ehxt/research/redos_full.pdf
-
ReScue: Crafting Regular Expression DoS Attacks：https://cs.nju.edu.cn/changxu/1_publications/ASE18.pdf
-
Regular Expression Matching Can Be Simple And Fast： https://swtch.com/~rsc/regexp/regexp1.html