CVE-2026-126301: Quadratic CPU Exhaustion in NLTK LegalitySyllableTokenizer

The Natural Language Toolkit (nltk) is a widely deployed Python library used for symbolic and statistical natural language processing (NLP). Within its tokenization module (nltk.tokenize.legality_principle), the library provides LegalitySyllableTokenizer, a class designed to syllabify words based on the phonological legality principle of onsets and codas. Applications that perform linguistic analysis, text preprocessing, or readability scoring frequently expose NLTK tokenization routines to untrusted user inputs.

In NLTK versions >= 3.6 and < 3.10.4, the LegalitySyllableTokenizer.tokenize method exhibits an inefficient algorithmic complexity flaw classified under CWE-407 (Inefficient Algorithmic Complexity) and CWE-400 (Uncontrolled Resource Consumption). The method iterates backward through an input token while accumulating characters into a candidate syllable onset string. During each character iteration, the accumulated onset string is reversed via slicing and hashed to test for membership in a set of precomputed legal onsets.

When the input token consists of a continuous sequence of vowels, the state machine within tokenize never satisfies the conditions required to reset the accumulated onset buffer. Consequently, the buffer grows linearly with the length of the vowel run, and reversing and hashing this buffer on every iteration causes the total execution time to scale quadratically ($\mathcal{O}(n^2)$).

If an application passes unsanitized user input to LegalitySyllableTokenizer.tokenize, an unauthenticated remote attacker can supply a single oversized vowel token to monopolize a Python worker thread or process. Because Python's Global Interpreter Lock (GIL) restricts bytecode execution to a single thread per process, sustained CPU saturation in string manipulation routines degrades service availability across multi-threaded web servers and asynchronous task queues.

The root cause of CVE-2026-126301 lies in the state transition logic of LegalitySyllableTokenizer.tokenize in nltk/tokenize/legality_principle.py and its interaction with how legal onsets are defined during initialization. When LegalitySyllableTokenizer is instantiated, it invokes find_legal_onsets(), which extracts initial consonant clusters from a source text corpus using the onset() helper method. Because onset() halts immediately upon encountering the first vowel in any word, every string stored in self.legal_onsets consists exclusively of consonants and is guaranteed to be vowel-free.

When tokenize(self, token) executes, it traverses the input token in reverse order (for char in token[::-1]:) while maintaining two boolean state flags (vowel and onset) and an accumulator string (current_onset). On the first vowel encountered from the right end of the token, the not vowel branch executes, appending the character to syllable and setting vowel = True. All subsequent iterations enter the else block because vowel remains True.

Inside the else block, the method first evaluates if char_lower + current_onset[::-1] in self.legal_onsets:. When processing a continuous run of vowels, char_lower is always a vowel, and self.legal_onsets contains no vowels. Therefore, this set membership check is guaranteed to evaluate to False on every iteration, and the onset flag is never set to True. Execution then falls through to elif char_lower in self.vowels and not onset:, which evaluates to True for every vowel in the sequence.

Within this elif branch, the method executes current_onset += char_lower, appending the vowel to current_onset without resetting the state. The final else branch—which contains the reset logic current_onset = ""—is only reachable if a consonant is encountered that does not form a valid legal onset, or after onset has already transitioned to True. On an all-vowel string of length $n$, current_onset grows from length $1$ to $n-1$. On each step $k$, evaluating char_lower + current_onset[::-1] in self.legal_onsets allocates a reversed string copy of length $k-1$, concatenates it into a string of length $k$, and computes its hash over all $k$ bytes, yielding $\sum_{k=1}^{n} \mathcal{O}(k) = \mathcal{O}(n^2)$ time complexity.

> [!NOTE] > During a prior security hardening pass across the NLTK codebase, the sibling class SyllableTokenizer was updated with a MAX_TOKEN_LEN guard to prevent similar algorithmic complexity issues. However, LegalitySyllableTokenizer was omitted during that review, leaving it without either an input length limit or an internal bound on onset accumulation.

Prior to version 3.10.4, the LegalitySyllableTokenizer.tokenize implementation in nltk/tokenize/legality_principle.py lacked bounds checking on both the input token length and the length of the current_onset accumulator:

