|
| 1 | +From e7b8f1050a540fdbe8771db94ad998ce7a5540d0 Mon Sep 17 00:00:00 2001 |
| 2 | +From: Serhiy Storchaka <storchaka@gmail.com> |
| 3 | +Date: Sat, 4 Jul 2026 20:40:22 +0300 |
| 4 | +Subject: [PATCH] gh-153030: Fix quadratic complexity in incremental parsing in |
| 5 | + HTMLParser (GH-153031) |
| 6 | + |
| 7 | +When an unterminated construct (e.g. a tag or comment) spanned many |
| 8 | +feed() calls, rescanning the growing buffer and concatenating new data |
| 9 | +onto it were both quadratic. New data is now accumulated in a list and |
| 10 | +only joined and parsed once enough has piled up. |
| 11 | + |
| 12 | +Co-Authored-By: Claude Opus 4.8 <noreply@anthropic.com> |
| 13 | +(cherry picked from commit bcf98ddbc40ec9b3ee87da0124a5660b19b7e606) |
| 14 | +--- |
| 15 | + Lib/html/parser.py | 32 +++++++++- |
| 16 | + Lib/test/test_htmlparser.py | 20 ++++++ |
| 17 | + Misc/NEWS.d/next/Security/2026-07-04-17-00-00.gh-issue-153030.RovkP6.rst | 3 |
| 18 | + 3 files changed, 53 insertions(+), 2 deletions(-) |
| 19 | + create mode 100644 Misc/NEWS.d/next/Security/2026-07-04-17-00-00.gh-issue-153030.RovkP6.rst |
| 20 | + |
| 21 | +Index: Python-3.11.15/Lib/html/parser.py |
| 22 | +=================================================================== |
| 23 | +--- Python-3.11.15.orig/Lib/html/parser.py 2026-07-31 16:17:58.516657311 +0200 |
| 24 | ++++ Python-3.11.15/Lib/html/parser.py 2026-07-31 16:18:04.726530944 +0200 |
| 25 | +@@ -137,6 +137,9 @@ |
| 26 | + self.cdata_elem = None |
| 27 | + self._support_cdata = True |
| 28 | + self._escapable = True |
| 29 | ++ self._pending = [] |
| 30 | ++ self._pending_len = 0 |
| 31 | ++ self._parse_threshold = 1 |
| 32 | + _markupbase.ParserBase.reset(self) |
| 33 | + |
| 34 | + def feed(self, data): |
| 35 | +@@ -145,11 +148,36 @@ |
| 36 | + Call this as often as you want, with as little or as much text |
| 37 | + as you want (may include '\n'). |
| 38 | + """ |
| 39 | +- self.rawdata = self.rawdata + data |
| 40 | +- self.goahead(0) |
| 41 | ++ # Accumulate new data in a list and only join and parse it once |
| 42 | ++ # enough has piled up. Rescanning an unparsed buffer (e.g. an |
| 43 | ++ # unterminated tag) and concatenating onto it on every call would |
| 44 | ++ # both be quadratic in the input size. |
| 45 | ++ self._pending_len += len(data) |
| 46 | ++ if self._pending_len < self._parse_threshold: |
| 47 | ++ self._pending.append(data) |
| 48 | ++ else: |
| 49 | ++ if not self._pending: |
| 50 | ++ self.rawdata += data |
| 51 | ++ else: |
| 52 | ++ self._pending.append(data) |
| 53 | ++ self.rawdata += ''.join(self._pending) |
| 54 | ++ self._pending.clear() |
| 55 | ++ self._pending_len = 0 |
| 56 | ++ n = len(self.rawdata) |
| 57 | ++ self.goahead(0) |
| 58 | ++ if len(self.rawdata) < n: |
| 59 | ++ # Some data was parsed; resume on the next call. |
| 60 | ++ self._parse_threshold = 1 |
| 61 | ++ else: |
| 62 | ++ # Nothing was parsed; wait until the buffer doubles. |
| 63 | ++ self._parse_threshold = len(self.rawdata) |
| 64 | + |
| 65 | + def close(self): |
| 66 | + """Handle any buffered data.""" |
| 67 | ++ if self._pending: |
| 68 | ++ self.rawdata += ''.join(self._pending) |
| 69 | ++ self._pending.clear() |
| 70 | ++ self._pending_len = 0 |
| 71 | + self.goahead(1) |
| 72 | + |
| 73 | + __starttag_text = None |
| 74 | +Index: Python-3.11.15/Lib/test/test_htmlparser.py |
| 75 | +=================================================================== |
| 76 | +--- Python-3.11.15.orig/Lib/test/test_htmlparser.py 2026-07-31 16:18:00.172812370 +0200 |
| 77 | ++++ Python-3.11.15/Lib/test/test_htmlparser.py 2026-07-31 16:18:04.727730991 +0200 |
| 78 | +@@ -929,6 +929,26 @@ |
| 79 | + check("<![CDATA[" * 9 * n) |
| 80 | + check("<!doctype" * 35 * n) |
| 81 | + |
| 82 | ++ @support.requires_resource('cpu') |
| 83 | ++ def test_incremental_no_quadratic_complexity(self): |
| 84 | ++ # An unterminated construct fed in many small chunks used to take |
| 85 | ++ # quadratic time, both to rescan and to concatenate the buffer. |
| 86 | ++ # Now it takes a fraction of a second. |
| 87 | ++ def check(prefix, chunk, suffix): |
| 88 | ++ parser = html.parser.HTMLParser() |
| 89 | ++ parser.feed(prefix) |
| 90 | ++ for _ in range(200_000): |
| 91 | ++ parser.feed(chunk) |
| 92 | ++ parser.feed(suffix) |
| 93 | ++ parser.close() |
| 94 | ++ chunk = "a" * 64 |
| 95 | ++ check("<!--", chunk, "-->") # comment |
| 96 | ++ check("<?", chunk, ">") # processing instruction |
| 97 | ++ check("<!doctype ", chunk, ">") # doctype |
| 98 | ++ check("<![CDATA[", chunk, "]]>") # CDATA section |
| 99 | ++ check("<a href='", chunk, "'>") # start tag |
| 100 | ++ check("<script>", chunk, "</script>") # RAWTEXT element |
| 101 | ++ |
| 102 | + |
| 103 | + class AttributesTestCase(TestCaseBase): |
| 104 | + |
| 105 | +Index: Python-3.11.15/Misc/NEWS.d/next/Security/2026-07-04-17-00-00.gh-issue-153030.RovkP6.rst |
| 106 | +=================================================================== |
| 107 | +--- /dev/null 1970-01-01 00:00:00.000000000 +0000 |
| 108 | ++++ Python-3.11.15/Misc/NEWS.d/next/Security/2026-07-04-17-00-00.gh-issue-153030.RovkP6.rst 2026-07-31 16:18:04.727885463 +0200 |
| 109 | +@@ -0,0 +1,3 @@ |
| 110 | ++Fixed quadratic complexity in incremental parsing of long unterminated |
| 111 | ++constructs (such as tags or comments) in :class:`html.parser.HTMLParser`, |
| 112 | ++which could be exploited for a denial of service. |
0 commit comments