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

我想保护自己免受(a+)+邪恶regexp及其亲属的伤害。

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

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

对于我的用例，我可以很好地找到糟糕的(而不是最糟糕的)但很短的输入。

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

发动机之间的差异

发动机类型

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

请注意，一些回溯实现使用FSM，但仅作为中间步骤。不要让这件事把你弄糊涂；它们不是FSM。

大多数旧的正则表达式引擎(如sed)都使用FSM匹配。有一些新引擎使用这个实现，比如Go。PCRE甚至有使用这种匹配的DFA函数(在这里搜索"DFA")。

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

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

优化

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

短路

在某些情况下，发动机可能能够快速确定不可能匹配。当针对字符串aaaaaaaaaaaaaaaaaaaaaaaaaa运行regexa*b?a*x时，Regex101表示：

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

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

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

修改器

我提到这一点是因为您可能不希望修饰符成为regex性能的一个因素。但事实确实如此。

即使是PCRE，一种更优化的实现，在启用u和i修饰符的情况下，也可能需要相当多的步骤。请在此处查看我的问题以了解更多信息。最后，我发现只有特定的角色才会触发这种行为。

分析字符串

字符串长度

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

贪婪与懒惰

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

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

本质上，当你认为需要大量匹配时，贪婪匹配是最好的。当你只需要搭配一点点的时候，懒惰的搭配是最好的。

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

Brute力测试

有几个框架是专门为查找正则表达式中的漏洞而设计的。尝试一下可能是值得的。

如果你想尝试制作自己的算法，我会建议你做一件事。尝试字典中的所有字符是不现实的，尤其是如果你想测试长字符串。

相反，查看正则表达式来确定应该测试哪些字符。如果您的正则表达式是(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 )

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

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

Perl

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

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