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) ;
     }

Reply via email to