當用戶需要搜索和替換文本時，正則表達式就會派上用場。然而，在某些情況下，它們可能會導致系統變慢，甚至容易受到ReDoS攻擊。 ?

簡介?

ReDoS是DoS攻擊的一種子類型。ReDoS攻擊的目的是通過低效的正則表達式停止應用程序或使其變慢。 ?

ReDoS攻擊分為兩種類型： ?

（1）將帶有惡意模式的字符串傳遞給應用程序。然后，這個字符串被用作正則表達式，從而導致ReDoS攻擊。 ?

（2）將特定格式的字符串傳遞給應用程序。然后，這個字符串由一個易受攻擊的正則表達式計算，從而導致ReDoS攻擊。 ?

任何ReDoS攻擊的要點都是在應用程序中使用易受攻擊的正則表達式。將某種格式的字符串傳遞給正則表達式會導致其計算時間過長。 ?

如果ReDoS攻擊成功，則正則表達式計算將導致災難性的回溯。這是正則表達式引擎中回溯函數的結果，該函數遍歷可能的字符串匹配，直到找到正確的字符串。如果沒有正確的匹配，正則表達式將不會停止，直到遍歷所有可能的選項。而所有可能選項的完整迭代將導致正則表達式計算的時間過長。這被稱為災難性回溯。?

如果正則表達式包含至少一個可能導致大量匹配選項的子表達式，則它很容易發生災難性的回溯。?

災難性回溯：真實的例子?

以下檢查幾個正則表達式的漏洞。?

在這里編寫了一個小程序，它顯示了正則表達式的計算時間如何依賴于計算字符串中的字符數的圖形。在接下來的示例中，將使用這個程序展示災難性的回溯。?

示例1 ?

以下看一個簡單的合成例子：?

(x+)+y ?

比較一下(x+)+y表達式在兩種情況下的計算時間：?

（1）正則表達式的輸入接受與指定模式一一對應的字符串。同時，每個后續字符串的長度都比前一個字符串多一個字符。 ?

（2）正則表達式的輸入接受不匹配模式的字符串(字符串末尾沒有y字符)。同時，每個后續字符串的長度都比前一個字符串多一個字符。 ?

實驗結果如下:?

圖1字符串匹配模式(x+)+y的正則表達式的執行時間?

圖2字符串不匹配(x+)+y模式(在結尾缺少y字符)的正則表達式的執行時間?

由上可見，第一組字符串立即被處理。然而，第二組的處理速度呈指數級增長！為什么會這樣? ?

問題是，在第一種情況下，正則表達式在第一次嘗試時就找到了匹配項。在第二種情況下處理字符串時，一切都變得非常復雜。x+模板可以匹配任意數量的x個字符。(x+)+模板可以適合由一個或多個對應于x+的子字符串組成的字符串。因此，有許多選項可以將字符串與正則表達式匹配。它們的數量取決于由x個字符組成的子字符串的長度。每當正則表達式沒有找到y字符時，它就開始檢查下一個選項。只有在檢查了所有這些之后，正則表達式才會給出答案——沒有找到匹配項。 ?

下表顯示了xxxx字符串與(x+)+y正則表達式的幾種可能匹配：

幸運的是，并非所有正則表達式都容易受到災難性回溯的影響。如果正則表達式滿足以下條件，則會受到ReDoS攻擊：?

（1）有兩個子表達式，其中一個子表達式包含另一個子表達式。此外，以下量詞之一應用于它們中的每一個：“*”、“+”、“*？”、“＋？”、在前面的示例中，（x+）+子表達式包含x+。?

（2）有一個字符串可以與兩個子表達式匹配。例如，字符串xxxx可以同時適合x+和(x+)+模板。 ?

(\d?|....|[1-9])+類型的表達式是一個小例外。這里的(\d?|....|[1-9])+表達式包含子表達式\d?和(1-9)。它們通過'|'運算符枚舉。這些子表達式也可以適合相同的字符串，例如111。在本例中，應用'?的量詞到子表達式之一也會導致漏洞。 ?

