https://github.com/python/cpython/commit/bcf98ddbc40ec9b3ee87da0124a5660b19b7e606 commit: bcf98ddbc40ec9b3ee87da0124a5660b19b7e606 branch: main author: Serhiy Storchaka <[email protected]> committer: serhiy-storchaka <[email protected]> date: 2026-07-04T20:40:22+03:00 summary:
gh-153030: Fix quadratic complexity in incremental parsing in HTMLParser (GH-153031) When an unterminated construct (e.g. a tag or comment) spanned many feed() calls, rescanning the growing buffer and concatenating new data onto it were both quadratic. New data is now accumulated in a list and only joined and parsed once enough has piled up. Co-Authored-By: Claude Opus 4.8 <[email protected]> files: A Misc/NEWS.d/next/Security/2026-07-04-17-00-00.gh-issue-153030.RovkP6.rst M Lib/html/parser.py M Lib/test/test_htmlparser.py diff --git a/Lib/html/parser.py b/Lib/html/parser.py index 38ddf9ef442d368..fbe0d3665e073cc 100644 --- a/Lib/html/parser.py +++ b/Lib/html/parser.py @@ -157,6 +157,9 @@ def reset(self): self.cdata_elem = None self._support_cdata = True self._escapable = True + self._pending = [] + self._pending_len = 0 + self._parse_threshold = 1 super().reset() def feed(self, data): @@ -165,11 +168,36 @@ def feed(self, data): Call this as often as you want, with as little or as much text as you want (may include '\n'). """ - self.rawdata = self.rawdata + data - self.goahead(0) + # Accumulate new data in a list and only join and parse it once + # enough has piled up. Rescanning an unparsed buffer (e.g. an + # unterminated tag) and concatenating onto it on every call would + # both be quadratic in the input size. + self._pending_len += len(data) + if self._pending_len < self._parse_threshold: + self._pending.append(data) + else: + if not self._pending: + self.rawdata += data + else: + self._pending.append(data) + self.rawdata += ''.join(self._pending) + self._pending.clear() + self._pending_len = 0 + n = len(self.rawdata) + self.goahead(0) + if len(self.rawdata) < n: + # Some data was parsed; resume on the next call. + self._parse_threshold = 1 + else: + # Nothing was parsed; wait until the buffer doubles. + self._parse_threshold = len(self.rawdata) def close(self): """Handle any buffered data.""" + if self._pending: + self.rawdata += ''.join(self._pending) + self._pending.clear() + self._pending_len = 0 self.goahead(1) __starttag_text = None diff --git a/Lib/test/test_htmlparser.py b/Lib/test/test_htmlparser.py index 6b7624f11505d92..3fdaed4ff46b9d0 100644 --- a/Lib/test/test_htmlparser.py +++ b/Lib/test/test_htmlparser.py @@ -1041,6 +1041,26 @@ def check(source): check("<![CDATA[" * 9 * n) check("<!doctype" * 35 * n) + @support.requires_resource('cpu') + def test_incremental_no_quadratic_complexity(self): + # An unterminated construct fed in many small chunks used to take + # quadratic time, both to rescan and to concatenate the buffer. + # Now it takes a fraction of a second. + def check(prefix, chunk, suffix): + parser = html.parser.HTMLParser() + parser.feed(prefix) + for _ in range(200_000): + parser.feed(chunk) + parser.feed(suffix) + parser.close() + chunk = "a" * 64 + check("<!--", chunk, "-->") # comment + check("<?", chunk, ">") # processing instruction + check("<!doctype ", chunk, ">") # doctype + check("<![CDATA[", chunk, "]]>") # CDATA section + check("<a href='", chunk, "'>") # start tag + check("<script>", chunk, "</script>") # RAWTEXT element + class AttributesTestCase(TestCaseBase): diff --git a/Misc/NEWS.d/next/Security/2026-07-04-17-00-00.gh-issue-153030.RovkP6.rst b/Misc/NEWS.d/next/Security/2026-07-04-17-00-00.gh-issue-153030.RovkP6.rst new file mode 100644 index 000000000000000..d1d60593f4ba7d2 --- /dev/null +++ b/Misc/NEWS.d/next/Security/2026-07-04-17-00-00.gh-issue-153030.RovkP6.rst @@ -0,0 +1,3 @@ +Fixed quadratic complexity in incremental parsing of long unterminated +constructs (such as tags or comments) in :class:`html.parser.HTMLParser`, +which could be exploited for a denial of service. _______________________________________________ Python-checkins mailing list -- [email protected] To unsubscribe send an email to [email protected] https://mail.python.org/mailman3//lists/python-checkins.python.org Member address: [email protected]
