如何避免.NET RegEx类中的无限循环？

StackOverflow https://stackoverflow.com/questions/1200655

  •  05-07-2019
  •  | 
  •  

题

获得一个简单的任务来获取XPath表达式并返回一个与（可能）选择的节点的父节点匹配的前缀。

示例：

/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]+(\[([^]]*(]"")?)+])?<*>quot;;

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

因为模式是相当规则的，所以我找了'/'后面跟着一个标识符，然后是一个在字符串末尾匹配的可选组（....）？$

代码似乎工作但是为输入字符串使用不同的值，我发现通过简单地插入一个空格（在注释中显示的位置），.NET IsMatch函数进入无限循环，占用所有它获得的CPU。

现在无论这个正则表达式模式是否是最好的（我有更复杂但是简化它来显示问题），这似乎表明使用RegEx与任何不重要的事情可能是非常危险的。

我错过了什么吗？有没有办法防止正则表达式匹配中的无限循环？

有帮助吗？

解决方案

好的，让我们分解一下：

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

（我假设你的意思是“在你的C＃-escaped字符串中，而不是”......从VB.NET翻译？）

首先， / [a-zA-Z0-9] + 将吞噬第一个方括号，留下：

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

外部组（\ [（[^]] *（]＆quot;＆quot;）？）+]）？$＆quot;如果在EOL之前有0或1个实例，则应匹配。所以，让我们进入内部，看看它是否与任何东西相匹配。

“[”]马上狼吞虎咽，留下我们：

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

分解模式：匹配0个或更多非] 字符然后匹配＆quot;] 0或1次，并继续这样做，直到你不能。然后尝试找到并吞噬] 。

模式基于 [^]] * 匹配，直到达到] 。

由于] 和＆quot; 之间存在空格，因此它不能吞噬这些字符，而是？ >（）＆quot;）无论如何都允许它返回true。

现在我们已成功匹配（[^]] *（]＆quot;）？）一次，但 + 表示我们应该尝试保持匹配我们可以的次数。

这给我们留下了：

Input: ] "]

这里的问题是这个输入可以匹配（[^]] *（]＆quot;）？） 无限次而不会被吞噬， ＆QUOT + QUOT;将迫使它继续尝试。

你基本上匹配“1或更多”您可以匹配“0或1”的情况后面跟着“0或1”的东西其他的东西。由于两个子模式都不存在于剩余的输入中，因此它在无限循环中保持与 [^]] \ * 的0和（]＆quot;）？的0匹配

输入永远不会被吞噬，而“+”之后的其余模式也会被吞噬。永远不会得到评估。

（希望我在正上方得到了正则表达式的逃脱。）

其他提示

  

这里的问题是这个输入可以无限次地匹配（[^]] *（]“”），而不会被吞噬，并且“+”将迫使它继续尝试。

这是.NET的RegEx实现中的一个错误。正则表达式就是这样。当你把它们变成自动机时，你会自动得到一个无限重复的空字符串仍然是空字符串的事实。

换句话说，任何非bug的正则表达式引擎都会立即执行此无限循环并继续使用正则表达式的其余部分。

如果您愿意，正则表达式是一种有限的语言，可以（并且很容易）检测并避免这种无限循环。

它表明使用代码包含任何不重要的内容都可能存在风险。您创建的代码可能导致无限循环，并且RegEx编译器有义务。自从第一个20 IF X = 0 THEN GOTO 10以来没有做过任何新的事情。

如果您在特定边缘情况下担心这种情况，可以为RegEx生成一个线程，然后在一段合理的执行时间后将其终止。

要回答原始问题（即如何避免使用正则表达式进行无限循环），使用.Net 4.5可以轻松实现这一点，因为您可以简单地将时间传递给Regex方法。有一个内部计时器，当超时到期时将停止正则表达式循环并引发RegexMatchTimeoutException

例如，您可以执行以下操作

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

您可以查看 MSDN 了解更多详情

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top