示例2 ?

結果發現(x+)+y表達式是脆弱的?，F在稍微改變一下，添加一個檢查另一個字符的存在: ?

(x+z)+y ?

現在有了(x+z)+子表達式，xz和xxxxz字符串可以與這個表達式匹配。這個子表達式包括x+子表達式，它可以對應于x、xxxx等字符串。正如人們所看到的，這些子表達式不能與相同的值匹配。因此，即使不滿足第二個條件，也不存在災難性的回溯。?

圖3使用一組字符串“中斷”正則表達式的嘗試失敗。它們中的每一個都對應于x+子表達式或(x+z)+子表達式。 ?

示例3 ?

現在看看下一個正則表達式：?

newDate\((-?\d+)*\)?

這個正則表達式有一個任務——搜索newDate(12-09-2022)類型的子字符串。能說這個正則表達式是安全的嗎?不。除了正確的字符串，正則表達式還會考慮糾正newDate(8-911-111-11-11)甚至newDate(11111111111)字符串。然而，要理解問題的本質，這樣的表達就已經足夠了。 ?

上述選項都不會導致災難性的回溯。然而，如果處理“newDate（1111111111111）”類型的字符串，就會發生這種情況。?

圖4正則表達式檢查與模式不匹配的字符串的執行時間（字符串末尾沒有右括號）?

在此將再次看到災難性的回溯。發生這種情況是因為（-？\d+）*子表達式，其中包含\d+子表達式?！?”或“+”量詞應用于兩個子表達式，并且同一字符串可以與它們中的每一個匹配，例如111。?

將這些觀察結果與前面檢查的帶有漏洞的正則表達式的條件進行比較：?

（1）有兩個子表達式，其中一個包含另一個子表達式。以下量詞之一應用于它們中的每一個：“*”、“+”、“*？”、“＋？”、｛…｝”。（-？\d+）*）子表達式包含\d+；?

（2）有一個字符串可以與兩個子表達式匹配。例如，1111字符串可以同時適合\d+模板和(-?\d+)*)。?

newDate\（（-？\d+）*\）regex在實際項目RestSharp庫中造成了一個漏洞（CVE-2021-27293）。?

示例4 ?

作為最后一個例子，在一個更復雜的正則表達式中尋找漏洞： ?

^(([A-Z]:|\\main)(\\[^\\]+)*(,\s)?)+$?

這個表達式的任務是查找表示文件或目錄路徑列表的字符串。這列表中的每個元素之間用逗號和空格字符分隔。列表項可以由對應于以下兩種類型之一的路徑表示：?

（1）完整路徑，例如:D:\catalog\subcatalog\file.txt。 ?

（2）主文件夾的相對路徑，例如:\main\catalog\file.exe。 ?

因此，對應于模式的字符串可能是這樣的: ?

D:\catalog, C:\catalog\file.cs, \main\file.txt, \main\, project\main.csproj ?

正則表達式將計算這樣的字符串而不會出現任何問題。?

這同樣適用于幾乎所有不正確的字符串處理，例如: ?

D:\catalog\file.cs\catalog\file.cs\catalog\file.cs\catalog\file.cs\catalog\file.cs\catalog\file.cs\\\?

然而，如果將以下類型的字符串傳遞給正則表達式，情況就會改變: ?

D:\main\main\main\main\main\main\main\main\main\main\main\main\main\main\main\\\

圖5正則表達式在處理 D:\main ...\main\\\ format

