Hoch

NLTK: Unbegrenzte CPU-Auslastung in SteppingRecursiveDescentParser.parse() bei mehrdeutigen oder selbsteinbettenden Grammatiken

  • Veröffentlicht: 13.11.2026
  • Aktualisiert: 18.11.2026 03:17

Die Originalmeldung wurde seit der Erstellung dieser Erklärung geändert. Prüfen Sie die aktuellen technischen Daten und die Originalmeldung unten.

Zusammenfassung

nltk.parse.recursivedescent.SteppingRecursiveDescentParser.parse() führt bei mehrdeutigen oder selbsteinbettenden kontextfreien Grammatiken eine unbegrenzte Top-Down-Suche ohne Begrenzung der Echtzeit (Wall-Clock) oder der Einzelschritte durch. Ein Angreifer, der die Grammatik beeinflussen und einer Aufruferfunktion, die diesen Parser verwendet, eine kurze Eingabe übergeben kann, kann einen einzelnen Aufruf von parse() dazu bringen, einen CPU-Kern dauerhaft zu blockieren und somit einen Denial-of-Service-Zustand hervorzurufen. Während die verwandte Basisklasse RecursiveDescentParser mit einer Echtzeit-Frist über max_time versehen wurde, steuert die Stepping-Subklasse ihre eigene Schrittschleife und initialisiert oder konsultiert diese Frist nicht. Zudem akzeptiert ihr Konstruktor keinen Parameter max_time, wodurch diese Schutzmaßnahme auf diesem Aufrufpfad nicht aktiviert werden kann.

Ursache

RecursiveDescentParser begrenzt die rekursive Suche innerhalb von _parse: Beim ersten Schritt wird eine Frist gesetzt und TimeoutError ausgelöst, sobald max_time (Standardwert: 5.0 Sekunden) überschritten wird. SteppingRecursiveDescentParser wurde für interaktives schrittweises Ausführen entwickelt und überschreibt sowohl parse() als auch _parse. Die Methode parse() führt initialize() gefolgt von einer while self.step() is not None-Schleife aus, die niemals das geschützte Basis-_parse betritt. Die überschriebene Methode _parse ist ein Zustand erfassender Stub, der den Verlauf speichert sowie einen Sentinel-Wert zurückgibt und zu keinem Zeitpunkt die geerbten Variablen self._parse_deadline oder self._max_time referenziert. Die Signatur von __init__ lässt max_time vollständig aus, sodass ein Aufrufer kein Limit vorgeben oder anpassen kann. Die Sicherheitsanforderung, dass ein Parsing-Vorgang innerhalb begrenzter Zeit enden muss, wird auf diesem Parser somit nicht durchgesetzt.

Affected component: nltk.parse.recursivedescent.SteppingRecursiveDescentParser
- parse()      nltk/parse/recursivedescent.py:428-433  (drives its own step loop, no bound armed or checked)
- _parse()     nltk/parse/recursivedescent.py:643-668  (stub override; never consults self._parse_deadline / self._max_time)
- __init__()   nltk/parse/recursivedescent.py:410-418  (signature (self, grammar, trace=0); no max_time parameter)
Base guard for comparison: RecursiveDescentParser._parse nltk/parse/recursivedescent.py:141-150

Auswirkungen

Ein Angreifer, der die an SteppingRecursiveDescentParser übergebene Grammatik kontrolliert oder beeinflusst und eine kurze Tokenfolge an eine aufrufende Stelle übergibt, die parse() ausführt, kann dafür sorgen, dass dieser Aufruf nicht zurückkehrt. Die Top-Down-Suche zählt einen Ableitungsraum auf, der in der Größenordnung der Catalan-Zahlen wächst – ohne Memoisation der Suche und ohne Zeitlimit –, sodass eine präparierte Grammatik in Verbindung mit einer kurzen Eingabe deterministisch einen CPU-Kern auslastet. In Umgebungen, die vom Angreifer beeinflusste Eingaben über einen begrenzten Worker-Pool verarbeiten, können wiederholte Anfragen den Pool erschöpfen und legitime Nutzer blockieren. In diesem Szenario ist keine Authentifizierung, kein Privileg und keine Benutzerinteraktion erforderlich. Für eine Ausnutzung muss das Ziel diesen Parser tatsächlich auf nicht vertrauenswürdige Eingaben anwenden; da der Stepping-Parser primär als Debugging- oder interaktive Komponente für GUIs dient, ist das Risiko in der Praxis geringer als beim Basis-Parser, wenngleich parse() eine reguläre öffentliche Methode darstellt, die als vollständiger Parser agiert.

Proof of Concept

Requires only the nltk package (3.10.3) and standard library; no data downloads or network access.

