JLine: ReDoS in Built-in grep Command Amplified by Automatic `.*` Wrapping

Summary

The JLine3 built-in grep command wraps the user-supplied regular expression with
.* before compiling it with Java's backtracking regex engine. This amplifies
catastrophic backtracking and allows a short pattern such as (a+)+b to hang the
command thread on non-matching input. In environments that expose the JLine shell to
remote users, this is a denial-of-service issue.

Details

In builtins/src/main/java/org/jline/builtins/PosixCommands.java, the grep
implementation rewrites the user pattern before compilation:

String regex = args.remove(0);
String regexp = regex;
if (opt.isSet("word-regexp")) {
    regexp = "\\b" + regexp + "\\b";
}
if (opt.isSet("line-regexp")) {
    regexp = "^" + regexp + "$";
} else {
    regexp = ".*" + regexp + ".*";
}

The transformed pattern is compiled with Pattern.compile(...) and then used to test
each input line. For a payload such as (a+)+b, the automatic .* prefix and suffix
increase the backtracking search space substantially.

Affected source location:

• builtins/src/main/java/org/jline/builtins/PosixCommands.java
• grep(...)

PoC

1. Create a file containing a long run of a characters:

printf 'aaaaaaaaaaaaaaaaaaaaaaa\n' > /tmp/testfile.txt

2. Run JLine3's built-in grep against that file:

grep '(a+)+b' /tmp/testfile.txt

Expected result:

• The command stops responding.
• The executing thread consumes high CPU.

Reproduction environment:

• JLine3 on x86_64 Linux
• OpenJDK 25.0.2

Impact

This is a denial-of-service vulnerability caused by catastrophic regex backtracking.
Any application embedding org.jline:jline-builtins and exposing the built-in grep
command is impacted. In remote shell deployments, an attacker can occupy a worker
thread indefinitely and repeat the attack across multiple sessions to reduce service
availability for other users.

Suggested Fix

The preferred fix for the current git head is:

• stop rewriting non-line-regexp searches as .*...*
• use Matcher.find() for substring semantics
• compile user patterns with a linear-time engine such as RE2/J

Suggested patch:

diff --git a/builtins/pom.xml b/builtins/pom.xml
--- a/builtins/pom.xml
+++ b/builtins/pom.xml
@@
         <dependency>
+            <groupId>com.google.re2j</groupId>
+            <artifactId>re2j</artifactId>
+            <version>1.8</version>
+        </dependency>
+        <dependency>
             <groupId>org.jline</groupId>
             <artifactId>jline-reader</artifactId>
         </dependency>

diff --git a/builtins/src/main/java/org/jline/builtins/PosixCommands.java b/builtins/src/main/java/org/jline/builtins/PosixCommands.java
--- a/builtins/src/main/java/org/jline/builtins/PosixCommands.java
+++ b/builtins/src/main/java/org/jline/builtins/PosixCommands.java
@@
-import java.util.regex.Pattern;
+import com.google.re2j.Pattern;
@@
         if (opt.isSet("line-regexp")) {
             regexp = "^" + regexp + "$";
-        } else {
-            regexp = ".*" + regexp + ".*";
         }
@@
-        boolean m = p.matcher(line).matches();
+        boolean m = opt.isSet("line-regexp")
+                ? p.matcher(line).matches()
+                : p.matcher(line).find();

Credits

This issue was identified by Michał Majchrowicz and Marcin Wyczechowski, members of the AFINE Team.