Java ReDos 易受攻击吗？

Question

我尝试使用 (a+)+ 正则表达式和 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!（大量 a）输入使用 jshell 重新创建 regular expression denial of service attack：

Pattern.compile("(a+)+")
    .matcher("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!")
    .matches()

但是我每次尝试都很快完成。 Java 中的正则表达式实现与其他的不同吗？或者链接的维基百科页面有误？

（顺便说一句。我正在使用 Java 11，如果相关的话）

编辑：看起来它与 Java 版本相关，当我在 Java 8 上尝试它时，它挂起，但在 Java 9 和 11 中它立即工作。那些可能影响它的版本之间发生了什么变化？现在 Java 中的所有正则表达式都安全吗？

是否有特定的 Java JEP 更改了正则表达式的实现？我想知道什么样的正则表达式对于较新的 Java.

仍然是个问题

Answer 1

我目前是运行 Java 8 并且以下代码挂起：

Pattern.compile("(a|aa)+")
       .matcher("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab")
       .matches()

鉴于您使用 Java 11 的方式（并且还使用 Java 9/10 对其进行了测试）并且发现它需要少量时间才能完成，显然有这些版本之间所做的更改。

通过查看 Java 11 中 Matcher 的源代码，我们发现 Java 8 中不存在以下添加：

/**
 * Storage used by top greedy Loop node to store a specific hash set to
 * keep the beginning index of the failed repetition match. The nodes
 * themselves are stateless, so they rely on this field to hold state
 * during a match.
 */
IntHashSet[] localsPos;

这个本地存储，以及添加的大量其他代码，似乎是 Java 9+ 中正则表达式的状态机比 [=21 中完成得快得多的主要原因之一=] 8及以下.

Answer 2

根据文章 RSPEC-2631，ReDoS 问题已在 Java 9 及更高版本中得到处理：

Java runtimes like OpenJDK 9+ are mitigating this problem by having additional protections in their implementation of regular expression evaluation. In those runtime the example above is not vulnerable.

Java ReDos 易受攻击吗？

Is Java ReDos vulnerable?

java

regex

security

java-11