CVE-2026-129225
## 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
Properties
- Summary
- NLTK: Uncontrolled recursion in DependencyGraph traversal causes denial of service via deep dependency chains
- Severity
- medium
- Nvd fetched at
- 2026-11-22T12:30:49.958423+00:00
- Epss score
- 0.00479
- Cvss score
- 5.3
- Cvss severity
- MEDIUM
- Retrieved at
- 2026-11-22T12:32:26+00:00
- Ghsa published
- 2026-11-19T23:52:20Z
- Source url
- https://github.com/advisories/GHSA-xfcv-m889-fmqg
- Ghsa updated
- 2026-11-19T23:52:22Z
- Ghsa id
- GHSA-xfcv-m889-fmqg
- Last source
- FIRST EPSS
- Score
- 5.3
- Cvss version
- 3.1
- Cve id
- CVE-2026-129225
- Cvss vector
- CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:L
- First seen by Signal
- 2026-11-19T19:29:21+00:00
- Name
- CVE-2026-129225
- Is ghsa only
- false
- Vector
- CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:L
Related Entities (3)
AFFECTS (1)
HAS_WEAKNESS (1)
VULNERABLE_TO (1)
Related research
Explore deeper with Ninja Signal's threat intelligence graph