Alta

NLTK: Denegación de servicio (CPU) de tiempo cuadrático en el analizador de léxico CCG (fromstring) ante cuerpos de corchetes anchos y cadenas de operadores

  • Publicada: 14.11.2026
  • Actualizado: 15.11.2026 10:00

Resumen

El analizador público de léxico CCG nltk.ccg.lexicon.fromstring procesa texto de léxico influenciado por el usuario mediante dos bucles en Python puro cuyo coste es cuadrático respecto a la longitud de la entrada. Un servicio que analice una cadena de léxico CCG no confiable puede sufrir decenas de segundos de consumo de CPU en un único hilo con una entrada de unos pocos megabytes, agotando los procesos de trabajo. No se requiere autenticación ni interacción del usuario.

Causa raíz

matchBrackets procesa el contenido de los corchetes carácter por carácter mediante inside = inside + rest[0]; rest = rest[1:]. La operación rest = rest[1:] copia la totalidad de la cadena restante en cada iteración, lo que implica que un cuerpo de corchetes plano cuesta O(n^2). Por su parte, augParseCategory ejecuta un bucle de operadores while rest != "": que vuelve a copiar el resto de la coincidencia de la expresión regular (rest = app[3]) una vez por operador, lo que también resulta en O(n^2) sobre una cadena larga de operadores. El analizador incluye una protección de profundidad de recursión (MAX_PARSE_DEPTH = 500) que genera un error ante categorías profundamente anidadas; sin embargo, ambos bucles cuadráticos operan sobre entradas planas cuya profundidad permanece en cero, por lo que la protección nunca se activa. No existe límite para la longitud de línea ni para el ancho de categoría antes de llegar a estos bucles.

Affected functions:
- nltk.ccg.lexicon.matchBrackets       (nltk/ccg/lexicon.py:149-172; tail re-slice at line 168)
- nltk.ccg.lexicon.augParseCategory    (nltk/ccg/lexicon.py:223-268; APP_RE tail re-copy at line 250)
Public entry point: nltk.ccg.lexicon.fromstring (nltk/ccg/lexicon.py:271), also re-exported as nltk.ccg.chart.fromstring.

Impacto

Un atacante capaz de suministrar la cadena de léxico CCG analizada por una aplicación puede provocar un consumo sostenido de CPU en un solo hilo (pérdida de disponibilidad). La ruta vulnerable es accesible a través de la red (AV:N) y no requiere privilegios ni interacción del usuario (PR:N, UI:N). Dado que el coste aumenta de forma cuadrática con el tamaño de la entrada, una carga útil de pocos megabytes consume decenas de segundos por núcleo, pudiendo agotar los hilos de trabajo con pocas peticiones concurrentes. La confidencialidad y la integridad no se ven afectadas. El tiempo de espera para expresiones regulares de NLTK solo cubre operaciones regex y no aplica a estos bucles de partición en Python puro, no ofreciendo protección.

Prueba de concepto

Environment: nltk 3.10.3, regex 2026.9.10, CPython. Run the parser on the shipped public API.
python
import nltk.ccg.lexicon as L

# Vector A: flat bracket body -> matchBrackets tail re-slice is O(n^2)
n = 400000
lex_a = ":- S\nw => (" + "a" * n + ")\n"

# Vector B: long operator chain -> augParseCategory tail re-copy is O(n^2)
m = 32000
lex_b = ":- a\nw => " + "a" + "/a" * m + "\n"

import time
for name, s in (("A", lex_a), ("B", lex_b)):
    t = time.perf_counter()
    try:
        L.fromstring(s)
    except Exception:
        pass  # downstream parse error is irrelevant; the CPU is already burned
    print(name, round(time.perf_counter() - t, 3), "s")
Negative control (":- a\nw => (a/a)"):   ~0.00007 s
Vector A (matchBrackets, flat body):     n=50k 0.078s | 100k 0.260s | 200k 1.046s | 400k 2.083s   (~4x per doubling => O(n^2))
Vector B (augParseCategory, operators):  m=4k 0.078s | 8k 0.215s | 16k 0.485s | 32k 1.329s        (super-linear)

