همهٔ گزارش‌ها
متوسط

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

متن اصلی

نسخه‌های متأثر

بازه‌ها نیاز به بررسی دارند.

PyPInltk
نسخه‌های متأثر
<= 3.10.2
نسخهٔ اصلاح‌شده
3.10.3
PyPInltk
نسخه‌های متأثر
<3.10.3
نسخهٔ اصلاح‌شده
3.10.3
نسخه‌های متأثر
نامشخص
نسخهٔ اصلاح‌شده
اعلام نشده
نسخه‌های متأثر
نامشخص
نسخهٔ اصلاح‌شده
اعلام نشده
نسخه‌های متأثر
نامشخص
نسخهٔ اصلاح‌شده
اعلام نشده
نسخه‌های متأثر
نامشخص
نسخهٔ اصلاح‌شده
اعلام نشده
نسخه‌های متأثر
نامشخص
نسخهٔ اصلاح‌شده
اعلام نشده
نسخه‌های متأثر
نامشخص
نسخهٔ اصلاح‌شده
اعلام نشده
نسخه‌های متأثر
نامشخص
نسخهٔ اصلاح‌شده
اعلام نشده

بهره‌برداری

CVE-2026-81722

احتمال بهره‌برداری در ۳۰ روز آینده: 0.52%

FIRST EPSS · ۱۴۰۵/۰۸/۲۸

شرح آسیب‌پذیری

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

پیوندها