AI and data stack advisories

Severe, 6 weeks2431Projects328

2431 severe, 6 weeks · 328 projects

NLTKGHSA-rh8m-wqhc-qmrf

Natural Language Toolkit (NLTK): Uncontrolled recursion (crash DoS) in DependencyGraph.tree()/triples()

NLTK

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

High7.5
Fix: upgrade to 3.10.4 or later
GitHub advisory

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,...

Affected versions

PackageAffectedFixed in
nltk
PyPI
< 3.10.43.10.4
Details and references

### 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

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

More NLTK advisories

All NLTK