Wysoka

NLTK: Odmowa usługi (DoS) przez kwadratowe zużycie procesora w Tree.chomsky_normal_form

  • Ujawniono: 14.11.2026
  • Aktualizacja: 15.11.2026 10:00

Podsumowanie

Metoda Tree.chomsky_normal_form() dokonuje binaryzacji drzewa składniowego i domyślnie stosuje faktoryzację prawostronną (right factoring). W przypadku węzła posiadającego N elementów potomnych gałąź faktoryzacji prawostronnej wielokrotnie usuwa pierwszy element z listy roboczej za pomocą list.pop(0), co każdorazowo przesuwa wszystkie pozostałe elementy. Sprawia to, że binaryzacja pojedynczego szerokiego węzła ma złożoność O(N^2). Aplikacja, która przekształca dostarczone przez atakującego drzewo typu treebank do postaci normalnej Chomsky'ego, może zostać zablokowana na dziesiątki sekund przez pojedyncze szerokie, płaskie drzewo obciążające jeden wątek procesora. Atak nie wymaga uwierzytelnienia ani interakcji ze strony użytkownika.

Przyczyna źródłowa

W domyślnej ścieżce faktoryzacji prawostronnej transformacja wykonuje wywołanie curNode[0:] = [nodeCopy.pop(0), newNode] wewnątrz pętli iterującej po N elementach potomnych węzła. Operacja list.pop(0) charakteryzuje się złożonościow O(len), ponieważ przesuwa każdy pozostały element o jedną pozycję. Wykonana N-2 razy na zmniejszającej się liście o długości początkowej N, sumuje się do złożoności O(N^2). Z kolei gałąź faktoryzacji lewostronnej korzysta z nodeCopy.pop() (usuwając ostatni element), co zajmuje czas O(1) i jest liniowe w ogólnym rozrachunku. Obie gałęzie różnią się wyłącznie usuwaniem elementu z początku zamiast z końca listy. Nie zaimplementowano żadnego limitu liczby węzłów potomnych, a publiczny parser Tree.fromstring akceptuje dowolnie szerokie drzewa.

Affected function:
- nltk.tree.transforms.chomsky_normal_form (nltk/tree/transforms.py; right-factor sink at line 168, O(1) left control at line 179)
Public entry points: nltk.tree.Tree.chomsky_normal_form (nltk/tree/tree.py:455, default factor="right"); nltk.tree.Tree.fromstring (nltk/tree/tree.py:592).

Wpływ

