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

Question

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

我想防止(a+)+邪恶的正义与他们的亲属.

为此,我正在寻找一种方法或现有的库,为给定的正则表达式和引擎生成"最坏情况"输入(基于NFA和DFA的引擎都在范围内).

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

对于我的用例,我很好找到可怕的输入(而不是最坏的可能),但很短.

Answer 1

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

引擎之间的差异

发动机类型

对于某些引擎，“最邪恶的”正则表达式仍然是良性的，以线性时间运行（或者O(n*m)正则表达式的长度和字符串的长度都可能变化的时间）。当然，其原因是实现。这些引擎不会回溯；相反，他们使用有限状态机（FSM）。

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

大多数旧的正则表达式引擎（如 sed）使用 FSM 匹配。有一些新引擎使用此实现，例如 Go。PCRE 甚至具有使用这种类型匹配的DFA 函数（在此处搜索“DFA” ）。

我的另一个答案也解决了两种实现之间潜在的速度差异。

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

优化

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

短路

在某些条件下，引擎也许能够快速判断匹配是不可能的。a*b?a*x在针对字符串运行正则表达式时aaaaaaaaaaaaaaaaaaaaaaaaaa，Regex101说：

你的比赛彻底失败了。这意味着引擎由于其内部优化，知道您的模式永远不会在任何位置匹配，因此甚至没有尝试匹配。

请记住，维基百科说正则表达式是邪恶的，尤其是与该字符串配对时。

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

修饰符

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

即使 PCRE（最优化的实现之一）在启用u和i修饰符的情况下也可能需要更多的步骤。有关此问题的更多信息，请参阅此处我的问题。最后，我发现只有某些角色才会触发这种行为。

分析字符串

字符串长度

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

贪婪与懒惰

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

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

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

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

暴力测试

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

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

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

设置超时

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

。网：

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

爪哇

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 )

设置允许脚本运行的秒数。如果达到此值，脚本将返回致命错误。默认限制为 30 秒，或者如果存在，max_execution_time则为php.ini.

调用时，set_time_limit()超时计数器从零重新启动。换句话说，如果超时默认为 30 秒，并且在脚本执行 25 秒后set_time_limit(20)进行调用，则脚本将在超时之前总共运行 45 秒。

珀尔

您不妨访问该链接，因为它就位于 Stack Overflow 上。