All reports
High

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

Affected versions

PyPInltk
Affected versions
<= 3.10.3
Fixed version
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.

Links

Credits

  • sonicnew