NLTK: CPU-Denial-of-Service mit quadratischer Laufzeit im CCG-Lexikon-Parser (fromstring) bei breiten Klammerinhalten und Operatorketten
Zusammenfassung
Der öffentliche CCG-Lexikon-Parser nltk.ccg.lexicon.fromstring verarbeitet vom Aufrufer beeinflussbaren Lexikontext mit zwei reinen Python-Schleifen, deren Ausführungsaufwand quadratisch zur Eingabelänge wächst. Ein Dienst, der eine nicht vertrauenswürdige CCG-Lexikon-Zeichenkette verarbeitet, kann durch eine wenige Megabyte große Eingabe für Dutzende Sekunden einen einzelnen CPU-Kern vollständig auslasten und den Worker-Thread blockieren. Es ist weder eine Authentifizierung noch eine Benutzerinteraktion erforderlich.
Ursache
matchBrackets liest einen Klammerinhalt zeichenweise über inside = inside + rest[0]; rest = rest[1:] ein. Die Tail-Slicing-Operation rest = rest[1:] kopiert bei jeder Iteration die verbleibende Zeichenkette vollständig, sodass flache Klammerinhalte O(n^2) kosten. augParseCategory steuert eine while rest != "":-Operatorschleife, die den Match-Rest des regulären Ausdrucks (rest = app[3]) pro Operator neu kopiert, was über eine lange Operatorkette ebenfalls O(n^2) beansprucht. Der Parser besitzt zwar eine Rekursionstiefen-Sperre (MAX_PARSE_DEPTH = 500), die bei tief verschachtelten Kategorien auslöst; da beide quadratischen Schleifen jedoch auf flachen Eingaben mit einer Verschachtelungstiefe von null arbeiten, wird diese Sperre nie aktiviert. Es existiert keine Beschränkung der Zeilenlänge oder Kategorienbreite vor Erreichen dieser Schleifen.
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.
Auswirkungen
Ein Angreifer, der die an eine Anwendung übergebene CCG-Lexikon-Zeichenkette beeinflussen kann, kann eine anhaltende CPU-Auslastung auf einem Thread hervorrufen (Verlust der Verfügbarkeit). Der Pfad ist über das Netzwerk erreichbar (AV:N) und erfordert keine Privilegien oder Benutzerinteraktionen (PR:N, UI:N). Da der Ressourcenaufwand quadratisch mit der Eingabegröße ansteigt, kann eine Payload von wenigen Megabytes Dutzende Sekunden CPU-Zeit beanspruchen; wenige parallele Anfragen können sämtliche Worker-Threads blockieren. Vertraulichkeit und Integrität sind nicht betroffen. Der NLTK-Timeout für reguläre Ausdrücke schützt nur Regex-Operationen und erfasst diese Python-Slicing-Schleifen nicht.
Proof of Concept
Environment: nltk 3.10.3, regex 2026.9.10, CPython. Run the parser on the shipped public API.
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)
Angriffskette
- Exposition: Eine Anwendung ruft die öffentliche Funktion
nltk.ccg.lexicon.fromstring(lex_str)(auch erreichbar alsnltk.ccg.chart.fromstring) mit vom Angreifer beeinflussbarem Text auf. - Kontrolle: Der Angreifer kontrolliert die Klammerbreite und die Länge der Operatorkette; beides wird von
fromstringnicht begrenzt. - Pfad:
fromstringzerlegt die Eingabe in Zeilen und leitet jede Kategorie annextCategoryweiter, was zumatchBrackets(Vektor A) oder in dieaugParseCategory-Operatorschleife (Vektor B) führt. - Schutzmechanismus: Der einzige Schutz ist die Rekursionsprüfung
MAX_PARSE_DEPTH = 500. Bei flachen Eingaben bleibt die Tiefe bei null, wodurchif _depth > max_depthnie erreicht wird und die Schleifen unbegrenzt laufen. - Primitiv: Das erneute Slicing
rest = rest[1:]und Kopierenrest = app[3]führt eine quadratische Anzahl von Kopiervorgängen aus. - Ergebnis: Anhaltende CPU-Erschöpfung auf einem Kern; wenige Megabyte blockieren den Parser-Thread für Dutzende Sekunden.
Bypass-Nachweis
Der einzige vorhandene Schutz ist die Rekursionstiefen-Prüfung MAX_PARSE_DEPTH = 500 (nltk/ccg/lexicon.py:22), geprüft in lexicon.py:153 und lexicon.py:228. Sie schützt nur vor Schachtelungstiefe und löst ValueError aus. Die Test-Payloads sind flach (Tiefe 0 bis 1), weshalb die Prüfung nicht anschlägt, während die Schleifen quadratische Zeit verbrauchen. Tests bestätigen, dass Payloads ohne ValueError oder Regex-TimeoutError durchlaufen (Vektor A zeigt einen Faktor von 4x pro Eingabeverdopplung). Auf dem Pfad fromstring existiert keine Begrenzung der Zeilen- oder Kategorielänge. CPythons In-Place-Optimierung greift hier nicht, da rest = rest[1:] eine unbedingte Kopie des verbleibenden Strings erzwingt, was das gemessene Verhältnis 4x belegt.
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
Die betroffenen Schleifen sind in allen Versionen mit CCG-Lexikon-Parser enthalten, einschließlich Release 3.10.3.
Status der Behebung
- PR: #3753 "[Do not merge yet] Fix GHSA-8mgp-746c-j5xp: URL-scheme bypass of pathsec.validate_path", offen; Head da55cab0e (auf Basis von 238f81500).
- Fix-Commit: cf12a5e6a (in
nltk/ccg/lexicon.pynutzenmatchBrackets,nextCategoryundaugParseCategoryeinen Zeiger/Cursor statt Slicing, die nachgestellte Erfassungsgruppe wurde entfernt, undMAX_PARSE_LEN=100000begrenzt die Eingabegröße). - Test:
nltk/test/unit/security_probes/ghsa_89p3_fcch_88ph.py. - Ergebnis: Behoben auf dem PR-Head (Skalierung 4.4x bei Eingabe von 4x; zu lange Ketten werden durch
MAX_PARSE_LENabgewiesen). Auf develop 2fa3f48fe ergaben Tests für Vektor A (Klammerinhalt, 100k vs 400k) 15.8x und für Vektor B (Operatorkette, 8k vs 32k) 11.3x bei 4x, was die Anfälligkeit vor dem Fix bestätigte.
Gemeldet von zx (GitHub: @manus-pi).
Was zu tun ist
Aktualisieren Sie NLTK auf Version 3.10.4 oder wenden Sie den Patch aus Commit cf12a5e6a (PR #3753) an.
Vorgeschlagene Abhilfemaßnahmen
Wie im Quellbericht vorgeschlagen:
- Klammerinhalte und Operatorketten mit einem Index-Zeiger auf den Original-String (oder über ein
collections.deque) durchlaufen, anstatt die Zeichenkette wiederholt zu kopieren. - Eine explizite Grenze für Zeilenlänge und Kategoriebreite an der Schnittstelle
fromstringerzwingen und bei Überschreitung einen Fehler auslösen. - Die maximal akzeptierte Eingabegröße für Lexika beschränken und nicht vertrauenswürdige Eingaben in isolierten Worker-Prozessen mit Zeit- oder CPU-Limits verarbeiten.
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-89p3-fcch-88ph
- https://nvd.nist.gov/vuln/detail/CVE-2026-126299
- https://github.com/nltk/nltk/pull/3944
- https://github.com/nltk/nltk/commit/0bb5b947bd235b950cf2f90e893a498e16da0fe3
- https://github.com/nltk/nltk/commit/cf12a5e6a
- 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-time-denial-of-service-via-ccg-lexicon-fromstring
- 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-89p3-fcch-88ph - 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: CPU-Denial-of-Service mit quadratischer Laufzeit im CCG-Lexikon-Parser (fromstring) bei breiten Klammerinhalten und Operatorketten 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.