GHSA-rh8m-wqhc-qmrf

Suggest an improvement
Source
https://github.com/advisories/GHSA-rh8m-wqhc-qmrf
Import Source
https://github.com/github/advisory-database/blob/main/advisories/github-reviewed/2026/11/GHSA-rh8m-wqhc-qmrf/GHSA-rh8m-wqhc-qmrf.json
JSON Data
https://api.osv.dev/v1/vulns/GHSA-rh8m-wqhc-qmrf
Aliases
Published
2026-11-19T23:53:41Z
Modified
2026-11-20T00:00:04Z
Severity
  • 7.5 (High) CVSS_V3 - CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H CVSS Calculator
Summary
Natural Language Toolkit (NLTK): Uncontrolled recursion (crash DoS) in DependencyGraph.tree()/triples()
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:

  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.

Database specific
{
    "cwe_ids": [
        "CWE-674"
    ],
    "github_reviewed": true,
    "github_reviewed_at": "2026-11-19T23:53:41Z",
    "nvd_published_at": "2026-11-19T18:18:07Z",
    "severity": "HIGH"
}
References

Affected packages

PyPI / nltk

Package

Affected ranges

Type
ECOSYSTEM
Events
Introduced
0 Unknown introduced version / All previous versions are affected
Fixed
3.10.4

Affected versions

2.*
2.0.1rc2-git
2.0b4
2.0b5
2.0b6
2.0b7
2.0b8
2.0b9
2.0.1rc1
2.0.1rc3
2.0.1rc4
2.0.1
2.0.2
2.0.3
2.0.4
2.0.5
0.*
0.8
0.9
0.9.3
0.9.4
0.9.5
0.9.6
0.9.7
0.9.8
0.9.9
3.*
3.0.0b1
3.0.0b2
3.0.0
3.0.1
3.0.2
3.0.3
3.0.4
3.0.5
3.1
3.2
3.2.1
3.2.2
3.2.3
3.2.4
3.2.5
3.3
3.4
3.4.1
3.4.2
3.4.3
3.4.4
3.4.5
3.5b1
3.5
3.6
3.6.1
3.6.2
3.6.3
3.6.4
3.6.5
3.6.6
3.6.7
3.7
3.8
3.8.1
3.9b1
3.9
3.9.1
3.9.2
3.9.3
3.9.4
3.10.0
3.10.1
3.10.2
3.10.3

Database specific

last_known_affected_version_range
"<= 3.10.3"
source
"https://github.com/github/advisory-database/blob/main/advisories/github-reviewed/2026/11/GHSA-rh8m-wqhc-qmrf/GHSA-rh8m-wqhc-qmrf.json"