CVE-2026-12876: 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 context-free grammar or input obtained from an untrusted source. The impact is limited to availability of the affected process; the provided data does not indicate confidentiality or integrity impact.
What does an attacker need to trigger the issue?
An attacker needs to cause parsing of a crafted grammar or input. A small grammar and a short input can trigger unbounded CPU consumption or Python recursion-stack exhaustion; the examples use 24 tokens.
Are all NLTK parsing configurations affected by default?
The issue is specifically described for RecursiveDescentParser and SteppingRecursiveDescentParser. The data does not establish that other NLTK parsers or default application configurations are affected.
What can be done if updating is not immediately possible?
Do not parse untrusted grammars or inputs with the affected parsers. Where parsing untrusted data cannot be avoided, isolate the parsing process and enforce execution time and resource limits to prevent a single parse from indefinitely pinning the application process.