All reports
Medium

NLTK: Quadratic-time DoS in PorterStemmer via long runs of 'y'

Affected versions

Version ranges need review.

PyPInltk
Affected versions
<= 3.10.2
Fixed version
3.10.3
PyPInltk
Affected versions
<3.10.3
Fixed version
3.10.3
Affected versions
Unknown
Fixed version
Not reported
Affected versions
Unknown
Fixed version
Not reported
Affected versions
Unknown
Fixed version
Not reported
Affected versions
Unknown
Fixed version
Not reported
Affected versions
Unknown
Fixed version
Not reported
Affected versions
Unknown
Fixed version
Not reported

Exploitation

CVE-2026-81722

Probability of exploitation in the next 30 days: 0.52%

FIRST EPSS · 2026-11-21

Description

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

Links