當(dāng)用戶需要搜索和替換文本時(shí)，正則表達(dá)式就會(huì)派上用場(chǎng)。然而，在某些情況下，它們可能會(huì)導(dǎo)致系統(tǒng)變慢，甚至容易受到ReDoS攻擊。 ?

簡(jiǎn)介?

ReDoS是DoS攻擊的一種子類型。ReDoS攻擊的目的是通過(guò)低效的正則表達(dá)式停止應(yīng)用程序或使其變慢。 ?

ReDoS攻擊分為兩種類型： ?

（1）將帶有惡意模式的字符串傳遞給應(yīng)用程序。然后，這個(gè)字符串被用作正則表達(dá)式，從而導(dǎo)致ReDoS攻擊。 ?

（2）將特定格式的字符串傳遞給應(yīng)用程序。然后，這個(gè)字符串由一個(gè)易受攻擊的正則表達(dá)式計(jì)算，從而導(dǎo)致ReDoS攻擊。 ?

任何ReDoS攻擊的要點(diǎn)都是在應(yīng)用程序中使用易受攻擊的正則表達(dá)式。將某種格式的字符串傳遞給正則表達(dá)式會(huì)導(dǎo)致其計(jì)算時(shí)間過(guò)長(zhǎng)。 ?

如果ReDoS攻擊成功，則正則表達(dá)式計(jì)算將導(dǎo)致災(zāi)難性的回溯。這是正則表達(dá)式引擎中回溯函數(shù)的結(jié)果，該函數(shù)遍歷可能的字符串匹配，直到找到正確的字符串。如果沒(méi)有正確的匹配，正則表達(dá)式將不會(huì)停止，直到遍歷所有可能的選項(xiàng)。而所有可能選項(xiàng)的完整迭代將導(dǎo)致正則表達(dá)式計(jì)算的時(shí)間過(guò)長(zhǎng)。這被稱為災(zāi)難性回溯。?

如果正則表達(dá)式包含至少一個(gè)可能導(dǎo)致大量匹配選項(xiàng)的子表達(dá)式，則它很容易發(fā)生災(zāi)難性的回溯。?

災(zāi)難性回溯：真實(shí)的例子?

以下檢查幾個(gè)正則表達(dá)式的漏洞。?

在這里編寫了一個(gè)小程序，它顯示了正則表達(dá)式的計(jì)算時(shí)間如何依賴于計(jì)算字符串中的字符數(shù)的圖形。在接下來(lái)的示例中，將使用這個(gè)程序展示災(zāi)難性的回溯。?

示例1 ?

以下看一個(gè)簡(jiǎn)單的合成例子：?

(x+)+y ?

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

（1）正則表達(dá)式的輸入接受與指定模式一一對(duì)應(yīng)的字符串。同時(shí)，每個(gè)后續(xù)字符串的長(zhǎng)度都比前一個(gè)字符串多一個(gè)字符。 ?

（2）正則表達(dá)式的輸入接受不匹配模式的字符串(字符串末尾沒(méi)有y字符)。同時(shí)，每個(gè)后續(xù)字符串的長(zhǎng)度都比前一個(gè)字符串多一個(gè)字符。 ?

實(shí)驗(yàn)結(jié)果如下:?

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

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

由上可見，第一組字符串立即被處理。然而，第二組的處理速度呈指數(shù)級(jí)增長(zhǎng)！為什么會(huì)這樣? ?

問(wèn)題是，在第一種情況下，正則表達(dá)式在第一次嘗試時(shí)就找到了匹配項(xiàng)。在第二種情況下處理字符串時(shí)，一切都變得非常復(fù)雜。x+模板可以匹配任意數(shù)量的x個(gè)字符。(x+)+模板可以適合由一個(gè)或多個(gè)對(duì)應(yīng)于x+的子字符串組成的字符串。因此，有許多選項(xiàng)可以將字符串與正則表達(dá)式匹配。它們的數(shù)量取決于由x個(gè)字符組成的子字符串的長(zhǎng)度。每當(dāng)正則表達(dá)式?jīng)]有找到y(tǒng)字符時(shí)，它就開始檢查下一個(gè)選項(xiàng)。只有在檢查了所有這些之后，正則表達(dá)式才會(huì)給出答案——沒(méi)有找到匹配項(xiàng)。 ?

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

幸運(yùn)的是，并非所有正則表達(dá)式都容易受到災(zāi)難性回溯的影響。如果正則表達(dá)式滿足以下條件，則會(huì)受到ReDoS攻擊：?

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

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

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

示例2 ?

結(jié)果發(fā)現(xiàn)(x+)+y表達(dá)式是脆弱的。現(xiàn)在稍微改變一下，添加一個(gè)檢查另一個(gè)字符的存在: ?

