Wysoka

NLTK: Odmowa usługi (CPU) o złożoności kwadratowej w parserze leksykonu CCG (fromstring) przy szerokich nawiasach i łańcuchach operatorów

  • Ujawniono: 14.11.2026
  • Aktualizacja: 15.11.2026 10:00

Podsumowanie

Publiczny parser leksykonu CCG nltk.ccg.lexicon.fromstring przetwarza tekst leksykonu kontrolowany przez wywołującego za pomocą dwóch pętli w czystym Pythonie, których koszt rośnie kwadratowo względem długości danych wejściowych. Usługa analizująca niezaufany ciąg leksykonu CCG może zostać obciążona wielosekundowym zużyciem procesora na pojedynczym wątku przez wejście o rozmiarze kilku megabajtów, powodując zagłodzenie procesów roboczych. Podatność nie wymaga uwierzytelnienia ani interakcji ze strony użytkownika.

Przyczyna błędu

Funkcja matchBrackets przetwarza zawartość nawiasów znak po znaku za pomocą inside = inside + rest[0]; rest = rest[1:]. Operacja rest = rest[1:] kopiuje cały pozostały ciąg w każdej iteracji, w związku z czym płaska zawartość nawiasu kosztuje O(n^2). Z kolei augParseCategory obsługuje pętlę operatorów while rest != "":, która kopiuje resztę dopasowania wyrażenia regularnego (rest = app[3]) raz na każdy operator, co również daje złożoność O(n^2) przy długich łańcuchach operatorów. Parser posiada zabezpieczenie głębokości rekurencji (MAX_PARSE_DEPTH = 500), które zgłasza błąd przy głęboko zagnieżdżonych kategoriach, jednak obie pętle kwadratowe działają na płaskich danych o głębokości zero, przez co zabezpieczenie to nigdy się nie aktywuje. Przed wejściem do tych pętli nie jest stosowane żadne ograniczenie długości linii ani szerokości kategorii.

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.

Wpływ

Atakujący mający wpływ na ciąg leksykonu CCG przekazywany do aplikacji może wywołać długotrwałe zużycie procesora na pojedynczym wątku (utrata dostępności). Ścieżka jest dostępna przez sieć (AV:N) i nie wymaga uprawnień ani interakcji użytkownika (PR:N, UI:N). Ponieważ koszt rośnie kwadratowo wraz z rozmiarem wejścia, kilkumegabajtowy ładunek może blokować rdzeń procesora przez dziesiątki sekund, a niewielka liczba równoległych żądań może wyczerpać zasoby wątków roboczych. Poufność i integralność nie są naruszone. Limit czasu wyrażeń regularnych w NLTK dotyczy tylko silnika regex i nie obejmuje operacji wycinania w Pythonie, nie stanowiąc ochrony.

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)

Łańcuch ataku

  1. Ekspozycja: Aplikacja wywołuje publiczną funkcję nltk.ccg.lexicon.fromstring(lex_str) (dostępną również jako nltk.ccg.chart.fromstring) na tekście leksykonu kontrolowanym przez atakującego.
  2. Kontrola: Atakujący kontroluje szerokość zawartości nawiasu i długość łańcucha operatorów; żadna z tych wartości nie jest ograniczana przez fromstring.
  3. Ścieżka: fromstring dzieli dane na linie i kieruje każdą kategorię do nextCategory, skąd następuje przejście do matchBrackets (Wektor A) lub do pętli operatorów augParseCategory (Wektor B).
  4. Zabezpieczenie: Jedyną blokadą jest test głębokości rekurencji MAX_PARSE_DEPTH = 500. Na płaskim wejściu głębokość wynosi zero, więc if _depth > max_depth nigdy nie zostaje osiągnięte, a pętle wykonują się bez ograniczeń.
  5. Prymityw: Operacje rest = rest[1:] i rest = app[3] wykonują kwadratową liczbę kopii ciągów znaków.
  6. Wynik: Długotrwałe wyczerpanie zasobów procesora; kilkumegabajtowy leksykon blokuje wątek analizujący na dziesiątki sekund.

Ominięcie zabezpieczeń

