Hoch

NLTK: CPU-Denial-of-Service mit quadratischer Laufzeit im CCG-Lexikon-Parser (fromstring) bei breiten Klammerinhalten und Operatorketten

  • Veröffentlicht: 14.11.2026
  • Aktualisiert: 15.11.2026 10:00

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.
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)

Angriffskette

  1. Exposition: Eine Anwendung ruft die öffentliche Funktion nltk.ccg.lexicon.fromstring(lex_str) (auch erreichbar als nltk.ccg.chart.fromstring) mit vom Angreifer beeinflussbarem Text auf.
  2. Kontrolle: Der Angreifer kontrolliert die Klammerbreite und die Länge der Operatorkette; beides wird von fromstring nicht begrenzt.
  3. Pfad: fromstring zerlegt die Eingabe in Zeilen und leitet jede Kategorie an nextCategory weiter, was zu matchBrackets (Vektor A) oder in die augParseCategory-Operatorschleife (Vektor B) führt.
  4. Schutzmechanismus: Der einzige Schutz ist die Rekursionsprüfung MAX_PARSE_DEPTH = 500. Bei flachen Eingaben bleibt die Tiefe bei null, wodurch if _depth > max_depth nie erreicht wird und die Schleifen unbegrenzt laufen.
  5. Primitiv: Das erneute Slicing rest = rest[1:] und Kopieren rest = app[3] führt eine quadratische Anzahl von Kopiervorgängen aus.
  6. 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: 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

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.py nutzen matchBrackets, nextCategory und augParseCategory einen Zeiger/Cursor statt Slicing, die nachgestellte Erfassungsgruppe wurde entfernt, und MAX_PARSE_LEN=100000 begrenzt 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_LEN abgewiesen). 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 fromstring erzwingen 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.

PlattformPaketAnfällige VersionenBehoben in
Python (PyPI) nltk < 3.10.4 3.10.4

Verweise

CVSS-Wert 7.5/10
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.

Alle (79) im Archiv
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

  1. 2019: 1
  2. 2020: 0
  3. 2021: 2
  4. 2022: 1
  5. 2023: 0
  6. 2024: 1
  7. 2025: 0
  8. 2026: 74
Schweregrad:
  1. NLTK: CPU-Denial-of-Service mit quadratischer Laufzeit im CCG-Lexikon-Parser (fromstring) bei breiten Klammerinhalten und Operatorketten dieser Eintrag
    Hoch · 7.5 CVE-2026-126299 < 3.10.4 3.10.4
  2. Hoch CVE-2026-79674 < 3.10.3 3.10.3
  3. Hoch · 8.8 CVE-2026-71513 >= 3.10.0, < 3.10.3 3.10.3
  4. Hoch · 5.9 CVE-2026-62385 < 3.10.0 3.10.0
  5. Hoch · 7.5 CVE-2026-33231 < 3.9.4 3.9.4
  6. Hoch · 8.6 CVE-2026-0847 < 3.9.3 3.9.3
  7. Kritisch · 10.0 CVE-2025-14009 < 3.9.3 3.9.3
  8. Hoch · 7.5 CVE-2024-39705 < 3.9 3.9
  9. Hoch · 7.5 CVE-2021-3842 < 3.6.6 3.6.6
  10. Hoch · 7.5 CVE-2021-3828 < 3.6.4 3.6.4
  11. Hoch · 7.5 CVE-2019-14751 < 3.4.5 3.4.5

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.

Anwendung verbinden
DockRay Newsletter

Anwendungssicherheit in Ihrem Postfach

Wichtige Schwachstellen, konkrete Empfehlungen und praktische Tipps für Ihre Anwendungen. Wählen Sie Ihre Technologien und verfolgen Sie, was für Ihr Projekt relevant ist.

  • Eine tägliche Zusammenfassung neuer Schwachstellen, auch kritischer.
  • Benachrichtigungen über wichtige Updates.
  • Praktische Tipps zur Sicherheit und Überwachung von Anwendungen.

Leer lassen, um Meldungen zu allen Technologien zu erhalten.

Kostenlos anmelden. In jeder E-Mail mit einem Klick abmelden.