# GHSA-RH8M-WQHC-QMRF: Natural Language Toolkit (NLTK): Uncontrolled recursion (crash DoS) in DependencyGraph.tree()/triples()

- Database: GitHub
- Severity: high (stated by ghsa, no CVSS score)
- Published: 2026-11-19
- Modified: 2026-11-20

## Tracked as

- [CVE-2026-129222](https://cve.now/CVE-2026-129222.md): NLTK denial of service via recursion in DependencyGraph.tree()

## Affected versions

- nltk (PyPI): fixed in 3.10.4

## Description

### Summary
DependencyGraph.tree()/triples() walk the parsed dependency structure using plain, unbounded Python recursion — one stack frame per edge in the graph — and never use the class's own cycle detector. A crafted dependency-parse file with a few thousand chained tokens (an entirely ordinary-looking long sentence) crashes the process with an unhandled RecursionError the moment .tree() or .triples() is called — which is NLTK's own documented usage pattern immediately after loading such a file.

### Details
`DependencyGraph._tree()` (~lines 393-406), `.tree()` (~408-417), and `.triples()` (~419-432) in `nltk/parse/dependencygraph.py` rebuild/walk the graph with `Tree(word, [self._tree(dep) for dep in deps])` and `yield from self.triples(node=dep)` — ordinary recursive calls, one per edge, with no depth check. `contains_cycle()` is defined on the class (~line 447) but is never invoked by any of these three methods.

This is exactly the CWE-674 pattern the project has already identified and fixed elsewhere: `nltk/tree/tree.py` adds `MAX_TREE_DEPTH = 500` with a comment stating that an arbitrarily deep tree would make every traversal raise RecursionError, and `nltk/test/unit/test_recursion_dos.py` locks in the identical fix for `FeatStructReader`, `LogicParser`, and `ResolutionProver`. But `DependencyGraph` builds its `Tree` objects **programmatically** (`Tree(word, [...])`), which bypasses `MAX_TREE_DEPTH` entirely — that guard only fires inside `Tree.fromstring()`'s bracket-string parser, never in `Tree.__init__`. `DependencyGraph`'s own recursive walk has no depth limit of its own.

Any Malt-TAB/CoNLL(3/4/7/10)-format text — read via `DependencyCorpusReader` (`nltk/corpus/reader/dependency.py`, lines 62-69, backing the public, documented `nltk.corpus.dependency_treebank` and `nltk.corpus.conll2007` corpora) or via the public classmethod `DependencyGraph.load(filename)` (~line 213) / `DependencyGraph(text)` directly — that chains more tokens than Python's default recursion limit (1000) via consecutive head references crashes with an unhandled `RecursionError` the moment `.tree()`/`.triples()` is called. Calling `.tree()` immediately after `parsed_sents()` is not a contrived edge case — it is NLTK's own documented usage pattern (`nltk/test/corpus.doctest`: `print(conll2007.parsed_sents('esp.train')[0].tree())`; `nltk/test/dependency.doctest`: `dg.tree().pprint()`).

**Related observation:** `contains_cycle()` itself has a separate bug that means it wouldn't help even if it were called on this path — it iterates `node["deps"]` as if it were a flat list of neighbor addresses, but `_parse()`/`add_arc()` actually store `deps` as `{relation_label: [addresses]}`; iterating that dict yields relation-label strings, which then fail the `dep not in self.nodes` check and get silently skipped. So `contains_cycle()` returns `False` (a false negative) on real parsed/`add_arc()`-built graphs even when a genuine cycle exists — it only works on the flat-list shape used in its own docstring example. This reinforces that there is no working recursion/cycle safety net on this code path today.

### PoC
A tiny (few KB) 3-column Malt-TAB file: one root line `w1 ROOT 0` followed by ~2000-3000 lines `wi X i-1`, each chaining a token to the previous one (an entirely ordinary-looking long sentence/coordination structure). Verified directly against current source:

1. Constructing a `DependencyGraph` from a 3000-token linear chain and calling `.tree()` → `RecursionError: maximum recursion depth exceeded`. Confirmed.
2. Same graph, `.triples()` fully consumed → `RecursionError`. Confirmed.
3. Full realistic path: wrote the 3000-token chain to a temp file, read it back through an actual `DependencyCorpusReader` (the exact class backing `dependency_treebank`/`conll2007`) via `parsed_sents()`, then called `.tree()` on the result → `RecursionError`, end-to-end through the real public API.

(One honest correction to an earlier draft of this finding: a "two lines whose head columns reference each other" file-based cycle does *not* actually reach this crash the way it might seem — in the single-head-per-token Malt-TAB/CoNLL format, a genuine mutual-reference pair can't simultaneously be reachable from the graph's root and form a back-edge, so it either leaves `self.root = None`, or the pair becomes a disconnected island that's silently walked past without crashing. The long-chain vector above is the one that's fully, independently confirmed; a cycle built via direct `add_arc()` graph manipulation does also crash, but that's a narrower trigger than a parsed file.)

### Impact
An unauthenticated party who can get a crafted CoNLL/Malt-TAB dependency file processed by a downstream application — a treebank upload, a shared-task submission portal, a user-editable corpus directory, or any code calling `DependencyGraph.load()`/`DependencyGraph()` on user-supplied text — crashes that request/worker/script with no further interaction needed. 100% reliable, trivial to construct.

Suggested fix: apply the same `MAX_TREE_DEPTH`-style depth guard used elsewhere in the codebase to `_tree()`/`tree()`/`triples()`, and fix `contains_cycle()`'s dict-vs-flat-list bug so it can actually be invoked as a real safety net on this path.


## 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 instead of recursing until RecursionError).

Probe: none of its own; nltk/test/unit/security_probes/ghsa_xfcv_m889_fmqg.py covers tree() and reports FIXED on develop 2fa3f48fe. The advisory PoC re-run on develop 2fa3f48fe (a 3000-token Malt-TAB chain): tree() and list(triples()) both raise ValueError (exceeded MAX_DEPTH=200), no RecursionError.

Release: none yet; no release tag contains e521ecafc.

## References

- https://github.com/nltk/nltk/security/advisories/GHSA-rh8m-wqhc-qmrf
- https://nvd.nist.gov/vuln/detail/CVE-2026-129222
- https://github.com/nltk/nltk/pull/3885
- https://github.com/nltk/nltk/commit/a74682757cee8c11128ad277d2f2bd0b8e1884ff
- https://github.com/nltk/nltk
- https://github.com/nltk/nltk/releases/tag/v3.10.4

Page: https://cve.now/GHSA-RH8M-WQHC-QMRF
