Advisory

GHSA-8fx7-8jr8-84rv

Also known as: CVE-2026-126303

Summary

NLTK: Unbounded CPU consumption in SteppingRecursiveDescentParser.parse() with ambiguous or self-embedding grammars

Details

Summary

nltk.parse.recursivedescent.SteppingRecursiveDescentParser.parse() performs an unbounded top-down search over ambiguous or self-embedding context-free grammars with no wall-clock or step limit. An actor who can influence the grammar and supply a short input to a caller that uses this parser can force a single parse() call to pin a CPU core indefinitely, producing a denial of service. The related base class RecursiveDescentParser gained a max_time wall-clock deadline, but the stepping subclass drives its own step loop and never arms or consults that deadline, and its constructor does not accept a max_time parameter, so the guard cannot be enabled on this path.

Root Cause

RecursiveDescentParser bounds its recursive search inside _parse: it arms a wall-clock deadline on the first step and raises TimeoutError once max_time (default 5.0 seconds) is exceeded. SteppingRecursiveDescentParser was designed for interactive single-stepping and overrides both parse() and _parse. Its parse() runs initialize() followed by a while self.step() is not None loop that never enters the guarded base _parse. Its _parse override is a state-capturing stub that records history and returns a sentinel, and it never references the inherited self._parse_deadline or self._max_time. Its __init__ signature omits max_time entirely, so a caller cannot enable or tighten a bound. The security invariant that a single parse must terminate within a bounded time is therefore never enforced on this parser.

Affected component: nltk.parse.recursivedescent.SteppingRecursiveDescentParser
- parse()      nltk/parse/recursivedescent.py:428-433  (drives its own step loop, no bound armed or checked)
- _parse()     nltk/parse/recursivedescent.py:643-668  (stub override; never consults self._parse_deadline / self._max_time)
- __init__()   nltk/parse/recursivedescent.py:410-418  (signature (self, grammar, trace=0); no max_time parameter)
Base guard for comparison: RecursiveDescentParser._parse nltk/parse/recursivedescent.py:141-150

Impact

An actor who controls or influences the grammar passed to SteppingRecursiveDescentParser and can supply a short token sequence to a caller that invokes parse() can cause that call to never return. The top-down search enumerates a derivation space that grows on the order of the Catalan numbers with no memoization of the search and no deadline, so one crafted grammar plus a short input deterministically consumes a CPU core. In a deployment that parses attacker-influenced input on a bounded worker pool, repeated requests exhaust the pool and deny service to legitimate users. No authentication, privilege, or user interaction is required in that worst-credible deployment. Exploitation requires that the target actually use this parser on untrusted input; because the stepping parser is primarily a debugging or interactive-stepping component that backs a GUI, real-world exposure is narrower than for the base parser, though parse() is a supported public method that behaves as a full parser.

Proof of Concept

Requires only the nltk package (3.10.3) and standard library; no data downloads or network access.

Reproduction steps:

  1. Build an ambiguous, self-embedding grammar such as S -> 'a' S S | 'a'.
  2. Confirm the base parser self-terminates: RecursiveDescentParser(g, max_time=2.0).parse(['a']*17) raises TimeoutError at about 2 seconds.
  3. Run the stepping parser on the same grammar and input and observe it never returns.
import time, inspect
from nltk import CFG
from nltk.parse.recursivedescent import RecursiveDescentParser, SteppingRecursiveDescentParser

g = CFG.fromstring("S -> 'a' S S | 'a'")

# Base parser is bounded and self-terminates.
try:
    list(RecursiveDescentParser(g, max_time=2.0).parse(['a'] * 17))
except TimeoutError:
    print("base: TimeoutError (guarded)")

# Stepping subclass cannot be bounded: no max_time parameter.
print("stepping __init__ sig:", inspect.signature(SteppingRecursiveDescentParser.__init__))

# Stepping parser runs unbounded on the same input.
t0 = time.perf_counter()
list(SteppingRecursiveDescentParser(g).parse(['a'] * 17))  # does not return
print("stepping: returned after", time.perf_counter() - t0)
base: TimeoutError (guarded)
stepping __init__ sig: (self, grammar, trace=0)
# stepping len3: 1 parse in 0.001s ; len7: 5 in 0.017s ; len9: 14 in 0.075s ; len11: 42 in 0.36s
# stepping len17: still running past a 10s watchdog, process alive, no RecursionError

Attack Chain

  1. Exposure: A caller uses nltk.parse.SteppingRecursiveDescentParser, a public exported symbol (nltk/parse/__init__.py:97), invoking parse(tokens) on grammar and input influenced by an actor.
  2. Control: The actor influences the grammar (an ambiguous, self-embedding CFG such as S -> 'a' S S | 'a') and supplies a short token list (for example 17 copies of 'a'). Both survive to the parser unchanged.
  3. Path: parse() (recursivedescent.py:428) calls initialize() then loops while self.step() is not None; step() (:479) calls match()/expand() (:552/:512) which call the inherited _match/_expand (:172/:214), which resolve self._parse by MRO to the subclass stub (:643).
  4. Guard: The max_time wall-clock deadline exists only in the base _parse (:141-150) and is never entered on this path; the stub _parse records state and returns without consulting the deadline, and __init__ exposes no max_time to enable a bound.
  5. Primitive: The unbounded top-down search enumerates a Catalan-number-sized derivation space with no memoization and no deadline.
  6. Result: The parse() call never returns and pins a CPU core; repeated calls exhaust a bounded worker pool, denying service.

Bypass Evidence

The prior fix for this class of issue added a max_time wall-clock deadline to the base RecursiveDescentParser._parse (recursivedescent.py:141-150, default 5.0 seconds). This report demonstrates that the fix does not cover the sibling SteppingRecursiveDescentParser entry point, and the maintainers separately hardened other parsers (chart, earley chart, viterbi, shift-reduce, non-projective dependency) with max_time while leaving this subclass unbounded.

Challenges attempted and their outcomes:

  • Hypothesis that the inherited self._max_time value (observed at 5.0) makes the path guarded: refuted; the value is inherited but never read on the stepping path, and the parser runs unbounded despite it being set.
  • Hypothesis that a caller can bound the parser via the constructor: refuted; inspect.signature(SteppingRecursiveDescentParser.__init__) is (self, grammar, trace=0), with no max_time parameter.
  • Hypothesis that the failure is merely an early RecursionError rather than CPU exhaustion: refuted; the step loop is iterative over an explicit history stack, so no exception is raised within a 10 second watchdog, CPU time grows exponentially with input length, and a small negative control input returns in about 0.001 seconds.
  • Hypothesis that the _tried_e/_tried_m records collapse the search: refuted; those records are keyed by the frozen full partial tree, so they deduplicate only identical productions at identical states and do not prevent the exponential enumeration.

Severity

High Basis: The source's own band: HIGH

Dates

Published
2026-11-13 21:02 UTC
Modified
2026-11-18 00:45 UTC

Affected packages and fixes

nltk

PyPI · All systems

Affected

  • introduced 0, fixed 3.10.4 (ecosystem)

Fixed versions

3.10.4

Fix

  • Fixed version 3.10.4
    pip install --upgrade nltk==3.10.4

Fix commands are the export's own generic commands. Ojuju never runs them. Check them against your setup first.

Check your own computer: guard packages check

View this record on OSV.dev

Source

Source: GitHub Advisory Database (reviewed advisories) · CC BY 4.0

Sources & licences