CVE-2026-12876: NLTK: Uncontrolled resource consumption in RecursiveDescentParser via ambiguous or left-recursive grammars
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;
Published Sep 2, 2026
Affected packages
nltk
- Ecosystem
- PyPI
- Affected
- <= 3.10.2
- Fixed in
- 3.10.3
- Check
pip show nltk
Advisory details
From the GitHub Advisory Database (CC BY 4.0).
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:
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)) # 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.
References
How this page is made: the data panel comes from the GitHub Advisory Database, CISA’s KEV catalog, the NVD and FIRST EPSS, and updates twice a day. No analysis has been written for this entry yet. Methodology
More PyPI vulnerabilities
All PyPI entriesCVE-2026-128135
NLTK: ZIP package extraction follows in-root hardlinks and overwrites files outside the NLTK data root
high7.1Nov 19, 2026CVE-2026-128136
NLTK: AllowlistUnpickler does not deny numpy submodule-local file-I/O sinks
medium6.1Nov 19, 2026CVE-2026-128137
NLTK corpus-reader view methods bypass the scoped root sandbox via intermediate-directory symlinks
medium5.5Nov 19, 2026CVE-2026-128138
NLTK incomplete fix: additional JVM/JAR sandbox bypass through unvalidated launcher tokens in java() command arguments
critical9.8Nov 19, 2026CVE-2026-128139
NLTK: XMLCorpusView comment and CDATA parsing permits quadratic CPU denial of service
high7.5Nov 19, 2026CVE-2026-128140
NLTK: Downloader cyclic collection indices cause an infinite closure walk
medium6.5Nov 19, 2026
