Natural Language Toolkit (NLTK): Uncontrolled recursion (crash DoS) in Synset.tree()/acyclic_tree() via WordNet relation traversal
Published 19 Nov 2026 · Updated 20 Nov 2026
Is your project on an affected nltk?
Look after several Python apps? Indie watches up to 15 repos, private ones too, for $5 a month. See Indie
Affected package
- Affected
- <3.10.4
- Fixed in
- 3.10.4
pip install 'nltk>=3.10.4'Details
Summary
The recursive traversal engines behind WordNetCorpusReader's Synset.tree() and Synset.acyclic_tree() have no maximum call-depth safeguard and default to unlimited depth. They guard against literal cycles, but not against a long, genuinely acyclic relation chain — which exhausts the Python call stack the same way as the sibling DependencyGraph finding I reported separately. Real-world exploitability requires the host application to load a custom/foreign WordNet-format lexical resource rather than NLTK's bundled default corpus — flagging that narrower scope honestly up front since it affects severity, not validity.
Details
nltk/util.py's acyclic_depth_first() (~lines 471-541) and acyclic_branches_depth_first() (~lines 544-625) recurse once per graph edge, default to depth=-1 ("unlimited"), and guard against re-visiting the same node via an explicit traversed set (hence "acyclic") — but that set only prevents literal cycles, it never bounds how many *distinct* nodes a single call chain may pass through before returning.
Synset.tree(rel, depth=-1) (nltk/corpus/reader/wordnet.py, ~line 664) calls the recursive acyclic_branches_depth_first. There is also a third, easy-to-miss method: Synset.acyclic_tree(), a vestigial class-attribute alias for acyclic_depth_first — also genuinely recursive and vulnerable.
Important correction to an earlier draft of this finding: Synset.closure(rel, depth=-1) (~line 609) does not share this bug — it actually calls acyclic_breadth_first(), a completely different, iterative queue/deque-based function with no recursion at all. I verified this directly: feeding both acyclic_breadth_first and the real Synset.closure() a 20,000-node genuinely-acyclic chain produces zero crash, while acyclic_depth_first/acyclic_branches_depth_first/Synset.tree()/Synset.acyclic_tree() crash reliably at ~1000-1500 nodes on the identical data. Only .tree() and .acyclic_tree() are affected — not .closure().
This is the same CWE-674 pattern already hardened elsewhere in the codebase (MAX_TREE_DEPTH in tree/tree.py, MAX_DEPTH in featstruct.py, MAX_PARSE_DEPTH in logic.py, MAX_TABLEAU_DEPTH in tableau.py, MAX_DECODE_DEPTH in jsontags.py, added by a commit whose message explicitly enumerates the sinks it covers) — but that hardening pass never reached nltk/util.py or wordnet.py.
Honest scope-limiting fact: I exhaustively measured the maximum possible traversal depth across the entire official, bundled WordNet 3.0 corpus (what the overwhelming majority of real deployments use) for every relation NLTK exposes to tree(): hypernyms/hyponyms max depth = 18 (across all 74,374 noun synsets); also_sees (a relation whose graph isn't curated to stay as shallow as the taxonomy) max eccentricity = 41, largest connected component = 824 nodes; similar_tos max eccentricity = 1; entailments/causes/verb_groups/member_holonyms/member_meronyms/attributes all ≤ 11. Every one of these is roughly 25-60x below the ~1000-node crash threshold — there is no word or relation an attacker could pick against the standard bundled corpus that reaches anywhere near a crash. nltk.app.wordnet_app, NLTK's own bundled reference consumer, only ever calls .tree() with the safe hypernym relation.
Real-world exploitability therefore strictly requires the host application to load a custom/foreign WordNet-format lexical resource — a legitimate, documented, WordNetCorpusReader-supported usage, but a comparatively uncommon one — and then call .tree()/.acyclic_tree() (not .closure()) with the default unbounded depth.
PoC
Generated a syntactically valid, minimal, real Princeton-WordNet-DB-format lexical database (data.noun/index.noun/lexnames/etc., with correct byte-offset-indexed synset records) encoding a 1500-node strictly-linear (genuinely acyclic) hypernym chain. Loaded it via the real, unmodified WordNetCorpusReader(root, None), obtained a real Synset, and called the real, documented, public synset.tree(lambda s: s.hypernyms()) — crashed with an uncaught RecursionError: maximum recursion depth exceeded, as did synset.acyclic_tree(...). synset.closure(...) on the identical data returned cleanly (1499 nodes, no crash), confirming the closure()/tree() distinction above.
Impact
An application that loads a custom WordNet-format lexical resource (e.g. a domain-specific or community-contributed WordNet, which WordNetCorpusReader is explicitly designed to support) and calls .tree()/.acyclic_tree() with an attacker-influenced or simply not-officially-curated relation/resource can be crashed via an unhandled RecursionError from a single long-but-acyclic relation chain. Narrower reach than a bundled-default-corpus bug, but a real, working, unpatched gap in the same CWE-674 family the project actively hardens elsewhere.
Suggested fix: apply the same MAX_TREE_DEPTH-style depth guard to acyclic_depth_first()/acyclic_branches_depth_first() (or reuse the existing Tree constant/pattern directly).
Fix status (2026-09-28)
Status: MERGED on develop (unreleased; v3.10.3 of 2026-08-12 predates the fix).
Fix commit: 0e474a7d7 "Merge commit from fork" (2026-08-26, merged on develop from this advisory's temporary private fork): nltk/util.py gains MAX_RECURSION_DEPTH=500 for the acyclic traversal helpers behind Synset.tree() and acyclic_tree(), with nltk/test/unit/test_wordnet_recursion.py and the probe.
Probe: nltk/test/unit/security_probes/ghsa_8846_p9w9_5frf.py; verdict on develop 2fa3f48fe: FIXED (depth cap prevents recursion overflow).
Release: none yet; no release tag contains 0e474a7d7.
Is GHSA-8846-p9w9-5frf in any of your client repos?
Checking one package by hand is fine. Checking it across forty client projects is not. NPMscan reads the lockfiles in every GitHub repo you pick, finds each project with an affected nltk, and gives you the command that fixes it.
More advisories for nltk
- HighCVE-2026-128135NLTK: ZIP package extraction follows in-root hardlinks and overwrites files outside the NLTK data root · 19 Nov 2026
- MediumCVE-2026-128136NLTK: AllowlistUnpickler does not deny numpy submodule-local file-I/O sinks · 19 Nov 2026
- MediumCVE-2026-128137NLTK corpus-reader view methods bypass the scoped root sandbox via intermediate-directory symlinks · 19 Nov 2026
- CriticalCVE-2026-128138NLTK incomplete fix: additional JVM/JAR sandbox bypass through unvalidated launcher tokens in java() command arguments · 19 Nov 2026
- HighCVE-2026-128139NLTK: XMLCorpusView comment and CDATA parsing permits quadratic CPU denial of service · 19 Nov 2026
- MediumCVE-2026-128140NLTK: Downloader cyclic collection indices cause an infinite closure walk · 19 Nov 2026
References
Advisory data from OSV.dev (opens OSV.dev in a new tab), refreshed daily.