Most recent entries from all

BREW-acronym-CVE-2026-12876 — NLTK: Uncontrolled resource consumption in RecursiveDescentParser via ambiguous or left-recursive grammars

2026-10-03T23:15:10.130883+00:00

Affected: Homebrew: acronym

`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.

GHSA-ff5c-cp5c-9wjf — NLTK: Uncontrolled resource consumption in RecursiveDescentParser via ambiguous or left-recursive grammars

2026-10-03T23:15:10.131074+00:00

Affected: PyPI: nltk

## 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

## 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.

PYSEC-2026-3869 — NLTK: Uncontrolled resource consumption in RecursiveDescentParser via ambiguous or left-recursive grammars

2026-10-03T23:15:10.131170+00:00

Affected: PyPI: nltk

## 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

## 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.

UBUNTU-CVE-2026-12876

2026-10-03T23:15:10.131237+00:00

Affected: Ubuntu:Pro:14.04:LTS: nltk, Ubuntu:Pro:16.04:LTS: nltk, Ubuntu:Pro:18.04:LTS: nltk, Ubuntu:Pro:20.04:LTS: nltk, Ubuntu:Pro:22.04:LTS: nltk, Ubuntu:Pro:24.04:LTS: nltk, Ubuntu:Pro:26.04:LTS: nltk

[Unknown description]