正则表达式中的灾难性回溯

Question

我正在尝试使用 RegEx 在文本中查找 URL。我找到了一个模式 here。这在大多数情况下效果很好，但我发现了一个奇怪的测试用例，它导致 Catastrophic Backtracking 错误。

你可以看到我的模式和一个测试用例here。在这种情况下它工作正常但如果你添加另一个“！”最后，它给你错误。

我想知道原因以及如何解决。

Answer 1

如果您只想知道如何使模式更安全并减少灾难性回溯的发生，您需要将每个 (?:x+|\(xxx\))* 模式替换为 (?:\(xxx\)|x)*。这大大减少了正则表达式引擎执行的步骤数。

因此，在这种情况下，您可以使用

(?i)\b((?:https?://|www\d{0,3}[.]|[a-z0-9.\-]+[.][a-z]{2,4}/)(?:\((?:\([^\s()<>]+\)|[^\s()<>])*\)|[^\s()<>])+(?:\((?:\([^\s()<>]+\)|[^\s()<>])*\)|[^\s`!()\[\]{};:'\".,<>?«»“”‘’]))

参见regex demo。

基本上，([^\s()<>]+|(\([^\s()<>]+\)))* 替换为匹配

的 (?:\((?:\([^\s()<>]+\)|[^\s()<>])*\)|[^\s()<>])+

(?: - non-capturing 组的开始：
- \( - 一个 ( 字符
- (?:\([^\s()<>]+\)|[^\s()<>])* - ( 出现零次或多次，除空格以外的任何一个或多个字符，(、)、< 和 >，然后是 ) 或除空格以外的单个字符，(、)、< 和 >
- \) - 一个 ) 字符
- | - 或
- [^\s()<>] - 除空格以外的任何字符，(、)、< 和 >
)+ - 出现一次或多次。

Answer 2

如果您查看 link(https://regex101.com/r/oPnn6n/1) 的旗帜部分上方。可以看到仅仅匹配一个字符串就用了49235步！！

要知道这里回溯的原因让我们分解一下表达式：

你的表达式可以写成：

(
(?: ~https?://~ | ~www\d{0,3}[.]~ | ~[a-z0-9.\-]+[.][a-z]{2,4}/~ )   <-Line1 with 3 conditions
(?: ~[^\s()<>]+~ | ~\(([^\s()<>]+|(\([^\s()<>]+\)))*\)~ )+       <-Line2 with 2 conditions
(?: ~\(([^\s()<>]+|(\([^\s()<>]+\)))*\)~ | ~[^\s`!()\[\]{};:\'".,<>?«»“”‘’]~ ) <-Line3 with 2 condition
)

让我们关注我在上面指出的三行，按条件我的意思是用布尔值 OR | 分隔的条件，它们被放在 ~ 之间以提高可读性（这不会与 on任何正则表达式，它只是为了可读性）。所以在 group1 中，我调用了 https?://、www\d{0,3}[.] 和 [a-z0-9.\-]+[.][a-z]{2,4}/ 这三个条件，接下来的两行也是如此。

现在让我们看看您的输入：https://test.com/test!!!!!!!!!!! 是如何被正则表达式引擎匹配的。

https:// 部分被 line1 的 condition1 匹配（消耗），因为它是一个布尔 OR，其他两个条件被跳过，正则表达式引擎移到 line2。
整个 test.com/test!!!!!!!!!!! 被第 2 行的条件 1 贪婪地匹配（消耗）。现在所有字符串都已被消耗 回溯开始，以便正则表达式引擎可以尝试将某些内容与第 3 行匹配。
引擎回溯一步（取消一个 !）并尝试将找到的 ! 与第 3 行匹配，第 3 行的条件都不匹配 !。所以引擎再次回到第 2 行。
此处条件 1 再次匹配 !，正则表达式引擎移动到第 3 行。

我假设这会重复直到达到某个限制并且引擎抛出错误。虽然我在这里可能是错的，但无论如何我希望你知道表达式的哪一部分导致回溯。

避免回溯的最佳方法是准确说明您要使用正则表达式匹配的内容。在您的情况下，您可以做的一件事是 simplify/remove 重复匹配条件。喜欢：https://regex101.com/r/I1u8Ho/1.

正则表达式中的灾难性回溯

Catastrophic Backtracking in RegEx

python

regex