Advisory details:
github_osv / GHSA-ff5c-cp5c-9wjf
| Advisory ID | github_osv/GHSA-ff5c-cp5c-9wjf |
| Aliases |
CVE-2026-12876
|
| Summary | 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: ```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. |
| Status | Published |
| Exploitability | 0.5 |
| Weighted Severity | 6.2 |
| Risk | 3.1 |
| Affected and Fixed Packages | Package Details |
| Introduced and Fixed Package Commit Patches | Package Commit Patches Details |
| CWE-674 | Uncontrolled Recursion |
| CWE-407 | Inefficient Algorithmic Complexity |
| System | Score | Found at |
|---|---|---|
| cvssv4 | 6.9 | https://github.com/github/advisory-database/blob/main/advisories/github-reviewed/2026/09/GHSA-ff5c-cp5c-9wjf/GHSA-ff5c-cp5c-9wjf.json |
| generic_textual | MODERATE |
No EPSS data available for this advisory.
| Patch URL | |
|---|---|
| There are no known patches. | |
| Attack Vector (AV) | Attack Complexity (AC) | Attack Requirements (AT) | Privileges Required (PR) | User Interaction (UI) | Vulnerable System Impact Confidentiality (VC) | Vulnerable System Impact Integrity (VI) | Vulnerable System Impact Availability (VA) | Subsequent System Impact Confidentiality (SC) | Subsequent System Impact Integrity (SI) | Subsequent System Impact Availability (SA) |
|---|---|---|---|---|---|---|---|---|---|---|
network adjacent local physical |
low high |
none present |
none low high |
none passive active |
high low none |
high low none |
high low none |
high low none |
high low none |
high low none |
There are no SSVC decisions available.