Wysoka

NLTK: Nieograniczone zużycie procesora w SteppingRecursiveDescentParser.parse() przy niejednoznacznych lub samorozszerzających się gramatykach

  • Ujawniono: 13.11.2026
  • Aktualizacja: 18.11.2026 03:17

Komunikat źródłowy zmienił się od przygotowania tego objaśnienia. Sprawdź aktualne dane techniczne i oryginalny komunikat poniżej.

Podsumowanie

nltk.parse.recursivedescent.SteppingRecursiveDescentParser.parse() wykonuje nieograniczone przeszukiwanie zstępujące (top-down) w przypadku niejednoznacznych lub samorozszerzających się (self-embedding) gramatyk bezkontekstowych, bez limitu czasu zegarowego ani limitu kroków. Osoba atakująca, która ma wpływ na gramatykę i przekaże krótkie dane wejściowe do obiektu wywołującego ten parser, może wymusić, aby pojedyncze wywołanie parse() trwale zajęło rdzeń procesora, wywołując odmowę usługi (DoS). Chociaż powiązana klasa bazowa RecursiveDescentParser otrzymała limit czasu zegarowego max_time, podklasa stepping zarządza własną pętlą kroków i nigdy nie ustawia ani nie sprawdza tego limitu, a jej konstruktor nie przyjmuje parametru max_time, przez co zabezpieczenie to nie może zostać aktywowane na tej ścieżce.

Przyczyna błędu

RecursiveDescentParser ogranicza swoje wyszukiwanie rekurencyjne wewnątrz _parse: przy pierwszym kroku ustawia limit czasu zegarowego i zgłasza TimeoutError, gdy max_time (domyślnie 5.0 s) zostanie przekroczony. Klasa SteppingRecursiveDescentParser została zaprojektowana do interaktywnego wykonywania krok po kroku i nadpisuje zarówno parse(), jak i _parse. Metoda parse() wykonuje initialize(), a następnie pętlę while self.step() is not None, która nigdy nie przechodzi do zabezpieczonej metody bazowej _parse. Nadpisana metoda _parse stanowi funkcję zastępczą (stub) przechwytującą stan, która rejestruje historię i zwraca wartownika (sentinel), nigdy nie odwołując się do odziedziczonych self._parse_deadline ani self._max_time. Sygnatura __init__ całkowicie pomija max_time, przez co wywołujący nie może włączyć ani zaostrzyć ograniczenia. W rezultacie niezmiennik bezpieczeństwa mówiący, że pojedyncze parsowanie musi zakończyć się w ograniczonym czasie, nie jest egzekwowany w tym parserze.

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

Wpływ

Osoba atakująca, która kontroluje lub ma wpływ na gramatykę przekazaną do SteppingRecursiveDescentParser oraz może dostarczyć krótką sekwencję tokenów do kodu wywołującego parse(), może doprowadzić do sytuacji, w której wywołanie to nigdy się nie zakończy. Wyszukiwanie zstępujące wylicza przestrzeń derywacji rosnącą rzędu liczb Catalana, bez spamiętywania (memoizacji) i bez limitu czasu, przez co spreparowana gramatyka wraz z krótkimi danymi wejściowymi w sposób deterministyczny w pełni obciąża rdzeń procesora. W środowiskach przetwarzających dane zależne od atakującego w ograniczonej puli procesów roboczych (worker pool), powtarzające się żądania wyczerpują pulę, odcinając dostęp uprawnionym użytkownikom. W tym scenariuszu nie jest wymagane uwierzytelnienie, uprawnienia ani interakcja ze strony użytkownika. Eksploatacja wymaga, aby aplikacja faktycznie używała tego parsera dla niezaufanych danych; ponieważ parser stepping służy głównie do debugowania i obsługi interaktywnej w GUI, rzeczywista ekspozycja jest mniejsza niż w przypadku parsera bazowego, chociaż parse() pozostaje obsługiwaną publiczną metodą działającą jako pełnoprawny parser.

Proof of Concept

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

Kroki reprodukcji:

  1. Skonstruuj niejednoznaczną gramatykę samorozszerzającą się, np. S -> 'a' S S | 'a'.
  2. Upewnij się, że bazowy parser samoczynnie przerywa pracę: RecursiveDescentParser(g, max_time=2.0).parse(['a']*17) zgłasza TimeoutError po około 2 sekundach.
  3. Uruchom parser stepping z tą samą gramatyką i danymi wejściowymi; zaobserwuj, że wywołanie nigdy się nie kończy.
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

