共用方式為

  • 發行項

本文章是由機器翻譯。

安全性簡報

規則運算式拒絕服務攻擊與防禦

Bryan Sullivan

在十一月 2009年的問題，我撰寫文章標題為 「 XML 拒絕的服務攻擊和防禦 」 (msdn.microsoft.com/magazine/ee335713)，我所描述一些特別有效拒絕服務 (DoS) 攻擊技術，對 XML 剖析器。 收到很多關於這份文件的電子郵件的讀者想要知道更，從它真的鼓勵我人了解如何嚴重的 DoS 攻擊可以是。

我相信在接下來的四到五年內作為特殊權限提升攻擊變成更難執行因為要增加採用的記憶體保護等資料執行防止 (DEP)]、 [地址空間配置隨機 (ASLR)，] 和 [隔離] 及 [特殊權限縮減技巧的攻擊者將會轉換其焦點到 blackmail 的 DoS 攻擊。 開發人員可以繼續保持超前攻擊趨勢曲線和今天定址潛在的未來 DoS 向量來保護他們的應用程式。

其中一個那些潛在的未來 DoS 向量是規則運算式 DoS。 在開啟 Web 應用程式安全性專案 (OWASP) 以色列會議 2009 Checkmarx 象架構設計人員俊 Roichman 和資深程式設計師 Adar Weidman 呈現一些絕佳的研究主題的規則運算式 DoS 或 「 ReDoS 」。研究揭露，以便小時或是多評估，可能需要花時間相當短的攻擊字串 (少於 50 個字元) 可以利用不良書面的規則運算式。 在最壞狀況案例處理時間是實際指數表示單一字元加入字串會加倍處理時間，輸入字串中字元的數目。

本文章中，我將說明如何成為 Regex 容易遭受這些攻擊。 我也會展示程式碼的模糊測試 (Fuzzer 一個 Regex)，設計用來識別易受攻擊 regexes 評估對數千個隨機的輸入，並標示是否輸入值的任何需要一個讓人無法接受長的時間來完成處理的測試公用程式。

(附註：這篇文章我假設您熟悉規則運算式語法。 如果不符合上述情況，您可能要筆刷，以藉由讀取發行項 「.NET Framework 規則運算式 」 在 msdn.microsoft.com/library/hs600312，或更深層的俯衝，參閱 Jeffrey Friedl ’s 絕佳參考書籍，「 掌握規則運算式第三版 」 [O’Reilly 2006])

原路返回：根目錄的問題

有基本上是兩種不同類型的規則運算式引擎：決定性的有限機械戰士 (DFA) 引擎與非決定性有限機械戰士 (NFA) 引擎。 這兩個引擎類型之間差異的完整分析已超出本文範圍 ； 我們只需要專注於兩個事實：

  1. 引擎 NFA 會回溯引擎。 不像評估的輸入字串中的每個字元最多一次的 DFAs NFA 引擎可以評估輸入字串中的每個字元多次。 (我稍後示範這個回溯評估演算法的運作方式)。回溯的方法有好處，因為這些引擎可以處理更複雜 regular] 運算式例如那些包含反向參考或擷取括號。 它也有缺點，因為它們的處理時間可以遠超過，DFAs。
  2. Microsoft.NET Framework System.Text.RegularExpression 類別使用 NFA 引擎。

原路返回一個重要的副作用是，雖然 regex 引擎可以相當快速地確認正數的符合項目 (也就是輸入的字串不會符合給定的 regex)，確認 (輸入的字串不符合 regex) 負相符項目可能要花上更久的相當一點時間。 在實際上，引擎必須確認都不可能透過輸入字串的 「 路徑 」 相符，表示所有的路徑必須要測試的 regex。

使用簡單的非群組規則運算式，確認負的相符項目所花費的時間不是非常大的問題。 比方說假設要針對符合規則運算式是：

^\d+$

這是相當簡單的 regex 符合如果整個輸入的字串會進行的數字的字元。 ^ 和 $ 字元開頭與結尾的字串分別代表、 運算式 \d 代表數字的字元和 + 表示一或多個字元會符合。 let’s 測試此運算式使用 123456X 作為輸入的字串。