# Vulnerable implementation in nltk/tokenize/legality_principle.py (< 3.10.4)
class LegalitySyllableTokenizer(TokenizerI):
    def tokenize(self, token):
        syllables = []
        syllable, current_onset = "", ""
        vowel, onset = False, False
        for char in token[::-1]:  # Walks token in reverse
            char_lower = char.lower()
            if not vowel:
                syllable += char
                vowel = bool(char_lower in self.vowels)
            else:
                # VULNERABLE SINK: O(k) string reversal, concatenation, and hashing on every iteration
                if char_lower + current_onset[::-1] in self.legal_onsets:
                    syllable += char
                    current_onset += char_lower
                    onset = True
                elif char_lower in self.vowels and not onset:
                    syllable += char
                    # VULNERABLE ACCUMULATION: grows unboundedly on continuous vowel runs
                    current_onset += char_lower
                else:
                    syllables.append(syllable)
                    syllable = char
                    current_onset = ""
                    vowel = bool(char_lower in self.vowels)
                    onset = False

The maintainers remediated this vulnerability in Pull Request #3895 across two distinct commits, implementing a defense-in-depth approach. The first commit (e20c40e26ec9306de885703f6e53250695f1f49b) introduced a class attribute MAX_TOKEN_LEN = 4096 (matching SyllableTokenizer) and added an explicit guard at the start of tokenize() that raises a ValueError if len(token) > self.MAX_TOKEN_LEN.

The second commit (78781ba4575d536fb1540897f27baca0fb40617c) eliminated the underlying quadratic complexity within the loop itself. The fix recognizes a fundamental invariant of the algorithm: because char_lower + current_onset[::-1] has length len(current_onset) + 1, it can never match an entry in self.legal_onsets once len(current_onset) reaches or exceeds the length of the longest string in self.legal_onsets.

# Patched implementation in nltk/tokenize/legality_principle.py (3.10.4)
class LegalitySyllableTokenizer(TokenizerI):
    MAX_TOKEN_LEN = 4096
 
    def tokenize(self, token):
        # Layer 1: Reject oversized tokens immediately
        if len(token) > self.MAX_TOKEN_LEN:
            raise ValueError(
                f"LegalitySyllableTokenizer: token length exceeds MAX_TOKEN_LEN "
                f"({self.MAX_TOKEN_LEN}); refusing to syllabify an oversized token "
                "(CWE-407). Raise MAX_TOKEN_LEN for longer tokens."
            )
        syllables = []
        syllable, current_onset = "", ""
        vowel, onset = False, False
        
        # Layer 2: Precompute the maximum possible legal onset length
        max_onset = max(map(len, self.legal_onsets), default=0)
        
        for char in token[::-1]:
            char_lower = char.lower()
            if not vowel:
                syllable += char
                vowel = bool(char_lower in self.vowels)
            else:
                # Short-circuit evaluation prevents O(k) reversal if current_onset is already at max_onset
                if (
                    len(current_onset) < max_onset
                    and char_lower + current_onset[::-1] in self.legal_onsets
                ):
                    syllable += char
                    current_onset += char_lower
                    onset = True
                elif char_lower in self.vowels and not onset:
                    syllable += char
                    # Cap growth of current_onset at max_onset
                    if len(current_onset) < max_onset:
                        current_onset += char_lower
                else:
                    syllables.append(syllable)
                    syllable = char
                    current_onset = ""
                    vowel = bool(char_lower in self.vowels)
                    onset = False

The fix is complete and eliminates the algorithmic complexity weakness even if a user overrides MAX_TOKEN_LEN to process longer strings. By precomputing max_onset = max(map(len, self.legal_onsets), default=0) and bounding current_onset growth to max_onset, the reversal and hashing operation executes in $\mathcal{O}(\text{max_onset})$ time per character. Because max_onset is bounded by natural language consonant cluster lengths (typically $\le 5$), the overall loop complexity is reduced from $\mathcal{O}(n^2)$ to strictly linear $\mathcal{O}(n \times \text{max_onset})$.

Exploiting CVE-2026-126301 requires no authentication or specialized privileges, provided an attacker can submit arbitrary text to an endpoint or processing pipeline that invokes LegalitySyllableTokenizer.tokenize(). Typical targets include NLP microservices, automated essay scoring systems, readability analyzers, and text-to-speech preprocessing pipelines. If the target application splits input documents on whitespace before passing individual word tokens to LegalitySyllableTokenizer, the attacker simply submits a payload consisting of a single unbroken string of vowels (e.g., "a" * 64000).

The following proof-of-concept script demonstrates the quadratic time scaling on continuous vowel runs compared against a linear control input of identical length consisting of alternating consonants and vowels:

import time
from nltk.tokenize import LegalitySyllableTokenizer
 
# Initialize tokenizer with a minimal onset vocabulary
tok = LegalitySyllableTokenizer("tr c d".split())
 
