如何避免.NET RegEx類中的無限循環？

獲得一個簡單的任務來獲取XPath表達式並返回一個匹配（可能）所選節點的父節點的前綴。如何避免.NET RegEx類中的無限循環？

例子：

/aaa/bbb  => /aaa 
/aaa/bbb/ccc => /aaa/bbb 
/aaa/bbb/ccc[@x='1' and @y="/aaa[name='z']"] => /aaa/bbb

由於方括號內的模式可能包含引號內支架，我決定嘗試用正則表達式來實現這一目標。這裏有一個代碼片段：

string input = 
    "/aaa/bbb/ccc[@x='1' and @y=\"/aaa[name='z'] \"]"; 
              // ^-- remove space for no loop 
string pattern = @"/[a-zA-Z0-9]+(\[([^]]*(]"")?)+])?$"; 

System.Text.RegularExpressions.Regex re = 
    new System.Text.RegularExpressions.Regex(pattern); 
bool ismatch = re.IsMatch(input); // <== Infinite loop in here 
// some code based on the match

因爲模式是比較有規律，我找了「/」後indentifier其次是在字符串的結尾（....）$

相匹配的可選的組？

該代碼似乎工作，但爲輸入字符串使用不同的值，我發現只需插入一個空間（在註釋中顯示的位置），.NET IsMatch函數進入無限循環，將所有它獲得的CPU。

現在無論這個正則表達式模式是否是最好的（我有更復雜但簡化它來顯示問題），這似乎表明，使用正則表達式與任何不平凡的可能是非常危險的。

我錯過了什麼嗎？有沒有辦法防止正則表達式匹配中的無限循環？

來源

2009-07-29 Dror Harari

一般來說，是不是等同於暫停問題？ – 2009-07-29 14:29:31

好吧，讓我們打破這則：

Input: /aaa/bbb/ccc[@x='1' and @y="/aaa[name='z'] "] 
Pattern: /[a-zA-Z0-9]+(\[([^]]*(]")?)+])?$

（我假設你的意思是\」在C＃轉義的字符串，而不是「」 ......從VB.NET翻譯）

首先，/[A-ZA-Z0-9] +將吞噬通過第一方括號，留下：

Input: [@x='1' and @y="/aaa[name='z'] "]

外組（\ [（[^]] *（] 「」）？）+]）？$「應該匹配，如果有0或者在EOL之前有1個實例。所以讓我們打破內部，看看它是否匹配任何東西。

的「[」被吞併馬上，留給我們：

Input: @x='1' and @y="/aaa[name='z'] "] 
Pattern: ([^]]*(]")?)+]

打破圖案：匹配0或多個非]字符，然後在匹配「] 0或1次，並繼續這樣做，直到你不能，然後試圖找到併吞噬一個]之後。

的模式匹配，基於[^] *，直到它到達]。

由於有]和之間的空間「，就不能狼吞虎嚥無論這些字符，但？後（]」）允許它反正返回true。

現在我們已經成功匹配（[^] *（]「）？）一次，但+說我們應該試圖保持它匹配任意次數的，我們可以！

這給我們留下了：

Input: ] "]

這裏的問題是，這種輸入可以匹配（[^] *（] 「？））的倍無限而沒有被吞噬了，而」 + 「將迫使它保持試。

你基本上匹配「1或更多」的情況下，你可以匹配「0或1」的東西，其次是「0或1」的其他東西。由於剩餘的輸入既不兩個子模式的存在，它不斷匹配0 [^]] \ *和0（]「）？無限循環。

輸入從未被吞噬，和圖案後的「+」永遠不會被評估。其餘

（但願我得到了SO-轉義的正則表達式逃逸正上方。）

來源

2009-07-29 21:37:57 richardtallent

那麼這是生產力（對我） - 謝謝理查德。我的結論是： 1.從外部源獲取一個正則表達式模式是危險的，可以很容易地軟管應用 2.即在.NET正則表達式不檢測無限循環，並且也沒有提供一種方式來限制處理 3.不同的正則表達式引擎可以給出不同的結果，所以即使語法相同，某些語義也可能不同（可移植性註釋）謝謝。 – 2009-07-29 22:19:19

我認爲你看到的差異是由於正則表達式的不同方言，而不是其他引擎中的花式無限循環檢測。核心問題是包裝一些可以匹配*空文本*無數次的東西。任何變化的（x？）+或（x？）*都可能是危險的，因爲輸入正確。重構你的模式應該讓你得到你所需要的東西，而不會造成無限循環的潛力。無論語言如何，本課總是要防禦性地針對任意用戶輸入進行編程。 – richardtallent 2009-07-30 06:48:30

它顯示使用代碼與任何不平凡的可能是有風險的。您創建的代碼可能導致無限循環，並且RegEx編譯器不得不執行。自從第一個20 IF X = 0 THEN GOTO 10以來沒有做過任何新的事情。

如果您在特定邊緣情況下擔心此問題，可以爲RegEx生成一個線程，然後在合理的執行時間。

來源

2009-07-29 14:32:42 richardtallent

我覺得這個答案是有效的。我嘗試過的其他RegEx引擎沒有進入無限循環（例如，試試http://www.regular-expressions.info/javascriptexample.html上的在線JavaScript RegEx測試程序，您會發現它的工作原理很好）。這個正則表達式很簡單，我發現它的_expected_ failure模式（當沒有找到匹配時）是一個無限循環並不重要。線程的想法也沒有用。我應該在任何提供外部RegEx的地方使用這個想法嗎？我不這麼認爲。我認爲這可能是RegEx中的一個錯誤（或者是一個巨大的漏洞）。 – 2009-07-29 19:18:03

要回答原來的問題（即如何避免使用正則表達式的無限循環），使用.Net 4.5可以輕鬆實現這一點，因爲您可以簡單地將時間傳遞給Regex方法。有一個內部計時器可以停止正則表達式循環母雞的超時和養RegexMatchTimeoutException

例如，你會做以下

string input = "/aaa/bbb/ccc[@x='1' and @y=\"/aaa[name='z'] \"]"; 
string pattern = @"/[a-zA-Z0-9]+(\[([^]]*(]"")?)+])?$"; 
bool ismatch = Regex.IsMatch(input, pattern, RegexOptions.None, TimeSpan.FromSeconds(5));

您可以瞭解更多詳情

退房 MSDN

來源

2014-10-16 20:11:29

這裏的問題是，這種輸入可以匹配（[^]] *（]「）？）無限次地沒有被吞噬，」+「會強制它繼續嘗試。

這是.NET RegEx實現中的一個漏洞。正則表達式不會像那樣工作。當你把它們變成自動機時，你會自動得到這樣的事實：空字符串的無限重複仍然是一個空字符串。

換句話說，任何沒有bug的正則表達式引擎都會立即執行這個無限循環並繼續處理其餘的正則表達式。

如果你願意，正則表達式就是這樣一種有限的語言，它有可能（並且容易）檢測和避免這種無限循環。

來源

2016-10-25 09:42:50

如何避免.NET RegEx類中的無限循環？

回答

相關問題