GHSA-ff5c-cp5c-9wjf: Pip/nltk vulnerability
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:
python from nltk import CFG from nltk.parse import RecursiveDescentParser
(a) left recursion -> unbounded recursion g = CFG.fromstring("S -> S S | 'a'") list(RecursiveDescentParser(g).parse(["a"] 24)) # hangs
(b) ambiguous grammar -> exponential number of parses g = CFG.fromstring("S -> 'a' S | 'a' S S | 'a'") list(RecursiveDescentParser(g).parse(["a"] 24)) # hangs
Impact
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.
Affected Software
Remediation
Recommended actions to resolve this vulnerability, in priority order.
- Upgrade
Upgrade
pip/nltkto a version that resolves this vulnerability.Fixed in 3.10.3
Event History
Frequently Asked Questions
Which applications are realistically exposed to this denial of service?
Applications are exposed when they run RecursiveDescentParser or SteppingRecursiveDescentParser using a grammar or input obtained from an untrusted source. The impact is limited to availability of the affected process; no confidentiality or integrity impact is described.
What does an attacker need to trigger the issue?
An attacker needs to supply a crafted context-free grammar or input that causes unbounded recursive parsing or an exponential number of parses. The provided examples use a 24-token input with either left-recursive or highly ambiguous grammar rules.
What can happen if the parser is exploited?
The parser can consume unbounded CPU and pin the process indefinitely, or exhaust the Python recursion stack. This is a single-process denial of service.