這個輸入的字串是很明顯地不相符的項目，因為 X 並非數字字元。 不過範例 regex 會有多少路徑來評估前來這個結論呢？ 它會啟動字串的開頭其評估，請參閱字元 1 是有效的數值字元，及符合 regex。 它會再移至字元 2，也會與相符。 讓 regex 此時已比對字串 12。 接下來它會重試 3 (和符合 123)，依此類推直到它有不符合的 X。

不過，因為我們引擎回溯 NFA 引擎它並不會提供最多此時。 而是，從它目前的配對 (123456) 備份以它上次已知的良好配對 (12345)，並再次嘗試從該處。 因為後 5 下一個字元不是字串的結尾，regex 不相符的項目，它會備份它先前上次已知的良好配對 (1234)，並再次嘗試。 就會一直等到引擎取得回至其第一個符合項目 (1)，並尋找的字元後 1 不是字串的結尾。 此時 regex 提供最多 ； 在找不相符。

所有在所有引擎評估六個路徑：123456、 12345、 1234，123、 12 和 1。 如果輸入的字串必須被一個字元長的時間，引擎會有評估一個更多的路徑。 因此這個規則運算式是線性的演算法，針對字串的長度並不是造成的風險 DoS。 System.Text.RegularExpressions.Regex 物件使用 ^ \d+$ 其模式比對是快速到幾乎立即清除透過甚至龐大的輸入字串 (超過 10,000 個字元)。

