當(dāng)用戶需要搜索和替換文本時，正則表達(dá)式就會派上用場。然而，在某些情況下，它們可能會導(dǎo)致系統(tǒng)變慢，甚至容易受到ReDoS攻擊。 ?
簡介?
ReDoS是DoS攻擊的一種子類型。ReDoS攻擊的目的是通過低效的正則表達(dá)式停止應(yīng)用程序或使其變慢。 ?
ReDoS攻擊分為兩種類型： ?
（1）將帶有惡意模式的字符串傳遞給應(yīng)用程序。然后，這個字符串被用作正則表達(dá)式，從而導(dǎo)致ReDoS攻擊。 ?
（2）將特定格式的字符串傳遞給應(yīng)用程序。然后，這個字符串由一個易受攻擊的正則表達(dá)式計算，從而導(dǎo)致ReDoS攻擊。 ?
任何ReDoS攻擊的要點都是在應(yīng)用程序中使用易受攻擊的正則表達(dá)式。將某種格式的字符串傳遞給正則表達(dá)式會導(dǎo)致其計算時間過長。 ?
如果ReDoS攻擊成功，則正則表達(dá)式計算將導(dǎo)致災(zāi)難性的回溯。這是正則表達(dá)式引擎中回溯函數(shù)的結(jié)果，該函數(shù)遍歷可能的字符串匹配，直到找到正確的字符串。如果沒有正確的匹配，正則表達(dá)式將不會停止，直到遍歷所有可能的選項。而所有可能選項的完整迭代將導(dǎo)致正則表達(dá)式計算的時間過長。這被稱為災(zāi)難性回溯。?
如果正則表達(dá)式包含至少一個可能導(dǎo)致大量匹配選項的子表達(dá)式，則它很容易發(fā)生災(zāi)難性的回溯。?
災(zāi)難性回溯：真實的例子?
以下檢查幾個正則表達(dá)式的漏洞。?
在這里編寫了一個小程序，它顯示了正則表達(dá)式的計算時間如何依賴于計算字符串中的字符數(shù)的圖形。在接下來的示例中，將使用這個程序展示災(zāi)難性的回溯。?
示例1 ?
以下看一個簡單的合成例子：?
(x+)+y ?
比較一下(x+)+y表達(dá)式在兩種情況下的計算時間：?
（1）正則表達(dá)式的輸入接受與指定模式一一對應(yīng)的字符串。同時，每個后續(xù)字符串的長度都比前一個字符串多一個字符。 ?
（2）正則表達(dá)式的輸入接受不匹配模式的字符串(字符串末尾沒有y字符)。同時，每個后續(xù)字符串的長度都比前一個字符串多一個字符。 ?
實驗結(jié)果如下:?
圖1字符串匹配模式(x+)+y的正則表達(dá)式的執(zhí)行時間?
圖2字符串不匹配(x+)+y模式(在結(jié)尾缺少y字符)的正則表達(dá)式的執(zhí)行時間?
由上可見，第一組字符串立即被處理。然而，第二組的處理速度呈指數(shù)級增長！為什么會這樣? ?
問題是，在第一種情況下，正則表達(dá)式在第一次嘗試時就找到了匹配項。在第二種情況下處理字符串時，一切都變得非常復(fù)雜。x+模板可以匹配任意數(shù)量的x個字符。(x+)+模板可以適合由一個或多個對應(yīng)于x+的子字符串組成的字符串。因此，有許多選項可以將字符串與正則表達(dá)式匹配。它們的數(shù)量取決于由x個字符組成的子字符串的長度。每當(dāng)正則表達(dá)式?jīng)]有找到y(tǒng)字符時，它就開始檢查下一個選項。只有在檢查了所有這些之后，正則表達(dá)式才會給出答案——沒有找到匹配項。 ?
下表顯示了xxxx字符串與(x+)+y正則表達(dá)式的幾種可能匹配：
幸運的是，并非所有正則表達(dá)式都容易受到災(zāi)難性回溯的影響。如果正則表達(dá)式滿足以下條件，則會受到ReDoS攻擊：?
（1）有兩個子表達(dá)式，其中一個子表達(dá)式包含另一個子表達(dá)式。此外，以下量詞之一應(yīng)用于它們中的每一個：“*”、“+”、“*？”、“＋？”、在前面的示例中，（x+）+子表達(dá)式包含x+。?
（2）有一個字符串可以與兩個子表達(dá)式匹配。例如，字符串xxxx可以同時適合x+和(x+)+模板。 ?
(d?|....|[1-9])+類型的表達(dá)式是一個小例外。這里的(d?|....|[1-9])+表達(dá)式包含子表達(dá)式d?和(1-9)。它們通過'|'運算符枚舉。這些子表達(dá)式也可以適合相同的字符串，例如111。在本例中，應(yīng)用'?的量詞到子表達(dá)式之一也會導(dǎo)致漏洞。 ?
示例2 ?
結(jié)果發(fā)現(xiàn)(x+)+y表達(dá)式是脆弱的。現(xiàn)在稍微改變一下，添加一個檢查另一個字符的存在: ?
(x+z)+y ?
現(xiàn)在有了(x+z)+子表達(dá)式，xz和xxxxz字符串可以與這個表達(dá)式匹配。這個子表達(dá)式包括x+子表達(dá)式，它可以對應(yīng)于x、xxxx等字符串。正如人們所看到的，這些子表達(dá)式不能與相同的值匹配。因此，即使不滿足第二個條件，也不存在災(zāi)難性的回溯。?
圖3使用一組字符串“中斷”正則表達(dá)式的嘗試失敗。它們中的每一個都對應(yīng)于x+子表達(dá)式或(x+z)+子表達(dá)式。 ?
示例3 ?
現(xiàn)在看看下一個正則表達(dá)式：?
newDate((-?d+)*)?
- 1.
這個正則表達(dá)式有一個任務(wù)——搜索newDate(12-09-2022)類型的子字符串。能說這個正則表達(dá)式是安全的嗎?不。除了正確的字符串，正則表達(dá)式還會考慮糾正newDate(8-911-111-11-11)甚至newDate(11111111111)字符串。然而，要理解問題的本質(zhì)，這樣的表達(dá)就已經(jīng)足夠了。 ?
上述選項都不會導(dǎo)致災(zāi)難性的回溯。然而，如果處理“newDate（1111111111111）”類型的字符串，就會發(fā)生這種情況。?
圖4正則表達(dá)式檢查與模式不匹配的字符串的執(zhí)行時間（字符串末尾沒有右括號）?
在此將再次看到災(zāi)難性的回溯。發(fā)生這種情況是因為（-？d+）*子表達(dá)式，其中包含d+子表達(dá)式。“*”或“+”量詞應(yīng)用于兩個子表達(dá)式，并且同一字符串可以與它們中的每一個匹配，例如111。?
將這些觀察結(jié)果與前面檢查的帶有漏洞的正則表達(dá)式的條件進(jìn)行比較：?
（1）有兩個子表達(dá)式，其中一個包含另一個子表達(dá)式。以下量詞之一應(yīng)用于它們中的每一個：“*”、“+”、“*？”、“＋？”、｛…｝”。（-？d+）*）子表達(dá)式包含d+；?
（2）有一個字符串可以與兩個子表達(dá)式匹配。例如，1111字符串可以同時適合d+模板和(-?d+)*)。?
newDate（（-？d+）*）regex在實際項目RestSharp庫中造成了一個漏洞（CVE-2021-27293）。?
示例4 ?
作為最后一個例子，在一個更復(fù)雜的正則表達(dá)式中尋找漏洞： ?
^(([A-Z]:|\main)(\[^\]+)*(,s)?)+$?
- 1.
這個表達(dá)式的任務(wù)是查找表示文件或目錄路徑列表的字符串。這列表中的每個元素之間用逗號和空格字符分隔。列表項可以由對應(yīng)于以下兩種類型之一的路徑表示：?
（1）完整路徑，例如:D:catalogsubcatalogfile.txt。 ?
（2）主文件夾的相對路徑，例如:maincatalogfile.exe。 ?
因此，對應(yīng)于模式的字符串可能是這樣的: ?
D:catalog, C:catalogfile.cs, mainfile.txt, main, projectmain.csproj ?
- 1.
正則表達(dá)式將計算這樣的字符串而不會出現(xiàn)任何問題。?
這同樣適用于幾乎所有不正確的字符串處理，例如: ?
D:catalogfile.cscatalogfile.cscatalogfile.cscatalogfile.cscatalogfile.cscatalogfile.cs\?
- 1.
然而，如果將以下類型的字符串傳遞給正則表達(dá)式，情況就會改變: ?
D:mainmainmainmainmainmainmainmainmainmainmainmainmainmainmain\
- 1.
圖5正則表達(dá)式在處理 D:main ...main\ format
檢查一下原始正則表達(dá)式（^（（[A-Z]：|\main）（\[^\]+）*（，s）？）+$）詳細(xì)信息。需要注意，相互跟隨的子表達(dá)式（[A-Z]：|\main）和（\[^\]+）*可以與同一個main字符串匹配。此外，以下子表達(dá)式（（，s）？）可以忽略，因為`?'量詞允許不與該模板匹配。?
因此，可以簡化原始正則表達(dá)式，只檢查一種特殊情況——D:main ...main format: ?
^(([A-Z]:|\main)(\main)*)+$?
- 1.
當(dāng)查看這個字符串的簡化版本時，災(zāi)難性的回溯漏洞變得很明顯。?
（1）有一個帶有“+”量詞的子表達(dá)式(([a-z]:|\main)(\main)*)+。這個子表達(dá)式包含帶有“*”量詞的(\main)*。 ?
（2）兩個子表達(dá)式:(([A-Z]:|\main)(\main)*)+和(\main)* 可以匹配相同的字符串，例如，mainmainmain。?
因此，脆弱表達(dá)式的兩個條件都滿足。?
在此強調(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á)式可以省略，因為'?'的量詞。 ?
如果至少缺少其中的一個，則正則表達(dá)式絕對安全。?
如何避免災(zāi)難性回溯?
以下了解保護(hù)正則表達(dá)式避免災(zāi)難性回溯的主要方法。將使用newDate((-?d+)*)作為例子。以下代碼是用C#編寫的。然而，類似的功能可能存在于其他支持正則表達(dá)式的編程語言中。?
選項1 ?
添加正則表達(dá)式處理字符串的執(zhí)行時間限制。在.NET中，可以在調(diào)用靜態(tài)方法或初始化新的正則表達(dá)式對象時設(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);?
- 1.
- 2.
- 3.
- 4.
- 5.
圖6正則表達(dá)式的執(zhí)行時間被限制為1秒?
選項2 ?
使用原子組(?>…)： ?
C# ?
Regex pattern = new Regex(@"newDate((-?d+)*)", options, timeout);?
- 1.
- 2.
對于標(biāo)記為原子組的表達(dá)式，將禁用回溯功能。因此，在所有可能的匹配選項中，一個原子組總是只匹配一個包含最大字符數(shù)的子字符串。?
盡管原子組是防止災(zāi)難性回溯的可靠方法，但建議謹(jǐn)慎使用它們。在某些情況下，使用原子組會降低正則表達(dá)式計算的準(zhǔn)確性。?
圖7標(biāo)記為原子組的子表達(dá)式不再容易受到災(zāi)難性回溯的影響?
選項3 ?
重寫正則表達(dá)式，用安全的等價子表達(dá)式替換不安全的子表達(dá)式。例如，要查找newDate（13-09-2022）類型的字符串，可以使用newDate（（d｛2｝-d｛2｛-d｛4｝）），而不是newDate （（-？d+）*）。?
后者有兩個子表達(dá)式:(-?d+)*和d+。d+子表達(dá)式包含在(-?d+)*中。同一子字符串可以匹配這兩個子表達(dá)式。安全的等效函數(shù)允許只與一個模板匹配任何子字符串，因為必須檢查模板d{…}之間的'-'字符。 ?
結(jié)論?
以下進(jìn)行總結(jié)：?
（1）正則表達(dá)式可能容易受到ReDoS攻擊，其目的是停止或減慢應(yīng)用程序。 ?
（2）由于災(zāi)難性的回溯，應(yīng)用程序變慢。如果有大量用于將輸入字符串與正則表達(dá)式匹配的選項，并且其中沒有正確的選項，則會發(fā)生這種情況。?
（3）如果正則表達(dá)式包含至少一個易受攻擊的子表達(dá)式，可能導(dǎo)致大量匹配選項，則正則表達(dá)式很容易發(fā)生災(zāi)難性的回溯。 ?
（4）通過檢查正則表達(dá)式中的以下條件，可以識別該表達(dá)式中的漏洞：?
a.有兩個子表達(dá)式，其中一個包含另一個子表達(dá)式。以下量詞之一應(yīng)用于它們中的每一個：“*”、“+”、“*？”、“＋？”、{...}';?
b.有一個字符串可以同時滿足這兩個子表達(dá)式。 ?
原文標(biāo)題：??Catastrophic Backtracking: How Can a Regular Expression Cause a ReDoS Vulnerability???,作者：Andrey Moskalev
