This is an automated email from the ASF dual-hosted git repository.

pjfanning pushed a commit to branch trunk
in repository https://gitbox.apache.org/repos/asf/poi.git


The following commit(s) were added to refs/heads/trunk by this push:
     new ce07f72083 openxml4j: avoid regex backtracking and recursion in part 
name and content type checks (#1438)
ce07f72083 is described below

commit ce07f720837c6a2260d03662b015ea975c55f54d
Author: PJ Fanning <[email protected]>
AuthorDate: Sun Oct 18 10:51:16 2026 +0100

    openxml4j: avoid regex backtracking and recursion in part name and content 
type checks (#1438)
    
    * openxml4j: avoid regex backtracking and recursion when loading part names 
and content types
    
    PackagePartName.isRelationshipPartURI and 
PackagingURIHelper.isRelationshipPartURI
    matched "^.*/_rels/.*\.rels$" and ".*_rels.*.rels$", which backtrack 
quadratically
    on "/_rels" (or "_rels") repeated. Both are replaced by indexOf/endsWith 
checks
    that give the same result for every string.
    
    ContentType matched parameters with "(;parameter)*$", which recurses per
    parameter and throws StackOverflowError at around 1,000 parameters. The
    parameters are now matched one at a time with lookingAt.
    
    Co-Authored-By: Claude Opus 5.5 <[email protected]>
    
    * Use escapes for U+2028/U+2029 in hasLineTerminator
    
    Co-Authored-By: Claude Opus 5.5 <[email protected]>
    
    ---------
    
    Co-authored-by: Claude Opus 5.5 <[email protected]>
---
 .../apache/poi/openxml4j/opc/PackagePartName.java  | 15 +++--
 .../poi/openxml4j/opc/PackagingURIHelper.java      | 33 ++++++++++-
 .../poi/openxml4j/opc/internal/ContentType.java    | 64 +++++++++++-----------
 .../apache/poi/openxml4j/opc/TestContentType.java  | 19 +++++++
 .../poi/openxml4j/opc/TestPackagePartName.java     | 25 +++++++++
 .../poi/openxml4j/opc/TestPackagingURIHelper.java  | 26 +++++++++
 6 files changed, 143 insertions(+), 39 deletions(-)

diff --git 
a/poi-ooxml/src/main/java/org/apache/poi/openxml4j/opc/PackagePartName.java 
b/poi-ooxml/src/main/java/org/apache/poi/openxml4j/opc/PackagePartName.java
index 100828196c..d48d5965a2 100644
--- a/poi-ooxml/src/main/java/org/apache/poi/openxml4j/opc/PackagePartName.java
+++ b/poi-ooxml/src/main/java/org/apache/poi/openxml4j/opc/PackagePartName.java
@@ -141,10 +141,17 @@ public final class PackagePartName implements 
Comparable<PackagePartName> {
         }
 
         final String uriPath = partUri.getPath();
-        return uriPath != null && uriPath.matches(
-                "^.*/" + PackagingURIHelper.RELATIONSHIP_PART_SEGMENT_NAME + 
"/.*\\"
-                        + PackagingURIHelper.RELATIONSHIP_PART_EXTENSION_NAME
-                        + "$");
+        if (uriPath == null || PackagingURIHelper.hasLineTerminator(uriPath)
+                || 
!uriPath.endsWith(PackagingURIHelper.RELATIONSHIP_PART_EXTENSION_NAME)) {
+            return false;
+        }
+
+        // same result as uriPath.matches("^.*/_rels/.*\\.rels$") but without 
the regex,
+        // which backtracks quadratically on "/_rels" repeated
+        final String segment = "/" + 
PackagingURIHelper.RELATIONSHIP_PART_SEGMENT_NAME + "/";
+        final int index = uriPath.indexOf(segment);
+        return index >= 0 && index + segment.length()
+                <= uriPath.length() - 
PackagingURIHelper.RELATIONSHIP_PART_EXTENSION_NAME.length();
     }
 
     /**
diff --git 
a/poi-ooxml/src/main/java/org/apache/poi/openxml4j/opc/PackagingURIHelper.java 
b/poi-ooxml/src/main/java/org/apache/poi/openxml4j/opc/PackagingURIHelper.java
index 7d3001d332..8f8c3408cb 100644
--- 
a/poi-ooxml/src/main/java/org/apache/poi/openxml4j/opc/PackagingURIHelper.java
+++ 
b/poi-ooxml/src/main/java/org/apache/poi/openxml4j/opc/PackagingURIHelper.java
@@ -167,10 +167,37 @@ public final class PackagingURIHelper {
             throw new IllegalArgumentException("partUri");
 
         final String path = partUri.getPath();
+        if (path == null || hasLineTerminator(path)) {
+            return false;
+        }
 
-        return path != null && path.matches(
-                ".*" + RELATIONSHIP_PART_SEGMENT_NAME + ".*"
-                        + RELATIONSHIP_PART_EXTENSION_NAME + "$");
+        // same result as path.matches(".*_rels.*.rels$") - the '.' before 
"rels" is any
+        // character - but without the regex, which backtracks quadratically 
on "_rels" repeated
+        final int segment = path.indexOf(RELATIONSHIP_PART_SEGMENT_NAME);
+        final int extension = path.length() - 
RELATIONSHIP_PART_EXTENSION_NAME.length();
+        return segment >= 0
+                && segment + RELATIONSHIP_PART_SEGMENT_NAME.length() <= 
extension
+                && 
path.startsWith(RELATIONSHIP_PART_EXTENSION_NAME.substring(1), extension + 1);
+    }
+
+    /**
+     * Whether the string contains a line terminator, i.e. a character that the
+     * regex {@code .} does not match by default (see {@link Pattern}).
+     */
+    static boolean hasLineTerminator(String s) {
+        for (int i = 0; i < s.length(); i++) {
+            switch (s.charAt(i)) {
+                case '\n':
+                case '\r':
+                case '\u0085':
+                case '\u2028':
+                case '\u2029':
+                    return true;
+                default:
+                    break;
+            }
+        }
+        return false;
     }
 
     /**
diff --git 
a/poi-ooxml/src/main/java/org/apache/poi/openxml4j/opc/internal/ContentType.java
 
b/poi-ooxml/src/main/java/org/apache/poi/openxml4j/opc/internal/ContentType.java
index dbe3aa3209..f760ab52a4 100644
--- 
a/poi-ooxml/src/main/java/org/apache/poi/openxml4j/opc/internal/ContentType.java
+++ 
b/poi-ooxml/src/main/java/org/apache/poi/openxml4j/opc/internal/ContentType.java
@@ -17,7 +17,6 @@
 
 package org.apache.poi.openxml4j.opc.internal;
 
-import java.util.Collections;
 import java.util.HashMap;
 import java.util.Map;
 import java.util.Locale;
@@ -72,9 +71,10 @@ public final class ContentType {
      */
     private static final Pattern patternTypeSubType;
     /**
-     * Media type compiled pattern, with parameters.
+     * Media type compiled pattern, without parameters, matched as a prefix of
+     * a content type that has parameters.
      */
-    private static final Pattern patternTypeSubTypeParams;
+    private static final Pattern patternTypeSubTypePrefix;
     /**
      * Pattern to match on just the parameters part, to work
      * around the Java Regexp group capture behaviour
@@ -130,8 +130,8 @@ public final class ContentType {
 
         patternTypeSubType       = Pattern.compile("^(" + token + "+)/(" +
                                                    token + "+)$");
-        patternTypeSubTypeParams = Pattern.compile("^(" + token + "+)/(" +
-                                                   token + "+)(;" + parameter 
+ ")*$");
+        patternTypeSubTypePrefix = Pattern.compile("^(" + token + "+)/(" +
+                                                   token + "+)");
         patternParams            = Pattern.compile(";" + parameter);
     }
 
@@ -145,38 +145,38 @@ public final class ContentType {
      */
     public ContentType(String contentType) throws InvalidFormatException {
         Matcher mMediaType = patternTypeSubType.matcher(contentType);
+        this.parameters = new HashMap<>();
         if (!mMediaType.matches()) {
-            // How about with parameters?
-            mMediaType = patternTypeSubTypeParams.matcher(contentType);
-        }
-        if (!mMediaType.matches()) {
-            throw new InvalidFormatException(
-                    "The specified content type '"
-                    + contentType
-                    + "' is not compliant with RFC 2616: malformed content 
type.");
+            // How about with parameters? Match them one at a time rather than 
with
+            // a single (;parameter)*$ regex, which recurses per parameter and 
throws
+            // StackOverflowError on a content type with many parameters.
+            // A parameter can only be followed by ';' or the end of the 
string,
+            // so this accepts and extracts exactly what that regex did.
+            mMediaType = patternTypeSubTypePrefix.matcher(contentType);
+            if (!mMediaType.lookingAt()) {
+                throw malformed(contentType);
+            }
+            Matcher mParams = patternParams.matcher(contentType);
+            int end = contentType.length();
+            for (int pos = mMediaType.end(); pos < end; pos = mParams.end()) {
+                mParams.region(pos, end);
+                if (!mParams.lookingAt()) {
+                    throw malformed(contentType);
+                }
+                this.parameters.put(mParams.group(1), mParams.group(2));
+            }
         }
 
         // Type/subtype
-        if (mMediaType.groupCount() >= 2) {
-            this.type = mMediaType.group(1);
-            this.subType = mMediaType.group(2);
+        this.type = mMediaType.group(1);
+        this.subType = mMediaType.group(2);
+    }
 
-            // Parameters
-            this.parameters = new HashMap<>();
-            // Java RegExps are unhelpful, and won't do multiple group captures
-            // See 
http://docs.oracle.com/javase/6/docs/api/java/util/regex/Pattern.html#cg
-            if (mMediaType.groupCount() >= 5) {
-                Matcher mParams = 
patternParams.matcher(contentType.substring(mMediaType.end(2)));
-                while (mParams.find()) {
-                    this.parameters.put(mParams.group(1), mParams.group(2));
-                }
-            }
-        } else {
-            // missing media type and subtype
-            this.type = "";
-            this.subType = "";
-            this.parameters = Collections.emptyMap();
-        }
+    private static InvalidFormatException malformed(String contentType) {
+        return new InvalidFormatException(
+                "The specified content type '"
+                + contentType
+                + "' is not compliant with RFC 2616: malformed content type.");
     }
 
     /**
diff --git 
a/poi-ooxml/src/test/java/org/apache/poi/openxml4j/opc/TestContentType.java 
b/poi-ooxml/src/test/java/org/apache/poi/openxml4j/opc/TestContentType.java
index d69bff5a24..9e03f89e09 100644
--- a/poi-ooxml/src/test/java/org/apache/poi/openxml4j/opc/TestContentType.java
+++ b/poi-ooxml/src/test/java/org/apache/poi/openxml4j/opc/TestContentType.java
@@ -99,6 +99,25 @@ public final class TestContentType {
         assertDoesNotThrow(() -> new ContentType(contentType));
     }
 
+    /**
+     * The single regex this used to be matched with recursed per parameter 
and threw StackOverflowError
+     */
+    @Test
+    void testContentTypeWithManyParameters() throws InvalidFormatException {
+        StringBuilder sb = new StringBuilder("application/x-test");
+        for (int i = 0; i < 5000; i++) {
+            sb.append(";p").append(i).append("=\"v").append(i).append('"');
+        }
+        ContentType contentType = new ContentType(sb.toString());
+        assertEquals("application", contentType.getType());
+        assertEquals("x-test", contentType.getSubType());
+        assertEquals(5000, contentType.getParameterKeys().length);
+        assertEquals("\"v4999\"", contentType.getParameter("p4999"));
+
+        sb.append(";bad");
+        assertThrows(InvalidFormatException.class, () -> new 
ContentType(sb.toString()));
+    }
+
     /**
      * Check rule [O1.2]: Format designers might restrict the usage of
      * parameters for content types.
diff --git 
a/poi-ooxml/src/test/java/org/apache/poi/openxml4j/opc/TestPackagePartName.java 
b/poi-ooxml/src/test/java/org/apache/poi/openxml4j/opc/TestPackagePartName.java
index 0ad3f54573..4de7584b9d 100644
--- 
a/poi-ooxml/src/test/java/org/apache/poi/openxml4j/opc/TestPackagePartName.java
+++ 
b/poi-ooxml/src/test/java/org/apache/poi/openxml4j/opc/TestPackagePartName.java
@@ -18,7 +18,12 @@
 package org.apache.poi.openxml4j.opc;
 
 import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertFalse;
 import static org.junit.jupiter.api.Assertions.assertNotNull;
+import static org.junit.jupiter.api.Assertions.assertTimeoutPreemptively;
+import static org.junit.jupiter.api.Assertions.assertTrue;
+
+import java.time.Duration;
 
 import org.junit.jupiter.api.Test;
 
@@ -56,4 +61,24 @@ public final class TestPackagePartName {
         assertEquals(partName.getURI(),
                 
PackagingURIHelper.getSourcePartUriFromRelationshipPartUri(relName.getURI()));
     }
+
+    @Test
+    void testIsRelationshipPartURI() throws Exception {
+        
assertTrue(PackagingURIHelper.createPartName("/_rels/.rels").isRelationshipPartURI());
+        
assertTrue(PackagingURIHelper.createPartName("/word/_rels/document.xml.rels").isRelationshipPartURI());
+        
assertFalse(PackagingURIHelper.createPartName("/word/document.xml").isRelationshipPartURI());
+        
assertFalse(PackagingURIHelper.createPartName("/word/_rels/document.xml").isRelationshipPartURI());
+        
assertFalse(PackagingURIHelper.createPartName("/word/_rels.rels").isRelationshipPartURI());
+    }
+
+    /**
+     * The regex this used to be checked with backtracked quadratically on 
"/_rels" repeated
+     */
+    @Test
+    void testIsRelationshipPartURISlowness() throws Exception {
+        String name = "/_rels".repeat(40_000) + "/x";
+        Boolean result = assertTimeoutPreemptively(Duration.ofSeconds(10),
+                () -> 
PackagingURIHelper.createPartName(name).isRelationshipPartURI());
+        assertFalse(result);
+    }
 }
diff --git 
a/poi-ooxml/src/test/java/org/apache/poi/openxml4j/opc/TestPackagingURIHelper.java
 
b/poi-ooxml/src/test/java/org/apache/poi/openxml4j/opc/TestPackagingURIHelper.java
index 714d81180b..97f291502d 100644
--- 
a/poi-ooxml/src/test/java/org/apache/poi/openxml4j/opc/TestPackagingURIHelper.java
+++ 
b/poi-ooxml/src/test/java/org/apache/poi/openxml4j/opc/TestPackagingURIHelper.java
@@ -17,9 +17,13 @@
 package org.apache.poi.openxml4j.opc;
 
 import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertFalse;
 import static org.junit.jupiter.api.Assertions.assertNotNull;
+import static org.junit.jupiter.api.Assertions.assertTimeoutPreemptively;
+import static org.junit.jupiter.api.Assertions.assertTrue;
 
 import java.net.URI;
+import java.time.Duration;
 
 import org.apache.poi.openxml4j.exceptions.InvalidFormatException;
 import org.junit.jupiter.api.Test;
@@ -143,4 +147,26 @@ class TestPackagingURIHelper {
         assertEquals("javascript:///", uri.toASCIIString());
     }
 
+    @Test
+    void testIsRelationshipPartURI() throws Exception {
+        assertTrue(PackagingURIHelper.isRelationshipPartURI(new 
URI("/_rels/.rels")));
+        assertTrue(PackagingURIHelper.isRelationshipPartURI(new 
URI("/word/_rels/document.xml.rels")));
+        // the '.' before "rels" matches any character
+        assertTrue(PackagingURIHelper.isRelationshipPartURI(new 
URI("/_relsxrels")));
+        assertTrue(PackagingURIHelper.isRelationshipPartURI(new 
URI("/_rels.rels")));
+        assertFalse(PackagingURIHelper.isRelationshipPartURI(new 
URI("/_relsrels")));
+        assertFalse(PackagingURIHelper.isRelationshipPartURI(new 
URI("/word/document.xml")));
+        assertFalse(PackagingURIHelper.isRelationshipPartURI(new 
URI("/_rels/x%0A.rels")));
+    }
+
+    /**
+     * The regex this used to be checked with backtracked quadratically on 
"_rels" repeated
+     */
+    @Test
+    void testIsRelationshipPartURISlowness() throws Exception {
+        URI uri = new URI("_rels".repeat(40_000) + "x");
+        Boolean result = assertTimeoutPreemptively(Duration.ofSeconds(10),
+                () -> PackagingURIHelper.isRelationshipPartURI(uri));
+        assertFalse(result);
+    }
 }


---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Reply via email to