CVE-2026-126299VulnerabilityPublished 14 Nov 2026

NLTK: Quadratic-time CPU denial of service

Affects nltkSource GCVE Database

Compare

Authoritative record:CVE-2026-126299· High 8.7

Not known to be exploited · CVSS 8.7 High : upgrade to 3.10.4 soon.

Data as of 14 Nov 2026, 01:02 UTC

CVSS 4.0 base score

8.7High

How severe the flaw is on the 0–10 CVSS scale.

Thin evidence

One scorer or none

CVSS scores by source
CNA (VulnCheck)	CVSS 4.0	8.7
CNA (VulnCheck)	CVSS 3.1	7.5

Patch: Available – fixed in 3.10.4

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

Attack Vector: Network
Attack Complexity: Low
Attack Requirements: None
Privileges Required: None
User Interaction: None
Vulnerable system confidentiality: None
Vulnerable system integrity: None
Vulnerable system availability: High
Subsequent system confidentiality: None
Subsequent system integrity: None
Subsequent system availability: None

Bold values are the worst case: easiest to exploit or largest impact.

Attack Vector: Network: The vulnerable system is bound to the network stack and the set of possible attackers extends beyond the other options listed below, up to and including the entire Internet. Such a vulnerability is often termed “remotely exploitable” and can be thought of as an attack being exploitable at the protocol level one or more network hops away (e.g., across one or more routers).
Attack Complexity: Low: The attacker must take no measurable action to exploit the vulnerability. The attack requires no target-specific circumvention to exploit the vulnerability. An attacker can expect repeatable success against the vulnerable system.
Attack Requirements: None: The successful attack does not depend on the deployment and execution conditions of the vulnerable system. The attacker can expect to be able to reach the vulnerability and execute the exploit under all or most instances of the vulnerability.
Privileges Required: None: The attacker is unauthorized prior to attack, and therefore does not require any access to settings or files of the vulnerable system to carry out an attack.
User Interaction: None: The vulnerable system can be exploited without interaction from any human user, other than the attacker.
Vulnerable system confidentiality: None: There is no loss of confidentiality within the Vulnerable System.
Vulnerable system integrity: None: There is no loss of integrity within the Vulnerable System.
Vulnerable system availability: High: There is a total loss of availability, resulting in the attacker being able to fully deny access to resources in the Vulnerable System; this loss is either sustained (while the attacker continues to deliver the attack) or persistent (the condition persists even after the attack has completed). Alternatively, the attacker has the ability to deny some availability, but the loss of availability presents a direct, serious consequence to the Vulnerable System (e.g., the attacker cannot disrupt existing connections, but can prevent new connections; the attacker can repeatedly exploit a vulnerability that, in each instance of a successful attack, leaks a only small amount of memory, but after repeated exploitation causes a service to become completely unavailable).
Subsequent system confidentiality: None: There is no loss of confidentiality within the Subsequent System or all confidentiality impact is constrained to the Vulnerable System.
Subsequent system integrity: None: There is no loss of integrity within the Subsequent System or all integrity impact is constrained to the Vulnerable System.
Subsequent system availability: None: There is no impact to availability within the Subsequent System or all availability impact is constrained to the Vulnerable System.

Definitions: FIRST CVSS v4.0 specification.

Exploitation evidence

Disclosed: evidence found.
CVE published 13 Nov 2026
Detectable: no evidence on record.
No public nuclei template indexed
Weaponized: no evidence on record.
No public exploit code indexed in Metasploit or Exploit-DB
Exploited in the wildExploited: no evidence on record.
Not in CISA KEV and no source reports exploitation
Observed by OffSeq MirageSeen by Mirage: no evidence on record.
No attack traffic recorded by OffSeq Mirage sensors

A missing step is not evidence of safety. Sources: cve.org (opens in a new tab), the Metasploit, Exploit-DB and nuclei-templates index as of 13 Nov 2026.

