Java正则表达式模式匹配花费太多时间

Question

当模式和单词类似于

时，java 正则表达式模式匹配功能需要太多时间才能完成

pattern = ".*.*.*.*.*.*.*.*.*.*1";
word = aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

将上述模式与单词进行匹配需要超过 10 秒的时间。确实，这种模式毫无意义，但在我的例子中，该模式被视为来自 GUI 表单的用户输入。

我使用了以下代码。

        boolean matches = false;
        long startTime = System.nanoTime();
        try {
            matches = Pattern.compile(pattern).matcher(word.toLowerCase()).matches();
        } catch (Exception e) {
            e.printStackTrace();
        }
        long elapseTime = System.nanoTime() - startTime;
        elapseTime = elapseTime / 1000000000;
        System.out.println("Time taken for regex match " + elapseTime + " out put " + matches);

Answer 1

这是一个或多或少众所周知的正则表达式安全问题:您可以轻松地对任何可以输入正则表达式的服务器进行拒绝服务。您可以制作一个正则表达式，该表达式实际上需要无限的时间来针对任何输入运行。你的例子很糟糕；你可能会变得更糟。

顺便说一句，这是固有的。如果输入的总长度是素数，则此正则表达式匹配，否则失败:.?|(..+?)\\1+ .

1. 找到素数很困难。
2. 以上是有效的正则表达式。
3. 因此，正则表达式可能会很慢并且无法变得更快。量子ED。

因此，除非我们跳出框框，否则您想要的东西是不可能的。解决办法有两种:

A.不匹配正则表达式，匹配其他东西。如果我们匹配几乎正则表达式会怎样:删除了一些外来功能的正则表达式。这会让你看到一个叫做 Thompson NFA 的东西。正则表达式匹配器有一些轻微的限制(主要是，没有反向引用，没有分组提取，不是没有额外的努力 - 没有反向引用，上面的质数查找器就无法工作)。也许您可以找到此正则表达式变体的 java 实现。此时，您可以简单地计算输入的大小加上正则表达式的大小，并得出有关执行该正则表达式需要多长时间的结论。

B.您必须使用计时器线程来保护任何正则表达式搜索并中止它，或者阻止用户输入正则表达式。仅出于此目的在单独的线程中运行正则表达式作业，该线程已经很好(优先级设置较低)，并由中断()它的计时器线程保护，尽管您必须测试匹配器代码是否实际上停止在如果你打断它，它会跟踪它(我打赌它不会，此时你根本无法阻止失控的正则表达式，并且你必须找到一些非java的东西，或者在某个地方找到一个正则表达式库并放入 if (Thread.interrupted()) throw new InterruptedException(); 在其循环之一内的某处。

C.向用户提供非正则表达式的内容。也许为了实现它，您将用户的输入转换为正则表达式，然后正常运行，但作为转换的一部分，您需要仔细检查某些条件以确保正则表达式不会很慢。

注意:您的示例正则表达式与 thompson-NFA 兼容； thompson-NFA 风格的正则表达式很快就能完成。然而，java 的正则表达式不是 t-NFA。