pjfanning opened a new pull request, #1439:
URL: https://github.com/apache/poi/pull/1439
Three regexes take quadratic time on input that has no match. All three
fixes give exactly the same output as before.
## Repro and cause
- `HeaderFooter.stripFields` (also used by `XSSFHeaderFooter.stripFields`
and `setAreFieldsStripped(true)`) runs `replaceAll("&\".*?,.*?\"", "")`. For
`&"` followed by 20,000 commas, or `&"` repeated 20,000 times, each start
position scans to the end of the line before it fails. Times: 4.4 s and 10.3 s.
- `OOXMLSignatureFacet.isSignedRelationship` runs
`replaceFirst(".*/relationships/", "")` on the relationship type.
`addManifestReferences` runs `replaceFirst("(.*)/_rels/.*", "$1")` on each rels
part name. Without the literal, `.*` is retried from every start position.
`"a"` x 20,000 takes 7.1 s, and `"/" + "a"` x 20,000 takes 10.9 s. These only
run when signing a document.
- `XSLFComment.setAuthor` works out the initials of a new author with
`replaceAll("\\s*(\\w)\\S*", "$1")`. A run of 20,000 spaces with no word
character after it takes 11-13 s.
## Fix
- `stripFontNames` replaces the regex with a hand-written scan. From each
`&"`, it looks for the first `,` and then the first `"` after that comma,
stopping at a line terminator (the characters `.` does not match). If one isn't
found, no later match can start before the end of that line, so the scan goes
straight on from there. Order relative to the other `replaceAll` calls in
`stripFields` is unchanged.
- `OOXMLSignatureFacet` patterns are prefixed with `(?<!.)`. If a match
starts at a position preceded by a non-terminator character, a match also
starts one character earlier. So the leftmost match always starts at a line
start, and the lookbehind only removes start positions that could never be the
leftmost one. Greedy `.*` then picks the same end.
- `XSLFComment` pattern is prefixed with `(?<!\s)`, by the same argument: a
match starting inside a whitespace run implies one starting earlier in the run.
After a match, `\S*` stops at whitespace or the end, so the next search
position is preceded by a non-space and is not affected.
## Equivalence check
Old and new were compared with exhaustive programs:
- stripFields over all strings up to length 9 from `{& " , a \n U+2028}`,
and up to length 7 from `{& " , \r U+0085 U+2029 and the two halves of a
surrogate pair}`. That is 14.5M strings.
- Both signature patterns with a short literal (`/r/`) at character level,
up to length 7 over `{/ r a \n \r U+0085 U+2029, surrogate halves}`. Then with
the real literals at token level (literal, partial literals, `a`, `/`, line
terminators, surrogate pair, lone surrogate), up to 6 tokens.
- The initials pattern over 10 tokens (space, tab, VT, `\n`, `a`, `!`, `_`,
`é`, NBSP, surrogate pair) up to length 7. That is 11.1M strings.
No differences were found. With the new code, every adversarial input above
runs in 0-2 ms.
## Tests
New tests use `assertTimeoutPreemptively(10 s)` with 50,000-character
inputs. Each one timed out on the old code and passes with the fix, and each
also checks the result:
- `TestHSSFHeaderFooter`: `testStripFieldsFontNames` (line-terminator
semantics) and `testStripFieldsUnclosedFontName`. 11 tests, all pass.
- `TestSignatureInfo.isSignedRelationship`. The full class passes: 31 tests,
1 skipped, which was already `@Disabled`.
- `TestXMLSlideShow.testCommentAuthorInitials`. 16 tests, all pass.
- `TestXSSFHeaderFooter`: 10 tests, all pass.
There is no test for `addManifestReferences`, because it needs a crafted
package to be signed. It uses the same rewrite as `isSignedRelationship` and is
covered by the equivalence check.
## Not changed
The `\s*,\s*` split in `XSSFDataValidationConstraint` has the same quadratic
shape. But the constructor calls `validate()` first, and that rejects list
formulas longer than 257 characters. So the split never sees more than 257
characters, and it is left alone.
🤖 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]
