NLTK: Denegación de servicio por consumo cuadrático de CPU en Tree.chomsky_normal_form
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.
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
- Exposición: Una aplicación analiza una cadena de treebank influenciada por un atacante mediante la función pública
Tree.fromstringy la normaliza conTree.chomsky_normal_form(). - 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 enfromstringni en la transformación. - Ruta:
Tree.chomsky_normal_formdelega ennltk.tree.transforms.chomsky_normal_formcon la configuración predeterminadafactor="right". - 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.
- Primitiva:
curNode[0:] = [nodeCopy.pop(0), newNode]ejecuta un desplazamiento frontal O(N) en cada una de las N iteraciones. - 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: nltkConfirmed affected range: <= 3.10.3Latest 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.
| Plataforma | Paquete | Versiones vulnerables | Corregida en |
|---|---|---|---|
| Python (PyPI) | nltk | < 3.10.4 | 3.10.4 |
Referencias
- https://github.com/nltk/nltk/security/advisories/GHSA-r53h-rw34-8h97
- https://nvd.nist.gov/vuln/detail/CVE-2026-126298
- https://github.com/nltk/nltk/pull/3909
- https://github.com/nltk/nltk/commit/457ebe349f8dd8080224f76a64aff806dd437057
- https://github.com/nltk/nltk/commit/677857dcafd84e4591865d976b562a27dfde566e
- https://github.com/nltk/nltk
- https://github.com/nltk/nltk/releases/tag/v3.10.4
- https://www.vulncheck.com/advisories/nltk-before-3.10.4-quadratic-cpu-denial-of-service-via-tree-chomsky-normal-form
- 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.
- 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
- 2019: 1
- 2020: 0
- 2021: 2
- 2022: 1
- 2023: 0
- 2024: 1
- 2025: 0
- 2026: 74
-
NLTK: Denegación de servicio por consumo cuadrático de CPU en Tree.chomsky_normal_form esta entrada
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.