CVE-2026-12876: 
Linux Debian vulnerability analysis and mitigation

CVE-2026-12876 is an uncontrolled resource consumption vulnerability in NLTK's RecursiveDescentParser (and SteppingRecursiveDescentParser) that allows a denial-of-service condition via crafted ambiguous or left-recursive context-free grammars. It affects all NLTK versions up to and including 3.10.2, with a fix available in version 3.10.3. The vulnerability was published on August 12, 2026, via coordinated disclosure. Feedly estimates the severity as HIGH, and the GitHub advisory classifies it as Moderate (GitHub Advisory).

The root cause is that nltk.parse.RecursiveDescentParser performs top-down enumeration of parses with no bound on recursive steps, classified under CWE-407 (Inefficient Algorithmic Complexity) and CWE-674 (Uncontrolled Recursion). When supplied with a left-recursive grammar (e.g., S -> S S | 'a'), the parser enters unbounded recursion; with an ambiguous grammar (e.g., S -> 'a' S | 'a' S S | 'a'), it generates an exponential number of parses. A short input of 24 tokens is sufficient to pin the process indefinitely, with growth that is super-linear in input length. A community fix (PR #3649) adds an opt-in max_steps limit but leaves the default behavior unprotected (GitHub Advisory).

Successful exploitation results in unbounded CPU consumption and/or Python recursion stack exhaustion, effectively pinning the affected process indefinitely and causing a denial of service. There is no confidentiality or integrity impact; the effect is limited to single-process availability. Applications that pass untrusted grammars or inputs to RecursiveDescentParser are at risk of complete process unavailability (GitHub Advisory).

A proof-of-concept is publicly available in the GitHub security advisory, demonstrating that a 24-token input with a crafted grammar causes the parser to hang within seconds. Exploitation requires no authentication or special privileges — only the ability to supply a grammar or input to an application using RecursiveDescentParser. There is no current evidence of in-the-wild exploitation, CISA KEV listing, or known threat actor attribution. The CVE was detected by Tenable Nessus plugin 335454 (GitHub Advisory, Tenable).

1. Identify target: Find an application that accepts user-supplied grammars or inputs and passes them to nltk.parse.RecursiveDescentParser or SteppingRecursiveDescentParser running NLTK <= 3.10.2.
2. Craft malicious grammar: Construct a left-recursive grammar (e.g., S -> S S | 'a') or an ambiguous grammar (e.g., S -> 'a' S | 'a' S S | 'a') designed to trigger exponential parse enumeration.
3. Supply short input: Provide a short token sequence (e.g., 24 repetitions of 'a') paired with the crafted grammar to the parser.
4. Trigger DoS: The parser enters unbounded recursion or exponential parse enumeration, consuming all available CPU and/or exhausting the Python call stack, causing the process to hang indefinitely (GitHub Advisory).

• Process: Python process consuming 100% CPU for an extended or indefinite period, associated with NLTK parsing operations.
• Logs: Application logs showing parsing requests that never complete or time out; Python RecursionError stack traces referencing nltk.parse.recursivedescent.
• Application Behavior: Requests to grammar-parsing endpoints that result in no response or connection timeouts, particularly with short inputs.

Upgrade NLTK to version 3.10.3 or later, which is the patched release addressing this vulnerability. As a workaround, avoid passing untrusted grammars or inputs to RecursiveDescentParser; validate and sanitize all grammar inputs before use. The community PR #3649 introduces an opt-in max_steps parameter — enabling this limit provides partial protection even on unpatched versions, though the default remains unprotected (GitHub Advisory).

The vulnerability was disclosed via GitHub's coordinated disclosure process by maintainer alvations on August 12, 2026. The advisory notes a sibling vulnerability (CVE-2026-12875, a RegexpTokenizer ReDoS) reported alongside this issue, suggesting a broader security review of NLTK's parsing components. No significant media coverage or notable external researcher commentary has been identified beyond the advisory itself (GitHub Advisory).