pjfanning opened a new pull request, #1438:
URL: https://github.com/apache/poi/pull/1438
Three regex problems in openxml4j that are reachable while loading a
package: every zip entry name and every `[Content_Types].xml` PartName goes
through `isRelationshipPartURI`, and every Default/Override `ContentType` value
goes through `new ContentType(...)`.
## Repro
- `PackagingURIHelper.createPartName("/_rels".repeat(40_000) +
"/x").isRelationshipPartURI()` runs for well over 10 s.
- `PackagingURIHelper.isRelationshipPartURI(new URI("_rels".repeat(40_000) +
"x"))` likewise.
- `new ContentType("application/x-test;p0=v;p1=v;...")` with 1,000 or more
parameters throws `StackOverflowError`.
## Cause
- `PackagePartName.isRelationshipPartURI` used
`uriPath.matches("^.*/_rels/.*\\.rels$")`. For each `/_rels/` occurrence the
second `.*` scans to the end and backtracks, so it is quadratic in the number
of occurrences.
- `PackagingURIHelper.isRelationshipPartURI(URI)` used
`path.matches(".*_rels.*.rels$")`, same problem (the `.` before `rels` is
unescaped, so it is any character).
- `ContentType` validated with `^(t+)/(t+)(;(t+)=("?t+"?))*$`. Java's regex
engine recurses once per repetition of the group, so a long but valid parameter
list overflows the stack.
## Fix
- `PackagePartName`: no line terminator in the path, path ends with `.rels`,
and the first `/_rels/` ends at or before the start of that `.rels`.
- `PackagingURIHelper`: no line terminator, the first `_rels` ends at or
before `length - 5`, and the path ends with any character followed by `rels`. A
package-private `hasLineTerminator` helper (the characters `.` does not match:
`\n \r \u0085
`) is shared by both.
- `ContentType`: the type/subtype-only pattern is tried first as before.
Otherwise type/subtype is matched as a prefix with `lookingAt`, then each
`;attr=value` is matched with `lookingAt` on the remaining region until the end
of the string. Since a parameter can only be followed by `;` or the end, this
accepts the same strings and extracts the same parameters as the old full match
+ `find` loop. Exception message unchanged. The `groupCount() < 2` branch was
unreachable and is gone.
## Equivalence check
Old vs new, run with `java File.java`, comparing the boolean result (for
`isRelationshipPartURI`) or the type, subtype and parameter map / exception
(for `ContentType`):
| Check | Strings compared | Mismatches |
|---|---|---|
| `PackagePartName` pattern: all strings up to length 8 over `/ _ r s . \n
`, up to length 5 over `/ _ r e l s . x \n \r \u0085
`, token sequences
(`/`, `_rels`, `.rels`, `rels`, `x`, `.`, each line terminator) up to 6 tokens
| 9,076,552 | 0 |
| `PackagingURIHelper` pattern: same char sets as above, token sequences up
to 6, all strings up to length 9 over `_ r e l s x \n` | 57,464,480 | 0 |
| `ContentType`: all strings up to length 8 over `a b / ; = " space \n`, up
to length 11 over `a / ; = "`, token sequences (`a/b`, `;`, `x=1`, `x="2"`,
`y="3`, `z=4"`, `=`, `"`, `/`, `a`, `;x`, `\n`) up to 6 | 83,466,554 | 0 |
## Timings (old vs new)
| Input | Old | New |
|---|---|---|
| `PackagePartName`, `"/_rels"` repeated + `/`, 5k chars | 34 ms | 0.006 ms |
| same, 20k chars | 579 ms | 0.018 ms |
| same, 80k chars | 13.8 s | 0.07 ms |
| `PackagingURIHelper`, `"_rels"` repeated + `x`, 5k chars | 73 ms | 0.008
ms |
| same, 20k chars | 1.5 s | 0.03 ms |
| same, 80k chars | 25.7 s | 0.1 ms |
| `ContentType`, 500 parameters | 2.9 ms | 1.9 ms |
| `ContentType`, 1,000 / 5,000 / 50,000 parameters | StackOverflowError |
2.7 / 11.5 / 164 ms |
## Tests
New tests: `TestPackagePartName.testIsRelationshipPartURI`,
`testIsRelationshipPartURISlowness`;
`TestPackagingURIHelper.testIsRelationshipPartURI`,
`testIsRelationshipPartURISlowness`;
`TestContentType.testContentTypeWithManyParameters` (5,000 parameters). Against
the old code the two slowness tests time out at 10 s and the content type test
fails with `StackOverflowError`.
Ran `TestPackagePartName`, `TestPackagingURIHelper`, `TestContentType`,
`TestContentTypeManager`, `TestRelationships`: 66 tests, all pass.
🤖 Generated with [Claude Code](https://claude.com/claude-code)
--
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]
