AI and data stack advisories

Severe, 6 weeks2431Projects328

2431 severe, 6 weeks · 328 projects

NLTKGHSA-cj8f-5fp3-6m88

NLTK: Quadratic CPU exhaustion in NLTK XMLCorpusView.read_block via deeply nested XML corpus tags

NLTK

CVE-2026-129232 · Published Nov 19, 2026 · updated Nov 20, 2026

Medium5.3
Fix: upgrade to 3.10.4 or later
GitHub advisory

Summary

NLTK's XMLCorpusView.read_block rebuilds the full root-to-node context path with "/".join(context) on every start tag while it is still searching for a matching element. Because the context stack grows with XML nesting depth and the join is repeated once per start tag, a single corpus file containing deeply nested tags forces O(n^2) pure-Python work, where n is the number of nested elements. Any application that parses attacker-influenced XML corpus data through an XMLCorpusView subclass (for example the nps_chat, framenet, bnc, mte, nkjp, or semcor readers) can be driven to exhaust a CPU core for an extended period, producing a denial of service without any authentication or special privilege.

Root Cause

read_block maintains a context list that is appended on each start tag and popped on each end tag, so it grows monotonically to the maximum nesting depth while an element is being sought. For every start tag, while no target element has been located yet (elt_start is None), the code recomputes the entire path string from scratch and matches it against the reader's tagspec. The tagspec is anchored (tagspec + "\\Z"), so a nested path such as a/a/a/... never completes a full match against a concrete tagspec like Session/Posts/Post; elt_start therefore stays None for the entire file and the per-start-tag join runs for all n tags...

Affected versions

PackageAffectedFixed in
nltk
PyPI
< 3.10.43.10.4
Details and references

## Summary NLTK's `XMLCorpusView.read_block` rebuilds the full root-to-node context path with `"/".join(context)` on every start tag while it is still searching for a matching element. Because the context stack grows with XML nesting depth and the join is repeated once per start tag, a single corpus file containing deeply nested tags forces O(n^2) pure-Python work, where n is the number of nested elements. Any application that parses attacker-influenced XML corpus data through an `XMLCorpusView` subclass (for example the `nps_chat`, `framenet`, `bnc`, `mte`, `nkjp`, or `semcor` readers) can be driven to exhaust a CPU core for an extended period, producing a denial of service without any authentication or special privilege. ## Root Cause `read_block` maintains a `context` list that is appended on each start tag and popped on each end tag, so it grows monotonically to the maximum nesting depth while an element is being sought. For every start tag, while no target element has been located yet (`elt_start is None`), the code recomputes the entire path string from scratch and matches it against the reader's tagspec. The tagspec is anchored (`tagspec + "\\Z"`), so a nested path such as `a/a/a/...` never completes a full match against a concrete tagspec like `Session/Posts/Post`; `elt_start` therefore stays `None` for the entire file and the per-start-tag join runs for all n tags over depths 1..n. Summing those join costs yields O(n^2). There is no nesting-depth limit, context-length bound, or cumulative-work budget in `read_block`, and the per-call regex timeout used elsewhere in the file does not observe this cumulative pure-Python string cost. ```text nltk/corpus/reader/xmldocs.py : XMLCorpusView.read_block context.append(name) # start-tag: stack grows with depth if elt_start is None: if tagspec.match("/".join(context)): # full path rebuilt per start tag -> O(depth) ... # empty-element variant rebuilds "/".join(context) + "/" + name the same way ``` ## Impact An unauthenticated attacker who can supply or influence an XML corpus file processed by an `XMLCorpusView` subclass can cause quadratic CPU consumption. A crafted file of roughly 200 KB consumes several seconds of a single core; a few-megabyte file pins a core for minutes, and an arbitrarily large or unclosed nested file can hang the affected process indefinitely on that core. The result is a denial-of-service condition (CWE-407 / CWE-400). No confidentiality or integrity impact is demonstrated; the impact is availability of the processing thread or process. The prerequisite is that the application feed untrusted or attacker-influenced corpus XML into one of the affected readers, which is the same trust boundary already accepted for the seed issue in the same file. ## Proof of Concept `Requires only the nltk package and its standard XML corpus reading path; no network or special configuration.` Reproduction drives a real `SeekableUnicodeStreamReader` and the real `read_block` with an `nps_chat`-style tagspec, comparing nested input (growing context depth) against a flat negative control with an identical tag count. ```python import time, io from nltk.corpus.reader.xmldocs import XMLCorpusView def measure(build, label): print(label) prev = None for n in (4000, 8000, 16000, 32000): body = build(n).encode("utf-8") # write to a temp file and open through an XMLCorpusView subclass tagspec import tempfile, os fd, path = tempfile.mkstemp(suffix=".xml") os.write(fd, b"<Session>" + body + b"</Session>"); os.close(fd) view = XMLCorpusView(path, "Session/Posts/Post") t = time.time() try: list(view) except Exception: pass dt = time.time() - t ratio = "" if prev is None else f"({dt/prev:.1f}x)" print(f" n={n:>6} time={dt:7.3f}s {ratio}") prev = dt os.remove(path) measure(

CVSS 3.1
CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:L
Severity from
GitHub (reviewed advisory)
Weakness
CWE-400, CWE-407
Also known as
CVE-2026-129232

More NLTK advisories

All NLTK