在 2009 年 11 月刊中，我寫了一篇標題為“XML 拒絕服務攻擊和防御” (msdn.microsoft.com/magazine/ee335713) 的文章，在這篇文章中，我介紹了一些對 XML 分 析程序特別有效的拒絕服務 (DoS) 攻擊技巧。我從讀者那裡收到許多有關此文章的電子郵件， 他們都想了解有關這方面的更多知識，這讓我真正意識到人們已經了解 DoS 攻擊的嚴重性。
我相信，在未來的四到五年中，隨著權限升級，執行攻擊會變得更加困難，這是由於不斷采 用諸如數據執行保護 (DEP)、地址空間布局隨機化 (ASLR) 以及隔離和權限降低技巧之類的內 存保護措施所致，攻擊者會將其目標轉移到 DoS 敲詐攻擊。目前，開發人員可以通過領先於攻 擊趨勢變化並針對未來可能的 DoS 演變方向繼續保護其應用程序。
正則表達式 DoS 就是這些未來可能的 DoS 演變方向之一。在以色列召開的 2009 年“開放 式 Web 應用安全項目 (OWASP)”會議上，Checkmarx 首席架構師 Alex Roichman 和高級程序 員 Adar Weidman 做了有關正則表達式 DoS（也稱為“ReDoS”）的深入研究報告。他們的研究 表明，編寫不嚴謹的正則表達式可能會受到攻擊，以致計算相對較短的攻擊字符串（少於 50 個字符）需要數小時或更長時間。在最壞的情況下，處理時間實際上相當於輸入字符串中字符 數的冪數，這意味著，向字符串中增加一個字符串就會使處理時間翻倍。
在本文中，我將介紹正則表達式在哪些情況下容易受到這些攻擊。我還將提供“正則表達式 模糊測試程序”代碼，這一測試程序是專為識別易受攻擊的正則表達式設計的，其識別方法為 通過針對成千上萬的隨機輸入計算正則表達式，並標記完成處理所需時間長度不可接受的輸入 。
（注意：在本文中，我假設您熟悉正則表達式的語法。如果您不熟悉此語法，可能需要閱讀 “.NET Framework 正則表達式”這篇文章（網址為 msdn.microsoft.com/library/hs600312） 來補充這些知識，如果要深入研究，請閱讀 Jeffrey Friedl 編寫的參考手冊《精通正則表達 式第 3 版》[O’Reilly，2006]。
回溯：問題的根源
從本質上講，存在兩種不同類型的正則表達式引擎：確定性有窮自動機 (DFA) 引擎和非確 定性有窮自動機 (NFA) 引擎。這兩種引擎類型的完整差異分析超出本文范圍，我們僅著重探討 以下兩個方面：
NFA 引擎是回溯引擎。與對輸入字符串中的每個字符最多計算一次的 DFA 不同，NFA 引擎 可以對輸入字符串中的每個字符計算多次。（我將在稍後說明此回溯計算算法的計算原理。） 回溯方法具有諸多優勢，因為這些引擎可以處理更復雜的正則表達式，如包含向後引用或捕獲 括號的正則表達式。它也具有一些缺點，因為其處理時間大大超過 DFA 的處理時間。
Microsoft .NET Framework System.Text.RegularExpression 使用 NFA 引擎。
回溯的一個重要負面影響是，雖然正則表達式可以相當快速地確定肯定匹配（即，輸入字符 串與給定正則表達式匹配），但確定否定匹配（輸入字符串與正則表達式不匹配）所需的時間 更長。實際上，此引擎必須確定輸入字符串中沒有任何可能的“路徑”與正則表達式匹配，這 意味著必須對所有路徑進行測試。
利用簡單的非分組正則表達式，確定否定匹配所花的時間並不是一個大問題。例如，假設要 匹配的正則表達式為：
^\d+$
如果整個輸入字符串僅包含數字字符，則這是一個相當簡單的匹配正則表達式。^ 和 $ 字 符分別表示字符串的開頭和結尾，表達式 \d 表示數字字符，+ 指示將有一個或多個字符匹配 。我們使用 123456X 作為輸入字符串測試此表達式。
此輸入字符串很明顯不是匹配項，因為 X 不是數字字符。但此示例正則表達式必須計算多 少個路徑才能得出此結論呢？它會在此字符串開頭處開始計算，發現字符 1 是一個有效的數字 字符，與此正則表達式匹配。然後它會移動到字符 2，該字符也匹配。因此，在此時，此正則 表達式與字符串 12 匹配。接下來，它會嘗試 3（匹配 123），依次類推，直到到達 X，該字 符不匹配。
但是，由於我們的引擎是回溯 NFA 引擎，它不會在此點上停止。而是從其當前的匹配 (123456) 返回到其上一個已知的匹配 (12345)，然後從那裡再次嘗試匹配。由於 5 後面的下 一個字符不是此字符串的結尾，因此，此正則表達式不是匹配項，它會返回到其上一個已知的 匹配 (1234)，然後再次嘗試匹配。按這種方式進行所有匹配，直到此引擎返回到其第一個匹配 (1)，發現 1 後面的字符不是此字符串的結尾。此時，正則表達式停止，沒有找到任何匹配。
總的說來，此引擎計算了六個路徑：123456、12345、1234、123、12 和 1。如果此輸入字 符串再增加一個字符，則引擎會多計算一個路徑。因此，此正則表達式是相對於字符串長度的 線性算法，不存在導致 DoS 的風險。對其模式使用 ^\d+$ 的 System.Text.RegularExpressions.Regex 對象計算速度非常快，足以迅速拆分計算大量輸入字 符串（超過 10,000 個字符）。
現在，讓我們更改此正則表達式，以對數字字符分組：
^(\d+)$
