为什么在Java中这个正则表达式如此缓慢？

Question

为什么在Java中这个正则表达式如此缓慢？

51

最近我注意到一个名为 SonarQube 规则 (https://rules.sonarsource.com/java/RSPEC-4784)，该规则提醒我有些性能问题可能会被用作反对Java正则表达式实现的拒绝服务攻击。

事实上，以下Java测试展示了错误的正则表达式会有多么慢：

    import org.junit.Test;

    public class RegexTest {

    @Test
    public void fastRegex1() {
        "aaaaaaaaaaaaaaaaaaaaaaaaaaaabs".matches("(a+)b");
    }

    @Test
    public void fastRegex2() {
        "aaaaaaaaaaaaaaaaaaaaaaaaaaaab".matches("(a+)+b");
    }

    @Test
    public void slowRegex() {
        "aaaaaaaaaaaaaaaaaaaaaaaaaaaabs".matches("(a+)+b");
    }
}

正如您所看到的，前两个测试非常快，第三个测试在Java 8中非常慢。

然而，在Perl或Python中使用相同的数据和正则表达式却并不慢，这让我想知道为什么在Java中评估这个正则表达式如此缓慢。

$ time perl -e '"aaaaaaaaaaaaaaaaaaaaaaaaaaaabs" =~ /(a+)+b/ && print "$1\n"'
aaaaaaaaaaaaaaaaaaaaaaaaaaaa

real    0m0.004s
user    0m0.000s
sys     0m0.004s

$ time python3 -c 'import re; m=re.search("(a+)+b","aaaaaaaaaaaaaaaaaaaaaaaaaaaabs"); print(m.group(0))'
aaaaaaaaaaaaaaaaaaaaaaaaaaaab

real    0m0.018s
user    0m0.015s
sys     0m0.004s

在数据中使用额外匹配修饰符+或尾字符s会导致这个正则表达式变得很慢，为什么只有Java受影响？

- AntonPiatek

2

你跑测试的频率有多高？试试使用JMH。 - JCWasmx86

2

为什么要使用 (a+)+b 而不是 a+b？如果你只想匹配而不是获取 b 前面的组，那么我不认为有任何理由使用组和组后的 +！ - Youcef LAIDANI

6

您提供的网站中有一个指向OWASP的链接，它更详细地解释了这个问题：https://owasp.org/www-community/attacks/Regular_expression_Denial_of_Service_-_ReDoS - Amongalen

29

请注意：你正在经历的是所谓的“灾难性回溯”。(For your information: what you're experiencing is called catastrophic backtracking) - Thomas

3

Java的.matches("(a+)b")实际上等同于Perl的/^(a+)+b\z/。 - ikegami

显示剩余9条评论

4个回答

20

我不太熟悉Perl，但是Python版本与Java版本不相同。你正在使用 search()，而Java版本使用的是matches()。在Python中等效的方法是fullmatch()。

当我在Python（3.8.2）中使用search()运行您的示例时，我得到了与您一样快的结果。当我使用fullmatch()运行它时，执行时间很长（多秒）。你的Perl示例也可能没有进行完全匹配吗？

顺便说一句：如果想要尝试Java版本的search，可以使用：

Pattern.compile("(a+)+b").matcher("aaaaaaaaaaaaaaaaaaaaaaaaaaaabs").find();

语义方面可能会有些微小的差异，但对于这个目的来说应该足够接近了。

- JimmyJames

1

Perl 代码等效于 Python 的 search() 代码：如果任何子字符串与正则表达式匹配，则视为成功匹配。 - Mark

@Mark 谢谢你。你知道在Perl中“fullmatch”的等效方法吗？ - JimmyJames

1

在Perl中，您可以通过更改正则表达式以包括起始和结束锚点来完成：/^(a+)+b$/。 - Mark

2

在 Perl v5.30 中非常快：echo aaaaaaaaaaaaaaaaaaaaaaaaaaaabs | perl -wne '/^((a+)+b)$/' - kubanczyk

8

关于您提到的Perl示例是否进行了完全匹配的问题，正确。Perl的等效表示将是/^(a+)+b\z/（而不是/^(a+)+b$/）。就此而言，在开始匹配之前，优化器意识到该模式根本无法匹配，并且会立即中止。因此，与Java和Python不同， "aaa...aaabs" =~ /^(a+)+b\z/ 会立即失败。您可以使用 perl -Mre=debug -e '"aaaaaaaaaaaaaaaaaaaaaaaaaaaabs" =~ /^(a+)+b\z/' 查看这一点（Did not find floating substr "ab"$... Match rejected by optimizer）。 - ikegami

@ikegami 谢谢。考虑到 Perl 和正则表达式的深厚历史，它比 Java 和 Python 的实现更“聪明”并不让我感到太惊讶。 - JimmyJames

14

额外的+会导致在无法匹配字符串时（在一个朴素的正则表达式实现中）出现大量的回溯。如果可以匹配字符串，则第一次尝试就已经知道答案。这就解释了为什么情况2很快，只有情况3很慢。

- Henry

我同意回溯算法，但它真的会慢到需要12秒吗？！ - f1sh

我无法使用快速而简单的脚本（50000次迭代）复制缓慢的正则表达式：13055纳秒（使用System.nanoTime()测量）。 - JCWasmx86

@JCWasmx86 你用了什么输入字符串？ - Amongalen

1

现在进行了500万次迭代，仍然大约在10000纳秒左右。 - JCWasmx86

@Henry 我知道这一点，但12秒对于评估具有那种长度的单词的类型3语言规则来说是非常长的时间。 - f1sh

显示剩余6条评论

9

该网站https://swtch.com/~rsc/regexp/regexp1.html详细介绍了正则表达式实现技术和其背后的理论知识。虽然仅提供链接非常不好，但它值得一读，其中展示了一个正则表达式的例子，使用更好的实现方法完整匹配只需30微秒，而使用较为显而易见的方法则需要60秒（慢2百万倍）。

该网站称：

"今天，正则表达式已经成为一个如何忽视良好理论导致糟糕程序的闪亮案例。今天流行工具所使用的正则表达式实现速度显著慢于那些三十年前Unix工具中的实现."

其他回答正确指出额外的+会导致过多的回溯，但只有当你忽略良好理论时才会出现这种情况。

- icarus

4

在这里使用NFA将会遇到完全相同的问题，就像更复杂的算法一样。（一个具有n个状态的NFA可能会有多达2^n条路径）。你必须理解那篇论文中使用的特定病态正则表达式，以了解为什么NFA在该正则表达式上运行得更快，以及为什么这不适用于一般情况。 - Voo

@Voo 为什么NFA中的路径数量很重要？要模拟一个NFA，你只需要存储每一步可能状态的集合，这个集合的大小最多为n。 - gmatht

@gmath 运行时间取决于自动机中可能路径的数量，而不是状态的数量。关键在于，如果您没有运行某些识别特定模式的优化器（当然您可以欺骗优化器），某些正则表达式将仅具有2^n的运行时间，而您选择哪种算法并不重要。 - Voo

@Voo 所有正则表达式都可以在线性时间内运行，而不是像你所说的2^n。它不仅仅是一个可以欺骗的优化器。随着时间的推移，人们已经添加了他们所谓的正则表达式，因此线性时间不再是可以依赖的属性，但这时它们也不再是正则表达式。 - icarus

@Voo 不行。例如，可以将NFA转换为DFA，这在输入长度上显然是线性的。您可以在维基百科上了解有关NFA的信息。https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton#Implementation - gmatht

@gmatht 是的，我也不确定当时在想什么。我把它归咎于早上还没喝咖啡就开始评论了。 - Voo

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Andy Turner · Accepted Answer

警告：我对正则表达式内部并不了解，这只是我的猜测。我也不能回答为什么Java会受到这种影响而其他语言不会（当我运行它时，它比你在jshell 11中的12秒要快得多，所以它可能只影响某些版本）。

"aaaaaaaaaaaaaaaaaaaaaaaaaaaabs".matches("(a+)+b")

有很多方法可以匹配许多a：

(a)(a)(a)(a)
(aa)(a)(a)
(a)(aa)(a)
(aa)(aa)
(a)(aaa)
etc.

对于输入字符串"aaaaaaaaaaaaaaaaaaaaaaaaaaaab"，它会贪婪地匹配所有这些a，在一次扫描中匹配b，完成工作。

对于"aaaaaaaaaaaaaaaaaaaaaaaaaaaabs"，当到达末尾并发现字符串不匹配（因为有一个s），它没有正确地识别出s意味着它永远无法匹配。因此，在经过并可能匹配了一些内容后，它会返回空结果。

(aaaaaaaaaaaaaaaaaaaaaaaaaaaa)bs

它想，“哦，也许是因为我分组的方式不对，导致失败了” - 然后回去尝试 a 标签的所有其他组合。

(aaaaaaaaaaaaaaaaaaaaaaaaaaa)(a)bs  // Nope, still no match
(aaaaaaaaaaaaaaaaaaaaaaaaaa)(aa)bs  // ...
(aaaaaaaaaaaaaaaaaaaaaaaaa)(aaa)bs  // ...
...
(a)(aaaaaaaaaaaaaaaaaaaaaaaaaaa)bs  // ...
(aaaaaaaaaaaaaaaaaaaaaaaaaa(a)(a)bs  // ...
(aaaaaaaaaaaaaaaaaaaaaaaaa(aa)(a)bs  // ...
(aaaaaaaaaaaaaaaaaaaaaaaa(aaa)(a)bs  // ...
...

这些组合很多（我认为对于28个a而言，有2^27 - 也就是134,217,728种组合方式 - 因为每个a既可以是前一个组的一部分，也可以开始一个新的组），所以需要很长时间。