regex - 停止失控的正则表达式

Question

有没有办法阻止失控的正则表达式？

我对如何修改它的建议不感兴趣。我知道可以对其进行修改，使其不会中断等，但是我正在针对数千个输入运行单个正则表达式，因此修改它意味着我需要在所有输入上重新测试它。不是很实用。

所以确切的问题是:是否有某种形式的计时器可用于终止需要超过 X 秒才能完成的正则表达式？

Answer 1

Perl 的内置 alarm不足以打破长期运行的正则表达式，因为 Perl 没有在内部操作码内提供警报超时的机会。 alarm根本无法穿透它。

在某些情况下，最明显的解决方案是 fork使用 alarm 处理一个子进程并在其运行时间过长后将其超时.这篇 PerlMonks 帖子演示了如何使 fork 进程超时:Re: Timeout on script

CPAN 上有一个名为 Sys::SigAction 的 Perl 模块有一个名为 timeout_call 的函数，这将使用不安全的信号中断长时间运行的正则表达式。但是，RE 引擎并非设计为中断，并且可能会处于不稳定状态，这可能导致大约 10% 的时间段故障。

下面是一些示例代码，展示了 Sys::SigAction 成功地突破了正则表达式引擎，并展示了 Perl 的 alarm无法这样做:

use Sys::SigAction 'timeout_call';
use Time::HiRes;


sub run_re {
  my $string = ('a' x 64 ) . 'b';

  if( $string =~ m/(a*a*a*a*a*a*a*a*a*a*a*a*)*[^Bb]$/ ) {
    print "Whoops!\n";
  }
  else {
    print "Ok!\n";
  }
}

print "Sys::SigAction::timeout_call:\n";
my $t = time();
timeout_call(2,\&run_re);
print time() - $t, " seconds.\n";

print "alarm:\n";
$t = time();

eval {
  local $SIG{ALRM} = sub { die "alarm\n" };
  alarm 2;
  run_re();
  alarm 0;
};

if( $@ ) {
  die unless $@ eq "alarm\n";
}
else {
  print time() - $t, " seconds.\n";
}

输出将类似于以下内容:

$ ./mytest.pl
Sys::SigAction::timeout_call:
Complex regular subexpression recursion limit (32766) exceeded at ./mytest.pl line 11.
2 seconds.
alarm:
Complex regular subexpression recursion limit (32766) exceeded at ./mytest.pl line 11.
^C

您会注意到，在第二次调用中——应该超时为 alarm 的调用。 ，我终于不得不 ctrl-C因为 alarm不足以打破 RE 引擎。

Sys::SigAction 的最大警告是，即使它能够打破长期运行的正则表达式，因为 RE 引擎不是为此类中断而设计的，整个过程可能会变得不稳定，从而导致段错误。虽然它不会每次都发生，但它可能会发生。这可能不是你想要的。

我不知道你的正则表达式是什么样的，但它是否符合 RE2 engine 允许的语法，您可以使用 Perl 模块， re::engine::RE2使用 RE2 C++ 库。这个引擎保证了线性时间搜索，尽管它提供的语义不如 Perl 的内置引擎强大。 RE2 方法通过提供线性时间保证首先避免了整个问题。

但是，如果您无法使用 RE2(可能是因为您的正则表达式的语义对其要求过高)，则 fork/alarm 方法可能是确保您保持控制的最安全方法。

(顺便说一句，这个问题和我的答案的一个版本被交叉发布到 PerlMonks 。)