Disclosed: The CVE record is public on cve.org. Its publication is t = 0.
Detectable: A public nuclei template can find exposed instances, for defenders and attackers alike.
Weaponized: A Metasploit exploit module or Exploit-DB entry exists (Metasploit scanner modules do not count), or CISA SSVC or the CVSS exploit maturity reports a public proof of concept.
Exploited in the wild: CISA KEV lists it, CISA SSVC rates exploitation active, or a source reports attacks.
Observed by OffSeq Mirage: OffSeq Mirage honeypot sensors recorded attack traffic for this CVE, or found exposed hosts without attack traffic.

Moments are spaced evenly, not to scale; a dashed line marks a gap of six months or more. Deltas count from t = 0. Sources that give only a date (CISA KEV, Exploit-DB, or a time of exactly 00:00Z) read “same day” rather than hours. Metasploit modules carry the flaw’s disclosure date, not their release date, and nuclei templates carry no date, so both appear above but not on the timeline.

What to do

Upgrade nltk to 3.10.4.

Affected software

Product	Affected	Fixed in
PyPInltk	Affected <3.10.4	Fixed in 3.10.4

Check your own hosts for these packages with threat-finder (opens in a new tab), our free open-source scanner.

Description

## Summary The public CCG lexicon parser `nltk.ccg.lexicon.fromstring` parses caller-influenced lexicon text with two pure-Python loops whose cost is quadratic in the input width. A service that parses an untrusted CCG lexicon string can be driven into tens of seconds of single-threaded CPU by a few-megabyte input, starving the request worker. No authentication or user interaction is required. ## Root Cause `matchBrackets` consumes a bracket body one character at a time with `inside = inside + rest[0]; rest = rest[1:]`. The `rest = rest[1:]` tail re-slice copies the entire remaining string on every iteration, so a flat bracket body costs O(n^2). `augParseCategory` drives a `while rest != "":` operator loop that re-copies the regular-expression match tail (`rest = app[3]`) once per operator, which is also O(n^2) over a long operator chain. The parser carries a recursion-depth guard (`MAX_PARSE_DEPTH = 500`) that raises on deeply nested categories, but both quadratic loops run on flat input whose nesting depth stays at zero, so that guard never fires. No bound is applied to line length or category width before the text reaches these loops. ```text Affected functions: - nltk.ccg.lexicon.matchBrackets (nltk/ccg/lexicon.py:149-172; tail re-slice at line 168) - nltk.ccg.lexicon.augParseCategory (nltk/ccg/lexicon.py:223-268; APP_RE tail re-copy at line 250) Public entry point: nltk.ccg.lexicon.fromstring (nltk/ccg/lexicon.py:271), also re-exported as nltk.ccg.chart.fromstring. ``` ## Impact An attacker who can influence the CCG lexicon string parsed by an application causes sustained single-threaded CPU consumption (availability loss). The vulnerable path is network-reachable (AV:N) and needs no privileges or user interaction (PR:N, UI:N). Because the cost grows quadratically with attacker-chosen input size, a few-megabyte payload costs tens of seconds per core, and a small number of concurrent requests can exhaust worker threads. Confidentiality and integrity are not affected. The NLTK regular-expression wall-clock timeout wraps regex matching only; it does not wrap these pure-Python slicing loops, so it provides no protection here. ## Proof of Concept ```text Environment: nltk 3.10.3, regex 2026.9.10, CPython. Run the parser on the shipped public API. ``` ```python import nltk.ccg.lexicon as L # Vector A: flat bracket body -> matchBrackets tail re-slice is O(n^2) n = 400000 lex_a = ":- S\nw => (" + "a" * n + ")\n" # Vector B: long operator chain -> augParseCategory tail re-copy is O(n^2) m = 32000 lex_b = ":- a\nw => " + "a" + "/a" * m + "\n" import time for name, s in (("A", lex_a), ("B", lex_b)): t = time.perf_counter() try: L.fromstring(s) except Exception: pass # downstream parse error is irrelevant; the CPU is already burned print(name, round(time.perf_counter() - t, 3), "s") ``` ```text Negative control (":- a\nw => (a/a)"): ~0.00007 s Vector A (matchBrackets, flat body): n=50k 0.078s | 100k 0.260s | 200k 1.046s | 400k 2.083s (~4x per doubling => O(n^2)) Vector B (augParseCategory, operators): m=4k 0.078s | 8k 0.215s | 16k 0.485s | 32k 1.329s (super-linear) ``` ## Attack Chain 1. **Exposure:** An application calls the public `nltk.ccg.lexicon.fromstring(lex_str)` (also reachable as `nltk.ccg.chart.fromstring`) on lexicon text the attacker can influence. 2. **Control:** The attacker fully controls the body width (a run of characters inside one bracket) and the operator-chain length; neither is capped by `fromstring`. 3. **Path:** `fromstring` splits input into lines and routes each category through `nextCategory`, which dispatches to `matchBrackets` (Vector A) or into the `augParseCategory` operator loop (Vector B). 4. **Guard:** The only relevant guard is the `MAX_PARSE_DEPTH = 500` recursion-depth check. On flat input the recursion depth is zero, so `if _depth > max_depth` is never reached; the width loops run unbounded. 5. **Primitive:** The tail re-slice `rest = rest[1:]` and tail re-copy `rest = app[3]` execute a quadratic number of string copies. 6. **Result:** Sustained single-core CPU exhaustion; a few-megabyte lexicon costs tens of seconds and scales quadratically, blocking the parsing thread. ## Bypass Evidence The one protection present on this path is the recursion-depth guard `MAX_PARSE_DEPTH = 500` (nltk/ccg/lexicon.py:22), checked at lexicon.py:153 and lexicon.py:228. It defends only against nesting depth and raises a bounded `ValueError` for deeply nested categories. The quadratic payloads here are flat: a single bracket body or a single operator run has nesting depth zero to one, so the depth check provably never fires while the width loops consume quadratic time. This was confirmed by running the shipped parser: the payloads complete without a `ValueError` or a regex `TimeoutError` while consuming quadratic CPU (Vector A shows a clean 4x cost per input doubling). A repository search finds no line-length or category-

