Java模式匹配进入无限循环

Question

Java模式匹配进入无限循环

12

一个朋友给了我这段代码，并说有一个错误。是的，这段代码会一直运行。

我得到的答案是:

在打印任何东西之前，它将运行>10 ^ 15年。

public class Match {
     public static void main(String[] args) {
         Pattern p = Pattern.compile("(aa|aab?)+");
         int count = 0;
         for(String s = ""; s.length() < 200; s += "a")
             if (p.matcher(s).matches())
                 count++;
         System.out.println(count);
     }
}

我不太明白为什么会出现这种情况，因为我是Java新手，你有什么建议吗？

- John

你能打印出每次迭代的计数（和时间戳）以查看它何时失控吗？ - Thilo

2

请注意，“无限”和“10^15年”之间存在（相当大的）差异。您可以通过在不同的硬件上运行循环来减少/增加计算时间，但我敢打赌您不能在不更改代码的情况下减少“while(true) {}”的计算时间！话虽如此，在调试目的上将此示例视为无限循环也无妨。 - Chris Browne

2个回答

1

正则表达式(aa|aab?)+是一种特别耗费正则表达式引擎处理时间的表达式，这些被称为邪恶的正则表达式。它类似于链接中的(a|aa)+示例。这个特定的表达式在由a组成的字符串上非常缓慢。

这段代码的作用是检查邪恶的正则表达式是否与越来越长的a字符串匹配，最长可达200个字符，因此肯定需要很长时间才能完成，而且只有在循环结束后才会打印出结果。我很想知道10^15年的数字是从哪里来的。

编辑

好的，10^15（实际上是问题中的整个代码）来自这个演讲，第37页。感谢zengr提供的链接。与问题最相关的信息是，对于这个正则表达式的检查需要时间，其时间复杂度与字符串长度呈指数关系。具体来说，它的时间复杂度为O(2^(n/2))，因此检查最后一个字符串所需的时间比第一个字符串长2^99（左右）倍。

- andronikus

2

第37页：http://strangeloop2010.com/system/talks/presentations/000/014/450/BlochLee-JavaPuzzlers.pdf - zengr

1

不错！实际上，整个讲话都非常有趣，但最相关的信息是，在这里发生的正则表达式检查在被扫描的字符串长度方面呈指数级增长。具体来说，是O(2^(n/2))。 - andronikus

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

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

- Ben · Accepted Answer

根据OWASP（他们大多数时候都知道在谈论什么），您正在使用的模式被称为恶意正则表达式：

https://www.owasp.org/index.php/Regular_expression_Denial_of_Service_-_ReDoS

基本上它匹配aa或aa或aab(因为通过添加?使b变成可选项)。

像这样的正则表达式容易受到ReDoS或正则表达式拒绝服务攻击的攻击。

所以，是的，请先确定要匹配的内容。我建议在上面的例子中，您应该简单地匹配aa，不需要分组、重复或交替。

Pattern p = Pattern.compile("aa");

还有一个人指出，现在已经删除了他的帖子，你不应该使用+=来添加字符串。你应该使用StringBuffer代替：

public class Match {
  public static void main(String[] args) {
    Pattern p = Pattern.compile("aa");
    StringBuffer buffy = new StringBuffer(200);
    int count = 0;
    for(int i = 0; i < 200; i++){
      buffy.append("a")
      if (p.matcher(buffy.toString()).matches()){
        count++;
      }
    }
    System.out.println(count);
  }
}