Cadena de ataque

  1. Exposición: Una aplicación invoca la función pública nltk.ccg.lexicon.fromstring(lex_str) (también accesible como nltk.ccg.chart.fromstring) sobre texto de léxico que el atacante puede controlar.
  2. Control: El atacante controla el ancho del contenido entre corchetes y la longitud de la cadena de operadores; ninguno está limitado por fromstring.
  3. Ruta: fromstring divide la entrada en líneas y canaliza cada categoría a través de nextCategory, que deriva a matchBrackets (Vector A) o al bucle de operadores augParseCategory (Vector B).
  4. Protección: La única comprobación es la de profundidad de recursión MAX_PARSE_DEPTH = 500. En entradas planas la profundidad es cero, por lo que nunca se alcanza if _depth > max_depth y los bucles se ejecutan sin restricciones.
  5. Primitiva: El recorte rest = rest[1:] y la copia rest = app[3] realizan un número cuadrático de copias de cadenas.
  6. Resultado: Agotamiento de CPU en un núcleo; un léxico de pocos megabytes bloquea el hilo de análisis durante decenas de segundos.

Evidencia de evasión

La única defensa presente en esta ruta es el control de profundidad de recursión MAX_PARSE_DEPTH = 500 (nltk/ccg/lexicon.py:22), evaluado en lexicon.py:153 y lexicon.py:228. Solo actúa contra la profundidad de anidación y genera ValueError. Las cargas útiles cuadráticas son planas (profundidad de anidación de cero a uno), por lo que el control no se activa mientras los bucles consumen tiempo cuadrático. Pruebas realizadas sobre el analizador original confirmaron que las cargas finalizan sin generar ValueError ni errores de regex TimeoutError, mostrando un factor de coste de 4x por duplicación de entrada en el Vector A. No existen límites de longitud en la ruta fromstring. La optimización de concatenación de CPython no mitiga el problema, ya que rest = rest[1:] copia incondicionalmente el resto de la cadena, confirmándose empíricamente con la relación 4x.

Versiones afectadas

  • Ecosystem: PyPI (pip)
  • Package: nltk
  • Confirmed affected range: <= 3.10.3
  • Latest release checked: 3.10.3 (PyPI, https://pypi.org/pypi/nltk/json)
  • Fix status: 3.10.4

Los bucles están presentes en todas las versiones que distribuyen el analizador de léxico CCG, incluyendo la versión 3.10.3.

Estado de corrección

  • PR: #3753 "[Do not merge yet] Fix GHSA-8mgp-746c-j5xp: URL-scheme bypass of pathsec.validate_path", abierto; commit da55cab0e (sobre 238f81500).
  • Commit de corrección: cf12a5e6a (en nltk/ccg/lexicon.py, matchBrackets, nextCategory y augParseCategory usan un cursor en lugar de recortar cadenas, se elimina el grupo de captura final y MAX_PARSE_LEN=100000 limita la entrada).
  • Prueba de verificación: nltk/test/unit/security_probes/ghsa_89p3_fcch_88ph.py.
  • Veredicto: Corregido en el PR (escalado 4.4x con entrada de 4x; cadenas excedentes son rechazadas por MAX_PARSE_LEN). En develop 2fa3f48fe, el vector A (100k vs 400k) arrojó 15.8x y el vector B (8k vs 32k) 11.3x sobre 4x, confirmando la vulnerabilidad antes del arreglo.

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

Qué hacer

Actualice NLTK a la versión 3.10.4 o aplique el parche del commit cf12a5e6a (PR #3753).

Mitigación sugerida

Según lo propuesto en el reporte original:

  • Recorrer el contenido de los corchetes y las cadenas de operadores utilizando un cursor de índice sobre la cadena original (o un collections.deque) en lugar de copiar repetidamente los extremos.
  • Establecer límites explícitos a la longitud de línea y al ancho de categoría en fromstring, generando un error en caso de superarlos.
  • Limitar el tamaño máximo de las entradas de léxico aceptadas y procesar datos no confiables en un proceso aislado con restricciones de tiempo o CPU.

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
14.11.2026
Actualizado
15.11.2026 10:00

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

OSV / GitHub Advisory Database - GHSA-89p3-fcch-88ph - 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: Denegación de servicio (CPU) de tiempo cuadrático en el analizador de léxico CCG (fromstring) ante cuerpos de corchetes anchos y cadenas de operadores esta entrada
    Alta · 7.5 CVE-2026-126299 < 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
Mostrar más (6) Mostrando 40 de 46

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.