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]