Schritte zur Reproduktion:

  1. Erstellen einer mehrdeutigen, selbsteinbettenden Grammatik wie S -> 'a' S S | 'a'.
  2. Bestätigen, dass der Basis-Parser von selbst stoppt: RecursiveDescentParser(g, max_time=2.0).parse(['a']*17) löst nach etwa 2 Sekunden TimeoutError aus.
  3. Ausführen des Stepping-Parsers mit derselben Grammatik und Eingabe; beobachten, dass der Aufruf nicht zurückkehrt.
python
import time, inspect
from nltk import CFG
from nltk.parse.recursivedescent import RecursiveDescentParser, SteppingRecursiveDescentParser

g = CFG.fromstring("S -> 'a' S S | 'a'")

# Base parser is bounded and self-terminates.
try:
    list(RecursiveDescentParser(g, max_time=2.0).parse(['a'] * 17))
except TimeoutError:
    print("base: TimeoutError (guarded)")

# Stepping subclass cannot be bounded: no max_time parameter.
print("stepping __init__ sig:", inspect.signature(SteppingRecursiveDescentParser.__init__))

# Stepping parser runs unbounded on the same input.
t0 = time.perf_counter()
list(SteppingRecursiveDescentParser(g).parse(['a'] * 17))  # does not return
print("stepping: returned after", time.perf_counter() - t0)
base: TimeoutError (guarded)
stepping __init__ sig: (self, grammar, trace=0)
# stepping len3: 1 parse in 0.001s ; len7: 5 in 0.017s ; len9: 14 in 0.075s ; len11: 42 in 0.36s
# stepping len17: still running past a 10s watchdog, process alive, no RecursionError

Angriffskette

  1. Exposition: Ein Aufrufer verwendet nltk.parse.SteppingRecursiveDescentParser, ein öffentlich exportiertes Symbol (nltk/parse/__init__.py:97), und ruft parse(tokens) mit einer durch einen Angreifer beeinflussten Grammatik und Eingabe auf.
  2. Kontrolle: Der Angreifer beeinflusst die Grammatik (eine mehrdeutige, selbsteinbettende CFG wie S -> 'a' S S | 'a') und liefert eine kurze Token-Liste (z. B. 17 Kopien von 'a'). Beides gelangt unverändert an den Parser.
  3. Pfad: parse() (recursivedescent.py:428) ruft initialize() auf und durchläuft dann while self.step() is not None; step() (:479) ruft match()/expand() (:552/:512) auf, welche die geerbten Methoden _match/_expand (:172/:214) aufrufen; diese lösen self._parse via MRO zum Subklassen-Stub (:643) auf.
  4. Schutzmechanismus: Das Zeitlimit über max_time existiert nur im Basis-_parse (:141-150) und wird auf diesem Pfad nie betreten; der Stub _parse speichert den Status und kehrt zurück, ohne die Frist zu prüfen, während __init__ kein max_time zur Begrenzung anbietet.
  5. Grundursache: Die unbegrenzte Top-Down-Suche zählt einen Ableitungsraum von der Größe der Catalan-Zahlen ohne Memoisation und ohne Frist auf.
  6. Ergebnis: Der Aufruf von parse() kehrt nie zurück und belegt einen CPU-Kern dauerhaft; wiederholte Aufrufe erschöpfen den Worker-Pool und führen zum Denial of Service.

Umgehungsanalyse

Der frühere Fix für diese Problemklasse fügte der Basisklasse RecursiveDescentParser._parse (recursivedescent.py:141-150, standardmäßig 5.0 Sekunden) ein Zeitlimit über max_time hinzu. Dieser Bericht zeigt, dass die Korrektur den alternativen Einstiegspunkt SteppingRecursiveDescentParser nicht abdeckt, und die Maintainer härteten andere Parser (Chart, Earley Chart, Viterbi, Shift-Reduce, Non-Projective Dependency) separat mit max_time ab, ließen diese Subklasse jedoch ungeschützt.

Getestete Hypothesen und Ergebnisse:

  • Hypothese, dass der geerbte Wert self._max_time (beobachtet bei 5.0) den Pfad absichert: widerlegt; der Wert wird geerbt, aber im Stepping-Pfad nicht gelesen, wodurch der Parser unbegrenzt weiterläuft.
  • Hypothese, dass ein Aufrufer den Parser über den Konstruktor begrenzen kann: widerlegt; inspect.signature(SteppingRecursiveDescentParser.__init__) lautet (self, grammar, trace=0) ohne max_time-Parameter.
  • Hypothese, dass der Fehler lediglich ein vorzeitiges RecursionError statt einer CPU-Erschöpfung darstellt: widerlegt; die Schrittschleife iteriert über einen expliziten Verlaufsspeicher, sodass innerhalb eines Watchdogs von 10 Sekunden keine Ausnahme auftritt, die CPU-Zeit exponentiell mit der Eingabelänge steigt und eine kleine negative Kontrolleingabe in etwa 0.001 Sekunden zurückkehrt.
  • Hypothese, dass die Aufzeichnungen in _tried_e/_tried_m den Suchraum reduzieren: widerlegt; diese Einträge verwenden den vollständigen Teilbaum als Schlüssel, deduplizieren also nur identische Produktionen an identischen Zuständen und verhindern die exponentielle Aufzählung nicht.

