CVE-2026-129222: Natural Language Toolkit (NLTK): Uncontrolled recursion (crash DoS) in DependencyGraph.tree()/triples()
High CVSS 7.5
- OSV id
- GHSA-rh8m-wqhc-qmrf
- Also known as
- CVE-2026-129222
- Published
- Last modified
Affected packages
| Package | Affected versions | Fixed in |
|---|---|---|
| nltk PyPI |
< 3.10.4 | 3.10.4 |
How to fix it
Upgrade nltk to 3.10.4 or later.
# in requirements.txt: change the line to nltk==3.10.4
pip install -r requirements.txt
- If it is an indirect dependency, upgrade the package that depends on it, or add a minimum version constraint for it (e.g. in constraints.txt, or as a dependency in pyproject.toml).
- Check the changelog for breaking changes (especially across major versions), update the lockfile with the package manager, and run your tests.
Not sure whether your project uses an affected version? Check your lockfile below for free.
Details
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:
- Constructing a
DependencyGraphfrom a 3000-token linear chain and calling.tree()→RecursionError: maximum recursion depth exceeded. Confirmed. - Same graph,
.triples()fully consumed →RecursionError. Confirmed. - Full realistic path: wrote the 3000-token chain to a temp file, read it back through an actual
DependencyCorpusReader(the exact class backingdependency_treebank/conll2007) viaparsed_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% rel
References
- GHSA-rh8m-wqhc-qmrf on OSV.dev
- Web: https://github.com/nltk/nltk/security/advisories/GHSA-rh8m-wqhc-qmrf
- Advisory: https://nvd.nist.gov/vuln/detail/CVE-2026-129222
- Web: https://github.com/nltk/nltk/pull/3885
- Web: https://github.com/nltk/nltk/commit/a74682757cee8c11128ad277d2f2bd0b8e1884ff
- Package: https://github.com/nltk/nltk
- Web: https://github.com/nltk/nltk/releases/tag/v3.10.4
Am I affected?
Upload or paste your lockfile. We check every package version in it against OSV.dev, this advisory included, and email you the vulnerable ones with the version that fixes them. Free, and no account needed.
About this data
Source: GitHub Advisory Database via OSV.dev (CC-BY 4.0). Severity comes from the advisory's own rating when it has one, else from its CVSS score.