NLTK: Odmowa usługi (DoS) przez kwadratowe zużycie procesora w Tree.chomsky_normal_form
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.
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
- Ekspozycja: Aplikacja przetwarza ciąg treebank kontrolowany przez atakującego za pomocą publicznej funkcji
Tree.fromstringi normalizuje go przezTree.chomsky_normal_form(). - Kontrola: Atakujący kontroluje liczbę potomków danego węzła (szerokie, płaskie drzewo, np.
(S (A a)(A a)...(A a))); wfromstringani w transformacji nie ma ograniczenia na liczbę potomków. - Ścieżka:
Tree.chomsky_normal_formprzekazuje wywołanie donltk.tree.transforms.chomsky_normal_formz domyślnym parametremfactor="right". - Zabezpieczenia: Brak. W pętli nie ma ograniczenia szerokości, a timeout regex nie obejmuje operacji na liście w Pythonie.
- 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. - 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: nltkConfirmed affected range: <= 3.10.3Latest 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.
| Platforma | Paczka | Podatne wersje | Poprawka w wersji |
|---|---|---|---|
| Python (PyPI) | nltk | < 3.10.4 | 3.10.4 |
Odnośniki
- https://github.com/nltk/nltk/security/advisories/GHSA-r53h-rw34-8h97
- https://nvd.nist.gov/vuln/detail/CVE-2026-126298
- https://github.com/nltk/nltk/pull/3909
- https://github.com/nltk/nltk/commit/457ebe349f8dd8080224f76a64aff806dd437057
- https://github.com/nltk/nltk/commit/677857dcafd84e4591865d976b562a27dfde566e
- https://github.com/nltk/nltk
- https://github.com/nltk/nltk/releases/tag/v3.10.4
- https://www.vulncheck.com/advisories/nltk-before-3.10.4-quadratic-cpu-denial-of-service-via-tree-chomsky-normal-form
- 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ć.
- 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
- 2019: 1
- 2020: 0
- 2021: 2
- 2022: 1
- 2023: 0
- 2024: 1
- 2025: 0
- 2026: 74
-
NLTK: Odmowa usługi (DoS) przez kwadratowe zużycie procesora w Tree.chomsky_normal_form ten wpis
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.