CVE-2026-126303: Uncontrolled Resource Consumption in NLTK SteppingRecursiveDescentParser

The Natural Language Toolkit (nltk) is a widely deployed Python library used for symbolic and statistical natural language processing (NLP). Within its parsing package (nltk.parse), NLTK provides multiple implementations for generating syntactic parse trees from input token sequences based on formal Context-Free Grammars (CFGs). One such implementation is the recursive descent parser module (nltk.parse.recursivedescent), which builds parse trees from the top down by recursively expanding non-terminal grammar symbols and matching terminal symbols against input tokens.

In versions of NLTK prior to 3.10.4, the SteppingRecursiveDescentParser subclass contains an uncontrolled resource consumption flaw classified under CWE-400 (Uncontrolled Resource Consumption), with contributing algorithmic mechanics mapped to CWE-407 (Inefficient Algorithmic Complexity) and CWE-674 (Uncontrolled Recursion). While the parent class RecursiveDescentParser incorporates a configurable wall-clock timeout mechanism (_max_time) to prevent infinite tree expansion, SteppingRecursiveDescentParser overrides both the initializer and the primary parse() execution loop without preserving or evaluating this deadline.

When an application exposes SteppingRecursiveDescentParser.parse() to untrusted grammar specifications or pathological token sequences under an ambiguous or left-recursive grammar, the parser enters a non-terminating search loop. Because this loop runs synchronously within the calling Python thread, it permanently consumes 100% of a CPU core and holds the Python Global Interpreter Lock (GIL) during bytecode execution. In multi-worker web applications or API backends, repeated requests quickly exhaust all available worker processes, resulting in a complete denial of service.

To understand the root cause of CVE-2026-126303, it is necessary to examine the operational limitations of top-down recursive descent parsing alongside the class hierarchy in nltk/parse/recursivedescent.py. A recursive descent parser operates by maintaining a frontier of unexpanded non-terminal symbols and unconsumed input tokens. At each step, if the leading item on the frontier is a non-terminal symbol, the parser selects a matching production rule from the grammar and replaces the non-terminal with the right-hand side of that production.

Top-down recursive descent parsers are fundamentally incompatible with left-recursive grammars—grammars containing rules of the form $A \rightarrow A \alpha$ (direct left recursion) or $A \rightarrow B \alpha$ where $B \Rightarrow^* A \beta$ (indirect left recursion). When encountering a left-recursive rule, a naive top-down parser continuously expands the leftmost non-terminal $A$ without ever consuming a terminal token from the input list. Without cycle detection, depth limits, or execution deadlines, this expansion proceeds until memory is exhausted or the process is terminated externally.

In the base class RecursiveDescentParser, NLTK mitigates this inherent algorithmic limitation by accepting a max_time parameter (defaulting to DEFAULT_MAX_TIME) in __init__() and checking time.perf_counter() within its internal recursive helper _parse(). However, SteppingRecursiveDescentParser was designed to allow iterative, step-by-step inspection of the parsing state via a step() method and an explicit self._frontier stack rather than Python call-stack recursion.

Two specific implementation errors in SteppingRecursiveDescentParser introduced the vulnerability:

1. Omission of max_time in Initialization: The subclass defined def __init__(self, grammar, trace=0): and called super().__init__(grammar, trace) without exposing or forwarding the max_time parameter.
2. Unbounded Iterative Stepping Loop: The subclass overrode parse(self, tokens) to execute while self.step() is not None: pass. Because self.step() manipulates heap-allocated tree structures and backtracking states rather than invoking the base _parse() method, the base class's timeout checks were completely bypassed. Furthermore, because state is maintained on heap lists (self._frontier, self._tried, self._backtrack) rather than the Python call stack, Python's built-in sys.getrecursionlimit() does not trigger a RecursionError cleanly before substantial CPU time is expended.

