Alta

NLTK: Denegación de servicio por consumo cuadrático de CPU en Tree.chomsky_normal_form

  • Publicada: 14.11.2026
  • Actualizado: 15.11.2026 10:00

Resumen

Tree.chomsky_normal_form() binariza un árbol sintáctico utilizando por defecto la factorización a la derecha (right factoring). Para un nodo con N hijos, esta rama elimina repetidamente el primer elemento de una lista de trabajo mediante list.pop(0), desplazando todos los elementos restantes en cada paso. Debido a esto, binarizar un nodo ancho tiene un coste de O(N^2). Una aplicación que convierta un árbol de treebank suministrado por un atacante a la Forma Normal de Chomsky puede quedar bloqueada consumiendo CPU durante decenas de segundos en un único hilo mediante un árbol plano y ancho. No se requiere autenticación ni interacción del usuario.

Causa raíz

En la rama de factorización a la derecha predeterminada, la transformación ejecuta curNode[0:] = [nodeCopy.pop(0), newNode] en un bucle sobre los N hijos de un nodo. list.pop(0) tiene una complejidad de O(len), ya que desplaza cada elemento restante una posición. Al ejecutarse N-2 veces sobre una lista decreciente de tamaño N, el tiempo acumulado es de O(N^2). Por contra, la rama de factorización a la izquierda usa nodeCopy.pop() (que elimina el último elemento), lo cual es O(1) y lineal en su totalidad. Por tanto, la diferencia crítica radica únicamente en la eliminación por el frente frente a la eliminación por el final. No se impone ningún límite a la cantidad de hijos en un nodo, y el analizador público Tree.fromstring acepta árboles anidados arbitrariamente anchos.

Affected function:
- nltk.tree.transforms.chomsky_normal_form (nltk/tree/transforms.py; right-factor sink at line 168, O(1) left control at line 179)
Public entry points: nltk.tree.Tree.chomsky_normal_form (nltk/tree/tree.py:455, default factor="right"); nltk.tree.Tree.fromstring (nltk/tree/tree.py:592).

Impacto

Un atacante que controle el árbol que una aplicación normaliza a la Forma Normal de Chomsky puede ocasionar un consumo sostenido de CPU en un único hilo (pérdida de disponibilidad). La ruta es alcanzable 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 computacional crece de forma cuadrática respecto al número de hijos establecido por el atacante, aproximadamente 1.5 MB de entrada en formato treebank requieren unos 14 segundos en un solo núcleo y escalan a razón de N^2 a partir de ahí. La confidencialidad y la integridad no se ven afectadas. El tiempo de espera (timeout) de expresiones regulares de NLTK solo cubre el emparejamiento por regex y no protege este bucle sobre listas en Python puro.

Prueba de concepto

Environment: nltk 3.10.3, CPython. Drive the public transform on a wide flat tree.
python
import time
from nltk.tree import Tree

for N in (80000, 160000, 320000):
    s = "(S " + "(A a)" * N + ")"
    t = Tree.fromstring(s)
    start = time.perf_counter()
    t.chomsky_normal_form()          # default factor="right"
    print("right", N, round(time.perf_counter() - start, 3), "s")
right (default):  N=80000 1.972s | N=160000 5.004s (2.54x) | N=320000 14.518s (2.90x)   -> super-linear
left  (control):  N=80000 1.399s | N=160000 2.731s (1.95x) | N=320000  5.379s (1.97x)   -> linear

Cadena de ataque

  1. Exposición: Una aplicación analiza una cadena de treebank influenciada por un atacante mediante la función pública Tree.fromstring y la normaliza con Tree.chomsky_normal_form().
  2. Control: El atacante controla el número de hijos de un nodo (un árbol plano y ancho como (S (A a)(A a)...(A a))); no existe ningún límite para el número de hijos en fromstring ni en la transformación.
  3. Ruta: Tree.chomsky_normal_form delega en nltk.tree.transforms.chomsky_normal_form con la configuración predeterminada factor="right".
  4. Protección: Ninguna. No existe un límite de ancho en el bucle, y el tiempo de espera por regex no abarca esta operación de lista nativa en Python.
  5. Primitiva: curNode[0:] = [nodeCopy.pop(0), newNode] ejecuta un desplazamiento frontal O(N) en cada una de las N iteraciones.
  6. Resultado: Agotamiento de CPU en un único núcleo con coste O(N^2); unos 1.5 MB de entrada requieren aproximadamente 14 segundos y escalan cuadráticamente, bloqueando el hilo de ejecución.

Evidencia de elusión

No existen mecanismos de control que eludir en esta ruta: ni Tree.fromstring ni chomsky_normal_form limitan el recuento de nodos hijos, y el timeout de expresiones regulares no supervisa este bucle. Las mediciones confirmaron la causa: las ramas de factorización a la derecha y a la izquierda realizan operaciones equivalentes de construcción de cadenas y copiado, por lo que el único factor discordante es pop(0) frente a pop(). La divergencia medida aumenta con N (la opción por la derecha escala hacia una relación de 4x al duplicar la entrada, mientras que la izquierda se mantiene cerca de 2x). Adicionalmente, la transformación inversa un_chomsky_normal_form ya había sido reescrita como un recorrido lineal para eliminar precisamente este problema cuadrático (véase el comentario en nltk/tree/transforms.py:195-201), mientras que la ruta predeterminada conservó el patrón pop(0).

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

El patrón pop(0) está presente en todas las versiones que incorporan esta transformación, incluida la versión 3.10.3.

Corrección sugerida

Reescribir la binarización para evitar eliminar elementos del inicio de la lista, utilizando un cursor de índice o un collections.deque para que cada paso sea de tiempo constante, de forma análoga a la reconstrucción lineal aplicada a un_chomsky_normal_form. Como defensa en profundidad, limitar el recuento de hijos aceptados para normalización. Hasta la publicación de la corrección, se debe restringir el ancho máximo del árbol y ejecutar la operación con límites de tiempo o CPU en un worker aislado.

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

Estado de corrección (2026-09-28)

PR: #3909 "Fix quadratic DoS in Tree.chomsky_normal_form right-factor binarization (GHSA-r53h-rw34-8h97)", integrado el 2026-09-23, commit de merge 2f53e20ce en develop.

Commits de solución: 457ebe349 (consumo frontal lineal en chomsky_normal_form) y 677857dca (rechazo de binarizaciones que anidarían un árbol más allá de MAX_TREE_DEPTH). Seguimiento en PR #3917 (merge 9ba132e43, commit f0686dea6) para recorrer la igualdad y conversión de Tree con una pila explícita y permitir que las pruebas de árboles profundos pasen en Python 3.10 y 3.11.

Sonda: nltk/test/unit/security_probes/ghsa_r53h_rw34_8h97.py; resultado en develop 2fa3f48fe: FIXED (chomsky_normal_form escala 5.1x sobre una entrada de 4x).

Qué hacer

Actualice NLTK a la versión 3.10.4 o superior. La corrección se implementó mediante los commits 457ebe349 y 677857dca en el PR #3909 (commit de fusión 2f53e20ce en develop), junto con el PR de seguimiento #3917.

Como mitigación alternativa, limite el ancho máximo permitido del árbol y ejecute la transformación con un límite de tiempo o CPU en un proceso aislado.

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-r53h-rw34-8h97 - 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 por consumo cuadrático de CPU en Tree.chomsky_normal_form esta entrada
    Alta · 7.5 CVE-2026-126298 < 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.