GHSA-ww6m-cw3f-q94g: Pip/nltk vulnerability
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).
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
Event History
Frequently Asked Questions
Who is realistically exposed to this denial-of-service condition?
Applications that pass attacker-controlled or otherwise unbounded tokens to nltk.stem.PorterStemmer.stem() are exposed. A single token in the roughly 20–50 KB range can occupy a CPU core when it has a long run of "y" characters and a suffix that causes the relevant stemming rules to run.
What input is needed to trigger the expensive processing?
The token needs a long sequence of "y" characters followed by a suffix such as "ness". A token made only of "y" characters is reported to be fast because it does not trigger the rules that call _measure().
How can I assess the operational impact in my environment?
Test representative processing with inputs such as "y" repeated 5,000 times followed by "ness". Reported Python 3.13 timings were 2.6 seconds at 5,000 characters and 11.3 seconds at 10,000 characters, consistent with quadratic growth.