Reading a message: the HTML stripper and the References parser take quadratic time on unbounded input

tiagoagueda commented

2026-10-01 10:47:58 +00:00

Owner

Found on 2026-09-29 in a read-only review of postulo-imap at cc09c6381, timing _strip_html and parse on inputs of growing size.

The regular expressions that turn an HTML part into text, and the one that reads the threading headers, rescan to the end of their input from every candidate start when the terminator they look for is missing. Their cost grows with the square of the input, nothing bounds the input, and the work runs inline in the scheduler pass or in a web worker. This is uncontrolled resource consumption through an inefficient regular expression on untrusted input.

Where:
- src/postulo_imap/mailbox.py:128-131, _strip_html: (?is)<(script|style).*?</\1>, <[^>]+> and \s+\n, each run over the whole decoded part.
- src/postulo_imap/mailbox.py:145-147, parse: re.findall(r"<[^>]+>", ...) over In-Reply-To and References, for every message whatever its body.
- src/postulo_imap/mailbox.py:102-111, plain_text: the cut to EXCERPT_CHARS is at line 111, after the stripping at lines 104 and 109.
- src/postulo_imap/mailbox.py:199, Mailbox.fetch: BODY.PEEK[] fetches each message whole, so no size limit applies earlier either.

What happens: measured on the snapshot (Python 3.14), on input made only of the shape named:

Shape	10 KB	20 KB	40 KB
`script` openings with no closing tag	0.06 s	0.25 s	1.09 s
`<` with no `>`	0.06 s	0.25 s	1.16 s
whitespace with no line break	0.17 s	0.75 s	3.08 s
`References` header of `<` with no `>`	0.06 s	0.30 s	1.16 s

Doubling the input quadruples the time, so a part of 1 MB takes between ten minutes and half an hour, and a message may be far larger than that. A text/plain body is not affected (1 MB of spaces: 0.03 s); only the HTML path and the two headers are.

Who can trigger it: any account, by pointing a connection at a mailbox it controls; there the size is whatever that server hands over. Also whoever can get a message into the folder a person's connection reads, within the size the receiving mail server accepts.
Why it matters: syncs run inline, one after another, in the scheduler pass (plugins/syncing.py:110-137, called from send_due_reminders under only_one_pass), and the sync budget only decides whether to start another connection: one already started is never cut off. While it runs, no later pass starts, so every person's reminders, quiet-application and closing notices, document copies and webhooks wait. The message is flagged only at the end of the pass, on a connection that has by then sat idle for as long as the regular expression ran; if the server has dropped it, nothing is flagged and the next pass repeats the cost. With Leave the mailbox untouched it repeats on every pass by design. Sync now (plugins/views.py:445-459) spends the same time in a web worker.
Fix:
- Cut the decoded part to a fixed size (200 KB is generous for an excerpt of 2,000 characters) before _strip_html, and the two threading headers to a few kilobytes before findall.
- Replace the regex stripper with a linear one: an html.parser.HTMLParser subclass that collects text and skips script, style and head. That also decodes entities, which the classification needs for its own reasons.
- Consider fetching BODY.PEEK[]<0.N> with a ceiling, so an oversized message is never held in memory whole.

Done when

tests/test_imap.py has a test that strips 1 MB of each of the three shapes above, and parses a message whose References header is 100 KB of <, each within one second. All four take minutes today.

Found on 2026-09-29 in a read-only review of postulo-imap at cc09c6381, timing `_strip_html` and `parse` on inputs of growing size. The regular expressions that turn an HTML part into text, and the one that reads the threading headers, rescan to the end of their input from every candidate start when the terminator they look for is missing. Their cost grows with the square of the input, nothing bounds the input, and the work runs inline in the scheduler pass or in a web worker. This is uncontrolled resource consumption through an inefficient regular expression on untrusted input. - **Where:** - `src/postulo_imap/mailbox.py:128-131`, `_strip_html`: `(?is)<(script|style).*?</\1>`, `<[^>]+>` and `\s+\n`, each run over the whole decoded part. - `src/postulo_imap/mailbox.py:145-147`, `parse`: `re.findall(r"<[^>]+>", ...)` over `In-Reply-To` and `References`, for every message whatever its body. - `src/postulo_imap/mailbox.py:102-111`, `plain_text`: the cut to `EXCERPT_CHARS` is at line 111, after the stripping at lines 104 and 109. - `src/postulo_imap/mailbox.py:199`, `Mailbox.fetch`: `BODY.PEEK[]` fetches each message whole, so no size limit applies earlier either. - **What happens:** measured on the snapshot (Python 3.14), on input made only of the shape named: | Shape | 10 KB | 20 KB | 40 KB | | --- | --- | --- | --- | | `script` openings with no closing tag | 0.06 s | 0.25 s | 1.09 s | | `<` with no `>` | 0.06 s | 0.25 s | 1.16 s | | whitespace with no line break | 0.17 s | 0.75 s | 3.08 s | | `References` header of `<` with no `>` | 0.06 s | 0.30 s | 1.16 s | Doubling the input quadruples the time, so a part of 1 MB takes between ten minutes and half an hour, and a message may be far larger than that. A `text/plain` body is not affected (1 MB of spaces: 0.03 s); only the HTML path and the two headers are. - **Who can trigger it:** any account, by pointing a connection at a mailbox it controls; there the size is whatever that server hands over. Also whoever can get a message into the folder a person's connection reads, within the size the receiving mail server accepts. - **Why it matters:** syncs run inline, one after another, in the scheduler pass (`plugins/syncing.py:110-137`, called from `send_due_reminders` under `only_one_pass`), and the sync budget only decides whether to start another connection: one already started is never cut off. While it runs, no later pass starts, so every person's reminders, quiet-application and closing notices, document copies and webhooks wait. The message is flagged only at the end of the pass, on a connection that has by then sat idle for as long as the regular expression ran; if the server has dropped it, nothing is flagged and the next pass repeats the cost. With *Leave the mailbox untouched* it repeats on every pass by design. *Sync now* (`plugins/views.py:445-459`) spends the same time in a web worker. - **Fix:** - Cut the decoded part to a fixed size (200 KB is generous for an excerpt of 2,000 characters) before `_strip_html`, and the two threading headers to a few kilobytes before `findall`. - Replace the regex stripper with a linear one: an `html.parser.HTMLParser` subclass that collects text and skips `script`, `style` and `head`. That also decodes entities, which the classification needs for its own reasons. - Consider fetching `BODY.PEEK[]<0.N>` with a ceiling, so an oversized message is never held in memory whole. ## Done when - `tests/test_imap.py` has a test that strips 1 MB of each of the three shapes above, and parses a message whose `References` header is 100 KB of `<`, each within one second. All four take minutes today.

