AI and data stack advisories

Severe, 6 weeks2431Projects328

2431 severe, 6 weeks · 328 projects

NLTKGHSA-xfcv-m889-fmqg

NLTK: Uncontrolled recursion in DependencyGraph traversal causes denial of service via deep dependency chains

NLTK

CVE-2026-129225 · Published Nov 19, 2026 · updated Nov 20, 2026

Medium5.3
Fix: upgrade to 3.10.4 or later
GitHub advisory

Root Cause

The dependency-graph traversal helpers recurse over dependency links without any depth

bound or visited set. DependencyGraph._tree (nltk/parse/dependencygraph.py:404)

recurses once per dependency link, triples (nltk/parse/dependencygraph.py:432) is a

recursive generator, and get_cycle_path (nltk/parse/dependencygraph.py:520) recurses

over dependencies. The neighbouring contains_cycle method was deliberately rewritten as

an iterative depth-first search, but these sibling helpers on the public traversal path

were left recursive with no depth counter.

Impact

An application that parses an untrusted CoNLL/Malt-TAB dependency structure and then walks

it via tree() or triples() aborts with an unhandled RecursionError, terminating the

affected operation or request worker (denial of service, CWE-674). The recursion is pure

Python, so the result is a catchable RecursionError, not memory corruption or code

execution. Confidentiality and integrity are unaffected. get_cycle_path additionally

lacks a visited set and will not terminate on a genuine cycle.

Attack Chain

1. The application constructs DependencyGraph(conll_str) from attacker-supplied text

where token *k*'s head is token *k+1*, forming a linear dependency chain of length *N*.

Graph construction (_parse) is iterative and completes without error.

2. The application calls the...

Affected versions

PackageAffectedFixed in
nltk
PyPI
< 3.10.43.10.4
Details and references

## Root Cause The dependency-graph traversal helpers recurse over dependency links without any depth bound or visited set. `DependencyGraph._tree` (`nltk/parse/dependencygraph.py:404`) recurses once per dependency link, `triples` (`nltk/parse/dependencygraph.py:432`) is a recursive generator, and `get_cycle_path` (`nltk/parse/dependencygraph.py:520`) recurses over dependencies. The neighbouring `contains_cycle` method was deliberately rewritten as an iterative depth-first search, but these sibling helpers on the public traversal path were left recursive with no depth counter. ## Impact An application that parses an untrusted CoNLL/Malt-TAB dependency structure and then walks it via `tree()` or `triples()` aborts with an unhandled `RecursionError`, terminating the affected operation or request worker (denial of service, CWE-674). The recursion is pure Python, so the result is a catchable `RecursionError`, not memory corruption or code execution. Confidentiality and integrity are unaffected. `get_cycle_path` additionally lacks a visited set and will not terminate on a genuine cycle. ## Attack Chain 1. The application constructs `DependencyGraph(conll_str)` from attacker-supplied text where token *k*'s head is token *k+1*, forming a linear dependency chain of length *N*. Graph construction (`_parse`) is iterative and completes without error. 2. The application calls the public `DependencyGraph.tree()` (`nltk/parse/dependencygraph.py:408`), which invokes `_tree(root)`. 3. `_tree` recurses once per chain link with no depth guard and no visited set, consuming one stack frame per link (the list comprehension costs roughly two frames per level). 4. Once the chain length exceeds the interpreter recursion limit, an unhandled `RecursionError` propagates out of the public API. `triples()` fails the same way. ## Bypass Evidence Against the shipped source at the default recursion limit, a chain of length 5 walks cleanly through `tree()`, while a chain of length 5000 raises an unhandled `RecursionError`; `triples()` fails identically. The minimal trigger is roughly *N*=500 tokens at the default recursion limit , a modest, realistic parse. Because the graph builds iteratively in both cases, the fault is isolated to the recursive traversal rather than to parsing. A repository-wide search confirms no depth guard exists in this file; the iterative rewrite was applied only to `contains_cycle`. ## Suggested Fix Convert `_tree`, `triples`, and `get_cycle_path` to iterative traversals, or add a recursion-depth bound (and, for `get_cycle_path`, a visited set) analogous to the iterative rewrite already applied to `contains_cycle`. Reported by pi (GitHub: @manus-pi). ## Fix status (2026-09-28) Status: MERGED on develop (unreleased; v3.10.3 of 2026-08-12 predates the fix). PR: #3885 "Bound recursion depth in parsers and traversal helpers" (ekaf), merged 2026-09-11, merge commit e521ecafc on develop. Fix commit: a74682757 (nltk/parse/dependencygraph.py: _tree, tree and triples stop at MAX_DEPTH=200 with ValueError). Probe: nltk/test/unit/security_probes/ghsa_xfcv_m889_fmqg.py (added in 2a6704952 on that PR); verdict on develop 2fa3f48fe: FIXED (bounded in tree() (ValueError)). Release: none yet; no release tag contains e521ecafc.

CVSS 3.1
CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:L
Severity from
GitHub (reviewed advisory)
Weakness
CWE-674
Also known as
CVE-2026-129225

More NLTK advisories

All NLTK