Java模式匹配进入无限循环

Question

一位朋友给了我这段代码并说有一个bug.是的,这段代码永远运行.

我得到的答案是:

在打印任何东西之前,它会持续> 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新手,你有什么建议吗？

Answer 1

根据OWASP,你正在使用的模式被称为邪恶的正则表达式(他们知道他们在大多数时间都在讨论什么):

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

它基本上匹配aaOR aa或aab(因为b是可选的加法?)

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

所以,是的,理清你想要匹配的东西.我建议在上面的例子中你应该简单匹配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);
  }
}

Answer 2

这个节目来自Josh Bloch的Java益智游戏,Bill Pugh @ Devoxx'10 在这里观看.我认为他们的解释是最好的.

它在幻灯片31中.但不要跳过任何幻灯片充满乐趣.