The vulnerability was remediated in commit e20c40e26ec9306de885703f6e53250695f1f49b (merged via Pull Request #3895) by modifying nltk/parse/recursivedescent.py. In the vulnerable implementation prior to version 3.10.4, SteppingRecursiveDescentParser was implemented as follows:

class SteppingRecursiveDescentParser(RecursiveDescentParser):
    def __init__(self, grammar, trace=0):
        # VULNERABLE: Does not expose max_time parameter, though super() defaults it
        super().__init__(grammar, trace)
        self._rtext = None
        self._tree = None
        self._frontier = [()]
        self._tried = []
        self._backtrack = []
        self._parses = []
 
    def parse(self, tokens):
        tokens = list(tokens)
        self.initialize(tokens)
        # VULNERABLE: Unbounded while loop calling self.step()
        # Bypasses RecursiveDescentParser._parse() deadline checks entirely
        while self.step() is not None:
            pass
        return self.parses()

The patch modifies both __init__() and parse() to enforce a monotonic wall-clock deadline using time.perf_counter(). The diff from commit e20c40e26ec9306de885703f6e53250695f1f49b demonstrates the exact changes applied:

diff --git a/nltk/parse/recursivedescent.py b/nltk/parse/recursivedescent.py
index 19eaaf6e19..08e9239bee 100644
--- a/nltk/parse/recursivedescent.py
+++ b/nltk/parse/recursivedescent.py
@@ -407,8 +407,8 @@ class SteppingRecursiveDescentParser(RecursiveDescentParser):
     :see: ``nltk.grammar``
     """
 
-    def __init__(self, grammar, trace=0):
-        super().__init__(grammar, trace)
+    def __init__(self, grammar, trace=0, max_time=DEFAULT_MAX_TIME):
+        super().__init__(grammar, trace, max_time)
         self._rtext = None
         self._tree = None
         self._frontier = [()]
@@ -428,8 +428,19 @@ def _freeze(self, tree):
     def parse(self, tokens):
         tokens = list(tokens)
         self.initialize(tokens)
+        # step() bypasses the base _parse deadline, so bound the stepping loop
+        # directly: a left-recursive or ambiguous grammar loops unbounded
+        # otherwise (CWE-407/674). max_time=None disables the bound.
+        deadline = None
+        if self._max_time is not None:
+            deadline = time.perf_counter() + self._max_time
         while self.step() is not None:
-            pass
+            if deadline is not None and time.perf_counter() > deadline:
+                raise TimeoutError(
+                    f"SteppingRecursiveDescentParser exceeded its {self._max_time}s "
+                    "time limit; the grammar may be ambiguous or left-recursive. "
+                    "Pass max_time=None to disable the limit."
+                )
         return self.parses()
 
     def initialize(self, tokens):

> [!NOTE] > Fix Completeness Assessment: The patch effectively bounds the parse() method by checking time.perf_counter() > deadline after every single step of the state machine. Because each invocation of self.step() performs a constant or small linear amount of work (expanding a single production, matching a single terminal, or popping a single state from self._backtrack), checking the timer between self.step() iterations guarantees prompt termination when parse() is called.

However, security engineers should note two edge cases regarding API usage:

1. If a developer explicitly passes max_time=None during instantiation, the deadline check is disabled, restoring the unbounded behavior.
2. If an application does not call parser.parse(tokens) but instead implements its own external loop calling parser.step(), parser.expand(), or parser.backtrack() directly, self.step() itself does not check self._max_time. Callers driving step() manually must implement their own iteration or time bounds.

Exploiting CVE-2026-126303 requires an attacker to trigger SteppingRecursiveDescentParser.parse() under conditions where the parser explores an infinite or exponentially large search space. This occurs in two primary application scenarios:

1. User-Supplied Grammars: Educational platforms, linguistic sandboxes, or rule-engine services that allow users to submit custom CFG specifications (e.g., via nltk.CFG.fromstring()) and test them against sample sentences.
2. Fixed Ambiguous Grammars with Crafted Input Tokens: If a server uses a static grammar that contains highly ambiguous or cyclic production rules (such as $S \rightarrow S\ S$ or indirect cycles), an attacker only needs to supply a moderately long sequence of valid tokens to trigger catastrophic backtracking within self.step().

No authentication or special privileges are required at the library level. Once the malicious grammar or token sequence reaches SteppingRecursiveDescentParser.parse(), the stepping loop begins expanding self._frontier and recording backtracking states in self._backtrack without progressing through the input tokens.

The following proof-of-concept script demonstrates the vulnerability using a minimal direct left-recursive grammar ($S \rightarrow S\ \text{'a'} \mid \text{'a'}$). On NLTK versions prior to 3.10.4, executing parser.parse(tokens) hangs the Python interpreter indefinitely while consuming 100% CPU on the executing core. On NLTK 3.10.4 and later, the parser enforces max_time and raises a TimeoutError.

"""
Proof of Concept for CVE-2026-126303 (GHSA-8fx7-8jr8-84rv)
Target: nltk < 3.10.4 (nltk.parse.recursivedescent.SteppingRecursiveDescentParser)
"""
 
import time
from nltk import CFG
from nltk.parse.recursivedescent import SteppingRecursiveDescentParser
 
# Define a direct left-recursive Context-Free Grammar
grammar_spec = """
S -> S 'a'
S -> 'a'
"""
 
grammar = CFG.fromstring(grammar_spec)
tokens = ["a", "a", "a", "a"]
 
# Instantiate the parser.
# In NLTK >= 3.10.4, max_time is supported and defaults to DEFAULT_MAX_TIME.
# Here we explicitly set max_time=1 for rapid verification on patched versions.
try:
    parser = SteppingRecursiveDescentParser(grammar, max_time=1)
except TypeError:
    # NLTK < 3.10.4 raises TypeError: __init__() got an unexpected keyword argument 'max_time'
    print("[-] Vulnerable NLTK version detected (< 3.10.4). Initializing without max_time...")
    parser = SteppingRecursiveDescentParser(grammar)
 
print("[*] Invoking parser.parse(tokens)...")
start_time = time.perf_counter()
 
try:
    # On vulnerable versions, this call never returns or hits a late RecursionError
    # inside deep nltk.tree.Tree copy operations after prolonged CPU exhaustion.
    trees = list(parser.parse(tokens))
    print(f"[+] Parse completed: {trees}")
except TimeoutError as exc:
    elapsed = time.perf_counter() - start_time
    print(f"[+] Patched behavior confirmed: TimeoutError raised after {elapsed:.2f}s")
    print(f"    Message: {exc}")

The primary security impact of CVE-2026-126303 is a high-severity Denial of Service (DoS) affecting system availability. Under CVSS v4.0, the vulnerability is scored at 8.7 (High) with the vector CVSS:4.0/AV:N/AC:L/AT:N/PR:N/UI:N/VC:N/VI:N/VA:H/SC:N/SI:N/SA:N. Because the vulnerability does not allow memory corruption or unauthorized data access, Confidentiality (VC) and Integrity (VI) impacts are rated as None (N), while Availability (VA) is rated as High (H).

In Python production environments, CPU-bound infinite loops present a severe operational hazard due to the architecture of Python web servers and task queues:

• Thread Pool Starvation & GIL Contention: In threaded WSGI/ASGI servers (or asyncio event loops running synchronous calls in a thread pool executor), a single stuck thread executing Python bytecode in while self.step() is not None: continuously acquires and holds the Python Global Interpreter Lock (GIL) until its switch interval expires, degrading performance across all other threads in the same process.
• Process Worker Exhaustion: In pre-fork process models (such as Gunicorn sync workers or uWSGI processes), each unauthenticated request triggering SteppingRecursiveDescentParser.parse() permanently locks one worker process until the master process's external worker timeout (if configured) kills and restarts the worker. Sending a small number of concurrent requests equal to the worker count renders the entire service unresponsive.
• Memory Growth: As the parser steps through left-recursive expansions, the self._tree structure grows deeper and snapshots are appended to self._backtrack and self._tried, causing steady heap memory consumption alongside CPU starvation.

Current threat intelligence indicates an EPSS score of 0.00488 (approximately 0.49%, placing it in the 42.56th percentile), and the vulnerability is not listed in the CISA Known Exploited Vulnerabilities (KEV) catalog. While public proof-of-concept code exists within the NLTK regression test suite and security advisories, no automated mass exploitation has been observed in the wild.

The definitive remediation for CVE-2026-126303 is to upgrade the nltk package to version 3.10.4 or later. Version 3.10.4 enforces DEFAULT_MAX_TIME across SteppingRecursiveDescentParser.parse() and raises a TimeoutError if parsing does not conclude within the configured threshold.

pip install --upgrade "nltk>=3.10.4"

After upgrading, verify that application code catches TimeoutError (a built-in subclass of OSError in Python 3) when invoking parser.parse() so that worker processes can return a clean HTTP 400/422 or 504 response rather than crashing with an unhandled exception:

from nltk.parse.recursivedescent import SteppingRecursiveDescentParser
 
parser = SteppingRecursiveDescentParser(grammar, max_time=2.0)
try:
    result_trees = list(parser.parse(tokens))
except TimeoutError:
    # Handle pathological grammar or input gracefully
    result_trees = []

> [!NOTE] > Architectural Workarounds: If immediate patching to nltk>=3.10.4 is blocked by dependency constraints, development teams should apply the following mitigations:

1. Replace Recursive Descent with Chart Parsing: SteppingRecursiveDescentParser is primarily intended for pedagogical visualization of top-down parsing steps. Production NLP pipelines parsing general Context-Free Grammars should use nltk.parse.ChartParser or nltk.parse.EarleyChartParser. Dynamic programming chart parsers handle left-recursive and ambiguous grammars in $O(n^3)$ time without entering infinite recursion.
2. Subprocess Isolation with Hard Timeouts: If SteppingRecursiveDescentParser must be used on untrusted inputs in an older NLTK release, execute the parsing routine inside an isolated child process using multiprocessing.Process or concurrent.futures.ProcessPoolExecutor with a strict timeout, terminating the process via SIGKILL if it exceeds the deadline.