给定正则表达式的最差输入

Question

我想在我的代码库中自动测试正则表达式。

我想防范 (a+)+ 邪恶的正则表达式及其同类。

为此，我正在寻找为给定的正则表达式和引擎生成 "worst case" 输入的方法或现有库（基于 NFA 和 DFA 的引擎都在范围内）。

诚然，正则表达式是一种强大的语言，显然 [计算上] 很难找到任意正则表达式的最差输入，尤其是。如果使用反向引用，它甚至可能是不可判定的。

对于我的用例，我很乐意找到糟糕的（而不是最糟糕的）但又很短的输入。

Answer 1

正则表达式的最差输入因引擎而异。相同的正则表达式和字符串在一个引擎上可能根本不需要时间，但在另一个引擎上永远不会完成。

引擎之间的差异

引擎类型

对于某些引擎，"evilest" regex 仍然是良性的，运行ning 在线性时间（或 O(n*m) 时间，当正则表达式的长度和字符串的长度都可能会有所不同。）当然，这是实现的原因。这些引擎不会回溯；相反，他们使用有限状态机 (FSM)。

请注意，一些回溯实现使用 FSM，但仅作为中间步骤。不要让这让你感到困惑；他们不是 FSM。

大多数旧的正则表达式引擎（如 sed）使用 FSM 匹配。有一些新的引擎使用了这个实现，比如 Go。 PCRE 甚至具有使用此类匹配的 DFA 函数（搜索 "DFA" here）。

还解决了两种实现之间潜在的速度差异。

如果您真的担心恶意输入会影响正则表达式的速度，那么考虑使用 FSM 实现是明智的。不幸的是，FSM 没有其他实现那么强大；它缺乏对某些功能的支持，例如反向引用。

优化

恶其实有点主观。对一个正则表达式引擎有害的东西对不同的引擎可能不是有害的。如果优化了引擎，就可以挫败邪恶的阴谋。考虑到回溯引擎的潜在指数运行时间，优化对于回溯引擎尤为重要。

短路

在某些条件下，引擎可能能够快速确定匹配是不可能的。当运行将正则表达式 a*b?a*x 与字符串 aaaaaaaaaaaaaaaaaaaaaaaaaa 相对应时，Regex101 表示：

Your match failed outright. What this means is the engine, due to its internal optimizations, understood that your pattern would never match at any position, and thus did not even attempt to.

请记住 Wikipedia 表示正则表达式是邪恶的，尤其是与该字符串配对时。

当然，引擎很聪明，不需要回溯来确定匹配无效。它看到了一些非常明显的东西：正则表达式需要一个 x 才能匹配，但字符串中没有 x。

修饰符

我提到这一点是因为您可能不希望修饰符成为影响正则表达式性能的一个因素。但他们是。

即使是更优化的实现之一 PCRE，在启用 u 和 i 修饰符的情况下，也可能会采取更多的步骤。有关此的更多信息，请参阅我的问题 here。最后，我发现只有某些字符会触发此行为。

分析字符串

字符串长度

一般来说，长字符串会比短字符串慢。事实上，如果你发现一个长度为 x 的字符串导致灾难性的回溯，你可以通过增加字符串的长度来让它回溯更多一点。

贪婪与懒惰

比较这些正则表达式的速度：

.*b 在 aaaaaaaa...aaaaab
.*?b 在 aaaaaaaa...aaaaab
.*b 在 abaaaaaaa...aaaaa
.*?b 在 abaaaaaaa...aaaaa

本质上，当您认为需要进行大量匹配时，贪心匹配是最好的选择。当你只需要匹配一点点时，惰性匹配是最好的。

请注意，如果您将正则表达式更改为 a*b 或 a*?b，那么引擎可能会进行相当大的优化。

暴力测试

有几个框架专门用于尝试查找正则表达式中的漏洞。可能值得一试。

如果您想尝试制作自己的算法，我真的会建议一件事。尝试字典中的所有字符是不切实际的，特别是如果你想测试长字符串。

相反，请查看您的正则表达式以确定您应该测试哪些字符。如果您将 (a+)+ 作为您的正则表达式，则实际上只有两件事进入匹配：a 而不是 a。你真的可以想象只有两个字符：a 和 b（又名不是 a）当你生成你的字符串来进行暴力破解时。

设置超时

如果能够确保您的正则表达式在宇宙热寂之前完成，那就太棒了，对吧？一些正则表达式引擎确实有设置超时的方法。

.NET:

AppDomain domain = AppDomain.CurrentDomain;
  // Set a timeout interval of 2 seconds.
  domain.SetData("REGEX_DEFAULT_MATCH_TIMEOUT", TimeSpan.FromSeconds(2));

Java

Runnable runnable = new Runnable() {
     @Override
     public void run()
     {
        long startTime = System.currentTimeMillis();
        Matcher interruptableMatcher = pattern.matcher(new InterruptibleCharSequence(input));
        interruptableMatcher.find(); // runs for a long time!
        System.out.println("Regex took:" + (System.currentTimeMillis() - startTime) + "ms");
     }
  };
  Thread thread = new Thread(runnable);
  thread.start();
  Thread.sleep(500);
  thread.interrupt();

PHP

bool set_time_limit ( int $seconds )

Set the number of seconds a script is allowed to run. If this is reached, the script returns a fatal error. The default limit is 30 seconds or, if it exists, the max_execution_time value defined in the php.ini.

When called, set_time_limit() restarts the timeout counter from zero. In other words, if the timeout is the default 30 seconds, and 25 seconds into script execution a call such as set_time_limit(20) is made, the script will run for a total of 45 seconds before timing out.

Perl

您不妨访问 link，因为它就在 Stack Overflow 上。

给定正则表达式的最差输入

Worst input for given regular expression

regex

algorithm

performance-testing

analysis