檢查一下原始正則表達式（^（（[A-Z]：|\\main）（\\[^\\]+）*（，\s）？）+$）詳細信息。需要注意，相互跟隨的子表達式（[A-Z]：|\\main）和（\\[^\\]+）*可以與同一個\main字符串匹配。此外，以下子表達式（（，\s）？）可以忽略，因為`?'量詞允許不與該模板匹配。?

因此，可以簡化原始正則表達式，只檢查一種特殊情況——D:\main ...\main format: ?

^(([A-Z]:|\\main)(\\main)*)+$?

當查看這個字符串的簡化版本時，災難性的回溯漏洞變得很明顯。?

（1）有一個帶有“+”量詞的子表達式(([a-z]:|\\main)(\\main)*)+。這個子表達式包含帶有“*”量詞的(\\main)*。 ?

（2）兩個子表達式:(([A-Z]:|\\main)(\\main)*)+和(\\main)* 可以匹配相同的字符串，例如，\main\main\main。?

因此，脆弱表達式的兩個條件都滿足。?

在此強調一下在^(([A-Z]:|\\main)(\\[^\\]+)*(，\s)?)+$正則表達式中導致災難性回溯的主要因素： ?

• '+'量詞應用于（（[A-Z]：|\\main）（\\[^\\]+）*（，\s）？）+子表達式; ?
• '*'量詞應用于(\\[^\\]+)*子表達式; ?
• 子表達式（[A-Z]：|\\main）和（\\[^\\]+）*可以匹配相同的\main字符串；?
• (，\s)?子表達式可以省略，因為'?'的量詞。 ?

如果至少缺少其中的一個，則正則表達式絕對安全。?

如何避免災難性回溯?

以下了解保護正則表達式避免災難性回溯的主要方法。將使用newDate\((-?\d+)*\)作為例子。以下代碼是用C#編寫的。然而，類似的功能可能存在于其他支持正則表達式的編程語言中。?

選項1 ?

添加正則表達式處理字符串的執行時間限制。在.Net中，可以在調用靜態方法或初始化新的正則表達式對象時設置matchTimeout參數。?

C# ?
 RegexOptions options = RegexOptions.None;?
 TimeSpan timeout = TimeSpan.FromSeconds(1);?
 Regex pattern = new Regex(@"newDate\((-?\d+)*\)", options, timeout);?
 Regex.Match(str, @"newDate\((-?\d+)*\)", options, timeout);?

圖6正則表達式的執行時間被限制為1秒?

選項2 ?

使用原子組(?>…)： ?

C# ?
 Regex pattern = new Regex(@"newDate\((-?\d+)*\)", options, timeout);?

對于標記為原子組的表達式，將禁用回溯功能。因此，在所有可能的匹配選項中，一個原子組總是只匹配一個包含最大字符數的子字符串。?

盡管原子組是防止災難性回溯的可靠方法，但建議謹慎使用它們。在某些情況下，使用原子組會降低正則表達式計算的準確性。?

圖7標記為原子組的子表達式不再容易受到災難性回溯的影響?

選項3 ?

重寫正則表達式，用安全的等價子表達式替換不安全的子表達式。例如，要查找newDate（13-09-2022）類型的字符串，可以使用newDate\（（\d｛2｝-\d｛2｛-\d｛4｝）\），而不是newDate \（（-？\d+）*\）。?

后者有兩個子表達式:(-?\d+)*和\d+。\d+子表達式包含在(-?\d+)*中。同一子字符串可以匹配這兩個子表達式。安全的等效函數允許只與一個模板匹配任何子字符串，因為必須檢查模板\d{…}之間的'-'字符。 ?

結論?

以下進行總結：?

（1）正則表達式可能容易受到ReDoS攻擊，其目的是停止或減慢應用程序。 ?

（2）由于災難性的回溯，應用程序變慢。如果有大量用于將輸入字符串與正則表達式匹配的選項，并且其中沒有正確的選項，則會發生這種情況。?

（3）如果正則表達式包含至少一個易受攻擊的子表達式，可能導致大量匹配選項，則正則表達式很容易發生災難性的回溯。 ?

（4）通過檢查正則表達式中的以下條件，可以識別該表達式中的漏洞：?

a.有兩個子表達式，其中一個包含另一個子表達式。以下量詞之一應用于它們中的每一個：“*”、“+”、“*？”、“＋？”、{...}';?

b.有一個字符串可以同時滿足這兩個子表達式。 ?

原文標題：??Catastrophic Backtracking: How Can a Regular Expression Cause a ReDoS Vulnerability???,作者：Andrey Moskalev