CVE-2026-126300: Algorithmic Complexity Denial of Service in NLTK TreebankWordTokenizer.span_tokenize

Vulnerability ID: CVE-2026-126300
CVSS Score: 5.3
Published: 2026-11-13

CVE-2026-126300 (GHSA-ffr9-mgrr-wcvr) is an inefficient algorithmic complexity vulnerability (CWE-407) in the Natural Language Toolkit (NLTK) Python library affecting versions 3.2.5 prior to 3.10.4. The flaw resides in the quote-restoration routine of TreebankWordTokenizer.span_tokenize and NLTKWordTokenizer.span_tokenize, where repeated calls to list.pop(0) over matched quote tokens introduce quadratic O(n^2) time complexity. An unauthenticated remote attacker who supplies input containing long sequences of double-quote characters can exhaust CPU resources and degrade service availability.

TL;DR

An O(n^2) algorithmic complexity flaw in NLTK's span_tokenize method (versions >= 3.2.5, < 3.10.4) occurs due to repeated list.pop(0) calls during quote restoration. Processing inputs with large numbers of double quotes causes severe CPU exhaustion, which is resolved in NLTK 3.10.4 by using collections.deque.popleft().

⚠️ Exploit Status: POC

Technical Details

Vulnerability Type: CWE-407: Inefficient Algorithmic Complexity (O(n^2) DoS)
Affected Component: TreebankWordTokenizer.span_tokenize / NLTKWordTokenizer.span_tokenize
Attack Vector: Network (Unauthenticated untrusted text input)
CVSS v3.1 / v4.0: 5.3 MEDIUM (v3.1) / 6.9 MEDIUM (v4.0)
EPSS Score: 0.51% (44.01st Percentile)
Impact: CPU Exhaustion / Application Denial of Service
Exploit Status: Public Proof-of-Concept (PoC) Available
CISA KEV Status: Not Listed

Affected Systems

Natural Language Toolkit (NLTK) Python Package (pkg:pypi/nltk)
TreebankWordTokenizer (nltk.tokenize.treebank)
NLTKWordTokenizer (nltk.tokenize.destructive)
nltk: >= 3.2.5, < 3.10.4 (Fixed in: 3.10.4)

Code Analysis

Commit: e20c40e

Replace list.pop(0) with collections.deque.popleft() in TreebankWordTokenizer.span_tokenize and NLTKWordTokenizer.span_tokenize to prevent O(n^2) CPU complexity (CWE-407).

--- a/nltk/tokenize/treebank.py +++ b/nltk/tokenize/treebank.py @@ -19,6 +19,7 @@ import re import warnings +from collections import deque from collections.abc import Iterator from typing import List, Tuple @@ -202,11 +203,13 @@ def span_tokenize(self, text: str) -> Iterator[tuple[int, int]]: # treated as starting quotes). if ('"' in text) or ("''" in text): # Find double quotes and converted quotes - matched = [m.group() for m in redos.finditer(r"``|'{2}|\"", text)] + # A deque keeps popleft() O(1); a list.pop(0) here is O(n) per token, + # so text with many quotes made span_tokenize O(n**2) (CWE-407). + matched = deque(m.group() for m in redos.finditer(r"``|'{2}|\"", text)) # Replace converted quotes back to double quotes tokens = [ - matched.pop(0) if tok in ['"', "``", "''"] else tok + matched.popleft() if tok in ['"', "``", "''"] else tok for tok in raw_tokens ] else:

Exploit Details

GitHub: Public benchmark proof-of-concept script demonstrating quadratic CPU time scaling in TreebankWordTokenizer.span_tokenize using repeated double-quote payloads.

Mitigation Strategies

Upgrade the NLTK library to version 3.10.4 or later to replace O(n) list.pop(0) calls with O(1) collections.deque.popleft().
Enforce strict maximum input length boundaries on all user-supplied text fields before invoking NLP tokenization pipelines.
Implement pre-processing filters or Web Application Firewall (WAF) rules to detect and block inputs containing excessive runs of consecutive double-quote characters.
Execute NLP span tokenization tasks within isolated worker processes subject to strict wall-clock execution timeouts.

Remediation Steps:

Audit application dependencies (requirements.txt, Pipfile.lock, poetry.lock) to identify installations of nltk >= 3.2.5 and < 3.10.4.
Upgrade NLTK by executing: pip install --upgrade "nltk>=3.10.4"
Verify the installed version and confirm linear time execution using: python -c "import nltk; print(nltk.version)"
Configure application-level payload validation to bound maximum document length passed to TreebankWordTokenizer.span_tokenize and NLTKWordTokenizer.span_tokenize.