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:
```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.
Fixed in Linux distributions
Distributions backport fixes, so the version that fixes this vulnerability differs per release — upgrade to at least the version shown. From the distributions' security trackers and advisories.
Debian
Security tracker ↗| Release | Package | Fixed in | Advisory |
|---|---|---|---|
| Debian 14 | nltk | No fix yet | — |
| Debian 13 | nltk | No fix yet | — |
| Debian 12 | nltk | No fix yet | — |
Ubuntu
Security tracker ↗| Release | Package | Fixed in | Advisory |
|---|---|---|---|
| Ubuntu 26.10 | nltk | No fix yet | — |
Show 7 more (older releases, extended support, other products)Fewer releases
| Release | Package | Fixed in | Advisory |
|---|---|---|---|
| Ubuntu Pro 26.04 LTS | nltk | No fix yet | — |
| Ubuntu Pro 24.04 LTS | nltk | No fix yet | — |
| Ubuntu Pro 22.04 LTS | nltk | No fix yet | — |
| Ubuntu Pro 20.04 LTS | nltk | No fix yet | — |
| Ubuntu Pro 18.04 LTS | nltk | No fix yet | — |
| Ubuntu Pro 16.04 LTS | nltk | No fix yet | — |
| Ubuntu Pro 14.04 LTS | nltk | No fix yet | — |
Wolfi
| Release | Package | Fixed in | Advisory |
|---|---|---|---|
| Wolfi rolling | open-webui | 0.11.3-r1 | — |
Affected packages
| Ecosystem | Package | Affected | Fixed | Record |
|---|---|---|---|---|
| PyPI | nltk | < 3.10.3 | 3.10.3 | GHSA-ff5c-cp5c-9wjf |