llamaCVEVulnerability Intelligence
/
Advisory · GitHub · PyPI · nltk

GHSA-XFCV-M889-FMQG

NLTK: Uncontrolled recursion in DependencyGraph traversal causes denial of service via deep dependency chains

Parche disponible
Descargar PNG JSON
CVSS 3.1
5.3
Media
CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:L Fuente: GitHub
ExplotaciónSin evidenciaNo figura en CISA KEV
Exploits públicos0Ninguno conocido
Parche1 versión3.10.4
Exposición17 hDesde la divulgación, 19 nov 2026, 6:52 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:52 p. m.
07:00 p. m.
11:34 a. m.
10:00 a. m.
04:23 p. m.
10:47 p. m.
05:10 a. m.
11:34 a. m.
FechaFaseEventoDetalle
Monitoreo Detectada Ingresó al índice
Divulgación Publicada GHSA-XFCV-M889-FMQG divulgada · CVSS 5.3 (GitHub)
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

## Root Cause
The dependency-graph traversal helpers recurse over dependency links without any depth
bound or visited set. `DependencyGraph._tree` (`nltk/parse/dependencygraph.py:404`)
recurses once per dependency link, `triples` (`nltk/parse/dependencygraph.py:432`) is a
recursive generator, and `get_cycle_path` (`nltk/parse/dependencygraph.py:520`) recurses
over dependencies. The neighbouring `contains_cycle` method was deliberately rewritten as
an iterative depth-first search, but these sibling helpers on the public traversal path
were left recursive with no depth counter.

## Impact
An application that parses an untrusted CoNLL/Malt-TAB dependency structure and then walks
it via `tree()` or `triples()` aborts with an unhandled `RecursionError`, terminating the
affected operation or request worker (denial of service, CWE-674). The recursion is pure
Python, so the result is a catchable `RecursionError`, not memory corruption or code
execution. Confidentiality and integrity are unaffected. `get_cycle_path` additionally
lacks a visited set and will not terminate on a genuine cycle.

## Attack Chain
1. The application constructs `DependencyGraph(conll_str)` from attacker-supplied text
where token *k*'s head is token *k+1*, forming a linear dependency chain of length *N*.
Graph construction (`_parse`) is iterative and completes without error.
2. The application calls the public `DependencyGraph.tree()`
(`nltk/parse/dependencygraph.py:408`), which invokes `_tree(root)`.
3. `_tree` recurses once per chain link with no depth guard and no visited set, consuming
one stack frame per link (the list comprehension costs roughly two frames per level).
4. Once the chain length exceeds the interpreter recursion limit, an unhandled
`RecursionError` propagates out of the public API. `triples()` fails the same way.

## Bypass Evidence
Against the shipped source at the default recursion limit, a chain of length 5 walks
cleanly through `tree()`, while a chain of length 5000 raises an unhandled
`RecursionError`; `triples()` fails identically. The minimal trigger is roughly *N*=500
tokens at the default recursion limit — a modest, realistic parse. Because the graph
builds iteratively in both cases, the fault is isolated to the recursive traversal rather
than to parsing. A repository-wide search confirms no depth guard exists in this file; the
iterative rewrite was applied only to `contains_cycle`.

## Suggested Fix
Convert `_tree`, `triples`, and `get_cycle_path` to iterative traversals, or add a
recursion-depth bound (and, for `get_cycle_path`, a visited set) analogous to the
iterative rewrite already applied to `contains_cycle`.

Reported by pi (GitHub: @manus-pi).

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

Probe: nltk/test/unit/security_probes/ghsa_xfcv_m889_fmqg.py (added in 2a6704952 on that PR); verdict on develop 2fa3f48fe: FIXED (bounded in tree() (ValueError)).

Release: none yet; no release tag contains e521ecafc.

Vector CVSS 3.1

Desglose de métricas

Opción resaltada = valor del vector · izquierda = peor caso · GitHub
Vector de ataqueAV:N
RedAdyacenteLocalFísica
ComplejidadAC:L
BajaAlta
PrivilegiosPR:N
NingunoBajosAltos
InteracciónUI:N
NingunaRequerida
AlcanceS:U
CambiadoSin cambio
ConfidencialidadC:N
AltoBajoNinguno
IntegridadI:N
AltoBajoNinguno
DisponibilidadA:L
AltoBajoNinguno
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-129225
Otrahttps://github.com/nltk/nltk/security/advisories/GHSA-xfcv-m889-fmqg
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.