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:

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

References

• GitHub Security Advisory: GHSA-ffr9-mgrr-wcvr
• VulnCheck Advisory: NLTK CPU Exhaustion via TreebankWordTokenizer.span_tokenize
• NLTK Pull Request #3895
• Official Fix Commit e20c40e26ec9306de885703f6e53250695f1f49b
• NLTK Upstream Release v3.10.4
• National Vulnerability Database (NVD): CVE-2026-126300
• CVE.org Official Record: CVE-2026-126300

Read the full report for CVE-2026-126300 on our website for more details including interactive diagrams and full exploit analysis.