CVE-2026-81722: nltk PorterStemmer before 3.10.3 Quadratic-time DoS
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
isconsonant(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 isconsonant(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 isconsonant 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).
Other sources
nltk PorterStemmer in versions <= 3.10.2 (fixed in 3.10.3) contains an inefficient-algorithmic-complexity denial of service in PorterStemmer.stem(). The isconsonant() helper walks backward over the entire run of trailing 'y' characters on every call, and measure() invokes it for each stem position, causing O(n^2) behavior. A single ~20-50 KB untrusted token consisting of a long run of the letter 'y' followed by a matching suffix (e.g., 'ness') can pin a CPU core for seconds to minutes, causing availability impact.
— MITRE
Affected Software
Remediation
Recommended actions to resolve this vulnerability, in priority order.
- Upgrade
Upgrade
pip/nltkto a version that resolves this vulnerability.Fixed in 3.10.3 - Upgrade
Upgrade
nltk.stem.PorterStemmerto a version that resolves this vulnerability.Fixed in 3.10.3 - Compensating control
Add resource protections around stemming of untrusted input (e.g., enforce a maximum token length and reject/skip tokens longer than the stated ~20–50 KB long 'y' runs) to prevent quadratic-time CPU pinning in PorterStemmer.stem().
Event History
Frequently Asked Questions
Who is realistically exposed to this denial of service?
Applications using nltk PorterStemmer on attacker-controlled or otherwise untrusted tokens are exposed. A single crafted token can consume a CPU core for seconds to minutes.
What input is needed to trigger the issue?
An attacker needs to submit a roughly 20–50 KB token containing a long run of the letter "y" followed by a matching suffix, such as "ness". No authentication or user interaction is required according to the supplied vector.
Are affected versions fixed, and what should be upgraded?
The issue affects nltk PorterStemmer versions 3.10.2 and earlier and is fixed in version 3.10.3. Upgrade to 3.10.3 to remove the inefficient quadratic-time behavior.
What can be done if upgrading is not immediately possible?
Limit the maximum length of untrusted tokens before passing them to PorterStemmer, particularly tokens with long repeated-character runs. This reduces the ability to submit the 20–50 KB crafted inputs described for exploitation.