停止失控的正则表达式

Question

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

我对如何修改它的建议不感兴趣.我知道它可以被修改,所以它不会破坏等,但我正在运行单个正则表达式对数千个输入,所以修改它意味着我需要在所有输入上重新测试它.不太实际.

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

Answer 1

Perl的内置alarm功能不足以打破长时间运行的正则表达式,因为Perl不会为内部操作码内的警报超时提供机会. alarm根本无法穿透它.

在某些情况下,最明显的解决方案是fork在进行太长时间后使用子进程并将其计时alarm.这篇PerlMonks文章演示了如何超时分叉进程: Re:脚本超时

CPAN 上有一个名为Sys :: SigAction的Perl模块,它有一个被调用的函数timeout_call,它将使用不安全的信号中断长时间运行的正则表达式.然而,RE引擎并未设计为被中断,并且可能处于不稳定状态,这可能导致大约10%的时间出现seg-fault.

下面是一些示例代码,演示了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引擎允许的语法,你可以使用Perl模块re :: engine :: RE2来处理RE2 C++库.该引擎保证线性时间搜索,但它提供的功能不如Perl的内置引擎.RE2方法首先通过提供线性时间保证来避免整个问题.

但是,如果你不能使用RE2(可能是因为你的正则表达式的语义要求太高),fork/alarm方法可能是确保你保持控制的最安全的方法.

(顺便说一句,这个问题,我的回答的一个版本是crossposted到PerlMonks.)