Jedynym mechanizmem obronnym jest zabezpieczenie rekurencji MAX_PARSE_DEPTH = 500 (nltk/ccg/lexicon.py:22), sprawdzane w lexicon.py:153 oraz lexicon.py:228. Chroni ono wyłącznie przed zagnieżdżeniem i zgłasza błąd ValueError. Ładunki wykorzystujące złożoność kwadratową są płaskie (głębokość zagnieżdżenia od zera do jednego), więc test głębokości nie reaguje. Zostało to potwierdzone testami na oficjalnym parserze: ładunki wykonują się bez wywołania ValueError lub błędu regex TimeoutError, wykazując kwadratowe zużycie procesora (4x przy podwojeniu wejścia dla Wektora A). Na ścieżce fromstring brak jest jakichkolwiek limitów długości linii czy kategorii. Optymalizacja konkatenacji w CPythonie nie eliminuje kopiowania, ponieważ rest = rest[1:] bezwarunkowo kopiuje pozostałą część ciągu, co potwierdza zmierzony współczynnik 4x.

Podatne wersje

  • 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

Pętle wycinające występują w każdym wydaniu zawierającym parser leksykonu CCG, w tym w wersji 3.10.3.

Status poprawki

  • PR: #3753 "[Do not merge yet] Fix GHSA-8mgp-746c-j5xp: URL-scheme bypass of pathsec.validate_path", otwarty; commit da55cab0e (na bazie 238f81500).
  • Commit poprawki: cf12a5e6a (w nltk/ccg/lexicon.py: matchBrackets, nextCategory i augParseCategory używają kursora zamiast wycinania fragmentów, usunięto końcową grupę przechwytującą, a MAX_PARSE_LEN=100000 ogranicza rozmiar wejścia).
  • Test weryfikacyjny: nltk/test/unit/security_probes/ghsa_89p3_fcch_88ph.py.
  • Werdykt testu: Naprawione na gałęzi PR (skalowanie 4.4x przy wejściu 4x; nadmiarowe ciągi są odrzucane przez MAX_PARSE_LEN). Na gałęzi develop 2fa3f48fe wektor A (zawartość nawiasu, 100k vs 400k) uzyskał 15.8x, a wektor B (łańcuch operatorów, 8k vs 32k) 11.3x przy wejściu 4x, co wskazywało na podatność gałęzi develop.

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

Co trzeba zrobić

Zaktualizuj bibliotekę NLTK do wersji 3.10.4 lub zastosuj poprawkę z commita cf12a5e6a (PR #3753).

Sugerowane środki zaradcze

Zgodnie z zaleceniami ze źródła:

  • Przeszukuj zawartość nawiasów i łańcuchy operatorów za pomocą wskaźnika indeksu w oryginalnym ciągu (lub collections.deque) zamiast wielokrotnego kopiowania końcówki ciągu.
  • Wprowadź jawne ograniczenie długości linii i szerokości kategorii w punkcie wejściowym fromstring, zgłaszając błąd po jego przekroczeniu.
  • Ogranicz rozmiar przyjmowanych leksykonów i przetwarzaj niezaufane dane w odizolowanym procesie z limitem czasu lub użycia procesora.

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
14.11.2026
Aktualizacja
15.11.2026 10:00

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

OSV / GitHub Advisory Database - GHSA-89p3-fcch-88ph - 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: Odmowa usługi (CPU) o złożoności kwadratowej w parserze leksykonu CCG (fromstring) przy szerokich nawiasach i łańcuchach operatorów ten wpis
    Wysoka · 7.5 CVE-2026-126299 < 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
  5. Wysoka · 8.8 CVE-2026-71513 >= 3.10.0, < 3.10.3 3.10.3
  6. Wysoka · 5.9 CVE-2026-62385 < 3.10.0 3.10.0
  7. Wysoka · 7.5 CVE-2026-33231 < 3.9.4 3.9.4
  8. Wysoka · 8.6 CVE-2026-0847 < 3.9.3 3.9.3
  9. Krytyczna · 10.0 CVE-2025-14009 < 3.9.3 3.9.3
  10. Wysoka · 7.5 CVE-2024-39705 < 3.9 3.9
  11. Wysoka · 7.5 CVE-2021-3842 < 3.6.6 3.6.6
  12. Wysoka · 7.5 CVE-2021-3828 < 3.6.4 3.6.4
  13. Wysoka · 7.5 CVE-2019-14751 < 3.4.5 3.4.5

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.