Łańcuch ataku

  1. Ekspozycja: Kod wywołujący korzysta z nltk.parse.SteppingRecursiveDescentParser, publicznie wyeksportowanego symbolu (nltk/parse/__init__.py:97), wywołując parse(tokens) na gramatyce i danych wejściowych zależnych od atakującego.
  2. Kontrola: Atakujący wpływa na gramatykę (niejednoznaczna CFG, np. S -> 'a' S S | 'a') i dostarcza krótką listę tokenów (np. 17 kopii 'a'). Obie wartości trafiają do parsera bez zmian.
  3. Ścieżka wykonania: parse() (recursivedescent.py:428) wywołuje initialize(), po czym wchodzi w pętlę while self.step() is not None; step() (:479) wywołuje match()/expand() (:552/:512), które wywołują dziedziczone _match/_expand (:172/:214), rozwiązujące self._parse wg MRO do metody w podklasie (:643).
  4. Zabezpieczenie: Limit czasu max_time istnieje wyłącznie w klasie bazowej _parse (:141-150) i nigdy nie jest sprawdzany na tej ścieżce; stub _parse rejestruje stan i kończy działanie bez weryfikacji limitu, a __init__ nie udostępnia max_time do nałożenia ograniczenia.
  5. Mechanizm błędu: Nieograniczone przeszukiwanie zstępujące enumeruje przestrzeń derywacji rzędu liczb Catalana bez memoizacji i limitu czasowego.
  6. Skutek: Wywołanie parse() nigdy się nie kończy i blokuje rdzeń procesora; kolejne wywołania wyczerpują pulę procesów roboczych, powodując odmowę usługi.

Analiza obejścia zabezpieczeń

Wcześniejsza poprawka dla tej klasy problemów wprowadziła limit czasu zegarowego max_time do bazowej klasy RecursiveDescentParser._parse (recursivedescent.py:141-150, domyślnie 5.0 s). Niniejsze zgłoszenie wykazuje, że poprawka nie obejmuje alternatywnego punktu wejścia SteppingRecursiveDescentParser, a autorzy zabezpieczyli inne parsery (chart, earley chart, viterbi, shift-reduce, non-projective dependency) za pomocą max_time, pozostawiając tę podklasę bez limitów.

Zweryfikowane hipotezy i wnioski:

  • Hipoteza, że odziedziczona wartość self._max_time (obserwowana w 5.0) zabezpiecza ścieżkę: odrzucona; wartość ta jest dziedziczona, lecz nigdy nieodczytywana na ścieżce stepping, a parser działa bez ograniczeń mimo jej ustawienia.
  • Hipoteza, że wywołujący może ograniczyć działanie parsera przez konstruktor: odrzucona; inspect.signature(SteppingRecursiveDescentParser.__init__) ma postać (self, grammar, trace=0), bez parametru max_time.
  • Hipoteza, że awaria to jedynie wczesne RecursionError, a nie wyczerpanie CPU: odrzucona; pętla kroków działa iteracyjnie na jawnym stosie historii, więc żaden wyjątek nie pojawia się w ramach 10-sekundowego watchdoga, czas CPU rośnie wykładniczo wraz z długością danych, a krótki negatywny przypadek kontrolny kończy działanie po około 0.001 s.
  • Hipoteza, że wpisy _tried_e/_tried_m zmniejszają przestrzeń poszukiwań: odrzucona; wpisy te są indeksowane pełnym drzewem częściowym, w związku z czym deduplikują jedynie identyczne produkcje w identycznych stanach i nie zapobiegają wykładniczej enumeracji.

Wersje dotknięte podatnością

  • 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

Podklasa stepping w żadnej wydanej wersji nie posiadała limitu czasu ani kroków; wcześniejsza poprawka zabezpieczyła wyłącznie klasę bazową. Obecność podatnych metod potwierdzono w oficjalnej dystrybucji źródłowej PyPI 3.10.3 (parse() w liniach 428-433, stub _parse w 643-668 bez odwołania do limitu czasu oraz __init__ bez max_time). Ponieważ klasa powstała przed wcześniejszą poprawką i nie wskazano konkretnej wersji wprowadzającej, dolna granica wersji nie została sztucznie zdefiniowana; górną granicę potwierdzono na aktualnym wydaniu (3.10.3). Opublikowana poprawka nie istnieje.

Sugerowane rozwiązanie

Wprowadzenie ograniczeń do parsera stepping: nadanie SteppingRecursiveDescentParser własnego budżetu czasu zegarowego lub kroków, weryfikowanego wewnątrz pętli kroków (np. w parse() i/lub na ścieżce _parse/step), oraz dodanie parametru max_time (lub równoważnego limitu kroków) do __init__, który będzie przekazywany i respektowany – analogicznie do bazowej klasy RecursiveDescentParser i pozostałych zabezpieczonych parserów. Jako doraźne obejście problemu bez ingerencji w kod zaleca się unikanie wywoływania SteppingRecursiveDescentParser.parse() na gramatykach lub danych pochodzących z niezaufanych źródeł, uruchamianie parsowania pod kontrolą zewnętrznego limitu czasu (timeout) lub w osobnym procesie z ograniczonymi zasobami, a także preferowanie parserów typu chart w przypadku niezaufanych danych.


