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.
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.
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
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.
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.
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(lambda n: "<a>"*n + "</a>"*n, "NESTED (context depth = n):")
measure(lambda n: "<a></a>"*n, "FLAT (context depth = 1, negative control):")
NESTED (context depth = n):
n= 4000 time= 0.162s
n= 8000 time= 0.484s (2.99x)
n= 16000 time= 1.595s (3.29x)
n= 32000 time= 5.667s (3.6x) -> ratios trend toward 4x per 2x input = O(n^2)
FLAT (context depth = 1, negative control):
n= 8000 time= 0.145s
n= 16000 time= 0.293s (2.03x)
n= 32000 time= 0.580s (2.0x) -> 2x per 2x input = linear
XMLCorpusView subclass (nps_chat, framenet, bnc, mte, nkjp, semcor, and similar) to read an XML corpus file whose contents an attacker can supply or influence."<a>" repeated n times followed by "</a>" repeated n times.read_block consumes the whole file in one call, appending to context on every start tag; the target element is never found, so the loop runs to end of file and context grows to depth n.read_block; the anchored tagspec match fails in O(1) at offset 0, so it is not the hot term, and the per-call regex timeout does not see cumulative string-build cost."/".join(context) rebuilds an O(depth) string, giving a cumulative O(n^2) pure-Python CPU cost.The seed fix for the previously published quadratic-CPU issue in this same file (CVE-2026-81723, GHSA-vp2x-qp44-57v7) is confined to _read_xml_fragment, where it added incremental in-tag / last-open-bracket tracking. The commit that shipped that fix touched the read_block match line only to change the match call form (from a module-level regex match to a precompiled tagspec match) and preserved the "/".join(context) argument byte-for-byte; it did not add any depth or length bound. This sink is therefore not covered by the seed remediation. It is also distinct from the sibling published issue CVE-2026-81725 (GHSA-8mpw-7fpc-4gqj), whose sink is a block.count(...) line tracker in Pl196xCorpusReader.read_block, a different class, mechanism, input, and fix. The strongest disproof attempts, that the anchored tagspec match is the quadratic term, that the file is not fully consumed in one call, that an end-tag sanity check aborts early, that a depth cap or the per-call regex timeout catches it, that the seed fix already covers it, and that deep nesting is entity expansion blocked by defused XML handling, were each checked and refuted: the flat negative control with identical tag count stays linear, isolating the quadratic term to the depth-dependent join; well-formed balanced input runs to end of file before any pop; no depth cap exists; the timeout is per call and does not observe cumulative pure-Python cost; and benign literal nesting is not custom-entity expansion.
Ecosystem: PyPI (pip)Package: nltkConfirmed affected range: <= 3.10.3Latest release checked: 3.10.3 (PyPI, nltk-3.10.3-py3-none-any.whl)Fix status: not fixed (no fix present in any released version or in the current development branch)The vulnerable join sink is present in the latest published artifact (3.10.3) and was corroborated in 3.9.1. No released version and no development-branch commit contains a fix, so the upper bound <= 3.10.3 is proven. The introduction boundary was not pinned to an exact first-affected release: the algorithm is long-standing legacy code present in all inspected supported releases, and pinning an exact introduced version would require bisecting historical wheels. The lower boundary is therefore left unestablished rather than asserted.
Bound the work performed while searching for a target element in read_block. Options that address the root cause: track the running context path incrementally (append and truncate a single cached path string alongside the context stack, rather than rejoining the whole list on every tag), or enforce an explicit maximum nesting depth / maximum accumulated tag count for a single block and raise a clear error when it is exceeded. The remediation must cover both the start-tag match at the primary join site and the empty-element variant that rebuilds "/".join(context) + "/" + name, and it should apply regardless of whether the input is well-formed and balanced or an unclosed nested run. As an interim mitigation, deployments can impose an upstream size limit on corpus XML fed to these readers and avoid parsing untrusted corpus files, though this does not remove the quadratic behavior for inputs under the limit.
Reported by zx (GitHub: @manus-pi).
Status: IN PROGRESS (fix on an open pull request, not yet on develop).
PR: #3895 "[WIP] Bound algorithmic-DoS and uncontrolled-recursion vectors (CWE-400/407/674/1333)", open, head b22ebe144.
Fix commit: 002bcf714 "Bound three quadratic algorithmic-DoS vectors on untrusted input" (XMLCorpusView.read_block no longer rebuilds the context path per piece).
No probe. The advisory PoC re-run (nested tags, n=8000 vs n=32000 through read_block): on the PR head 0.7x over a 4x input (linear); on develop 2fa3f48fe 11.3x (3.08 s vs 34.9 s), so develop is still VULNERABLE. The open PR #3753 measured on its head 238f81500 also gives 10.9x: its xmldocs change targets the unclosed CDATA/comment rescan of GHSA-j8g8, not this vector.
Release: none.
{
"cwe_ids": [
"CWE-400",
"CWE-407"
],
"github_reviewed": true,
"github_reviewed_at": "2026-11-19T23:48:18Z",
"nvd_published_at": "2026-11-19T17:17:56Z",
"severity": "MODERATE"
}