tiagoagueda added this to the 0.5.0 milestone

2026-10-01 10:47:58 +00:00

tiagoagueda added the

security

bug

labels

2026-10-01 10:47:58 +00:00

tiagoagueda commented

2026-10-17 10:40:31 +00:00

Author

Owner

From the 2026-10-16 security review: the same two headers have a second problem besides the regex's time, the number of identifiers kept.

parse keeps every <...> match of In-Reply-To and References (mailbox.py:145-147,156), and match binds all of them into one IN clause (matching.py:90-98: filter(external_id__in=mail.references, ...)). Django splits an IN list only on Oracle (max_in_list_size() is None for SQLite and PostgreSQL), so a header with more identifiers than the database accepts as bound parameters (SQLite's default 32 766, roughly a 100 KB header; PostgreSQL's 65 535, roughly 200 KB) raises OperationalError inside the loop. The pass ends before box.mark(uids), and the next pass fetches the same message and fails again. Such a header is far outside normal mail and often above the receiving MTA's limit (Postfix defaults to 102 400 bytes), so this is Low, but nothing in the plugin bounds it.

Cutting the headers to a few kilobytes before findall, as proposed here, bounds the count as a side effect. To make it explicit, please also:

keep only what threading needs: the In-Reply-To identifier plus the last few of References (RFC 5322 §3.6.4 puts the parent last), e.g. references[-8:], each cut to the 250 characters Suggestion.external_id holds;
add a "Done when" with a References header of several thousand well-formed identifiers: the pass files the other messages, flags them, and the query binds at most nine values. The current "Done when" (100 KB of < with no >) yields zero identifiers and would not exercise the IN.

From the 2026-10-16 security review: the same two headers have a second problem besides the regex's time, the *number* of identifiers kept. `parse` keeps every `<...>` match of `In-Reply-To` and `References` (`mailbox.py:145-147,156`), and `match` binds all of them into one `IN` clause (`matching.py:90-98`: `filter(external_id__in=mail.references, ...)`). Django splits an `IN` list only on Oracle (`max_in_list_size()` is `None` for SQLite and PostgreSQL), so a header with more identifiers than the database accepts as bound parameters (SQLite's default 32 766, roughly a 100 KB header; PostgreSQL's 65 535, roughly 200 KB) raises `OperationalError` inside the loop. The pass ends before `box.mark(uids)`, and the next pass fetches the same message and fails again. Such a header is far outside normal mail and often above the receiving MTA's limit (Postfix defaults to 102 400 bytes), so this is Low, but nothing in the plugin bounds it. Cutting the headers to a few kilobytes before `findall`, as proposed here, bounds the count as a side effect. To make it explicit, please also: - keep only what threading needs: the `In-Reply-To` identifier plus the last few of `References` (RFC 5322 §3.6.4 puts the parent last), e.g. `references[-8:]`, each cut to the 250 characters `Suggestion.external_id` holds; - add a "Done when" with a `References` header of several thousand well-formed identifiers: the pass files the other messages, flags them, and the query binds at most nine values. The current "Done when" (100 KB of `<` with no `>`) yields zero identifiers and would not exercise the `IN`.

tiagoagueda referenced this issue

2026-10-17 10:40:32 +00:00

Sync: one message that cannot be parsed fails the whole pass, and every pass after it #8

tiagoagueda referenced this issue from Postulo/postulo

2026-10-17 10:41:23 +00:00

SEC2 index: security review of 2026-10-16 (86 issues across the core, plugins and extensions) #992

tiagoagueda referenced this issue from a commit

2026-10-19 07:00:13 +00:00

Fix the review findings: reading, classifying, matching, the form and what a refusal does

tiagoagueda referenced this issue

2026-10-19 07:00:17 +00:00

Fix the open bug and security issues (#8-#22, #24) #25