Alta

NLTK: Consumo desmedido de CPU en SteppingRecursiveDescentParser.parse() con gramáticas ambiguas o autorrecurrentes

  • Publicada: 13.11.2026
  • Actualizado: 18.11.2026 03:17

El aviso original ha cambiado desde que se preparó esta explicación. Consulta los datos técnicos actuales y el aviso original a continuación.

Resumen

nltk.parse.recursivedescent.SteppingRecursiveDescentParser.parse() ejecuta una búsqueda descendente (top-down) no acotada sobre gramáticas libres de contexto ambiguas o con autorrecurrencia (self-embedding) sin ningún límite de tiempo de reloj o de pasos. Un atacante capaz de influir en la gramática y proporcionar una entrada corta a un llamador que utilice este analizador puede provocar que una única llamada a parse() bloquee indefinidamente un núcleo de CPU, generando una denegación de servicio. Aunque la clase base relacionada RecursiveDescentParser incorporó un límite de tiempo de reloj mediante max_time, la subclase stepping gestiona su propio bucle de pasos y nunca activa ni consulta dicho límite, y su constructor no acepta el parámetro max_time, impidiendo habilitar esta protección en dicha ruta.

Causa raíz

RecursiveDescentParser limita su búsqueda recursiva dentro de _parse: fija un plazo de reloj en el primer paso y lanza TimeoutError si se supera max_time (por defecto 5.0 segundos). SteppingRecursiveDescentParser fue diseñado para la ejecución interactiva paso a paso y sobrescribe tanto parse() como _parse. Su método parse() ejecuta initialize() seguido de un bucle while self.step() is not None que nunca ingresa en la base protegida _parse. La sobrescritura de _parse es un stub de captura de estado que registra el historial y devuelve un centinela, sin hacer referencia a self._parse_deadline o self._max_time heredados. La firma de __init__ omite max_time por completo, por lo que el invocador no puede definir ni ajustar un límite. Por lo tanto, el principio de seguridad de que un análisis debe terminar en un tiempo acotado nunca se aplica en este analizador.

Affected component: nltk.parse.recursivedescent.SteppingRecursiveDescentParser
- parse()      nltk/parse/recursivedescent.py:428-433  (drives its own step loop, no bound armed or checked)
- _parse()     nltk/parse/recursivedescent.py:643-668  (stub override; never consults self._parse_deadline / self._max_time)
- __init__()   nltk/parse/recursivedescent.py:410-418  (signature (self, grammar, trace=0); no max_time parameter)
Base guard for comparison: RecursiveDescentParser._parse nltk/parse/recursivedescent.py:141-150

Impacto

Un atacante que controle o influya en la gramática enviada a SteppingRecursiveDescentParser y proporcione una secuencia corta de tokens a un llamador que invoque parse() puede causar que la llamada nunca retorne. La búsqueda descendente enumera un espacio de derivaciones que crece en el orden de los números de Catalan, sin memoización de la búsqueda y sin tiempo límite, de modo que una gramática manipulada junto con una entrada corta consume de manera determinista un núcleo de CPU. En un entorno que analiza entradas influenciadas por atacantes utilizando un conjunto finito de procesos de trabajo (worker pool), peticiones repetidas agotan dicho conjunto y deniegan el servicio a usuarios legítimos. En este escenario no se requiere autenticación, privilegios ni interacción del usuario. La explotación requiere que el objetivo utilice efectivamente este analizador con datos no confiables; dado que el analizador stepping es principalmente un componente para depuración e interacción visual (GUI), la exposición real es menor en comparación con el analizador base, aunque parse() es un método público compatible que funciona como un analizador completo.

Prueba de concepto

Requires only the nltk package (3.10.3) and standard library; no data downloads or network access.

Pasos de reproducción:

  1. Construir una gramática ambigua y con autorrecurrencia como S -> 'a' S S | 'a'.
  2. Confirmar que el analizador base termina por sí mismo: RecursiveDescentParser(g, max_time=2.0).parse(['a']*17) lanza TimeoutError aproximadamente a los 2 segundos.
  3. Ejecutar el analizador stepping con la misma gramática y entrada, y comprobar que nunca finaliza.
python
import time, inspect
from nltk import CFG
from nltk.parse.recursivedescent import RecursiveDescentParser, SteppingRecursiveDescentParser

g = CFG.fromstring("S -> 'a' S S | 'a'")

# Base parser is bounded and self-terminates.
try:
    list(RecursiveDescentParser(g, max_time=2.0).parse(['a'] * 17))
except TimeoutError:
    print("base: TimeoutError (guarded)")

# Stepping subclass cannot be bounded: no max_time parameter.
print("stepping __init__ sig:", inspect.signature(SteppingRecursiveDescentParser.__init__))

