NLTK: Quadratic-time DoS in PorterStemmer via long runs of 'y'
nltk.stem.PorterStemmer.stem() -- a ubiquitous public API applied to arbitrary, often untrusted, tokens -- runs in O(n^2) time on a token containing a long run of the letter 'y', letting a single ~20-50 KB token pin a CPU core (CWE-407).
Root cause
_is_consonant(word, i) was made iterative (commit for #3633, GHSA/CWE-674) to fix an earlier unbounded-recursion RecursionError on 'y'*10000. The iterative form walks backward over the whole run of 'y's on every call:
while i > 0 and word[i] == 'y':
negate = not negate
i -= 1_measure() then calls _is_consonant(stem, i) once for every position i of the stem. For a run of n 'y's that is sum_{i} O(i) = O(n^2). The recursion fix therefore traded a CWE-674 RecursionError for a CWE-407 quadratic-time DoS.
Proof of concept
Measured (Python 3.13): stem('y'*5000 + 'ness') = 2.6s, stem('y'*10000 + 'ness') = 11.3s (2x input -> ~4.3x time = quadratic), stem('y'*20000 + 'ness') > 20s. A pure run of 'y' with no matching suffix is fast because the stemmer rules that call _measure do not fire; a real suffix such as 'ness' triggers _measure on the long stem.
from nltk.stem import PorterStemmer
PorterStemmer().stem('y' * 20000 + 'ness') # >20s of CPUImpact
Stemming is routinely applied to untrusted text (search, indexing, NLP pipelines). A single unbroken ~20-50 KB token of 'y' characters (no whitespace, so it survives tokenization) causes multi-second-to-minutes CPU consumption per request. No confidentiality/integrity impact; single-process availability only.
Fix direction
Classify each character's consonant/vowel status in a single left-to-right O(n) pass (memoise the 'y' run parity) instead of re-walking the run on every _is_consonant call, so _measure and stemming are linear. This is a sibling of the corpus-reader quadratic advisories GHSA-vp2x-qp44-57v7 and GHSA-8mpw-7fpc-4gqj (CWE-407).
Betroffene Software
Klicken Sie auf eine Technologie, um alle zugehörigen Schwachstellen anzuzeigen.
| Plattform | Paket | Anfällige Versionen | Behoben in |
|---|---|---|---|
| Python (PyPI) | nltk | < 3.10.3 | 3.10.3 |
Verweise
- https://www.vulncheck.com/advisories/nltk-porterstemmer-before-3.10.3-quadratic-time-dos
- https://github.com/nltk/nltk/security/advisories/GHSA-ww6m-cw3f-q94g
- https://nvd.nist.gov/vuln/detail/CVE-2026-81722
- https://github.com/nltk/nltk/commit/7808692d451b962711005d954859bb83aabcf8fa
- https://github.com/nltk/nltk
- https://github.com/nltk/nltk/releases/tag/v3.10.3
- https://github.com/pypa/advisory-database/tree/main/vulns/nltk/PYSEC-2026-3738.yaml
- CVSS-Vektor
CVSS:4.0/AV:N/AC:L/AT:N/PR:N/UI:N/VC:N/VI:N/VA:L/SC:N/SI:N/SA:N- Schwäche (CWE)
CWE-407- Plattform
- Python (PyPI)
- Paket
nltk- Veröffentlicht
- 27.08.2026
- Aktualisiert
- 11.10.2026 15:17
Quellen und Lizenzen
OSV / GitHub Advisory Database - PYSEC-2026-3738 - PyPA Advisory Database; CC BY 4.0
OSV / GitHub Advisory Database - GHSA-ww6m-cw3f-q94g - 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.
- Einträge insgesamt
- 52
- Erste → letzte
- 08.2019 09.2026
- Ohne Fix
- 6
- In Angriffen ausgenutzt
- 0
Verteilung nach Schweregrad
- Kritisch 5
- Hoch 32
- Mittel 13
- Niedrig 2
Veröffentlichungen pro Jahr
- 2019: 1
- 2020: 0
- 2021: 2
- 2022: 1
- 2023: 0
- 2024: 1
- 2025: 0
- 2026: 47
-
NLTK: Quadratic-time DoS in PorterStemmer via long runs of 'y' dieser Eintrag
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.