Betroffene Versionen

  • Ecosystem: PyPI
  • Package: nltk
  • Confirmed affected range: <= 3.10.3
  • Latest release checked: 3.10.3 (PyPI sdist nltk-3.10.3.tar.gz)
  • Fix status: 3.10.4

Die Stepping-Subklasse hatte in keiner veröffentlichten Version eine Zeit- oder Schrittbegrenzung; der frühere Fix ergänzte die Absicherung lediglich in der Basisklasse. Das Vorhandensein der verwundbaren Methoden wurde im veröffentlichten PyPI-3.10.3-Quellpaket überprüft (parse() in Zeilen 428-433, Stub _parse bei 643-668 ohne Bezug zur Frist und __init__ ohne max_time). Da die Klasse älter als die vorherige Behebung ist und kein historisches Einführungs-Tag bestimmt wurde, bleibt die Untergrenze offen; die Obergrenze wurde am aktuellen Artefakt (3.10.3) verifiziert. Eine veröffentlichte Korrektur existiert nicht.

Vorgeschlagene Behebung

Implementierung einer Begrenzung im Stepping-Parser: SteppingRecursiveDescentParser sollte ein eigenes Zeit- oder Schritt-Budget erhalten, das innerhalb der Schrittschleife überprüft wird (z. B. in parse() und/oder im Pfad _parse/step), und __init__ sollte um einen Parameter max_time (oder eine äquivalente Begrenzung) erweitert werden, analog zu RecursiveDescentParser und den anderen gehärteten Parsern. Als Übergangslösung ohne Codeänderung sollten Aufrufer vermeiden, SteppingRecursiveDescentParser.parse() mit Grammatiken oder Eingaben aus nicht vertrauenswürdigen Quellen auszuführen, derartige Parse-Vorgänge mit einem externen Timeout oder in einem separaten, ressourcenbeschränkten Prozess ausführen und für nicht vertrauenswürdige Eingaben vorzugsweise einen Chart-Parser verwenden.


Gemeldet von zx (GitHub: @manus-pi).

Status des Fixes (2026-09-28)

PR: #3895 „[WIP] Bound algorithmic-DoS and uncontrolled-recursion vectors (CWE-400/407/674/1333)“, offen, Head b22ebe144.

Fix-Commit: e20c40e26 „Bound tokenizer/parser algorithmic DoS (ffr9/gpwc/8fx7)“ (SteppingRecursiveDescentParser erhält den Parameter max_time, Standardwert 5.0 s, und berücksichtigt die Parse-Frist).

Kein Probe. Erneute Ausführung des PoC (Grammatik S -> 'a' S S | 'a', 17 Tokens): Auf dem Head des PRs löst das Parsen nach 5.0 s einen TimeoutError aus, und die Konstruktorsignatur lautet (self, grammar, trace=0, max_time=5.0); auf develop 2fa3f48fe lief derselbe Aufruf über einen Watchdog von 45 s hinaus, sodass develop weiterhin VERWUNDBAR ist.

Release: keines.

Was zu tun ist

Aktuell ist keine offizielle Version mit Fehlerbehebung veröffentlicht. Zur Schadensminderung wird empfohlen, SteppingRecursiveDescentParser.parse() nicht mit nicht vertrauenswürdigen Grammatiken oder Eingaben auszuführen, externe Timeouts oder ressourcenbeschränkte Prozesse zu verwenden und für nicht vertrauenswürdige Daten Chart-Parser einzusetzen.

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
13.11.2026
Aktualisiert
18.11.2026 03:17

Quellen und Lizenzen · Von DockRay bearbeitet oder übersetzt; Rechte und Lizenzen der Quellen bleiben erhalten.

OSV / GitHub Advisory Database - GHSA-8fx7-8jr8-84rv - 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: Unbegrenzte CPU-Auslastung in SteppingRecursiveDescentParser.parse() bei mehrdeutigen oder selbsteinbettenden Grammatiken dieser Eintrag
    Hoch · 7.5 CVE-2026-126303 < 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.