Resource exhaustion in Natural Language Toolkit - #VU159487
Published: November 5, 2026
Vulnerability details
The vulnerability allows an attacker to cause unbounded CPU consumption and denial of service in Natural Language Toolkit applications that invoke SteppingRecursiveDescentParser.parse() on attacker-influenced grammars and token sequences. A single crafted parse can monopolize a CPU core indefinitely, and repeated requests can exhaust a bounded worker pool, preventing legitimate users from receiving service.
The vulnerability exists due to an unbounded top-down search over ambiguous or self-embedding context-free grammars without a wall-clock or step limit. A remote attacker can influence the grammar and supply a short token sequence to an exposed application that invokes this parser, causing it to enumerate an exponentially growing derivation space. The subclass overrides parse() and _parse(): parse() initializes the parser and repeatedly calls step(), while the _parse() override captures state and returns a sentinel instead of entering the guarded base implementation. Consequently, this path neither arms nor checks the inherited deadline or time limit, and the constructor exposes no max_time parameter. The search has no effective memoization: its tried-expansion and tried-match records deduplicate only identical productions at identical full partial-tree states, leaving the combinatorial enumeration intact.
The affected component is nltk.parse.recursivedescent.SteppingRecursiveDescentParser in nltk/parse/recursivedescent.py, also publicly exported through nltk.parse. An example grammar is S → 'a' S S | 'a', paired with 17 copies of the token 'a'; its derivation space grows on the order of the Catalan numbers. The stepping loop uses an explicit history stack, so this failure is CPU exhaustion rather than an early RecursionError. Exploitation requires an application to use this particular parser with an attacker-influenced grammar and input; its primary use for debugging, interactive stepping, and a GUI narrows practical exposure. In an exposed deployment accepting such requests, no authentication, privileges, or user interaction is required.