Fix `RegexUtil` comments mode bug and `RegexUtilFuzzTest` setup (#32313)
### Description
Fixes for `RegexUtil`, which backs all regex-valued flags such as `--remote_download_regex`, and for its fuzz test:
* **Comments mode bug:** The `.*suffix` optimization appends `\z` to the suffix and uses `find()`. If the suffix enables comments mode via an inline `(?x)` flag, a `#` starts a comment that swallows the `\z`, so that e.g. `.*(?x)foo #comment` matched `foobar`. Such regexes now fall back to `Matcher#matches()`.
* **Fuzz test without coverage feedback:** rules_fuzzing 0.6.0 uses Jazzer 0.24.0, which can't instrument Java 25 class files ("Unsupported class file major version 69"). Since Bazel is compiled with Java 25, `RegexUtilFuzzTest` ran without any coverage feedback and its corpus never grew beyond a single input. rules_fuzzing 0.8.0 uses Jazzer 0.28.0, which supports Java 25. All of rules_fuzzing's dependencies already resolve to newer versions, so nothing else changes.
* **Fuzz test timeouts:** `java.util.regex` can take exponential time on fuzzer-generated regexes, which ended runs with a timeout after a few minutes, both in the original regex and in the optimized matcher. The haystack length is now capped at 16 characters (the optimized matcher can't be bounded directly and may use `find()`, which retries at every position) and inputs for which the original regex exceeds a budget of character accesses are skipped.
### Motivation
Found while working on #32287. `RegexUtilFuzzTest` is tagged `manual` and thus neither built nor run on CI, which is how the Jazzer incompatibility went unnoticed.
### Build API Changes
No
### Checklist
- [x] I have added tests for the new use cases (if any).
- [ ] I have updated the documentation (if applicable).
### Release Notes
RELNOTES: None
Closes #32313
COPYBARA_INTEGRATE_REVIEW=https://github.com/bazelbuild/bazel/pull/32313 from fmeum:ccr-a098070d-9za8in-regex-fuzz-fixes d51319ee49447c9b604df5d8bbc7f66cc0d62146
PiperOrigin-RevId: 1023243222
Change-Id: Ie226225cfe5fc582010d1f2dab714173753ea6b5
diff --git a/MODULE.bazel b/MODULE.bazel
index 38b7890..73f6266 100644
--- a/MODULE.bazel
+++ b/MODULE.bazel
@@ -519,7 +519,7 @@
# =========================================
bazel_dep(name = "bazel_ci_rules", version = "2.1.2")
-bazel_dep(name = "rules_fuzzing", version = "0.6.0")
+bazel_dep(name = "rules_fuzzing", version = "0.8.0")
bazel_dep(name = "wabt", version = "1.0.37.bcr.1")
rbe = use_extension("@bazel_ci_rules//:rbe_config.bzl", "rbe_config_extension")
diff --git a/MODULE.bazel.lock b/MODULE.bazel.lock
index 724f3dd..5b61e16 100644
--- a/MODULE.bazel.lock
+++ b/MODULE.bazel.lock
@@ -259,8 +259,8 @@
"https://bcr.bazel.build/modules/rules_cc/0.2.9/MODULE.bazel": "34263f1dca62ea664265438cef714d7db124c03e1ed55ebb4f1dc860164308d1",
"https://bcr.bazel.build/modules/rules_foreign_cc/0.10.1/MODULE.bazel": "b9527010e5fef060af92b6724edb3691970a5b1f76f74b21d39f7d433641be60",
"https://bcr.bazel.build/modules/rules_foreign_cc/0.9.0/MODULE.bazel": "c9e8c682bf75b0e7c704166d79b599f93b72cfca5ad7477df596947891feeef6",
- "https://bcr.bazel.build/modules/rules_fuzzing/0.6.0/MODULE.bazel": "85e11f0640353bd11190db8d8e11162ab7684f382085b81c1bab0702d568f445",
- "https://bcr.bazel.build/modules/rules_fuzzing/0.6.0/source.json": "5dda75d267a03611001147cb00874de5c8e7503e1cfbe3c225479dff89bfd111",
+ "https://bcr.bazel.build/modules/rules_fuzzing/0.8.0/MODULE.bazel": "fc925dc0717fe92538d5e769827be0499f3b40bbc5a4a4e44880c98f5a0abc9e",
+ "https://bcr.bazel.build/modules/rules_fuzzing/0.8.0/source.json": "edf68f7e3df618baef6c7d6dae92bb8a39cf78c403e768d6f58e84dfea3c6eff",
"https://bcr.bazel.build/modules/rules_go/0.41.0/MODULE.bazel": "55861d8e8bb0e62cbd2896f60ff303f62ffcb0eddb74ecb0e5c0cbe36fc292c8",
"https://bcr.bazel.build/modules/rules_go/0.42.0/MODULE.bazel": "8cfa875b9aa8c6fce2b2e5925e73c1388173ea3c32a0db4d2b4804b453c14270",
"https://bcr.bazel.build/modules/rules_go/0.45.1/MODULE.bazel": "6d7884f0edf890024eba8ab31a621faa98714df0ec9d512389519f0edff0281a",
diff --git a/src/main/java/com/google/devtools/build/lib/util/regex/RegexUtil.java b/src/main/java/com/google/devtools/build/lib/util/regex/RegexUtil.java
index bcaa77a..ded16ff 100644
--- a/src/main/java/com/google/devtools/build/lib/util/regex/RegexUtil.java
+++ b/src/main/java/com/google/devtools/build/lib/util/regex/RegexUtil.java
@@ -33,6 +33,10 @@
private static final Pattern EXTRACT_SUFFIX_MATCH =
Pattern.compile("(?:\\^|\\\\A)*\\.\\*(?<suffix>[^?+].*)?");
+ // Matches inline flags that may enable comments mode, in which "#" starts a comment that extends
+ // to the end of the line and would thus swallow a "\\z" appended to the pattern.
+ private static final Pattern MAY_ENABLE_COMMENTS = Pattern.compile("\\(\\?[a-zA-Z-]*x");
+
/**
* Returns a {@link Predicate} that matches the input string (in internal encoding according to
* {@link com.google.devtools.build.lib.util.StringEncoding}) against the regex pattern with the
@@ -75,6 +79,9 @@
// Turn the "match" pattern into an equivalent "find" pattern, since these are the only ones
// that benefit from the Boyer-Moore optimization in the Java regex engine.
// https://github.com/openjdk/jdk/blob/50dced88ff1aed23bb4c8fe9e4a08e6cc200b897/src/java.base/share/classes/java/util/regex/Pattern.java#L1959-L1969
+ if (MAY_ENABLE_COMMENTS.matcher(suffixPattern).find()) {
+ return s -> regexPattern.matcher(internalToUnicode(s)).matches();
+ }
Pattern compiled = Pattern.compile(suffixPattern + "\\z", Pattern.DOTALL);
return s -> compiled.matcher(internalToUnicode(s)).find();
}
diff --git a/src/test/java/com/google/devtools/build/lib/util/regex/BUILD b/src/test/java/com/google/devtools/build/lib/util/regex/BUILD
index 170b8cf..fe2d4b3 100644
--- a/src/test/java/com/google/devtools/build/lib/util/regex/BUILD
+++ b/src/test/java/com/google/devtools/build/lib/util/regex/BUILD
@@ -42,6 +42,7 @@
java_fuzz_test(
name = "RegexUtilFuzzTest",
srcs = ["RegexUtilFuzzTest.java"],
+ dicts = ["RegexUtilFuzzTest.dict"],
jvm_flags = [
"-Djazzer.instrumentation_includes=java.util.regex.*:com.google.devtools.build.lib.util.*",
# The fuzz test intentionally passes untrusted input into Pattern#compile, don't report that fact.
diff --git a/src/test/java/com/google/devtools/build/lib/util/regex/RegexUtilFuzzTest.dict b/src/test/java/com/google/devtools/build/lib/util/regex/RegexUtilFuzzTest.dict
new file mode 100644
index 0000000..845134f
--- /dev/null
+++ b/src/test/java/com/google/devtools/build/lib/util/regex/RegexUtilFuzzTest.dict
@@ -0,0 +1,41 @@
+# Regex syntax that is relevant to the optimizations in RegexUtil.
+".*"
+".*?"
+".*+"
+"^"
+"$"
+"\\A"
+"\\z"
+"\\Z"
+"("
+")"
+"(?:"
+"(?="
+"(?!"
+"(?<="
+"(?<!"
+"(?>"
+"(?<n>"
+"(?i)"
+"(?x)"
+"#"
+"\x0A"
+"(?i:"
+"|"
+"["
+"]"
+"[^"
+"[]"
+"\\"
+"\\."
+"\\c"
+"\\0"
+"\\1"
+"\\k<n>"
+"\\Q"
+"\\E"
+"?"
+"*"
+"+"
+"{2}"
+"{"
diff --git a/src/test/java/com/google/devtools/build/lib/util/regex/RegexUtilFuzzTest.java b/src/test/java/com/google/devtools/build/lib/util/regex/RegexUtilFuzzTest.java
index cac2c4c..9ec00cf 100644
--- a/src/test/java/com/google/devtools/build/lib/util/regex/RegexUtilFuzzTest.java
+++ b/src/test/java/com/google/devtools/build/lib/util/regex/RegexUtilFuzzTest.java
@@ -25,9 +25,17 @@
* RegexUtil#asOptimizedMatchingPredicate} behaves just like the original regex matcher.
*/
public class RegexUtilFuzzTest {
+ // Bound the time spent per input: java.util.regex can take exponential time in the length of the
+ // haystack for the regexes generated by the fuzzer. The original regex is bounded by its number
+ // of character accesses below. The optimized matcher can't be bounded directly and may be much
+ // slower since it can use find() instead of matches(), which retries at every position, so the
+ // haystack has to be kept short.
+ private static final int MAX_HAYSTACK_LENGTH = 16;
+ private static final int MAX_CHAR_ACCESSES = 1_000_000;
+
public static void fuzzerTestOneInput(FuzzedDataProvider data) {
String needle = data.consumeString(30);
- String haystack = data.consumeRemainingAsString();
+ String haystack = data.consumeString(MAX_HAYSTACK_LENGTH);
Pattern originalPattern;
try {
originalPattern = Pattern.compile(needle, Pattern.DOTALL);
@@ -36,8 +44,15 @@
return;
}
+ boolean originalMatches;
+ try {
+ originalMatches =
+ originalPattern.matcher(new BoundedCharSequence(haystack, MAX_CHAR_ACCESSES)).matches();
+ } catch (BudgetExceededException e) {
+ // The original regex backtracks catastrophically on this input, skip it.
+ return;
+ }
Predicate<String> optimizedMatcher = RegexUtil.asOptimizedMatchingPredicate(originalPattern);
- boolean originalMatches = originalPattern.matcher(haystack).matches();
boolean optimizedMatches = optimizedMatcher.test(unicodeToInternal(haystack));
if (originalMatches != optimizedMatches) {
throw new AssertionError(
@@ -51,4 +66,44 @@
.formatted(needle, haystack, originalMatches, optimizedMatches));
}
}
+
+ private static final class BudgetExceededException extends RuntimeException {
+ BudgetExceededException() {
+ super(null, null, /* enableSuppression= */ false, /* writableStackTrace= */ false);
+ }
+ }
+
+ /** A {@link CharSequence} that throws once its characters have been accessed too often. */
+ private static final class BoundedCharSequence implements CharSequence {
+ private final String delegate;
+ private int remainingAccesses;
+
+ BoundedCharSequence(String delegate, int maxAccesses) {
+ this.delegate = delegate;
+ this.remainingAccesses = maxAccesses;
+ }
+
+ @Override
+ public char charAt(int index) {
+ if (--remainingAccesses < 0) {
+ throw new BudgetExceededException();
+ }
+ return delegate.charAt(index);
+ }
+
+ @Override
+ public int length() {
+ return delegate.length();
+ }
+
+ @Override
+ public CharSequence subSequence(int start, int end) {
+ return new BoundedCharSequence(delegate.substring(start, end), remainingAccesses);
+ }
+
+ @Override
+ public String toString() {
+ return delegate;
+ }
+ }
}
diff --git a/src/test/java/com/google/devtools/build/lib/util/regex/RegexUtilTest.java b/src/test/java/com/google/devtools/build/lib/util/regex/RegexUtilTest.java
index f6114b8..612ee4a 100644
--- a/src/test/java/com/google/devtools/build/lib/util/regex/RegexUtilTest.java
+++ b/src/test/java/com/google/devtools/build/lib/util/regex/RegexUtilTest.java
@@ -49,6 +49,7 @@
"()",
"+",
"|",
+ "foobar",
})
String haystack,
@TestParameter({
@@ -74,6 +75,9 @@
".*|",
".*^",
".*+",
+ ".*(?x)foo #comment",
+ ".*(?ix)foo",
+ ".*(?x:foo)#bar",
})
String needle) {
Pattern originalPattern = Pattern.compile(needle, Pattern.DOTALL);