NLTK: Uncontrolled resource consumption in RecursiveDescentParser via ambiguous or left-recursive grammars
MediumCVE-2026-12876 · Published Sep 2, 2026 · updated Sep 10, 2026
`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 ...
Affected versions
| Package | Affected | Fixed in |
|---|---|---|
| nltk PyPI | < 3.10.3 | 3.10.3 |
Details and references
`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.
More NLTK advisories
All NLTK| Date | Advisory | Severity | Fixed in |
|---|---|---|---|
| Sep 2 | NLTK: Default ENFORCE=False Disables All pathsec Security Controls HighSep 2 | High | 3.10.0 |
| Sep 2 | NLTK: SSRF Fail-Open in validate_network_url() via DNS Resolution FailureMediumSep 2 | Medium | 3.10.0 |
| Sep 2 | NLTK: Quadratic-time DoS in PorterStemmer via long runs of 'y'MediumSep 2 | Medium | 3.10.3 |
| Sep 2 | NLTK: Downloader.download follows hardlinks and overwrites outside-root filesMedium7.1Sep 2 | Medium7.1 | 3.10.3 |
| Sep 2 | NLTK: Model-artifact APIs bypass pathsec and touch files outside allowed rootsHigh7.0Sep 2 | High7.0 | No fix yet |
| Sep 2 | NLTK: Quadratic CPU Exhaustion in `XMLCorpusView._read_xml_fragment()`Medium3.7Sep 2 | Medium3.7 | 3.10.3 |