Atakujący mający wpływ na drzewo przekazywane do normalizacji w aplikacji może doprowadzić do długotrwałego, jednowątkowego zużycia procesora (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 obliczeniowy rośnie kwadratowo wraz z wybraną przez atakującego liczbą elementów potomnych, wejście treebank o rozmiarze około 1.5 MB zajmuje około 14 sekund na jednym rdzeniu i skaluje się dalej jako N^2. Poustność i integralność danych nie są naruszone. Limit czasu wyrażeń regularnych w NLTK dotyczy wyłącznie dopasowywania regex i nie obejmuje tej pętli operującej na liście w czystym Pythonie.

Dowód koncepcji (PoC)

Environment: nltk 3.10.3, CPython. Drive the public transform on a wide flat tree.
python
import time
from nltk.tree import Tree

for N in (80000, 160000, 320000):
    s = "(S " + "(A a)" * N + ")"
    t = Tree.fromstring(s)
    start = time.perf_counter()
    t.chomsky_normal_form()          # default factor="right"
    print("right", N, round(time.perf_counter() - start, 3), "s")
right (default):  N=80000 1.972s | N=160000 5.004s (2.54x) | N=320000 14.518s (2.90x)   -> super-linear
left  (control):  N=80000 1.399s | N=160000 2.731s (1.95x) | N=320000  5.379s (1.97x)   -> linear

Łańcuch ataku

  1. Ekspozycja: Aplikacja przetwarza ciąg treebank kontrolowany przez atakującego za pomocą publicznej funkcji Tree.fromstring i normalizuje go przez Tree.chomsky_normal_form().
  2. Kontrola: Atakujący kontroluje liczbę potomków danego węzła (szerokie, płaskie drzewo, np. (S (A a)(A a)...(A a))); w fromstring ani w transformacji nie ma ograniczenia na liczbę potomków.
  3. Ścieżka: Tree.chomsky_normal_form przekazuje wywołanie do nltk.tree.transforms.chomsky_normal_form z domyślnym parametrem factor="right".
  4. Zabezpieczenia: Brak. W pętli nie ma ograniczenia szerokości, a timeout regex nie obejmuje operacji na liście w Pythonie.
  5. Prymityw: curNode[0:] = [nodeCopy.pop(0), newNode] wykonuje przesunięcie elementów o złożoności O(N) przy każdej z N iteracji.
  6. Wynik: Wyczerpanie zasobów pojedynczego rdzenia procesora w czasie O(N^2); dane wejściowe rzędu 1.5 MB blokują wątek na około 14 sekund i skalują się kwadratowo.

Weryfikacja podatności

Na analizowanej ścieżce nie ma zabezpieczeń: ani Tree.fromstring, ani chomsky_normal_form nie ograniczają liczby potomków. Problem został potwierdzony pomiarami czasowymi: domyślna faktoryzacja prawostronna i lewostronna wykonują te same operacje łączenia ciągów i kopiowania węzła, a jedyną różnicą jest wywołanie pop(0) zamiast pop(). Różnica czasowa rośnie wraz z N (dla faktoryzacji prawostronnej stosunek czasu przy podwojeniu zbliża się do 4x, podczas gdy lewostronna zachowuje wartość bliską 2x). Ponadto odwrotna transformacja un_chomsky_normal_form została już wcześniej przepisana na pojedyncze przejście liniowe w celu eliminacji identycznej klasy problemu (zob. komentarz w nltk/tree/transforms.py:195-201), podczas gdy domyślna ścieżka nadal zawierała konstrukcję pop(0).

Wersje dotknięte podatnością

  • 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

Konstrukcja pop(0) występuje we wszystkich wydaniach zawierających tę transformację, w tym w wydaniu 3.10.3.

Sugerowane rozwiązanie

Należy przepisać faktoryzację prawostronną, unikając usuwania elementów z początku listy, np. poprzez iterację wskaźnikiem indeksu lub z użyciem collections.deque, analogicznie do zmian w un_chomsky_normal_form. W ramach ochrony wielowarstwowej warto ograniczyć dopuszczalną liczbę węzłów potomnych. Do czasu instalacji poprawki zaleca się limitowanie szerokości drzew oraz uruchamianie transformacji w izolowanym procesie z limitem czasu lub CPU.

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

Status naprawy (2026-09-28)

PR: #3909 "Fix quadratic DoS in Tree.chomsky_normal_form right-factor binarization (GHSA-r53h-rw34-8h97)", scalony 2026-09-23, commit scalający 2f53e20ce w gałęzi develop.

Commity naprawiające: 457ebe349 (liniowe przetwarzanie początku listy w chomsky_normal_form) oraz 677857dca (odrzucanie binaryzacji przekraczającej MAX_TREE_DEPTH). Dodatkowy PR #3917 (scalenie 9ba132e43, commit f0686dea6) wprowadza jawną strukturę stosu przy porównywaniu i konwersji Tree, zapewniając poprawne działanie testów głębokich drzew w Pythonie 3.10 i 3.11.

Test sprawdzający: nltk/test/unit/security_probes/ghsa_r53h_rw34_8h97.py; wynik na develop 2fa3f48fe: FIXED (chomsky_normal_form skaluje się jako 5.1x dla danych wejściowych 4x).

Co trzeba zrobić

Zaktualizuj bibliotekę NLTK do wersji 3.10.4 lub nowszej. Poprawka została wprowadzona w commitach 457ebe349 i 677857dca w ramach PR #3909 (commit scalający 2f53e20ce w gałęzi develop) oraz powiązanym PR #3917.

W ramach obejścia problemu należy ograniczyć dopuszczalną szerokość drzew oraz wykonywać transformację z limitem czasu lub CPU w odizolowanym procesie roboczym.

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-r53h-rw34-8h97 - 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 (DoS) przez kwadratowe zużycie procesora w Tree.chomsky_normal_form ten wpis
    Wysoka · 7.5 CVE-2026-126298 < 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.