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

The Natural Language Toolkit (NLTK) is a widely deployed Python library used for symbolic and statistical natural language processing (NLP). Among its core text preprocessing primitives are TreebankWordTokenizer (defined in nltk/tokenize/treebank.py) and its destructive counterpart NLTKWordTokenizer (defined in nltk/tokenize/destructive.py). These classes provide both standard word tokenization and span tokenization (span_tokenize), which calculates the exact start and end character offsets (start, end) for every token in a given source string.

Span tokenization is frequently exposed on the attack surface of web applications, document ingestion pipelines, named entity recognition (NER) services, and search indexing backends. Whenever an application must correlate extracted tokens back to their exact positions in raw user-submitted text—such as for syntax highlighting, annotation alignment, or clinical text extraction—it invokes span_tokenize on untrusted input.

In NLTK versions 3.2.5 through 3.10.3, both TreebankWordTokenizer.span_tokenize and NLTKWordTokenizer.span_tokenize contain an algorithmic complexity flaw classified under CWE-407 (Inefficient Algorithmic Complexity) and CWE-400 (Uncontrolled Resource Consumption). When restoring converted Penn Treebank directional quotes back to their original literal representations, the routine uses a standard Python list as a first-in, first-out (FIFO) queue by calling list.pop(0) inside a list comprehension.

Because removing the leading element from a contiguous array in CPython requires shifting all remaining elements in memory, executing list.pop(0) across $n$ quote tokens degrades execution from linear $O(n)$ time to quadratic $O(n^2)$ time. An unauthenticated attacker capable of submitting text payloads containing thousands of quote characters can occupy a CPU core for several seconds or minutes per request, leading to worker thread starvation and denial of service.