print("Testing quadratic growth on vowel runs ('a' * n):")
for n in (8000, 16000, 32000, 64000):
    payload = "a" * n
    start = time.perf_counter()
    tok.tokenize(payload)
    elapsed = time.perf_counter() - start
    print(f"vowel-run length {n:5d}: {elapsed:0.4f} seconds")
 
print("\nTesting linear scaling on control input ('ba' * (n/2)):")
control = "ba" * 32000  # 64,000 characters total
start = time.perf_counter()
tok.tokenize(control)
elapsed_control = time.perf_counter() - start
print(f"control   length 64000: {elapsed_control:0.4f} seconds")

Executing this benchmark against NLTK 3.10.3 produces empirical confirmation of $\mathcal{O}(n^2)$ complexity:

vowel-run length  8000: 0.031s
vowel-run length 16000: 0.120s  (~3.87x increase for 2x input)
vowel-run length 32000: 0.468s  (~3.90x increase for 2x input)
vowel-run length 64000: 1.840s  (~3.93x increase for 2x input)
 
control   length 64000: 0.004s  (~460x faster than all-vowel payload of same size)

As shown in the benchmark output, doubling the length of the vowel sequence consistently quadruples the CPU execution time ($2^2 = 4$). While a 64,000-character control string completes in 4 milliseconds, an all-vowel string of the same size blocks the interpreter for 1.84 seconds. Increasing the token length to 256,000 characters (~256 KB, well within standard HTTP POST body limits of 1 MB to 10 MB) extends single-request execution time to approximately 30 seconds.

The security impact of CVE-2026-126301 is confined to system availability, with no direct impact on confidentiality or integrity. The vulnerability carries a CVSS v3.1 score of 5.3 (Medium) (CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:L) from the GitHub Advisory Database and 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) assigned by VulnCheck. The low attack complexity reflects that an attacker only needs to supply a repetitive string of vowels without needing to know the target's internal legal_onsets corpus.

In production Python environments, the practical availability impact depends on the concurrency model of the host application. In synchronous WSGI deployments (such as Gunicorn or uWSGI with a fixed pool of worker processes), each malicious request occupies one worker process for the duration of the quadratic loop. Sending a small number of concurrent requests containing vowel runs of $10^5$ to $10^6$ characters is sufficient to exhaust all available workers, causing legitimate requests to queue until they time out at the reverse proxy layer.

In asynchronous Python frameworks (such as FastAPI or aiohttp running on an asyncio event loop), invoking CPU-bound tokenization directly inside an async def coroutine blocks the entire event loop thread. Because the GIL is held during synchronous string slicing and hashing in Python, a single unauthenticated request can freeze all concurrent connections handled by that event loop process. As of publication, the EPSS score for CVE-2026-126301 is 0.00509 (44.01st percentile), and the vulnerability is not listed in the CISA Known Exploited Vulnerabilities (KEV) catalog.

The primary remediation is to upgrade the nltk package to version 3.10.4 or later, which incorporates both the MAX_TOKEN_LEN = 4096 guard and the $\mathcal{O}(n)$ onset capping optimization. Administrators and developers can apply the update via pip:

pip install --upgrade "nltk>=3.10.4"

> [!IMPORTANT] > After upgrading to nltk>=3.10.4, calling LegalitySyllableTokenizer.tokenize() on any token longer than 4,096 characters will raise a ValueError. Applications that process untrusted text must catch ValueError exceptions during tokenization to prevent unhandled exceptions from returning HTTP 500 errors to clients.

For environments where an immediate package upgrade is not possible, developers should enforce strict input length validation before passing individual tokens to LegalitySyllableTokenizer.tokenize(). Wrapping the tokenizer call with a pre-check mitigates the quadratic complexity by bounding the maximum value of $n$:

MAX_SAFE_TOKEN_LEN = 1000
 
def safe_syllabify(tokenizer, token: str) -> list[str]:
    if len(token) > MAX_SAFE_TOKEN_LEN:
        raise ValueError(f"Token length {len(token)} exceeds maximum safe limit of {MAX_SAFE_TOKEN_LEN}")
    return tokenizer.tokenize(token)

As an additional layer of defense, web applications and APIs exposing NLP functionality should enforce strict request body size limits at the reverse proxy or API gateway layer (such as Nginx client_max_body_size or AWS WAF size constraint rules). Furthermore, CPU-intensive NLP pipelines should be executed in isolated worker pools with strict per-task execution timeouts rather than directly within main web server threads or asynchronous event loops.