標籤：

如何徹底避免正則表達式的災難性回溯？

12-24

正則表達式的災難性回溯（Catastrophic Backtracking）是指，正則在匹配的時候回溯過多，造成 CPU 100%，正常服務被阻塞。

背景

這裡有一篇文章詳細的描述了一次正則回溯導致 CPU 100% 的發現和解決過程，原文比較長，我之前也在 OpenResty 的開發中遇到過兩次類似的問題。

這裡簡單歸納下，你就可以不用花費時間去了解背景了：

  1. 大部分開發語言的正則引擎是用基於回溯的 NFA 來實現（而不是基於 Thompson』s NFA）；
  2. 如果回溯次數過多，就會導致災難性回溯，CPU 100%；
  3. 需要用 gdb 分析 dump，或者 systemtap 分析線上環境來定位；
  4. 這種問題很難在代碼上線前發現，需要逐個 review 正則表達式；

站在開發的角度，修復完有問題的正則表達式，就告一段落了。最多再加上一個保險機制，限制下回溯的次數，比如在 OpenResty 中這樣設置：

lua_regex_match_limit 100000;

這樣即使出現災難性回溯，也會被限制住，不會跑滿 CPU。

嗯，看上去已經很完美了嗎？讓我們來跳出開發的層面，用不同的維度來看待這個問題。

攻擊者

只用一台機器，發送一個請求，就可以打跨對方的伺服器，這簡直就是黑客夢寐以求的核武器。與之相比，什麼 DDoS 弱爆了，動靜大還花錢多。

這種攻擊也有自己的名字：ReDoS (RegEx Denial of Service)。

由於正則表達式應用非常廣泛，幾乎存在於後端服務的各個部分，所以只要找到其中一個漏洞，就有機可趁。

試想一個場景，黑客發現了 WAF 中存在 ReDoS 漏洞，發送一個請求打垮了 WAF；你無法在短時間內定位這個問題，甚至意識不到這是一次攻擊；為了保證業務的正常，你選擇重啟或者暫時關閉 WAF；在 WAF 失效期間，黑客利用 SQL 注入，拖走了你的資料庫。而你，可能還完全蒙在鼓裡。

由於開源軟體和雲服務的廣泛使用，只保證自己寫的正則表達式沒有漏洞，也是不夠的。這是另外一個話題了，我們這裡先只討論自己可控範圍內的正則。

如何發現這類正則表達式？

解決問題的第一步，就是發現問題，而且要盡量發現所有問題，也就是所謂安全的發現能力。

指望人工 code review 來發現有問題的正則，自然是靠不住的。大部分開發者是沒有這方面安全意識的，就算有意去找，人也不可能從複雜的正則表達式中找到問題所在。

這正是自動化工具大顯身手的時候。

我們有以下兩種自動化的方法來解決：

  • 靜態檢測

這類工具可以掃描代碼中正則表達式，根據一定的演算法，從中找出有災難性回溯的正則。

比如RXXR2（cs.bham.ac.uk/%7Ehxt/re），它是基於一篇 paper 中的演算法來實現，把正則轉換為ε-NFA，然後再進行搜索，但並不支持正則表達式的擴展語法，所以會有漏報。

  • 動態 fuzzing

fuzz 測試是一種通用的軟體測試方法，通過長時間輸入大量隨機的數據，來檢測軟體是否有崩潰、內存泄漏等問題。

同樣的，在正則的測試中我們也可以用到這種方法。我們可以根據已有的正則表達式來生成測試數據，也可以完全隨機生成。

SlowFuzz 是其中一個開源的工具，也是基於一篇 paper 的演算法實現，本文最後會列出 paper，它是一個通用的工具，並沒有針對正則的結構做處理，所以會有漏報。

SDLFuzzer 是幾年前微軟開發的一個專門的 ReDoS 檢測工具，但已經不再維護了。

這方面的工具可選擇的不多，而且關注度不高。不過讓我興奮的是，在搜索資料的過程中，發現了南京大學幾位老師和博士關於 ReDoS 的一篇paper，並且和 paper 一起開源了 ReScue這個工具： 2bdenny.github.io/ReScu。這個工具已經找出了幾個開源項目中的 ReDoS 漏洞。

下面是 paper 中對比測試的結果：

可否一勞永逸？

即使我們用了這類工具，有難免會有誤報和漏報，那麼有沒有一勞永逸的方式來解決 ReDoS 呢？

那麼我們就要回到問題產生的根源去尋找答案：正則引擎使用了回溯的方式來匹配。

如果我們棄用這種方法，是不是就可以了呢？沒錯，已經有不少其他的正則引擎的實現，都可以一勞永逸的來解決。他們都放棄了回溯，用 NFA/DFA 自動機的方法來實現，優點是適合流式匹配，也更加安全，缺點不支持很多正則的擴展語法，比如 backreferences，好在這些一般也用不到。

  • Google RE2

谷歌的 RE2 是其中完成度比較高開源項目。它支持 PCRE 的大部分語法，而且有 Go、Python、Perl、Node.js 等多種開發語言的庫實現，上手和替換成本很低。

我們以 Perl 為例，看下 RE2 是否可以避免災難性回溯問題。

我們先來看下這個結果對比圖：

代碼如下，感興趣的可以自己試試看：

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，感興趣的可以作為擴展閱讀。

  1. SlowFuzz: Automated Domain-Independent Detection of Algorithmic Complexity Vulnerabilities： arxiv.org/pdf/1708.0843
  2. Static Analysis for Regular Expression Exponential Runtime via Substructural Logics：cs.bham.ac.uk/%7Ehxt/re
  3. ReScue: Crafting Regular Expression DoS Attacks：cs.nju.edu.cn/changxu/1
  4. Regular Expression Matching Can Be Simple And Fast： swtch.com/~rsc/regexp/r

推薦閱讀：

TAG:正則表達式 | 字元串 | 科技 |