Kestrel
대시보드로 돌아가기
CVE-2026-81722MEDIUMMITRENVDGHSA대응게시일: 2026. 08. 27.수정일: 2026. 09. 02.

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

위협 신호 · CVSS · EPSS · KEV

정기 패치· 높은 악용 신호 없음
CVSS
medium

이론적 심각도 점수

EPSS
0.4%상위 70.4%

30일 내 악용 확률 예측

KEV
미등재

실측 악용 기록 없음

권장 대응 기한60일 이내CISA SSVC 기준

계획된 패치 주기 내 조치(60일 이내)

외부 노출· KEV 미등재 · 자동화 어려움 · 부분 영향 · 외부 노출

CVSS 벡터 · 메트릭

CVSS 벡터 정보 없음

상세 설명

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:

text
1while i > 0 and word[i] == 'y':
2 negate = not negate
3 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.

text
1from nltk.stem import PorterStemmer
2PorterStemmer().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).

AI 심층 분석

공격 시나리오 · 재현 가능한 PoC 페이로드 · 즉시 적용 가능한 차단 패치를 한 번에 받아 보세요. 보안 운영팀이 그대로 점검·티켓팅에 쓸 수 있는 형태로 정리해 드립니다.