GHSA-ww6m-cw3f-q94g

Suggest an improvement
Source
https://github.com/advisories/GHSA-ww6m-cw3f-q94g
Import Source
https://github.com/github/advisory-database/blob/main/advisories/github-reviewed/2026/09/GHSA-ww6m-cw3f-q94g/GHSA-ww6m-cw3f-q94g.json
JSON Data
https://api.osv.dev/v1/vulns/GHSA-ww6m-cw3f-q94g
Aliases
Downstream
Published
2026-09-02T14:36:15Z
Modified
2026-09-10T03:50:54Z
Severity
  • 6.9 (Medium) CVSS_V4 - 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 CVSS Calculator
Summary
NLTK: Quadratic-time DoS in PorterStemmer via long runs of 'y'
Details

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 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).

Database specific 
{
    "cwe_ids": [
        "CWE-407"
    ],
    "github_reviewed": true,
    "github_reviewed_at": "2026-09-02T14:36:15Z",
    "nvd_published_at": null,
    "severity": "MODERATE"
}
References

Affected packages

PyPI / nltk

Package

Name
nltk
View open source insights on deps.dev
Purl
pkg:pypi/nltk

Affected ranges

Type
ECOSYSTEM
Events
Introduced
0 Unknown introduced version / All previous versions are affected
Fixed
3.10.3

Affected versions

2.*
2.0.1rc2-git
2.0b4
2.0b5
2.0b6
2.0b7
2.0b8
2.0b9
2.0.1rc1
2.0.1rc3
2.0.1rc4
2.0.1
2.0.2
2.0.3
2.0.4
2.0.5
0.*
0.8
0.9
0.9.3
0.9.4
0.9.5
0.9.6
0.9.7
0.9.8
0.9.9
3.*
3.0.0b1
3.0.0b2
3.0.0
3.0.1
3.0.2
3.0.3
3.0.4
3.0.5
3.1
3.2
3.2.1
3.2.2
3.2.3
3.2.4
3.2.5
3.3
3.4
3.4.1
3.4.2
3.4.3
3.4.4
3.4.5
3.5b1
3.5
3.6
3.6.1
3.6.2
3.6.3
3.6.4
3.6.5
3.6.6
3.6.7
3.7
3.8
3.8.1
3.9b1
3.9
3.9.1
3.9.2
3.9.3
3.9.4
3.10.0
3.10.1
3.10.2

Database specific

last_known_affected_version_range 
"<= 3.10.2"
source 
"https://github.com/github/advisory-database/blob/main/advisories/github-reviewed/2026/09/GHSA-ww6m-cw3f-q94g/GHSA-ww6m-cw3f-q94g.json"