The root cause of CVE-2026-126300 lies in how span_tokenize reconciles Penn Treebank tokenization conventions with raw string offset mapping. During initial tokenization (self.tokenize(text)), the Treebank tokenizer converts standard ASCII double quotes (") into directional opening quotes ( ``) and closing quotes (''). Because these converted tokens no longer match the exact characters in the source text, direct substring searching to calculate character spans would fail unless the original quote characters are restored prior to alignment.

To perform this restoration, span_tokenize inspects the input string to check whether " or '' is present. If found, it executes a regular expression scan using redos.finditer(r"``|'{2}|\"", text) and collects every matched quote substring into a standard Python list named matched. Subsequently, it iterates through raw_tokens—the output of self.tokenize(text)—and replaces each quote token ('"', "``", or "''") with the next original character sequence by invoking matched.pop(0).

In the CPython runtime, a list object (PyListObject) is implemented as an over-allocated, contiguous C array of PyObject* pointers (ob_item). While appending or popping from the end of a Python list operates in amortized $O(1)$ constant time, removing the element at index 0 via list.pop(0) (internally handled by list_ass_slice or list_pop_impl) requires shifting every remaining pointer from index 1 through $k-1$ one position to the left using memmove. Consequently, a single call to matched.pop(0) on a list of length $k$ incurs $O(k)$ memory movement overhead.

When an input string consists of $n$ double-quote characters, matched is initialized with $n$ elements and raw_tokens contains $n$ corresponding quote tokens. The list comprehension invokes matched.pop(0) exactly $n$ times as the list shrinks from $n$ down to $1$. The total number of pointer shift operations follows the arithmetic series:

$$\sum_{k=1}^{n} (k - 1) = \frac{n(n - 1)}{2} = O(n^2)$$

> [!NOTE] > Existing safeguards in NLTK do not intercept this condition. First, unlike SyllableTokenizer or LegalitySyllableTokenizer, TreebankWordTokenizer.span_tokenize enforces no MAX_TOKEN_LEN input boundary check. Second, although NLTK wraps regular expression operations in nltk/redos.py to enforce regex execution timeouts and prevent catastrophic backtracking, the quadratic delay in CVE-2026-126300 occurs inside a pure-Python list comprehension after redos.finditer has already completed in linear time.

The vulnerable logic is duplicated across two files in the NLTK repository: nltk/tokenize/treebank.py (within TreebankWordTokenizer.span_tokenize) and nltk/tokenize/destructive.py (within NLTKWordTokenizer.span_tokenize). Both implementations share the same quote-matching and restoration block.

In the unpatched code prior to version 3.10.4, matched is constructed via a list comprehension and mutated via matched.pop(0):

# Vulnerable implementation in nltk/tokenize/treebank.py (lines 202-214)
if ('"' in text) or ("''" in text):
    # Find double quotes and converted quotes
    # VULNERABILITY: matched is constructed as a contiguous CPython list
    matched = [m.group() for m in redos.finditer(r"``|'{2}|\"", text)]
 
    # Replace converted quotes back to double quotes
    # VULNERABILITY: matched.pop(0) shifts all remaining list elements left in O(k) time.
    # Executed across all quote tokens in raw_tokens, total complexity is O(n^2).
    tokens = [
        matched.pop(0) if tok in ['"', "``", "''"] else tok
        for tok in raw_tokens
    ]
else:
    tokens = raw_tokens

Upstream commit e20c40e26ec9306de885703f6e53250695f1f49b (merged via Pull Request #3895) remediates the vulnerability in both nltk/tokenize/treebank.py and nltk/tokenize/destructive.py by importing collections.deque and replacing the list comprehension with a deque generator initialization:

--- 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:

In CPython, collections.deque is implemented as a doubly linked list of fixed-size pointer blocks (64 elements per block). Calling matched.popleft() simply increments the left index cursor of the head block (and frees the block when exhausted) without shifting any subsequent pointers in memory. This guarantees strict $O(1)$ time complexity per token restoration and restores the overall span_tokenize method to $O(n)$ linear scaling.

Fix Completeness Assessment: The patch completely eliminates the quadratic bottleneck in the quote restoration path for both TreebankWordTokenizer and NLTKWordTokenizer. Furthermore, downstream call align_tokens(tokens, text) advances a single monotonic character pointer point across text, which operates in $O(n)$ time. No residual quadratic behavior remains in the span_tokenize execution path.

Exploiting CVE-2026-126300 requires no authentication or complex payload formatting beyond reaching an application endpoint that passes user-controlled text into TreebankWordTokenizer().span_tokenize() or NLTKWordTokenizer().span_tokenize(). Note that span_tokenize returns a Python generator (Iterator[tuple[int, int]]), but the vulnerable matched.pop(0) loop executes eagerly before the first yield from align_tokens(tokens, text) statement is reached, meaning the CPU stall occurs immediately upon the first iteration (such as calling list() or iterating in a for loop).

An attacker crafts a string consisting solely of repeated double-quote characters ('"' * n). Because every byte in the payload is tokenized as a quote token and matched by r"``|'{2}|\"", the payload achieves maximum token density: a 256 KB string produces 256,000 elements in matched and triggers 256,000 sequential list.pop(0) calls, resulting in approximately $3.27 \times 10^{10}$ pointer movements.

The following proof-of-concept script demonstrates the quadratic scaling behavior by measuring execution duration across doubling payload sizes and comparing it against a non-quote control payload of identical character and token count:

import time
from nltk.tokenize import TreebankWordTokenizer
 
tok = TreebankWordTokenizer()
 
print("[*] Testing TreebankWordTokenizer.span_tokenize quadratic complexity:")
for n in (32000, 64000, 128000, 256000):
    payload = '"' * n
    start = time.perf_counter()
    list(tok.span_tokenize(payload))
    duration = time.perf_counter() - start
    print(f"  [+] quote-run length={n:<7}: {duration:.3f} seconds")
 
# Control run with equal token count (128,000 tokens, 256,000 chars)
# that bypasses the quote-restoration branch
control = "a " * 128000
start = time.perf_counter()
list(tok.span_tokenize(control))
duration = time.perf_counter() - start
print(f"  [*] control non-quote length=256000: {duration:.3f} seconds")

Empirical benchmark measurements confirm the $O(n^2)$ time growth where doubling the input length increases execution time by nearly a factor of 4:

• '"' * 32000 (32 KB): 0.23 seconds
• '"' * 64000 (64 KB): 0.52 seconds (~2.26x increase)
• '"' * 128000 (128 KB): 1.76 seconds (~3.38x increase)
• '"' * 256000 (256 KB): 6.57 seconds (~3.73x increase)
• "a " * 128000 (256 KB Control): 0.16 seconds (~41x faster than the quote payload)

At 512,000 characters (~512 KB), a single invocation blocks the Python interpreter for approximately 26 seconds. Payloads exceeding 1 MB block a CPU core for several minutes while holding the Global Interpreter Lock (GIL) during each C-level memmove operation.

The primary security impact of CVE-2026-126300 is Application-Layer Denial of Service (DoS) via CPU exhaustion. The vulnerability has no direct impact on confidentiality or integrity, as the memory shifts stay strictly within the allocated bounds of the PyListObject pointer array.

In synchronous Python web frameworks (such as Flask, Django, or FastAPI running synchronous worker endpoints under Gunicorn or uWSGI), each worker process typically handles a single request at a time, or shares a single Python interpreter across multiple OS threads constrained by the CPython Global Interpreter Lock (GIL). When an attacker submits a few concurrent HTTP requests containing 256 KB to 1 MB of repeated quote characters, all available worker processes become saturated in the matched.pop(0) loop.

The National Vulnerability Database (NVD) and GitHub Advisory Database score this vulnerability at CVSS v3.1 5.3 (MEDIUM) (CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:L), while the assigning CNA (VulnCheck) assigns a CVSS v4.0 score of 6.9 (MEDIUM) (CVSS:4.0/AV:N/AC:L/AT:N/PR:N/UI:N/VC:N/VI:N/VA:L/SC:N/SI:N/SA:N). Both vectors reflect that the flaw is network-exploitable without privileges, user interaction, or special attack requirements (AV:N/AC:L/PR:N/UI:N), with a Low availability impact (A:L / VA:L) because the service recovers automatically once the long-running tokenization calls finish.

According to threat intelligence metrics, CVE-2026-126300 is not listed in the CISA Known Exploited Vulnerabilities (KEV) catalog. It holds a FIRST EPSS score of 0.00509 (0.51%), placing it at the 44.01st percentile of indexed vulnerabilities. While public proof-of-concept benchmark code is available in the security advisory, no automated mass-exploitation campaigns have been observed.

The definitive remediation for CVE-2026-126300 is to upgrade the nltk package to version 3.10.4 or later. In version 3.10.4, the collections.deque.popleft() replacement reduces the execution time for a 128,000-character quote payload from 1.76 seconds down to under 0.20 seconds, restoring linear $O(n)$ performance across all input compositions.

Administrators and developers should update their environment dependencies using pip or their respective package manager:

pip install --upgrade "nltk>=3.10.4"

For environments where an immediate dependency upgrade cannot be deployed, security engineers should apply defense-in-depth controls at the application boundary:

1. Input Size Clamping: Enforce strict request body and field length limits at the API gateway, reverse proxy (e.g., NGINX client_max_body_size), or application validation layer (such as Pydantic max_length constraints) before passing text to NLP tokenizers.
2. Quote Density Filtering: Pre-validate or sanitize untrusted strings to reject or collapse pathological runs of consecutive quote characters (for example, rejecting inputs matching the pattern "{50,} or ('{2}|``){50,}) prior to invoking span_tokenize.
3. Process Isolation and Task Timeouts: Offload heavy NLP preprocessing to isolated background worker processes (such as Celery or RQ with multiprocessing pools) configured with hard execution timeouts (time_limit), ensuring that runaway tokenization tasks are terminated without starving main web server threads.