pjfanning opened a new pull request, #1442:
URL: https://github.com/apache/poi/pull/1442
Three places run regular expressions over file content that backtrack
quadratically on crafted input. Each fix keeps the same accept/reject results
and the same captured groups.
## Repro and cause
**`sl.draw.geom.Context.DOUBLE_PATTERN`** (the `Double.valueOf` javadoc
regex, used by `getValue` on guide formula operands and path values from PPTX
`a:custGeom`). On `"1" * n + "x"`, the digits can be split between
`(\p{Digit}+)` and the optional `(\p{Digit}+)?` after the optional `.` in every
possible way before the match fails.
**`hwpf.converter.AbstractWordConverter`** field patterns:
- `PATTERN_HYPERLINK_EXTERNAL` `^[ \t\r\n]*HYPERLINK "(.*)".*$` on
`HYPERLINK "` + `"` * n + `"\nx`: every `"` is tried as the closing quote, and
each time `.*$` scans to the line break.
- `PATTERN_HYPERLINK_LOCAL` `^[ \t\r\n]*HYPERLINK \\l "(.*)"[ ](.*)$` on
`HYPERLINK \l "` + `" ` * n + `\nx`: same problem.
- `PATTERN_PAGEREF` `^[ \t\r\n]*PAGEREF ([^ ]*)[ \t\r\n]*\\h.*$` on `PAGEREF
` + `\t` * n + `x` (`([^ ]*)` and `[ \t\r\n]*` compete for the tabs), and on
`PAGEREF ` + `\h` * n + `\n\n` (every `\h` is retried against a failing `.*$`).
**`hsmf.MAPIMessage.guess7BitEncoding`** (called by `OutlookTextExtractor`),
`content-type:.*?charset=["']?([^;'"]+)["']?` with `matches()` on transport
header lines. On `content-type:` + `charset=a` * k + `;`, every `charset=` is
tried, and each time `[^;'"]+` scans to the trailing `;`.
## Fix
- `Context`: the digit runs are now possessive (`\p{Digit}++`,
`\p{XDigit}++`). Giving digits back can't turn a failed match into a successful
one, because whatever follows each run can't start with a digit, or (for the
first run) the next run just picks up the same digits and ends at the same
place.
- `AbstractWordConverter`: the leading part of each pattern is wrapped in an
atomic group, so only its longest match is kept:
- `^[ \t\r\n]*HYPERLINK "(?>(.*)").*$`
- `^[ \t\r\n]*HYPERLINK \\l "(?>(.*)"[ ])(.*)$`
- `^[ \t\r\n]*PAGEREF (?>([^ ]*)(?: [ \t\r\n]*+)?\\h).*$`
The old patterns used the longest match anyway (greedy). When the trailing
`.*$` fails, it fails because of a line break that every shorter match would
hit as well, so trying them again can't help. In PAGEREF, the whitespace
between `([^ ]*)` and `\h` now has to start with a space. Tabs or line breaks
right after the group would have been taken by `([^ ]*)` itself on an earlier,
longer attempt, so this doesn't change what matches. It removes the
tab-splitting inside the atomic group. The patterns are now package-private so
the tests can reach them.
- `MAPIMessage`: the regex is replaced by `getCharsetFromContentType`, a
package-private static helper that matches in linear time. It checks for an
ASCII case-insensitive `content-type:` prefix. The value ends at the end of the
header, or one character earlier if the last character is a quote, and it must
not contain `;` or a quote. The helper scans the first line for `charset=`,
skips one optional opening quote, and returns the value at the first position
that satisfies those rules. Case folding is ASCII-only, like `CASE_INSENSITIVE`
without `UNICODE_CASE`. For example, `ſ` (U+017F) does not match `s`.
## Equivalence check
Old and new were compared exhaustively (matches/find result plus start/end
of every group):
- `DOUBLE_PATTERN`: all strings up to length 7 over `0 1 a . e x p + d space
\n N U+0660`, about 68M strings, 34,676 accepted, no differences.
- `HYPERLINK_EXTERNAL` and `HYPERLINK_LOCAL`: all bodies up to length 8 over
`" a space \n \r U+0085 U+2028 U+2029` (EXTERNAL) and `" space a` plus the same
line terminators (LOCAL), each after 4 prefixes (none, the matching prefix, a
prefix with leading whitespace/CRLF, the other HYPERLINK prefix). That is 76.7M
strings per pattern, no differences.
- `PAGEREF`: all bodies up to length 7 over `space \t \ h a \n \r U+0085
U+2028` after 5 prefixes. That is 26.9M strings, 329,414 matched, no
differences.
- MAPI helper vs the old regex `group(1)`, two runs, no differences:
- all sequences of up to 6 tokens (`charset=`, `CharSet=`, `charsex=`,
`a`, `;`, `'`, `"`, line terminators, space) after 8 prefixes, including
near-miss prefixes and Unicode case-folding traps. That is 41.8M strings, 2.37M
matched.
- all strings up to length 7 over `c C h s U+017F e t = ; " ' \n x` after
4 prefixes. That is 272M strings, 17.6M matched.
## Timings (old vs new, ms)
| input | old | new |
|---|---|---|
| Context `"1"*5000+"x"` | 6,813 | 14 |
| Context `"1"*20000+"x"` | 145,849 | 3 |
| HYPERLINK external n=20k / 50k | 2,608 / 38,143 | 0 / 0 |
| HYPERLINK local n=20k / 50k | 5,341 / 34,271 | 0 / 0 |
| PAGEREF tabs n=20k / 50k | 9,833 / 55,278 | 6 / 5 |
| PAGEREF `\h` n=20k / 50k | 2,364 / 6,521 | 1 / 0 |
| MAPI k=2k / 5k / 10k `charset=a` | 808 / 3,660 / 15,650 | 8 / 9 / 13 |
The new code takes about 100 ms on 1M-character inputs. The machine was
loaded while these ran, so the absolute numbers are noisy, but the quadratic
growth is clear.
## Tests
New tests:
- `TestFormulaParser.testNumericValues`: number parsing, plus a 50k-digit
key that must be rejected within 10 s.
- `TestWordToHtmlConverter.testFieldPatterns` and
`testFieldPatternsBacktracking`.
- `Test7BitCodepage.testCharsetFromContentType`.
The slowness tests use `assertTimeoutPreemptively(Duration.ofSeconds(10),
...)`. I ran their exact inputs against the old patterns in a standalone
harness, and all six timed out at 10 s. I also checked their positive
assertions against the old patterns.
Targeted runs, all passing:
- `poi`: TestFormulaParser (2), TestPresetGeometries (1)
- `poi-scratchpad`: TestWordToHtmlConverter (24), TestWordToFoConverter (8),
TestWordToTextConverter (168), Test7BitCodepage (2), TestBasics (12, 1 skipped
as before), TestOutlookTextExtractor (8)
- `poi-ooxml`: TestXSLFSimpleShape (7)
🤖 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]
