Perl正则表达式引擎存在漏洞？

Question

我一直在尝试编写正则表达式来验证文件，以确保其遵循特定格式。该文件应该有一个version();行，然后是一个或多个element();块。

这是一个有效文件的示例：

version(1.0);

element
(
);

element
(
);

element
(
);

作为测试，我创建了以下Perl示例：

use strict;
use warnings;

my $text = <<'END_TEXT';
version(1.0);

element
(
);

garbage <--- THIS SHOULD NOT MATCH!

element
(
);

element
(
);

END_TEXT

my $rx_defs = qr{(?(DEFINE)
    (?<valid_text>
        \A\s*(?&version)\s*
        (?: (?&element) \s* )+
        \s*\Z
    )
    (?<version>
        version\(.+?\);
    )
    (?<element>
        element\s*
        (?&element_body);
    )
    (?<element_body>
        \( (?: [^()]++ | (?&element_body) )* \)
    )
)}xms;

if ($text =~ m/(?&valid_text)$rx_defs/) {
    print "match";
}

正如您所看到的，文本中有一行“垃圾”文本，应该使其无效，但是由于某种原因，Perl仍然认为这个文本是有效的！当我运行这段代码时，它会产生以下输出：

match

我花了几个小时的时间来追踪我的正则表达式哪里出了问题，但我就是看不出来。我甚至使用了一个在线正则表达式测试工具来测试这个正则表达式，根据测试结果，我的正则表达式应该没问题！（如果您想查看在格式正确时它是否匹配正确，请尝试删除“垃圾”行。） 这让我整整一天都感到困惑，并让我怀疑Perl正则表达式引擎本身是否存在错误。请问有人能告诉我为什么这会匹配而不应该匹配吗？

我正在使用perl v5.20.1

- tjwrona1992

---

这一部分看起来有些可疑： version\(.+?\); - 括号中可能包含元素和垃圾内容。考虑限制内容，例如[^)]+。 - amon

看起来问题解决了...但是怎么做到的呢？非贪婪匹配应该在满足条件后立即停止！ - tjwrona1992

一个非常酷的正则表达式，毫无疑问，正则表达式是一个伟大的工具，毫无疑问...但我不禁要说：这很难，而可以通过使用处理这些嵌套/平衡分隔符的工具来避免。 （在您之前的问题中，此答案的确切观点。） - zdim

提示：这从来不是引擎/语言/编译器的错误，而总是用户的错误。好吧...除非...但那只是可能导致行为问题的长长列表中的最后一件事。（我会重新考虑这样的标题；你真的确定吗？） - zdim

无论是perl出了问题还是regex101.com出了问题，它们的结果不一致。 - tjwrona1992

Answer 1

来自PCRE文档http://www.pcre.org/current/doc/html/pcre2compat.html：

8. 子程序调用（无论是递归还是非递归）在PCRE2 10.23版本之前被视为原子组，但从10.30版本开始，这种情况发生了改变，现在支持回溯到子程序调用中，就像Perl一样。

regex101使用PHP运行PCRE。根据http://php.net/manual/en/pcre.installation.php，PHP仅支持PCRE1（8.x分支）。因此，regex101不支持回溯到子程序调用。

...这正是这里发生的事情：

• we go into (?&valid_text>) and try to match \A\s*(?&version)\s*
• \A (beginning-of-string) and \s* (optional whitespace) are simple
• (?&version) does version\(.+?\);

• this matches the following part of the input:

  version();
  
  element
  (
  );
  

  version( is matched literally. The next character, ), is consumed by .+? (which requires at least one character to match). Then .+? slowly consumes more and more characters (it's non-greedy) until it reaches );. The first time this happens is after consuming ; element (, so that's where we stop for now.

• the (?&version) call returns
• we consume any following whitespace
• the next part is (?: (?&element) \s* )+, i.e. one or more element, each followed by optional whitespace
• (?&element) does element\s*, i.e. it must start with element
• our current position in the input is garbage ..., so this fails

此时正则表达式引擎尝试回溯。在PCRE < 10.30中，唯一可以回溯的部分是\s*（即“可选空白”位），但匹配较少的空白字符也不能导致成功匹配，因此整个过程很快失败。

然而，在Perl中，我们可以回溯到子程序调用：我们重新进入(?&version)，让.+?匹配更多字符（直到找到下一个出现的);为止），然后重试(?&element)。这最终使(?&version)消耗垃圾和以下element，从而允许整个正则表达式成功匹配。

“有人能告诉我为什么这会匹配，而不应该吗？”

我不明白你为什么认为它不应该匹配。:-)

PHP中它不匹配的唯一原因是它使用的旧PCRE版本的限制。

- melpomene

---

我试图解析的真正文本在version(<some other text here>)的括号中间有文本。看起来我的例子可能过于简化了，但即使是其他文本也可以被.+?匹配到。我猜这是正确的行为，尽管它非常令人困惑。 - tjwrona1992

@tjwrona1992，当你在正则表达式中使用.*或者.+时，这可能会导致一个潜在的错误。如果需要整个正则表达式匹配成功，.*可以跳过任何文本（除非它被(?> )组或者(*PRUNE)动词等所限制）。注意：贪婪模式不影响正则表达式是否匹配，只影响匹配的长度。 - melpomene

有道理，我以前从未意识到这一点，所以现在知道了真的很好。我一直以为将它设为非贪婪模式会使其停止在那里。 - tjwrona1992

Answer 2

非贪婪匹配不会在满足条件后立即停止，它会尽快继续匹配。如果正则表达式的其余部分匹配失败，回溯仍然会发生 - 但对于非贪婪量词，回溯意味着更多的匹配。

避免这种情况的一种可能是通过控制回溯来实现。例如，您可能希望一旦 version 初始匹配成功后就禁止回溯。我们可以通过使用 (?> ...) 结构来实现这一点。它将独立匹配包含的模式与外部模式。如果剩余模式失败，则回溯将不会继续进入包含的模式，而是跳过整个包含的模式。描述这一点有点困难，请参见perldoc perlre 获取详细信息。

将 + 添加到量词中 (如 ++, ?+, *+) 具有类似于 (?> ...) 的效果。在高效的正则表达式中，建议使用这些不需要回溯的量词和 (?>...) 组。

具体地说，将以下内容替换：

(?<valid_text>
    \A\s*(?&version)\s*
    (?: (?&element) \s* )+
    \s*\Z
)

使用

(?<valid_text>
    \A\s*(?>(?&version))\s*
    (?: (?&element) \s* )++
    \s*\Z
)

作为另一种选择，您可以使用(*PRUNE)回溯控制动词。一旦遇到PRUNE命令，就不会发生超过该点的后退。这将确认已选择的备选方案的匹配结果。

(?<valid_text>
    \A\s*(?&version)\s* (*PRUNE)
    (?: (?&element) \s* )+
    \s*\Z
)

- amon