Zgłoszone przez zx (GitHub: @manus-pi).

Status poprawki (2026-09-28)

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

Commit z poprawką: e20c40e26 „Bound tokenizer/parser algorithmic DoS (ffr9/gpwc/8fx7)” (SteppingRecursiveDescentParser otrzymuje parametr max_time, domyślnie 5.0 s, oraz respektuje limit czasu parsowania).

Brak sondy. Ponowne uruchomienie PoC (gramatyka S -> 'a' S S | 'a', tokeny: 17): na gałęzi PR parsowanie zgłasza TimeoutError po 5.0 s, a sygnatura konstruktora to (self, grammar, trace=0, max_time=5.0); na gałęzi develop 2fa3f48fe to samo wywołanie przekroczyło 45 s, co oznacza, że gałąź develop jest nadal PODATNA.

Wydanie: brak.

Co trzeba zrobić

Obecnie nie opublikowano oficjalnej wersji naprawionej. Zaleca się unikanie wywoływania SteppingRecursiveDescentParser.parse() na niezaufanych gramatykach lub danych wejściowych, stosowanie zewnętrznych limitów czasu bądź izolacji procesów oraz używanie parserów typu chart.

Czego dotyczy

Kliknij technologię, aby zobaczyć wszystkie dotyczące jej podatności.

PlatformaPaczkaPodatne wersjePoprawka w wersji
Python (PyPI) nltk < 3.10.4 3.10.4

Odnośniki

Ocena CVSS 7.5/10
Wektor CVSS
CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H
Słabość (CWE)
CWE-400, CWE-407
Platforma
Python (PyPI)
Paczka
nltk
Ujawniono
13.11.2026
Aktualizacja
18.11.2026 03:17

Źródła i licencje · Redakcja lub tłumaczenie: DockRay. Zachowano prawa źródeł i obowiązujące licencje.

OSV / GitHub Advisory Database - GHSA-8fx7-8jr8-84rv - CC BY 4.0

Historia podatności: nltk

Wszystkie opisane podatności tej paczki (Python (PyPI)), od najnowszej. Widać, czy to jednorazowa wpadka, czy paczka, której trzeba pilnować.

Wszystkie (79) w archiwum
Wszystkich wpisów
79
Pierwsza → ostatnia
08.2019 11.2026
Bez poprawki
5
Wykorzystywana w atakach
0

Rozkład istotności

  • Krytyczna 5
  • Wysoka 41
  • Średnia 31
  • Niska 2

Ujawnienia w latach

  1. 2019: 1
  2. 2020: 0
  3. 2021: 2
  4. 2022: 1
  5. 2023: 0
  6. 2024: 1
  7. 2025: 0
  8. 2026: 74
Istotność:
  1. Wysoka · 7.5 CVE-2026-129229 >= 3.10.0, < 3.10.4 3.10.4
  2. NLTK: Nieograniczone zużycie procesora w SteppingRecursiveDescentParser.parse() przy niejednoznacznych lub samorozszerzających się gramatykach ten wpis
    Wysoka · 7.5 CVE-2026-126303 < 3.10.4 3.10.4
  3. Wysoka · 7.8 CVE-2026-78680 < 3.10.3 3.10.3
  4. Wysoka CVE-2026-79674 < 3.10.3 3.10.3
Pokaż więcej (20) Widać 20 z 46

Dowiedz się, które podatności dotyczą Twojej aplikacji

Po podłączeniu integracji DockRay i włączeniu raportowania oprogramowania DockRay porównuje zgłoszone wersje komponentów ze znanymi podatnościami i powiadamia o potwierdzonych dopasowaniach. Zakres zależy od obsługiwanej technologii i dostępnych biuletynów.

Podłącz swoją aplikację
Newsletter DockRay

Bezpieczeństwo aplikacji w Twojej skrzynce

Najważniejsze podatności, konkretne zalecenia i praktyczne wskazówki dla Twoich aplikacji. Wybierz technologie i śledź to, co ma znaczenie dla Twojego projektu.

  • Codzienne zestawienie nowych podatności, także krytycznych.
  • Powiadomienia o ważnych aktualizacjach.
  • Praktyczne porady o bezpieczeństwie i monitoringu aplikacji.

Pozostaw puste, aby otrzymywać informacje o wszystkich technologiach.

Zapis jest bezpłatny. Wypiszesz się jednym kliknięciem w wiadomości.