NLTK: Uncontrolled resource consumption in RecursiveDescentParser via ambiguous or left-recursive grammars
위협 신호 · CVSS · EPSS · KEV
이론적 심각도 점수
예측 데이터 없음
실측 악용 기록 없음
계획된 패치 주기 내 조치(60일 이내)
CVSS 벡터 · 메트릭
CVSS 벡터 정보 없음
상세 설명
nltk.parse.RecursiveDescentParser (and SteppingRecursiveDescentParser) enumerate parses top-down with no bound on the number of recursive steps. A small, crafted context-free grammar makes a short input consume unbounded CPU (and/or exhaust the Python recursion stack), pinning a process indefinitely — a denial of service.
Proof of concept
Both of the following hang on a 24-token input (killed after 8s; growth is super-linear in input length), on NLTK develop:
1from nltk import CFG 2from nltk.parse import RecursiveDescentParser 3 4# (a) left recursion -> unbounded recursion 5g = CFG.fromstring("S -> S S | 'a'") 6list(RecursiveDescentParser(g).parse(["a"] * 24)) # hangs 7 8# (b) ambiguous grammar -> exponential number of parses 9g = CFG.fromstring("S -> 'a' S | 'a' S S | 'a'")10list(RecursiveDescentParser(g).parse(["a"] * 24)) # hangsImpact
An application that runs RecursiveDescentParser on a grammar (or an input) drawn from an untrusted source can be driven into an unbounded CPU / stack-exhaustion loop by a tiny payload. No confidentiality or integrity impact; single-process availability only.
Sibling
The RegexpTokenizer ReDoS reported alongside this (CVE-2026-12875) is a different class (caller-supplied regex) and is addressed under GHSA-w3v8-gmh9-3wv7.
AI 심층 분석
공격 시나리오 · 재현 가능한 PoC 페이로드 · 즉시 적용 가능한 차단 패치를 한 번에 받아 보세요. 보안 운영팀이 그대로 점검·티켓팅에 쓸 수 있는 형태로 정리해 드립니다.