{"id":"GHSA-ww6m-cw3f-q94g","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).\n\n## Root cause\n\n`_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:\n\n```python\nwhile i \u003e 0 and word[i] == 'y':\n    negate = not negate\n    i -= 1\n```\n\n`_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.\n\n## Proof of concept\n\nMeasured (Python 3.13): `stem('y'*5000 + 'ness')` = 2.6s, `stem('y'*10000 + 'ness')` = 11.3s (2x input -\u003e ~4.3x time = quadratic), `stem('y'*20000 + 'ness')` \u003e 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.\n\n```python\nfrom nltk.stem import PorterStemmer\nPorterStemmer().stem('y' * 20000 + 'ness')   # \u003e20s of CPU\n```\n\n## Impact\n\nStemming 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.\n\n## Fix direction\n\nClassify 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).","aliases":["CVE-2026-81722","PYSEC-2026-3738"],"modified":"2026-09-10T03:50:54.572733114Z","published":"2026-09-02T14:36:15Z","database_specific":{"severity":"MODERATE","github_reviewed":true,"github_reviewed_at":"2026-09-02T14:36:15Z","nvd_published_at":null,"cwe_ids":["CWE-407"]},"references":[{"type":"WEB","url":"https://github.com/nltk/nltk/security/advisories/GHSA-ww6m-cw3f-q94g"},{"type":"ADVISORY","url":"https://nvd.nist.gov/vuln/detail/CVE-2026-81722"},{"type":"WEB","url":"https://github.com/nltk/nltk/commit/7808692d451b962711005d954859bb83aabcf8fa"},{"type":"PACKAGE","url":"https://github.com/nltk/nltk"},{"type":"WEB","url":"https://github.com/nltk/nltk/releases/tag/v3.10.3"},{"type":"WEB","url":"https://github.com/pypa/advisory-database/tree/main/vulns/nltk/PYSEC-2026-3738.yaml"},{"type":"WEB","url":"https://www.vulncheck.com/advisories/nltk-porterstemmer-before-3.10.3-quadratic-time-dos"}],"affected":[{"package":{"name":"nltk","ecosystem":"PyPI","purl":"pkg:pypi/nltk"},"ranges":[{"type":"ECOSYSTEM","events":[{"introduced":"0"},{"fixed":"3.10.3"}]}],"versions":["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","2.0.1","2.0.1rc1","2.0.1rc2-git","2.0.1rc3","2.0.1rc4","2.0.2","2.0.3","2.0.4","2.0.5","2.0b4","2.0b5","2.0b6","2.0b7","2.0b8","2.0b9","3.0.0","3.0.0b1","3.0.0b2","3.0.1","3.0.2","3.0.3","3.0.4","3.0.5","3.1","3.10.0","3.10.1","3.10.2","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.5","3.5b1","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.9","3.9.1","3.9.2","3.9.3","3.9.4","3.9b1"],"database_specific":{"last_known_affected_version_range":"\u003c= 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"}}],"schema_version":"1.9.0","severity":[{"type":"CVSS_V4","score":"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"}]}