# Stepping parser runs unbounded on the same input.
t0 = time.perf_counter()
list(SteppingRecursiveDescentParser(g).parse(['a'] * 17))  # does not return
print("stepping: returned after", time.perf_counter() - t0)
base: TimeoutError (guarded)
stepping __init__ sig: (self, grammar, trace=0)
# stepping len3: 1 parse in 0.001s ; len7: 5 in 0.017s ; len9: 14 in 0.075s ; len11: 42 in 0.36s
# stepping len17: still running past a 10s watchdog, process alive, no RecursionError

Cadena de ataque

  1. Exposición: Un llamador utiliza nltk.parse.SteppingRecursiveDescentParser, un símbolo público exportado (nltk/parse/__init__.py:97), invocando parse(tokens) sobre una gramática y una entrada influenciadas por un atacante.
  2. Control: El atacante influye en la gramática (una CFG ambigua y con autorrecurrencia como S -> 'a' S S | 'a') y suministra una lista corta de tokens (por ejemplo, 17 copias de 'a'). Ambas llegan inalteradas al analizador.
  3. Ruta: parse() (recursivedescent.py:428) llama a initialize() y luego itera en while self.step() is not None; step() (:479) llama a match()/expand() (:552/:512), que a su vez llaman a los métodos heredados _match/_expand (:172/:214), los cuales resuelven self._parse por MRO hacia el stub de la subclase (:643).
  4. Protección: El límite de tiempo de reloj max_time existe únicamente en la base _parse (:141-150) y nunca se ejecuta en esta ruta; el stub _parse registra el estado y retorna sin consultar el límite, mientras que __init__ no expone max_time para configurar una cota.
  5. Mecanismo: La búsqueda descendente no acotada enumera un espacio de derivaciones del orden de los números de Catalan sin memoización ni límite de tiempo.
  6. Resultado: La llamada a parse() nunca finaliza y satura un núcleo de CPU; peticiones sucesivas agotan el grupo de workers y producen una denegación de servicio.

Evidencia de evasión

La solución anterior para esta clase de problema añadió un plazo de tiempo de reloj max_time a la clase base RecursiveDescentParser._parse (recursivedescent.py:141-150, por defecto 5.0 segundos). Este informe demuestra que esa corrección no cubre el punto de entrada alternativo SteppingRecursiveDescentParser, y los mantenedores reforzaron por separado otros analizadores (chart, earley chart, viterbi, shift-reduce, non-projective dependency) con max_time mientras dejaron esta subclase sin acotar.

Hipótesis evaluadas y resultados:

  • Hipótesis de que el valor heredado self._max_time (observado en 5.0) protege la ruta: refutada; el valor se hereda pero nunca se lee en la ruta de ejecución stepping, y el analizador continúa sin límite a pesar de estar definido.
  • Hipótesis de que el llamador puede acotar el analizador mediante el constructor: refutada; inspect.signature(SteppingRecursiveDescentParser.__init__) es (self, grammar, trace=0), sin el parámetro max_time.
  • Hipótesis de que la falla es una excepción temprana RecursionError en lugar de consumo excesivo de CPU: refutada; el bucle de pasos es iterativo sobre una pila de historial explícita, por lo que no se produce ninguna excepción dentro de un temporizador de 10 segundos, el tiempo de CPU crece exponencialmente con la longitud de entrada y una entrada corta de control negativo retorna en aproximadamente 0.001 segundos.
  • Hipótesis de que los registros en _tried_e/_tried_m reducen la búsqueda: refutada; dichos registros se indexan mediante el árbol parcial completo, por lo que solo descartan producciones idénticas en estados idénticos y no evitan la enumeración exponencial.

Versiones afectadas

  • Ecosystem: PyPI
  • Package: nltk
  • Confirmed affected range: <= 3.10.3
  • Latest release checked: 3.10.3 (PyPI sdist nltk-3.10.3.tar.gz)
  • Fix status: 3.10.4

La subclase stepping nunca ha incorporado un límite de tiempo o pasos en ninguna versión publicada; la mitigación anterior solo se añadió a la clase base. Se comprobó la presencia de los métodos vulnerables en la distribución oficial de código en PyPI 3.10.3 (parse() en las líneas 428-433, el stub _parse en 643-668 sin referencia a límites y __init__ sin max_time). Dado que la clase es anterior a la corrección previa y no se especificó la versión exacta donde se originó, el límite inferior permanece abierto; el límite superior se verificó frente al artefacto publicado actual (3.10.3). No existe una versión corregida publicada.

Corrección sugerida

Aplicar un límite en el análisis con la clase stepping: asignar a SteppingRecursiveDescentParser su propio presupuesto de tiempo o pasos evaluado dentro de su bucle de pasos (por ejemplo en parse() y/o en la ruta _parse/step), y añadir el parámetro max_time (o un límite de pasos equivalente) a __init__, el cual debe ser propagado y respetado, imitando la base RecursiveDescentParser y los demás analizadores corregidos. Como mitigación temporal sin modificar el código, se aconseja no invocar SteppingRecursiveDescentParser.parse() con gramáticas o datos no confiables, procesar dichas operaciones bajo un temporizador externo o en un proceso aislado con recursos limitados, y optar por analizadores tipo chart para entradas no seguras.