(x+z)+y ?

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

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

示例3 ?

現(xiàn)在看看下一個(gè)正則表達(dá)式：?

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

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

上述選項(xiàng)都不會(huì)導(dǎo)致災(zāi)難性的回溯。然而，如果處理“newDate（1111111111111）”類型的字符串，就會(huì)發(fā)生這種情況。?

圖4正則表達(dá)式檢查與模式不匹配的字符串的執(zhí)行時(shí)間（字符串末尾沒(méi)有右括號(hào)）?

在此將再次看到災(zāi)難性的回溯。發(fā)生這種情況是因?yàn)椋?？\d+）*子表達(dá)式，其中包含\d+子表達(dá)式。“*”或“+”量詞應(yīng)用于兩個(gè)子表達(dá)式，并且同一字符串可以與它們中的每一個(gè)匹配，例如111。?

將這些觀察結(jié)果與前面檢查的帶有漏洞的正則表達(dá)式的條件進(jìn)行比較：?

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

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

newDate\（（-？\d+）*\）regex在實(shí)際項(xiàng)目RestSharp庫(kù)中造成了一個(gè)漏洞（CVE-2021-27293）。?

示例4 ?

作為最后一個(gè)例子，在一個(gè)更復(fù)雜的正則表達(dá)式中尋找漏洞： ?

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

這個(gè)表達(dá)式的任務(wù)是查找表示文件或目錄路徑列表的字符串。這列表中的每個(gè)元素之間用逗號(hào)和空格字符分隔。列表項(xiàng)可以由對(duì)應(yīng)于以下兩種類型之一的路徑表示：?

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

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

因此，對(duì)應(yīng)于模式的字符串可能是這樣的: ?

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

正則表達(dá)式將計(jì)算這樣的字符串而不會(huì)出現(xiàn)任何問(wèn)題。?

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

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

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

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

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

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

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

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

當(dāng)查看這個(gè)字符串的簡(jiǎn)化版本時(shí)，災(zāi)難性的回溯漏洞變得很明顯。?

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

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

因此，脆弱表達(dá)式的兩個(gè)條件都滿足。?

在此強(qiáng)調(diào)一下在^(([A-Z]:|\\main)(\\[^\\]+)*(，\s)?)+$正則表達(dá)式中導(dǎo)致災(zāi)難性回溯的主要因素： ?

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

如果至少缺少其中的一個(gè)，則正則表達(dá)式絕對(duì)安全。?

如何避免災(zāi)難性回溯?

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

選項(xiàng)1 ?

添加正則表達(dá)式處理字符串的執(zhí)行時(shí)間限制。在.Net中，可以在調(diào)用靜態(tài)方法或初始化新的正則表達(dá)式對(duì)象時(shí)設(shè)置matchTimeout參數(shù)。?

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正則表達(dá)式的執(zhí)行時(shí)間被限制為1秒?

選項(xiàng)2 ?

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

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

對(duì)于標(biāo)記為原子組的表達(dá)式，將禁用回溯功能。因此，在所有可能的匹配選項(xiàng)中，一個(gè)原子組總是只匹配一個(gè)包含最大字符數(shù)的子字符串。?

盡管原子組是防止災(zāi)難性回溯的可靠方法，但建議謹(jǐn)慎使用它們。在某些情況下，使用原子組會(huì)降低正則表達(dá)式計(jì)算的準(zhǔn)確性。?

圖7標(biāo)記為原子組的子表達(dá)式不再容易受到災(zāi)難性回溯的影響?

選項(xiàng)3 ?

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

后者有兩個(gè)子表達(dá)式:(-?\d+)*和\d+。\d+子表達(dá)式包含在(-?\d+)*中。同一子字符串可以匹配這兩個(gè)子表達(dá)式。安全的等效函數(shù)允許只與一個(gè)模板匹配任何子字符串，因?yàn)楸仨殭z查模板\d{…}之間的'-'字符。 ?

結(jié)論?

以下進(jìn)行總結(jié)：?

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

（2）由于災(zāi)難性的回溯，應(yīng)用程序變慢。如果有大量用于將輸入字符串與正則表達(dá)式匹配的選項(xiàng)，并且其中沒(méi)有正確的選項(xiàng)，則會(huì)發(fā)生這種情況。?

（3）如果正則表達(dá)式包含至少一個(gè)易受攻擊的子表達(dá)式，可能導(dǎo)致大量匹配選項(xiàng)，則正則表達(dá)式很容易發(fā)生災(zāi)難性的回溯。 ?

（4）通過(guò)檢查正則表達(dá)式中的以下條件，可以識(shí)別該表達(dá)式中的漏洞：?

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

b.有一個(gè)字符串可以同時(shí)滿足這兩個(gè)子表達(dá)式。 ?

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