Advisory details:
github_osv / GHSA-ww6m-cw3f-q94g
| Advisory ID | github_osv/GHSA-ww6m-cw3f-q94g |
| Aliases |
CVE-2026-81722
|
| Summary | 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: ```python 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. ```python from nltk.stem import PorterStemmer PorterStemmer().stem('y' * 20000 + 'ness') # >20s of CPU ``` ## Impact 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). |
| Status | Published |
| Exploitability | 0.5 |
| Weighted Severity | 6.2 |
| Risk | 3.1 |
| Affected and Fixed Packages | Package Details |
| Introduced and Fixed Package Commit Patches | Package Commit Patches Details |
| System | Score | Found at |
|---|---|---|
| cvssv4 | 6.9 | https://github.com/github/advisory-database/blob/main/advisories/github-reviewed/2026/09/GHSA-ww6m-cw3f-q94g/GHSA-ww6m-cw3f-q94g.json |
| generic_textual | MODERATE |
No EPSS data available for this advisory.
| Patch URL | |
|---|---|
| There are no known patches. | |
| Attack Vector (AV) | Attack Complexity (AC) | Attack Requirements (AT) | Privileges Required (PR) | User Interaction (UI) | Vulnerable System Impact Confidentiality (VC) | Vulnerable System Impact Integrity (VI) | Vulnerable System Impact Availability (VA) | Subsequent System Impact Confidentiality (SC) | Subsequent System Impact Integrity (SI) | Subsequent System Impact Availability (SA) |
|---|---|---|---|---|---|---|---|---|---|---|
network adjacent local physical |
low high |
none present |
none low high |
none passive active |
high low none |
high low none |
high low none |
high low none |
high low none |
high low none |
There are no SSVC decisions available.