Java 9+ 中的灾难性回溯正则表达式示例

Question

有没有人有 catastrophic backtracking in a regular expression, which works in Java 11? Most of the usual examples (like "(a+a+)+b") are fixed since java 9 的例子。最好是没有反向引用的，不知道在 JDK 9+.

中是否可行

在我们的应用程序中，我们有一个逻辑来控制这种回溯，并且为了测试该逻辑，我们使用了表达式“(x+x+)+y”。升级到 JDK 11 后，它不再导致需要行为。

Answer 1

我运行 java 14岁，回溯问题依然存在。失败需要以下大约 6 秒。

String regex = "(a+a+a+a+a+a+)+b";
String str = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac";
System.out.println(str.matches(regex));

这可以通过使用独立组来避免(?>X)。一旦该组第一次匹配，引擎就会检查以下内容是否与 b 匹配。如果没有，则无需重复，因为回溯不会改变该结果。所以它立即失败（即使对于更大的表达式 and/or 测试字符串）。

String regex1 = "(?>(a+a+a+a+a+a+)+)b";
System.out.println(str.matches(regex1));

Catastrophic Backtracking regular expression example in Java 9+