現在 let’s 變更為上數字的字元群組的 [規則運算式：

^(\d+)$

這並不會大幅變更評估的結果，它只是可讓開發人員存取任何符合項目為所擷取的群組。 (這項技巧可以用來更複雜的規則運算式您可能要套用重複運算子，但是在這個特定案例中，它有沒有值)新增群組括號在這種情況下不會大幅改變運算式 ’s 執行速度可能。 測試對輸入 123456X 圖樣仍使引擎評估只是六個不同的路徑。 但是，這種情況是大幅不同，如果我們對 regex 進行更多的小變更:

^(\d+)+$

額外 + 字元之後群組運算式 (\d+) 會告訴 regex 引擎來比對任何數目的擷取群組。 引擎同前進行 123456 來取得前原路返回到 12345。

以下是 [事情取得 「 有趣 」 (如 horribly 危險)。 而非只檢查後 5 下一個字元不是字串的結尾，引擎會將下一個字元，作為新擷取的 6 分組，並開始 rechecking 從該處。 一旦該路由失敗，它會取消最多 1234年，然後試著以不同的擷取群組 56，然後每 5 和 6 個為個別的擷取群組。 最終結果是，引擎實際結束向上評估 32 不同的路徑。

如果我們現在評估字串加入一個更多的數字字元，引擎將必須評估 64 路徑 — 兩次為許多 — 來判斷不 ’s 相符的項目。 這是由 regex 引擎執行工時的量增加了指數。 攻擊者可以提供相對較短的輸入的字串 — 30 個字元或操作 — 並強制引擎至處理序數百個數以百萬計的向上代表小時或天將的路徑。

播放 dirty 洗衣

它 ’s 錯誤夠當應用程式具有 DoS 能指數 regexes tucked 開在伺服器端程式碼中。 它甚至更糟的是 ’s 當應用程式會通告它的用戶端程式碼中的弱點。 許多 ASP.NET 驗證器控制項衍生自包括 RegularExpressionValidator 的 System.Web.UI.WebControls.BaseValidator 自動將執行中 JavaScript 用戶端上相同的驗證邏輯，.NET 程式碼在伺服器上所顯示的一樣。

大部分的時間這是一件好事。 它 ’s 良好節省使用者送出表單至伺服器，只是以讓它在驗證程式被拒絕，因為使用者輸入錯誤的輸入的欄位的來回行程時間。 它 ’s 良好太儲存在伺服器的處理時間。 不過，如果應用程式在其伺服端程式碼中使用不正確的 regex，該錯誤的 regex 也將用於其用戶端程式碼中，而且現在它會讓攻擊者找出該 regex，並為它開發為攻擊字串極為容易。

比方說說我建立新的 Web 表單，並將一個文字方塊和一個 RegularExpressionValidator 新增到該表單。 我將驗證器 ’s ControlToValidate 屬性設定為文字方塊的名稱，然後將其 ValidationExpression 設定其中一個錯誤 regexes 我討論：

this.RegularExpressionValidator1.ControlToValidate = "TextBox1";

this.RegularExpressionValidator1.ValidationExpression = @"^(\d+)+$";

如果我現在在瀏覽器中開啟此頁面，並檢視其來源，我會看到下列的 JavaScript 程式碼，接近以頁面的底部：

<scripttype="text/javascript">

//< ![CDATA[

var RegularExpressionValidator1 = document.all ? 

  document.all["RegularExpressionValidator1"] : 

  document.getElementById("RegularExpressionValidator1");

RegularExpressionValidator1.controltovalidate = "TextBox1";

RegularExpressionValidator1.validationexpression = "^(\\d+)+$";

//]] >

</script>

它沒有，給整個世界，以查看：在指令碼區塊的最後一行普通視野指數的 regex。

更多問題模式

當然 ^(\d+)+$ is not the only bad regular expression in the world. 基本上，包含與本身重複出現的重複群組運算式任何規則運算式將會受影響。 例如，這包括 regexes：

^(\d+)*$
^(\d*)*$
^(\d+|\s+)*$

在另外包含替代的子運算式重疊的地方另一個替代任何群組也是易受攻擊：

^ (\d|\d\d)+$
^(\d|\d?)+$

如果您像先前的範例運算式在中看到您的程式碼現在，可能可以識別為易受攻擊只是從查看它。 但您可能會錯過中一個長的弱點變得更加複雜的 (和更逼真的) 的運算式：

^ ([0-9a-是-Z]([-. \w]*[0-9a-zA-Z])*@(([0-9a-zA-Z])+([-\w]*[0-9a-zA-Z])*\.)+ [一層是-Z] {2,9}) $

這是規則運算式，在規則運算式程式庫的網站 (regexlib.com)，要用來驗證電子郵件地址上找到。 不過，它 ’s 也容易受到攻擊。 您可能會發現這項弱點，透過手動的程式碼檢查或不可能。 一較佳的技巧，找出這些問題是必要的且的 ’s 將我接下來討論。

在您的程式碼中尋找錯誤 Regexes

在理想的情況下，會尋找在您程式碼中的指數 regexes 編譯時間，並警告您有關它們的方法。 想必，要 regex 字串剖析和分析的潛在弱點，您會需要另一個的 regex。 這個時候，我感覺像 regex addict：「 我 don’t 需要協助，我只需要更多 regexes 」!sadly，我 regex 技術並非最多到撰寫來分析 regexes regex 的任務。 如果您認為您有此程式碼，傳送給我的工作，而且我是快樂給予您信用卡等下個月 ’s 安全性 Briefs 欄中。 在此同時因為我 don’t 有一個方法，可在編譯時期偵測錯誤 regexes，我做下一個最佳的事：我撰寫 regex 模糊測試 (Fuzzer)。

模糊是提供來嘗試使其失敗的應用程式 ’s 輸入到隨機的格式不正確資料的程序。 更 fuzzing 反覆項目您執行，您到一個錯誤，所以 ’s 很常見的小組執行千分位或數以百萬計的反覆項目每輸入愈好機會。 Microsoft 安全性小組發現這是非常有效的方法來尋找 Bug，所以安全性開發生命週期小組完成了模糊所有的產品和服務小組的需求。

我模糊測試 (Fuzzer)，而言，我想要模糊 (Fuzz) 到我的規則運算式的隨機輸入的字串。 我啟動藉由定義為我的 regex testInputValue 方法，請在檢查 regex const 字串和 runTest 的方法，就會收集隨機輸入餵送可 testInputValue 的字串。

const string regexToTest = @"^(\d+)+$";



static void testInputValue(string inputToTest)

{

  System.Text.RegularExpressions.Regex.Match(inputToTest, regexToTest);

}



void runTest()

{

  string[] inputsToTest = {};



  foreach (string inputToTest in inputsToTest)

  testInputValue(inputToTest);

}

請注意 ’s 還來產生 fuzzed 的輸入的值沒有程式碼 ； 我很快就得到的。 同時也請注意程式碼 doesn’t 檢查傳回值從 Regex.Match 造成困擾。 這是因為我實際上 don’t 處理或未輸入是否符合模式。 我在這種情況下關心的就是是否 regex 引擎太長而無法決定輸入是否符合。

通常 fuzzers 用來嘗試尋找可利用來攻擊的特殊權限提高的弱點，但一次，在這種情況下我 ’m 只尋找 DoS 弱點有興趣。 我只是 can’t 餵送我測試應用程式資料，以查看如果它損毀 ； 我必須要能夠偵測是否鎖定。 雖然它不可能大多數的科學方法，我可以完成這可以有效地藉由在不同的背景工作執行緒上依序執行每個 regex] 測試，並設定該執行緒 ’s 完成的等候逾時值。 如果執行緒不會未完成其處理在合理的時間，內說五秒的時間才能測試單一輸入，我們假設規則運算式已被 DoS ’d。 我新增一個 ManualResetEvent 及相應， 所示修改 testInputValue 和 runTest 方法圖 1.

圖 1測試使用不同的背景工作執行緒

static ManualResetEvent threadComplete = new ManualResetEvent(false);



static void testInputValue(object inputToTest)

{

  System.Text.RegularExpressions.Regex.Match((string)inputToTest, 

    regexToTest);

  threadComplete.Set();

}



void runTest()

{

  string[] inputsToTest = {};



  foreach (string inputToTest in inputsToTest)

  {

    Thread thread = new Thread(testInputValue);

    thread.Start(inputToTest);



    if (!threadComplete.WaitOne(5000))

    {

      Console.WriteLine("Regex exceeded time limit for input " + 

        inputToTest);

      return;

    }



    threadComplete.Reset();

  }



  Console.WriteLine("All tests succeeded within the time limit.");

}

現在它 ’s 產生輸入的值的時間。這是聽起來比實際更困難。如果我只是產生完全隨機資料，’s 不太可能它的任何會符合足夠的 regex，以顯示一項弱點。範例如果我測試 regex ^ (\d+)+$ 與輸入 XdO(*iLy@Lm4p$, the regex will instantly not match and the problem will remain hidden.我需要產生 ’s 相當接近至何種應用程式預期會很有用，測試的輸入，為此，我需要一種方法來產生符合給定的 regex 的隨機資料。

資料產生計劃，以救

幸運的是，功能中沒有可以執行僅具有的 Visual Studio 資料庫專案:資料產生計畫。如果您使用 Visual Studio 小組套件，您也可以存取這項功能。資料產生計畫用來快速地填入測試資料的資料庫。他們可以使用隨機字串或數值填滿資料表，或者 (或者幸好為我們) 比對的字串指定規則運算式。

您必須先在 SQL Server 2005 或 2008年在其中您可以產生測試資料的資料庫中建立資料表。一旦，完成回來入 Visual Studio 並建立新的 SQL Server 資料庫專案。編輯資料庫專案屬性，以提供您的資料庫的連接字串。一旦您輸入連接字串，並測試以確定它的確可以作用，回到 [方案總管] 中，並將新的資料產生計畫項目加入至專案。這個時候，您應該看到 類似圖 2.


圖 2Visual Studio 中一個資料產生計劃項目

現在選擇資料表和您要填入模糊測試 (Fuzzer) 輸入資料的資料行。在 [資料表] 區段設定數的測試應該值產生 (插入資料行資料列)。我稍早撰寫 fuzzers 通常測試數百個千分位或數以百萬計的反覆項目來嘗試找出問題。雖然我通常核准此層級之 rigor，它這個 regex 模糊測試 (Fuzzer) 的目的 ’s 麻煩。如果將 Regex 鎖，它要這麼做一些幾百測試反覆項目內。我建議將資料列設定為 200，插入值，但如果您想要測試多，請隨意。

在 [欄] 區段現在設定為 [規則運算式產生器，然後輸入您想要測試做為資料行 ’s 屬性] 索引標籤中的 [運算式] 屬性值的 regex 模式值。它 ’s 一點要注意的是運算式屬性 doesn’t 支援每個合法的規則運算式字元。can’t 輸入開始和結束行錨點 ^ 和 $ (或更準確您可以將它們，輸入但產生器會產生常值 ^ 或輸入測試中的 $ 字元)。只要將這些字元保留。您找到 在規則運算式產生器所支援的運算子的完整清單msdn.microsoft.com/library/aa833197(VS.80).

更大的問題是運算式屬性也 doesn’t 支援常見的速記標記法，例如 \d 的數字或 \w 字的字元。如果您的 regex 會使用這些，需要取代其等價的字元類別：[0-9] 代替 \d [A-是-Z0-9_] \w 而的等等。如果需要取代 \s (空白字元) 您可以在它的位置中輸入常值的空間。

資料庫專案中的您最後一個工作，就是實際將資料庫填入測試資料，根據您的規格。如此做，請選擇 [資料 | DataGenerator | 產生的資料] 功能表項目或只是按下 F5。

加入攻擊

回在將模糊測試 (Fuzzer) 程式碼修改 runTest 方法，因此它會提取資料庫中產生的測試資料。您可能會認為完成之後，但事實上 ’s 進行一項更重要的變更。如果您執行模糊測試 (Fuzzer) 現在，甚至對已知不正確的 regex，例如 ^(\d+)+$, it will fail to find any problems and report that all tests succeeded.這是因為產生的所有測試資料都是有效的符合項目，為您的 regex。

請記得稍早所述 NFA regex 引擎可以相當快速地確認正數的符合項目和該問題真的只會發生負的相符項目上。此外，因為 NFAs ’ 回溯本質屬於只時，會發生的問題有大量的比對字元開頭的輸入和不正確字元出現在結尾。如果不正確的字元出現在輸入字串前面，會立即完成測試。

對模糊測試 (Fuzzer) 程式碼進行最後的變更是附加到測試輸入兩端的錯誤字元。字串陣列，包含數字、 字母、 標點符號與空白字元做：

 

string[] attackChars = { "0", "1", "9", "X", "x", "+", 

"-", "@", "!", "(", ")", "[", "]", "\\", "/", 

"?", "<", ">", ".", ",", ":", ";", " ", "" };

現在修改程式碼，以便從資料庫擷取每個輸入的字串測試與每個附加到它這些攻擊字元。 因此第一個輸入的字串會測試以 0 字元，然後附加到它，以 1 字元，後面再加上等。 一旦該輸入的字串已經過測試與每個攻擊字元，移動至下一個輸入字串，並測試與每個攻擊字元。

foreach (string inputToTest in inputsToTest)

{

  foreach (string attackChar in attackChars)

  {

    Threadthread = new Thread(testInputValue);

    thread.Start(inputToTest + attackChar);

...

 

現在您有兩個問題

沒有著名的引號由 ex Netscape 工程李明 Zawinski 有關規則運算式：

「 當因遇到一個問題而困惑有些人認為，‘ 我知道，我使用規則運算式 ’現在它們有兩個問題 」。

雖然我關於為 Mr regexes nowhere 不久一樣 cynical。Zawinski，我會承認它可以只是要寫入一個正確的 regex 很少是安全的對抗 DoS 攻擊的正確 regex 相當具挑戰性。我鼓勵您檢查所有指數複雜性您 regexes，並使用 fuzzing 技術來確認您的發現。

Bryan Sullivan* 是 Microsoft 安全性開發生命週期] 小組的安全性程式管理員，他專門在 Web 應用程式和.NET 安全性問題。他是 「 艾傑克斯安全性 」 (Addison-Wesley，2007年) 作者。*

多虧來檢閱本文的下列的技術專家：Barclay Hill、 Michael Howard、 Ron Petrusha 及 Justin van Patten