Reportado por zx (GitHub: @manus-pi).

Estado de la solución (2026-09-28)

PR: #3895 "[WIP] Bound algorithmic-DoS and uncontrolled-recursion vectors (CWE-400/407/674/1333)", abierto, head b22ebe144.

Commit de corrección: e20c40e26 "Bound tokenizer/parser algorithmic DoS (ffr9/gpwc/8fx7)" (SteppingRecursiveDescentParser incorpora el parámetro max_time, por defecto 5.0 s, y respeta el límite de tiempo de análisis).

Sin verificación adicional. Reejecución de la PoC (gramática S -> 'a' S S | 'a', 17 tokens): en el head del PR el análisis genera TimeoutError tras 5.0 s y la firma del constructor es (self, grammar, trace=0, max_time=5.0); en develop 2fa3f48fe la misma prueba superó un límite de 45 s, por lo que la rama develop sigue siendo VULNERABLE.

Versión publicada: ninguna.

Qué hacer

No se ha publicado una versión corregida. Para mitigar el riesgo, evite utilizar SteppingRecursiveDescentParser.parse() con datos o gramáticas no confiables, ejecute el análisis bajo un tiempo de espera externo o en procesos restringidos, y emplee analizadores tipo chart.

Software afectado

Haz clic en una tecnología para ver todas sus vulnerabilidades.

PlataformaPaqueteVersiones vulnerablesCorregida en
Python (PyPI) nltk < 3.10.4 3.10.4

Referencias

Puntuación CVSS 7.5/10
Vector CVSS
CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H
Debilidad (CWE)
CWE-400, CWE-407
Plataforma
Python (PyPI)
Paquete
nltk
Publicada
13.11.2026
Actualizado
18.11.2026 03:17

Fuentes y licencias · Editado o traducido por DockRay; se mantienen los derechos y las licencias de las fuentes.

OSV / GitHub Advisory Database - GHSA-8fx7-8jr8-84rv - CC BY 4.0

Historial de vulnerabilidades: nltk

Todas las vulnerabilidades publicadas de este paquete (Python (PyPI)), de la más reciente a la más antigua. Muestra si es un fallo aislado o un paquete que hay que vigilar.

Todas (79) en el archivo
Entradas en total
79
Primera → última
08.2019 11.2026
Sin corrección
5
Explotada en ataques
0

Distribución por gravedad

  • Crítica 5
  • Alta 41
  • Media 31
  • Baja 2

Divulgaciones por año

  1. 2019: 1
  2. 2020: 0
  3. 2021: 2
  4. 2022: 1
  5. 2023: 0
  6. 2024: 1
  7. 2025: 0
  8. 2026: 74
Gravedad:
  1. NLTK: Consumo desmedido de CPU en SteppingRecursiveDescentParser.parse() con gramáticas ambiguas o autorrecurrentes esta entrada
    Alta · 7.5 CVE-2026-126303 < 3.10.4 3.10.4
  2. Alta CVE-2026-79674 < 3.10.3 3.10.3
  3. Alta · 8.8 CVE-2026-71513 >= 3.10.0, < 3.10.3 3.10.3
  4. Alta · 5.9 CVE-2026-62385 < 3.10.0 3.10.0
  5. Alta · 7.5 CVE-2026-33231 < 3.9.4 3.9.4
  6. Alta · 8.6 CVE-2026-0847 < 3.9.3 3.9.3
  7. Crítica · 10.0 CVE-2025-14009 < 3.9.3 3.9.3
  8. Alta · 7.5 CVE-2024-39705 < 3.9 3.9
  9. Alta · 7.5 CVE-2021-3842 < 3.6.6 3.6.6
  10. Alta · 7.5 CVE-2021-3828 < 3.6.4 3.6.4
  11. Alta · 7.5 CVE-2019-14751 < 3.4.5 3.4.5

Identifica las vulnerabilidades de tu aplicación

Con la integración de DockRay y el inventario de software activado, DockRay compara las versiones notificadas de los componentes con las vulnerabilidades conocidas y avisa de las coincidencias confirmadas. La cobertura depende de la tecnología compatible y de los avisos disponibles.

Conectar tu aplicación
Newsletter DockRay

La seguridad de tus aplicaciones en tu correo

Vulnerabilidades importantes, recomendaciones concretas y consejos prácticos para tus aplicaciones. Elige tus tecnologías y sigue lo que importa para tu proyecto.

  • Un resumen diario de nuevas vulnerabilidades, también las críticas.
  • Avisos sobre actualizaciones importantes.
  • Consejos prácticos sobre seguridad y monitorización de aplicaciones.

Déjalo vacío para recibir avisos de todas las tecnologías.

Suscripción gratuita. Date de baja con un clic en cualquier correo.