pjfanning commented on code in PR #1525:
URL: https://github.com/apache/poi/pull/1525#discussion_r4454724370


##########
poi-ooxml/src/main/java/org/apache/poi/openxml4j/opc/PackagePartCollection.java:
##########
@@ -63,17 +71,24 @@ public final class PackagePartCollection implements 
Serializable {
      */
     public PackagePart put(final PackagePartName partName, final PackagePart 
part) {
         final String ppName = partName.getName();
-        final StringBuilder concatSeg = new StringBuilder();
-        // split at slash, but keep leading slash
-        final String delim = 
"(?=["+PackagingURIHelper.FORWARD_SLASH_STRING+"])";
-        for (String seg : ppName.split(delim)) {
-            concatSeg.append(seg);
-            if (registerPartNameStr.contains(concatSeg.toString())) {
+        // check the name up to each slash (but the leading one) and the whole 
name -
+        // only build the prefixes which are as long as a registered name, as 
building
+        // every prefix takes quadratic time for deeply nested names
+        int end = ppName.indexOf(PackagingURIHelper.FORWARD_SLASH_CHAR, 1);

Review Comment:
   Older gap, not introduced here: M1.11 is only checked one way. Adding a part 
whose name is a prefix of an existing part is not rejected, so 
`/word/document.xml/x.xml` followed by `/word/document.xml` opens fine, while 
the reverse order throws. Whether a package is accepted therefore depends on 
the order of its zip entries. Fine as a follow-up.



##########
poi-ooxml/src/main/java/org/apache/poi/openxml4j/opc/PackagePartCollection.java:
##########
@@ -63,17 +71,24 @@ public final class PackagePartCollection implements 
Serializable {
      */
     public PackagePart put(final PackagePartName partName, final PackagePart 
part) {
         final String ppName = partName.getName();
-        final StringBuilder concatSeg = new StringBuilder();
-        // split at slash, but keep leading slash
-        final String delim = 
"(?=["+PackagingURIHelper.FORWARD_SLASH_STRING+"])";
-        for (String seg : ppName.split(delim)) {
-            concatSeg.append(seg);
-            if (registerPartNameStr.contains(concatSeg.toString())) {
+        // check the name up to each slash (but the leading one) and the whole 
name -
+        // only build the prefixes which are as long as a registered name, as 
building
+        // every prefix takes quadratic time for deeply nested names
+        int end = ppName.indexOf(PackagingURIHelper.FORWARD_SLASH_CHAR, 1);
+        while (true) {
+            final int len = (end < 0) ? ppName.length() : end;
+            if (registerPartNameLengths.containsKey(len)
+                    && registerPartNameStr.contains(ppName.substring(0, len))) 
{

Review Comment:
   Older gap, not introduced here: part names are equal regardless of case (and 
`packagePartLookup` compares them that way), but this lookup is case-sensitive. 
So `/Word/Document.xml/image1.gif` is accepted after `/word/document.xml` is 
registered.



##########
poi-ooxml/src/main/java/org/apache/poi/openxml4j/opc/PackagePartCollection.java:
##########
@@ -63,17 +71,24 @@ public final class PackagePartCollection implements 
Serializable {
      */
     public PackagePart put(final PackagePartName partName, final PackagePart 
part) {
         final String ppName = partName.getName();
-        final StringBuilder concatSeg = new StringBuilder();
-        // split at slash, but keep leading slash
-        final String delim = 
"(?=["+PackagingURIHelper.FORWARD_SLASH_STRING+"])";
-        for (String seg : ppName.split(delim)) {
-            concatSeg.append(seg);
-            if (registerPartNameStr.contains(concatSeg.toString())) {
+        // check the name up to each slash (but the leading one) and the whole 
name -
+        // only build the prefixes which are as long as a registered name, as 
building
+        // every prefix takes quadratic time for deeply nested names
+        int end = ppName.indexOf(PackagingURIHelper.FORWARD_SLASH_CHAR, 1);
+        while (true) {
+            final int len = (end < 0) ? ppName.length() : end;
+            if (registerPartNameLengths.containsKey(len)

Review Comment:
   The length filter only helps when the registered names don't have lengths 
that line up with the slash positions, and an attacker controls both. For 
example, take ~500 decoy entries with distinct lengths in 30,000..31,000 (none 
of them a prefix of the other names), plus ~500 entries like `/a/a/.../N.xml` 
of ~60,000 chars. Each deep name then matches ~500 lengths and builds and 
hashes a ~30k-char substring for each one, about 7.5e9 chars per file during 
`OPCPackage.open`. So the worst case is still O(entries × depth × name length).
   
   A trie over the segments (or a rolling hash over the name, compared only on 
a hash hit) would make this linear in the name length.
   
   Also minor: `containsKey(len)` boxes an `Integer` at every slash. A `BitSet` 
or `int[]` indexed by length (zip entry names are at most 65,535 chars) would 
avoid the boxing and hashing.



##########
poi-ooxml/src/test/java/org/apache/poi/openxml4j/opc/TestPackagePartCollection.java:
##########
@@ -42,4 +51,43 @@ void testPackagePartCollection_64473() throws Exception {
         }
     }
 
+    /**
+     * Checking rule M1.11 used to build and look up every prefix of a part 
name,
+     * which is quadratic in the length of deeply nested names
+     */
+    @Test
+    void testDeeplyNestedPartNames() throws Exception {
+        UnsynchronizedByteArrayOutputStream bos = 
UnsynchronizedByteArrayOutputStream.builder().get();
+        try (ZipOutputStream zos = new ZipOutputStream(bos)) {
+            zos.putNextEntry(new ZipEntry("[Content_Types].xml"));
+            zos.write(("<Types 
xmlns=\"http://schemas.openxmlformats.org/package/2006/content-types\";>" +
+                "<Default Extension=\"xml\" 
ContentType=\"application/xml\"/></Types>").getBytes(StandardCharsets.UTF_8));
+            String folder = "a/".repeat(30_000);
+            for (int i = 0; i < 20; i++) {
+                zos.putNextEntry(new ZipEntry(folder + i + ".xml"));
+                zos.write("<x/>".getBytes(StandardCharsets.UTF_8));
+            }
+        }
+
+        int parts = assertTimeoutPreemptively(Duration.ofSeconds(10), () -> {

Review Comment:
   A 10 s wall-clock timeout on building and opening a ~1.2 MB zip could be 
flaky on loaded CI or with coverage instrumentation, and it would not catch the 
remaining slow case described on `PackagePartCollection` line 80. Testing 
`PackagePartCollection.put` directly, with a smaller input and a test that 
compares work done rather than elapsed time, would be more robust.



##########
poi-ooxml/src/main/java/org/apache/poi/openxml4j/opc/PackagePartCollection.java:
##########
@@ -44,6 +46,12 @@ public final class PackagePartCollection implements 
Serializable {
      */
     private final Set<String> registerPartNameStr = new HashSet<>();
 
+    /**
+     * The lengths of the names in {@link #registerPartNameStr}, with the 
number
+     * of names of each length.
+     */

Review Comment:
   `PackagePartCollection` is `Serializable`, so an instance serialized by an 
older POI version deserializes with this field as `null`, and the next `put()` 
throws an NPE. Making it `transient` and rebuilding it lazily from 
`registerPartNameStr` would avoid that.
   
   It would also help to wrap the name set and its length counts in one small 
helper. As it is, `put`/`remove` (and any future mutator) have to keep the two 
in sync by hand.



##########
poi-ooxml/src/main/java/org/apache/poi/openxml4j/opc/PackagePartCollection.java:
##########
@@ -83,8 +98,8 @@ public PackagePart remove(PackagePartName key) {
         }
         final String ppName = key.getName();
         PackagePart pp = packagePartLookup.remove(ppName);
-        if (pp != null) {
-            this.registerPartNameStr.remove(ppName);
+        if (pp != null && this.registerPartNameStr.remove(ppName)) {

Review Comment:
   Same case issue here: `packagePartLookup.remove` matches regardless of case, 
but `registerPartNameStr.remove(ppName)` is exact. After `put('/A.xml')` and 
then `remove('/a.xml')`, the part is gone but `/A.xml` stays in the set and the 
length counts, so a later valid `/A.xml/x` is wrongly rejected. This existed 
before for the set; the new length map now inherits it.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]


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

Reply via email to