llamaCVEVulnerability Intelligence
/
Advisory · GitHub · PyPI · nltk

GHSA-RH8M-WQHC-QMRF

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

Parche disponible
Descargar PNG JSON
CVSS
—
high
Fuente: —
ExplotaciónSin evidenciaNo figura en CISA KEV
Exploits públicos0Ninguno conocido
Parche1 versión3.10.4
Exposición7 hDesde la divulgación, 19 nov 2026, 6:53 p. m.
Detección1 minDesde la divulgación hasta su ingreso al índice
Timeline

Ciclo de vida de la vulnerabilidad

Hoy
Divulgación
Publicada
Modificada
Explotación
Remediación
Monitoreo
Detectada
Fuente: GitHub Security Advisories +2
10:00 a. m.
06:53 p. m.
07:00 p. m.
02:18 a. m.
10:00 a. m.
02:05 p. m.
06:09 p. m.
10:14 p. m.
02:18 a. m.
FechaFaseEventoDetalle
Monitoreo Detectada Ingresó al índice
Divulgación Publicada GHSA-RH8M-WQHC-QMRF divulgada
Divulgación Modificada Última actualización del registro
Monitoreo Fuente: GitHub Security Advisories Registro visto por primera vez en GitHub Security Advisories
Monitoreo Fuente: OSV Registro visto por primera vez en OSV
Monitoreo Verificada Última verificación contra las fuentes
Resumen
Descripción del advisory
Texto original · GitHub · en inglés

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

Incluye detalles técnicos publicados por el investigador. Úselos solo para validar y corregir sus propios sistemas.

Versiones

Rangos afectados

Afectada Corregida
nltk< 3.10.4
3.10.4
Remediación

Estado del parche por paquete

Paquete / productoEstadoCorregida enDesde divulgaciónÚltima versión
PyPInltk
Corregida 3.10.4 — —
Versiones corregidas3.10.4
Explotación

Arsenal público

Sin exploits, módulos ni PoC públicos conocidos a la fecha de verificación.

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

Las referencias externas se muestran para copiar: cve.llama.ec no lo redirige a otros sitios.