NLTK: denial of service
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...
Affected versions
| Package | Affected | Fixed in |
|---|---|---|
| nltk PyPI | < 3.10.4 | 3.10.4 |
Details and references
## 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. ```text 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. ```python 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("stepp
- CVSS 3.1
- CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H
- Severity from
- GitHub (reviewed advisory)
- Weakness
- CWE-400, CWE-407
- Also known as
- CVE-2026-126303
- github.com/nltk/nltk/security/advisories/GHSA-8fx7-8jr8-84rv
- nvd.nist.gov/vuln/detail/CVE-2026-126303
- github.com/nltk/nltk/pull/3895
- github.com/nltk/nltk/commit/e20c40e26ec9306de885703f6e53250695f1f49b
- github.com/nltk/nltk
- github.com/nltk/nltk/releases/tag/v3.10.4
- www.vulncheck.com/advisories/nltk-before-3.10.4-denial-of-service-via-steppingrecursivedescentparser-parse