This is an automated email from the ASF dual-hosted git repository. afs pushed a commit to branch main in repository https://gitbox.apache.org/repos/asf/jena.git
commit b7db0a8fc6520d374458eda2bdee83c957d16d55 Author: Rob Vesse <[email protected]> AuthorDate: Mon Oct 5 09:29:08 2026 +0100 Limit apf:strSplit runtime Ensures that the ARQ property function strSplit time bounds regular expression splitting time --- .../org/apache/jena/sparql/expr/RegexEngine.java | 252 +++++++++++++++++++-- .../jena/sparql/pfunction/library/strSplit.java | 14 +- .../org/apache/jena/sparql/expr/TestRegex.java | 28 ++- .../sparql/pfunction/library/TestStrSplit.java | 58 ++++- .../java/org/apache/jena/atlas/lib/StrUtils.java | 2 +- 5 files changed, 319 insertions(+), 35 deletions(-) diff --git a/jena-arq/src/main/java/org/apache/jena/sparql/expr/RegexEngine.java b/jena-arq/src/main/java/org/apache/jena/sparql/expr/RegexEngine.java index 2734668154..e9abbd51b1 100644 --- a/jena-arq/src/main/java/org/apache/jena/sparql/expr/RegexEngine.java +++ b/jena-arq/src/main/java/org/apache/jena/sparql/expr/RegexEngine.java @@ -21,6 +21,7 @@ package org.apache.jena.sparql.expr; +import java.text.CharacterIterator; import java.util.Objects; import java.util.regex.Matcher; import java.util.regex.Pattern; @@ -38,44 +39,70 @@ import org.apache.jena.sparql.util.Symbol; /** * Encapsulate a specific regular expression systems. * <p> - * The two provided are the regular expression implement in Apache Xerces (2.11.0) - * and the JDK {@code java.util.regex}. + * The two provided are the regular expression implement in Apache Xerces (2.11.0) and the JDK {@code java.util.regex}. * <p> * By default {@code java.util.regex} is used. It does not support the "x" flag. * <p> - * The default is set by symbol {@code ARQ.regexImpl} (comand line {@code arq:regexImpl}) - * to either "javaRegex" or "xercesRegex". + * The default is set by symbol {@code ARQ.regexImpl} (comand line {@code arq:regexImpl}) to either "javaRegex" or + * "xercesRegex". * */ public abstract class RegexEngine { + + /** + * Default maximum permitted regular expression evaluation time + * @see #MAX_REGEX_EVALUATION_TIME + */ + public static final long DEFAULT_MAX_REGEX_EVALUATION_TIME = 250; + /** + * Maximum permitted regular expression evaluation time, defaults to {@link #DEFAULT_MAX_REGEX_EVALUATION_TIME} + * <p> + * For some regular expression patterns the evaluation time can be excessive, especially if a pattern, or the + * pattern combined with the data leads to catastrophic backtracking. Therefore, we bound the evaluation time by + * using a special {@link CharSequence}/{@link CharacterIterator} wrapper that enforces a time limit. If the limit + * is exceeded then an {@link ExprEvalException} is thrown. This does impose a small performance penalty though + * this generally should be negligible. + * </p> + * <p> + * If an application makes extensive use of complex regular expressions, and you are certain that those are not + * subject to catastrophic backtracking you can either increase the limit appropriately. Or you can set to a + * zero/negative value to disable the limit entirely. + * </p> + */ + public static long MAX_REGEX_EVALUATION_TIME = DEFAULT_MAX_REGEX_EVALUATION_TIME; + public abstract boolean match(String string); // ---- ---- - public static enum RegexImpl { Java, Xerces } + public static enum RegexImpl {Java, Xerces} private static RegexImpl regexImpl = chooseRegexImpl(ARQ.getContext()); private static RegexImpl chooseRegexImpl(Context context) { Object v = ARQ.getContext().get(ARQ.regexImpl); - if ( v == null ) + if (v == null) { return RegexImpl.Java; + } - if ( v instanceof String str ) { - return switch(str) { + if (v instanceof String str) { + return switch (str) { case ARQConstants.strJavaRegex -> RegexImpl.Java; case ARQConstants.strXercesRegex -> RegexImpl.Xerces; default -> throw new IllegalArgumentException("Unexpected value: " + str); }; } - if ( v instanceof Symbol sym ) + if (v instanceof Symbol sym) { Log.error(E_Regex.class, "Regex implementation context setting is a symbol : default to Java"); - else + } else { Log.warn(E_Regex.class, "Regex implementation not recognized : default to Java"); + } return RegexImpl.Java; } - /** For testing */ + /** + * For testing + */ public static void setRegexImpl(RegexImpl valRegexImpl) { Objects.requireNonNull(valRegexImpl); regexImpl = valRegexImpl; @@ -85,10 +112,11 @@ public abstract class RegexEngine { public static Pattern makePattern(String label, String patternStr, String flags) { try { int mask = 0; - if ( flags != null ) { + if (flags != null) { mask = makeMask(flags); - if ( flags.contains("q") ) + if (flags.contains("q")) { patternStr = Pattern.quote(patternStr); + } } return Pattern.compile(patternStr, mask); } catch (PatternSyntaxException pEx) { @@ -97,10 +125,11 @@ public abstract class RegexEngine { } public static int makeMask(String modifiers) { - if ( modifiers == null ) + if (modifiers == null) { return 0; + } int newMask = 0; - for ( int i = 0; i < modifiers.length(); i++ ) { + for (int i = 0; i < modifiers.length(); i++) { switch (modifiers.charAt(i)) { case 'i' -> { newMask |= Pattern.UNICODE_CASE; @@ -110,9 +139,9 @@ public abstract class RegexEngine { case 's' -> newMask |= Pattern.DOTALL; case 'x' -> newMask |= Pattern.COMMENTS; // Handled separately. - case 'q' -> {} - default -> - throw new ExprEvalException("Unsupported flag in regex modifiers: " + modifiers.charAt(i)); + case 'q' -> { + } + default -> throw new ExprEvalException("Unsupported flag in regex modifiers: " + modifiers.charAt(i)); } } return newMask; @@ -127,7 +156,7 @@ public abstract class RegexEngine { @Override public boolean match(String s) { - Matcher m = regexPattern.matcher(s); + Matcher m = MAX_REGEX_EVALUATION_TIME >= 0 ? regexPattern.matcher(new TimeBoundedCharSequence(s, MAX_REGEX_EVALUATION_TIME)) : regexPattern.matcher(s); return m.find(); } } @@ -136,7 +165,7 @@ public abstract class RegexEngine { private final RegularExpression regexPattern; public RegexXerces(String pattern, String flags) { - if ( flags != null && flags.contains("q") ) { + if (flags != null && flags.contains("q")) { flags = flags.replace("q", ""); pattern = REUtil.quoteMeta(pattern); } @@ -145,7 +174,11 @@ public abstract class RegexEngine { @Override public boolean match(String s) { - return regexPattern.matches(s); + if (MAX_REGEX_EVALUATION_TIME > 0) { + return regexPattern.matches(new TimeBoundedCharSequence(s, MAX_REGEX_EVALUATION_TIME)); + } else { + return regexPattern.matches(s); + } } private RegularExpression makePattern(String patternStr, String flags) { @@ -170,4 +203,181 @@ public abstract class RegexEngine { }; } + /** + * A {@link CharSequence} and {@link CharacterIterator} that time bounds operations so that if too much time is + * spent accessing it {@link ExprEvalException}'s will be thrown. This is used to protect the regular expression + * evaluation against catastrophic backtracking. + */ + public static final class TimeBoundedCharSequence implements CharSequence, CharacterIterator { + + private final CharSequence data; + private final long timeLimit; + private int iterIndex = 0; + + public TimeBoundedCharSequence(CharSequence characters, long timeLimitMillis) { + this.data = characters; + this.timeLimit = timeLimitMillis < System.currentTimeMillis() ? System.currentTimeMillis() + timeLimitMillis : timeLimitMillis; + // Note always make an immediate time limit check as if we've been constructed as a sub-sequence then + // the time limit may have been exceeded already + checkTimeLimit(); + } + + private void checkTimeLimit() { + if (System.currentTimeMillis() >= this.timeLimit) { + throw new ExprEvalException("Regular expression time limit exceeded"); + } + } + + @Override + public int length() { + checkTimeLimit(); + return this.data.length(); + } + + @Override + public char charAt(int index) { + checkTimeLimit(); + return this.data.charAt(index); + } + + private void checkIndex(String checkType, int index) { + if (index < 0 || index >= this.data.length()) { + throw new IndexOutOfBoundsException( + String.format("%s %,d out of bounds, must be in range 0-%,d", checkType, index, this.data.length())); + } + } + + @Override + public CharSequence subSequence(int start, int end) { + checkTimeLimit(); + if (start == end) { + return new TimeBoundedCharSequence("", this.timeLimit); + } + checkIndex("Subsequence Start Index", start); + checkIndex("Subsequence End Index", end - 1); + if (start > end) { + throw new IllegalArgumentException("Subsequence Start Index cannot be greater than Subsequence End Index"); + } + return new TimeBoundedCharSubsequence(this, start, end); + } + + @Override + public char first() { + this.iterIndex = this.getBeginIndex(); + if (this.length() == 0) { + return CharacterIterator.DONE; + } + return this.charAt(this.iterIndex); + } + + @Override + public char last() { + this.iterIndex = this.length() > 0 ? this.getEndIndex() - 1 : 0; + if (this.length() == 0) { + return CharacterIterator.DONE; + } + return this.charAt(this.iterIndex); + } + + @Override + public char current() { + if (this.iterIndex >= this.length()) { + return CharacterIterator.DONE; + } + return this.charAt(this.iterIndex); + } + + @Override + public char next() { + this.iterIndex++; + if (this.iterIndex >= this.getEndIndex()) { + this.iterIndex = this.getEndIndex(); + return CharacterIterator.DONE; + } + return this.charAt(this.iterIndex); + } + + @Override + public char previous() { + if (this.iterIndex == this.getBeginIndex()) { + return CharacterIterator.DONE; + } + this.iterIndex--; + return this.charAt(this.iterIndex); + } + + @Override + public char setIndex(int position) { + this.iterIndex = position; + if (this.iterIndex >= 0 && this.iterIndex < this.data.length()) { + if (this.iterIndex == this.getEndIndex()) { + return CharacterIterator.DONE; + } + return charAt(this.iterIndex); + } else { + throw new IllegalArgumentException("Invalid iterator position " + position); + } + } + + @Override + public int getBeginIndex() { + checkTimeLimit(); + return 0; + } + + @Override + public int getEndIndex() { + checkTimeLimit(); + return this.data.length(); + } + + @Override + public int getIndex() { + return this.iterIndex; + } + + @Override + public Object clone() { + throw new IllegalStateException("Unable to clone"); + } + + @Override + public String toString() { + return this.data.toString(); + } + + private static final class TimeBoundedCharSubsequence implements CharSequence { + private final TimeBoundedCharSequence parent; + private final int startIndex, endIndex, length; + + public TimeBoundedCharSubsequence(TimeBoundedCharSequence parent, int startIndex, int endIndex) { + this.parent = parent; + this.startIndex = startIndex; + this.endIndex = endIndex; + this.length = this.endIndex - this.startIndex; + } + + @Override + public int length() { + this.parent.checkTimeLimit(); + return this.length; + } + + @Override + public char charAt(int index) { + return this.parent.charAt(this.startIndex + index); + } + + @Override + public CharSequence subSequence(int start, int end) { + return this.parent.subSequence(this.startIndex + start, this.startIndex + end); + } + + @Override + public String toString() { + return this.parent.data.subSequence(this.startIndex, this.endIndex).toString(); + } + } + } + } diff --git a/jena-arq/src/main/java/org/apache/jena/sparql/pfunction/library/strSplit.java b/jena-arq/src/main/java/org/apache/jena/sparql/pfunction/library/strSplit.java index deb2ea23c0..96554f36d8 100644 --- a/jena-arq/src/main/java/org/apache/jena/sparql/pfunction/library/strSplit.java +++ b/jena-arq/src/main/java/org/apache/jena/sparql/pfunction/library/strSplit.java @@ -24,6 +24,7 @@ package org.apache.jena.sparql.pfunction.library ; import java.util.Arrays ; import java.util.Iterator ; import java.util.List; +import java.util.regex.Pattern; import org.apache.jena.atlas.iterator.Iter ; import org.apache.jena.atlas.lib.StrUtils ; @@ -37,6 +38,8 @@ import org.apache.jena.sparql.engine.QueryIterator ; import org.apache.jena.sparql.engine.binding.Binding ; import org.apache.jena.sparql.engine.binding.BindingFactory ; import org.apache.jena.sparql.engine.iterator.QueryIterPlainWrapper ; +import org.apache.jena.sparql.expr.ExprEvalException; +import org.apache.jena.sparql.expr.RegexEngine; import org.apache.jena.sparql.pfunction.PFuncSimpleAndList ; import org.apache.jena.sparql.pfunction.PropFuncArg ; import org.apache.jena.sparql.util.IterLib; @@ -73,7 +76,16 @@ public class strSplit extends PFuncSimpleAndList String regex = object.getArg(1).getLiteralLexicalForm() ; // StrUtils will also trim whitespace - List<String> tokens = Arrays.asList(StrUtils.split(s, regex)); + List<String> tokens; + if (RegexEngine.MAX_REGEX_EVALUATION_TIME > 0) { + Pattern pattern = Pattern.compile(regex); + tokens = Arrays.stream( + pattern.split(new RegexEngine.TimeBoundedCharSequence(s, RegexEngine.MAX_REGEX_EVALUATION_TIME), 0)) + .map(String::trim) + .toList(); + } else { + tokens = Arrays.asList(StrUtils.split(s, regex)); + } if (Var.isVar(subject)) { diff --git a/jena-arq/src/test/java/org/apache/jena/sparql/expr/TestRegex.java b/jena-arq/src/test/java/org/apache/jena/sparql/expr/TestRegex.java index 46be0830ca..3dfc4ca08f 100644 --- a/jena-arq/src/test/java/org/apache/jena/sparql/expr/TestRegex.java +++ b/jena-arq/src/test/java/org/apache/jena/sparql/expr/TestRegex.java @@ -122,7 +122,7 @@ public class TestRegex public static Stream<Arguments> backtrackingRegex() { return Stream.of( - Arguments.of("1,2,3,4,5,6,7,8,9,10,11,12,13", "^(.*?,){11}P", "m", false), + Arguments.of("a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,z,y,z", "^(.*?,){11}P", "m", false), Arguments.of(Strings.repeat("a", 4096) + "!", "(a+)+$", "m", false), Arguments.of(Strings.repeat("a", 32 * 1024) + "!", "(a+)+$", "m", false) ); @@ -130,8 +130,30 @@ public class TestRegex @ParameterizedTest(name = "{1}") @MethodSource("backtrackingRegex") - public void givenBacktrackingRegex_whenEvaluatingRegex_thenOk(String input, String pattern, String flags, boolean shouldMatch) { + public void givenBacktrackingRegex_whenEvaluatingRegexWithoutTimeLimit_thenEventuallyCompletes(String input, String pattern, String flags, boolean shouldMatch) { // Given, When and Then - regexTest(input, pattern, flags, shouldMatch); + long existingMax = RegexEngine.MAX_REGEX_EVALUATION_TIME; + try { + RegexEngine.MAX_REGEX_EVALUATION_TIME = -1; + regexTest(input, pattern, flags, shouldMatch); + } finally { + RegexEngine.MAX_REGEX_EVALUATION_TIME = existingMax; + } + } + + @ParameterizedTest(name = "{1}") + @MethodSource("backtrackingRegex") + public void givenBacktrackingRegex_whenEvaluatingRegexWithTimeLimit_thenFails(String input, String pattern, String flags, boolean shouldMatch) { + // Given, When and Then + long existingMax = RegexEngine.MAX_REGEX_EVALUATION_TIME; + try { + // Intentionally minimal evaluation time so should fail near immediately, while we could set a more + // realistic limit for the test the reality is that the different regex engines evaluate at different speed + // so it's hard to pick a limit that reliably fails other than a trivially small one + RegexEngine.MAX_REGEX_EVALUATION_TIME = 1; + assertThrows(ExprEvalException.class, () -> regexTest(input, pattern, flags, shouldMatch)); + } finally { + RegexEngine.MAX_REGEX_EVALUATION_TIME = existingMax; + } } } diff --git a/jena-arq/src/test/java/org/apache/jena/sparql/pfunction/library/TestStrSplit.java b/jena-arq/src/test/java/org/apache/jena/sparql/pfunction/library/TestStrSplit.java index 18aa7f73ca..5e0b299acb 100644 --- a/jena-arq/src/test/java/org/apache/jena/sparql/pfunction/library/TestStrSplit.java +++ b/jena-arq/src/test/java/org/apache/jena/sparql/pfunction/library/TestStrSplit.java @@ -21,24 +21,27 @@ package org.apache.jena.sparql.pfunction.library; -import static org.junit.jupiter.api.Assertions.assertArrayEquals; -import static org.junit.jupiter.api.Assertions.assertEquals; -import static org.junit.jupiter.api.Assertions.assertFalse; -import static org.junit.jupiter.api.Assertions.fail; - import java.util.ArrayList; import java.util.List; +import java.util.stream.Stream; +import org.apache.commons.lang3.StringUtils; +import org.apache.commons.lang3.Strings; +import org.apache.jena.query.*; +import org.apache.jena.sparql.expr.ExprEvalException; +import org.apache.jena.sparql.expr.RegexEngine; import org.junit.jupiter.api.Test; import org.apache.jena.graph.Node; import org.apache.jena.graph.NodeFactory; -import org.apache.jena.query.QueryBuildException; -import org.apache.jena.query.QueryExecution; -import org.apache.jena.query.QueryExecutionFactory; -import org.apache.jena.query.ResultSet; import org.apache.jena.rdf.model.ModelFactory; import org.apache.jena.sparql.core.Var; +import org.junit.jupiter.params.ParameterizedTest; +import org.junit.jupiter.params.provider.Arguments; +import org.junit.jupiter.params.provider.MethodSource; + +import static org.junit.jupiter.api.Assertions.*; +import static org.junit.jupiter.api.Assertions.assertTrue; public class TestStrSplit { private final static String prologue = @@ -121,6 +124,43 @@ public class TestStrSplit { assertAsk(false); } + public static Stream<Arguments> slowSplits() { + return Stream.of(Arguments.of(StringUtils.repeat("abc,", 1_000_000), ",", 1_000_000)); + } + + @ParameterizedTest(name = "{1}") + @MethodSource("slowSplits") + public void givenSlowRegex_whenSplittingWithTimeLimit_thenFails(String data, String pattern, int expectedResultCount) { + long existingLimit = RegexEngine.MAX_REGEX_EVALUATION_TIME; + try { + RegexEngine.MAX_REGEX_EVALUATION_TIME = 1; + query("SELECT ?x WHERE { ?x apf:strSplit ('" + data + "' '" + pattern + "') }"); + long start = System.currentTimeMillis(); + ExprEvalException e = assertThrows(ExprEvalException.class, () -> qe.execSelect().hasNext()); + long elapsed = System.currentTimeMillis() - start; + assertTrue(elapsed <= 250, "Elapsed time was " + elapsed); + assertTrue(Strings.CI.contains(e.getMessage(), "time limit exceeded")); + } finally { + RegexEngine.MAX_REGEX_EVALUATION_TIME = existingLimit; + } + } + + @ParameterizedTest(name = "{1}") + @MethodSource("slowSplits") + public void givenSlowRegex_whenSplittingWithNoTimeLimit_thenEventuallySucceeds(String data, String pattern, int expectedResultCount) { + long existingLimit = RegexEngine.MAX_REGEX_EVALUATION_TIME; + try { + // Given + query("SELECT ?x WHERE { ?x apf:strSplit ('" + data + "' '" + pattern + "') }"); + + // When and Then + RegexEngine.MAX_REGEX_EVALUATION_TIME = -1; + assertEquals(expectedResultCount, ResultSetFormatter.consume(qe.execSelect())); + } finally { + RegexEngine.MAX_REGEX_EVALUATION_TIME = existingLimit; + } + } + private void assertQueryBuildException(String selectQueryString) { try { query(selectQueryString); diff --git a/jena-base/src/main/java/org/apache/jena/atlas/lib/StrUtils.java b/jena-base/src/main/java/org/apache/jena/atlas/lib/StrUtils.java index dab1bfe933..a9582f2cf2 100644 --- a/jena-base/src/main/java/org/apache/jena/atlas/lib/StrUtils.java +++ b/jena-base/src/main/java/org/apache/jena/atlas/lib/StrUtils.java @@ -154,7 +154,7 @@ public class StrUtils //extends StringUtils return Objects.toString(x, "<null>"); } - /** Split but also trim whiespace. */ + /** Split but also trim whitespace. */ public static String[] split(String s, String splitStr) { return stream(s.split(splitStr)).map(String::trim).toArray(String[]::new) ; }