CWE-400Uncontrolled Resource Consumption (opens in a new tab)
Class weaknessLikelihood of exploit: High
The product does not properly control the allocation and maintenance of a limited resource.
MITRE discourages mapping vulnerabilities to this broad entry; the root cause is usually a more specific weakness.
Architecture and Design
Design throttling mechanisms into the system architecture. The best protection is to limit the amount of resources that an unauthorized user can cause to be expended. A strong authentication and access control model will help prevent such attacks from occurring in the first place.
Architecture and Design
Mitigation of resource exhaustion attacks requires that the target system either: recognizes the attack and denies that user further access for a given amount of time, or; uniformly throttles all requests in order to make it more difficult to consume resources more quickly than they can again be freed.
Architecture and Design
Ensure that protocols have specific limits of scale placed on them.
OWASP Cheat Sheets
File Upload (opens in a new tab)
OWASP ASVS 4.0.3
V12.1.1 (opens in a new tab)
Attack patterns
XML Ping of the Death (opens in a new tab)
Regular Expression Exponential Blowup (opens in a new tab)
Sustained Client Engagement (opens in a new tab)
From MITRE CWE, MITRE CAPEC and OWASP (Top 10, OpenCRE).
CWE-407Inefficient Algorithmic Complexity (opens in a new tab)
Class weaknessLikelihood of exploit: Low
An algorithm in a product has an inefficient worst-case computational complexity that may be detrimental to system performance and can be triggered by an attacker, typically using crafted manipulations that ensure that the worst case is being reached.
OWASP Cheat Sheets
File Upload (opens in a new tab)
OWASP ASVS 4.0.3
V12.1.1 (opens in a new tab)
From MITRE CWE, MITRE CAPEC and OWASP (Top 10, OpenCRE).

References

Community reviews

Loading reviews…

Exploitation evidence

What to do

Affected software

Description

WeaknessesCWE-400, CWE-407

Technical details

References

Community reviews

Related threats