代码之家 › 专栏 › 技术社区 › pierroz

如何处理来自用户提交的regex的从不相关的匹配项

user-input regex .net c#

pierroz · 技术社区 · 17 年前

让我们考虑一下C中的以下两行(使用framework.net 3.5)

Regex regex = new Regex(@"^((E|e)t )?(M|m)oi (?<NewName>[A-Za-z]\.?\w*((\-|\s)?[A-Za-z]?\w{1,})+)$", RegexOptions.Compiled | RegexOptions.IgnoreCase);
Match m = regex.Match("moi aussi jaimerai etre un ordinateur pour pas m'Ã©nnerver ");

(抱歉,这是一个法语节目:)

当它们被执行时,进程会被卡在 Match() 方法,永远不会退出。我猜regex模式中的空白有一些问题,但是我想做的不是改变模式(实际上它是由我的工具的最终用户在程序外部设置的),而是能够停止进程(例如超时)。

是否有人知道这是.NET正则表达式的一个众所周知的问题,以及是否有一种简单的方法来解决它,或者我是否必须线程这些行并在需要时中止它们(当然我不想这样做)。

5 回复 | 直到 10 年前

Cerebrus 17 年前

我认为您应该简单地在一个单独的线程上启动regex匹配,并允许它在达到某个最大时间限制时中止。

Lieven Keersmaekers 17 年前

如果我在regexbuddy中输入表达式,它将显示以下消息

匹配尝试提前中止因为正则表达式也是复杂的。你计划使用的Regex引擎使用时可能无法处理它完全崩溃了。仰望 “灾难性的回溯” 帮助文件了解如何避免这种情况情况。

仰视 灾难性回溯 给出以下解释

失控正则表达式:灾难性回溯
考虑正则表达式(x+x+)+y。在你惊恐地尖叫说这个人为的例子应该是写为xx+y以精确匹配同样,没有那些非常嵌套的量词:假设每个“x” 代表更复杂的东西, 与某些字符串匹配都是“X”。请参阅有关HTML的部分下面的文件是一个真实的例子。

让我们看看你申请的时候会发生什么此regex到XXXXXXXXX Y。第一 X+将匹配所有10个X字符。这个第二个X+失败。第一个X+然后回溯到9场比赛, 第二个选择了剩余的X。该组现在匹配了一次。这个组重复,但第一次失败 X+。因为一次重复足够了,小组匹配。Y 匹配Y,整体匹配为找到了。正则表达式已声明功能,代码被发送到他的电脑爆炸了。几乎。

上面的正则表达式在y 主题字符串中缺少。当y失败时,regex引擎回溯。这个小组有一个它可以回溯到迭代中。这个第二个x+只匹配一个x,所以它无法回溯。但是第一个X+罐立即放弃一个X。第二个X+。匹配XX。小组又有一个迭代,下一个失败,并且 Y失败了。再次回溯, 第二个X+现在有一个回溯位置,缩小到与X匹配。该组尝试第二次迭代。第一个x+匹配,但第二个是卡在绳子的末端。再次回溯,第一个X+In 小组的第一次迭代减少了它本身有7个字符。第二个X+ 匹配XXX。失败的Y,第二个X+ 减为x x,然后减为x。现在, 组可以匹配第二个迭代, 每个X+有一个X。但这 (7,1),(1,1)组合也失败。所以它转到(6,4),然后转到(6,2)(1,1) 然后(6,1),(2,1),然后 (6,1),(1,2)然后我认为你开始去弄清楚。

如果你用一个10倍的字符串来尝试这个regex 在RegexBuddy的调试器中,需要 2558计算最终Y的步骤遗失了。对于一个11倍的字符串, 需要5118步。12个,需要 10238个步骤。很明显我们有这里是O(2^n)的指数复杂性。 21倍时,调试器在2.8倍时退出。百万步,诊断一个坏案例灾难性的回溯。

雷格斯巴迪原谅了这一点检测到它在转 和中止匹配尝试。 其他正则表达式引擎(如.NET)将继续运行永远 ,而其他人将与堆栈溢出(如Perl 版本5.10)。堆栈溢出为尤其是在窗户上,因为他们往往会向你提出申请消失而不留下痕迹或解释。如果你运行一个网络,要非常小心允许用户提供的服务他们自己的正则表达式。人很少有雷杰克斯的经验出奇制胜的技巧指数复正则表达。

我想你必须用代码来处理它。我建议你联系的作者 Regexbuddy 并询问需要什么来检测这种情况。

-1

John Saunders 17 年前

一般来说,正则表达式的时间可能比预期的要长。您应该尝试使用正则表达式来调整类似工具的调节器。

-1

Lucero 17 年前

问题是,您已经在regex中嵌套了“循环”,这使得它非常低效(因此,由于表达式的复杂性,它基本上需要永远)。

如果你说你想匹配什么,我可以试着找出一个更有效的正则表达式。

-1

bendecko Alex Perry 12 年前

在我看来,正则表达式的匹配度呈指数级增长。见 BCL blog .

最好的解决方案是在regex上设置一个超时,而不必纠结于线程。

看这里如何 strip out strings with timeout .