NLTK: Quadratic CPU exhaustion in NLTK XMLCorpusView.read_block via deeply nested XML corpus tags
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
| Package | Affected | Fixed in |
|---|---|---|
| nltk PyPI | < 3.10.4 | 3.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(