HIGH 7.5 PyPI

Natural Language Toolkit (NLTK): Uncontrolled recursion (crash DoS) in Synset.tree()/acyclic_tree() via WordNet relation traversal

GHSA-8846-p9w9-5frf · CVE-2026-129223

Published · Modified

AI SAST

Find this class of vulnerability in your own code

Corgea's AI-native static analysis detects vulnerabilities like this one across your repositories, ranks them by exploitability, and returns review-ready fixes.

Description

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.

Ready to move

Start Securing

Free, no credit card | First findings in minutes