naruto-lgtm commented on code in PR #1525:
URL: https://github.com/apache/poi/pull/1525#discussion_r4465448945


##########
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:
   Agreed, the length filter was only ever a cheap filter and an attacker picks 
the lengths. Replaced it with a tree of the name segments: a name is checked by 
walking it segment by segment, so the cost is linear in its length whatever 
else is registered, decoys included. Runs of segments without a branch or a 
name end are kept in one node, so memory stays linear in the registered names 
as well (a plain per-segment trie would have cost about 100x the zip size for 
1000 distinct deep paths). That also drops the length map, so there's no boxing 
or BitSet to worry about anymore.
   
   I checked the tree against the trunk algorithm over all names up to length 7 
over '/', 'a' and 'b', every ordered pair and 200k random put/remove sequences: 
14.5M operations, no difference. On your 500 decoys + 500 deep names case the 
tree does about 0.5 s of work for the 1000 names of 60k chars; the rest of the 
time opening such a package is PackagePartName.compare in the TreeMap, which 
lower-cases both names on every comparison, and that's linear per entry.



##########
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:
   Good catch. The tree is transient now and rebuilt from the keys of 
packagePartLookup on first use, so an instance serialized by an older version 
keeps working. The name set and the length map are gone, the tree is the one 
helper that put and remove go through.



##########
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:
   Agreed, left for a follow-up. With the segment tree it's a cheap extra check 
(a name that ends at a node with children, or inside a node, is a prefix of a 
registered name), so that can be a small separate change.



##########
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:
   Fixed. The tree lower-cases the names with Locale.ROOT, the same folding 
PackagePartName.hashCode uses, and part names are ASCII-only after validation, 
so this matches how packagePartLookup compares them. 
/Word/Document.xml/image1.gif is now rejected after /word/document.xml; covered 
by testDerivedPartNamesIgnoreCase.



##########
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 fix: remove goes through the same lower-cased lookup, so put('/A.xml'), 
remove('/a.xml'), put('/A.xml/x.xml') works now. Also in 
testDerivedPartNamesIgnoreCase.



##########
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:
   Reworked. The test builds a PackagePartCollection directly, registers 100 
names in the same folder whose lengths line up with the slashes of 100 deep 
names of about 4k chars, and asserts that the M1.11 check compared at most two 
characters per character of the deep names, read from a package-private counter 
on the collection. No zip, no wall clock, and it covers the decoy case; it runs 
in well under a second. If you'd rather not carry the counter in the class I 
can swap it for a timeout with a large margin instead.



-- 
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