NLTK: Denial of Service durch quadratischen CPU-Aufwand in Tree.chomsky_normal_form
Zusammenfassung
Tree.chomsky_normal_form() binarisiert einen Parse-Baum und verwendet standardmäßig Right-Factoring. Bei einem Knoten mit N Kindknoten entfernt der Right-Factor-Zweig wiederholt das erste Element einer Arbeitsliste mittels list.pop(0), wodurch die verbleibenden Elemente jedes Mal verschoben werden. Dadurch entsteht beim Binarisieren eines breiten Knotens ein Aufwand von O(N^2). Eine Anwendung, die einen von Angreifern bereitgestellten Treebank-Baum in die Chomsky-Normalform konvertiert, kann durch einen einzelnen breiten, flachen Baum für Dutzende Sekunden einen CPU-Thread blockieren. Es ist weder eine Authentifizierung noch eine Benutzerinteraktion erforderlich.
Ursache
Im standardmäßigen Right-Factor-Zweig führt die Transformation curNode[0:] = [nodeCopy.pop(0), newNode] innerhalb einer Schleife über die N Kindknoten eines Knotens aus. list.pop(0) hat eine Laufzeit von O(len), da jedes verbleibende Element um eine Position nach vorne verschoben wird. Wird dies N-2-mal über eine schrumpfende Liste der Länge N ausgeführt, summiert sich der Aufwand auf O(N^2). Der Left-Factor-Zweig verwendet stattdessen nodeCopy.pop() (Entfernen des letzten Elements), was O(1) und insgesamt linear ist. Die beiden Zweige unterscheiden sich somit nur im Entfernen am Anfang gegenüber dem Entfernen am Ende der Liste. Es existiert keine Obergrenze für die Anzahl der Kindknoten, und der öffentliche Parser Tree.fromstring akzeptiert beliebig breite geklammerte Bäume.
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).
Auswirkungen
Angreifer, die Einfluss auf den von einer Anwendung in die Chomsky-Normalform konvertierten Baum nehmen können, können eine anhaltende Single-Thread-CPU-Auslastung herbeiführen (Verlust der Verfügbarkeit). Der Pfad ist über das Netzwerk erreichbar (AV:N) und erfordert weder Berechtigungen noch Benutzerinteraktion (PR:N, UI:N). Da der Aufwand quadratisch mit der vom Angreifer gewählten Kinderanzahl wächst, verursachen etwa 1.5 MB Treebank-Eingabedaten rund 14 Sekunden CPU-Last auf einem Kern und skalieren darüber hinaus mit N^2. Vertraulichkeit und Integrität sind nicht betroffen. Das Regex-Timeout von NLTK überwacht ausschließlich den Abgleich von regulären Ausdrücken und greift bei dieser reinen Python-Listenschleife nicht.
Proof of Concept
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
Angriffskette
- Exposition: Eine Anwendung parst eine von Angreifern beeinflusste Treebank-Zeichenkette mit dem öffentlichen
Tree.fromstringund normalisiert sie mitTree.chomsky_normal_form(). - Kontrolle: Der Angreifer steuert die Anzahl der Kindknoten (ein breiter, flacher Baum wie
(S (A a)(A a)...(A a))); es gibt keine Begrenzung der Kindknotenanzahl infromstringoder der Transformation. - Pfad:
Tree.chomsky_normal_formdelegiert annltk.tree.transforms.chomsky_normal_formmit dem Standardfactor="right". - Schutzmechanismen: Keine vorhanden. Weder existiert eine Breitenbegrenzung in der Schleife, noch schützt das Regex-Timeout vor dieser reinen Python-Listenoperation.
- Primitive:
curNode[0:] = [nodeCopy.pop(0), newNode]führt bei jeder der N Iterationen eine O(N)-Verschiebung durch. - Ergebnis: CPU-Erschöpfung auf einem Kern mit O(N^2); etwa 1.5 MB Eingabedaten benötigen ca. 14 Sekunden und skalieren quadratisch, wodurch der verarbeitende Thread blockiert wird.
Nachweis
Es existiert auf diesem Pfad kein Schutzmechanismus, der umgangen werden müsste: Weder Tree.fromstring noch chomsky_normal_form begrenzen die Anzahl der Kindknoten. Der Befund wurde durch Zeitmessungen belegt: Der Standard-Right-Factor-Zweig und der Left-Factor-Zweig erzeugen identische begrenzte Head-Strings und kopieren den Knoten einmal. Der einzige Unterschied besteht im Aufruf von pop(0) im Vergleich zu pop(). Die gemessene Divergenz wächst mit N (bei Right-Factor nähert sich das Verhältnis bei Verdoppelung einem Faktor von 4x, während Left-Factor nahe 2x bleibt). Die inverse Transformation un_chomsky_normal_form wurde bereits zuvor auf einen linearen Durchlauf umgeschrieben, um genau diese Klasse quadratischen Verhaltens zu beseitigen (siehe Kommentar in nltk/tree/transforms.py:195-201), während der reguläre Standardpfad das pop(0)-Idiom beibehielt.
Betroffene Versionen
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
Das Idiom pop(0) ist in allen Releases enthalten, die diese Transformation bereitstellen, einschließlich der Version 3.10.3.
Vorgeschlagene Behebung
Die Binarisierung mit Right-Factoring sollte so umgeschrieben werden, dass Elemente nicht mehr am Anfang einer Liste entfernt werden, beispielsweise durch Iteration mit einem Indexzeiger oder einem collections.deque, analog zur linearen Implementierung in un_chomsky_normal_form. Als Defense-in-Depth sollte die akzeptierte Anzahl an Kindknoten begrenzt werden. Bis zur Aktualisierung sollten Aufrufer die Baumbreite begrenzen und Zeitlimits festlegen.
Gemeldet von zx (GitHub: @manus-pi).
Status der Fehlerbehebung (2026-09-28)
PR: #3909 "Fix quadratic DoS in Tree.chomsky_normal_form right-factor binarization (GHSA-r53h-rw34-8h97)", gemergt am 2026-09-23, Merge-Commit 2f53e20ce auf develop.
Fix-Commits: 457ebe349 (linearer Konsum am Anfang in chomsky_normal_form) und 677857dca (Ablehnung einer Binarisierung, die einen Baum über MAX_TREE_DEPTH hinaus verschachteln würde). Folge-PR #3917 (Merge 9ba132e43, Commit f0686dea6) durchläuft Baumgleichheit und Konvertierung mit einem expliziten Stack, sodass die Deep-Tree-Tests auf Python 3.10 und 3.11 erfolgreich sind.
Probe: nltk/test/unit/security_probes/ghsa_r53h_rw34_8h97.py; Ergebnis auf develop 2fa3f48fe: FIXED (chomsky_normal_form skaliert mit 5.1x bei einer Eingabe von 4x).
Was zu tun ist
Aktualisieren Sie NLTK auf Version 3.10.4 oder höher. Zur Behebung des Problems wurden die Commits 457ebe349 und 677857dca in PR #3909 (Merge-Commit 2f53e20ce auf develop) sowie der Folge-PR #3917 integriert.
Als Notbehelf sollten Aufrufer die verarbeitete Baumbreite begrenzen und die Transformation mit einem Zeit- oder CPU-Budget in einem isolierten Worker ausführen.
Betroffene Software
Klicken Sie auf eine Technologie, um alle zugehörigen Schwachstellen anzuzeigen.
| Plattform | Paket | Anfällige Versionen | Behoben in |
|---|---|---|---|
| Python (PyPI) | nltk | < 3.10.4 | 3.10.4 |
Verweise
- 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
- CVSS-Vektor
CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H- Schwäche (CWE)
CWE-400, CWE-407- Plattform
- Python (PyPI)
- Paket
nltk- Veröffentlicht
- 14.11.2026
- Aktualisiert
- 15.11.2026 10:00
Quellen und Lizenzen · Von DockRay bearbeitet oder übersetzt; Rechte und Lizenzen der Quellen bleiben erhalten.
OSV / GitHub Advisory Database - GHSA-r53h-rw34-8h97 - CC BY 4.0
Schwachstellenhistorie: nltk
Alle veröffentlichten Schwachstellen dieses Pakets (Python (PyPI)), neueste zuerst. Zeigt, ob es ein einmaliger Ausrutscher ist oder ein Paket, das man im Auge behalten muss.
- Einträge insgesamt
- 79
- Erste → letzte
- 08.2019 11.2026
- Ohne Fix
- 5
- In Angriffen ausgenutzt
- 0
Verteilung nach Schweregrad
- Kritisch 5
- Hoch 41
- Mittel 31
- Niedrig 2
Veröffentlichungen pro Jahr
- 2019: 1
- 2020: 0
- 2021: 2
- 2022: 1
- 2023: 0
- 2024: 1
- 2025: 0
- 2026: 74
-
NLTK: Denial of Service durch quadratischen CPU-Aufwand in Tree.chomsky_normal_form dieser Eintrag
Erkennen Sie Schwachstellen in Ihrer Anwendung
Mit der DockRay-Integration und aktivierter Softwareinventarisierung prüft DockRay gemeldete Komponentenversionen auf bekannte Schwachstellen und benachrichtigt Sie über bestätigte Treffer. Die Abdeckung hängt von der unterstützten Technologie und den verfügbaren Meldungen ab.