Inefficient Algorithmic Complexity in Natural Language Toolkit - #VU159485
Published: November 5, 2026
Vulnerability details
The vulnerability allows an unauthenticated remote attacker to cause quadratic CPU consumption and denial of service or increased latency in a service that passes attacker-controlled text to NLTK's LegalitySyllableTokenizer.tokenize. A single sufficiently long all-vowel token can occupy one CPU core for a prolonged period. Concurrent requests could exhaust available workers, although this consequence was inferred rather than demonstrated against a live deployment. There is no confidentiality or integrity impact.
The vulnerability exists due to an unguarded reverse traversal that repeatedly constructs and hashes a growing string without bounding token length. A remote attacker can submit a long all-vowel token to a network-reachable service that invokes this tokenizer, without authentication, special configuration, or user interaction. After the first vowel, the loop evaluates char_lower + current_onset[::-1] in self.legal_onsets. Because LegalitySyllableTokenizer.onset returns only the prefix before the first vowel, the legal-onset set is vowel-free. For an all-vowel token, the membership branch therefore never matches, the onset flag never becomes true, and the reset branch never clears current_onset. The accumulated string grows on every iteration, and repeated reversal and hashing cost O(k) at iteration k, producing O(n²) total CPU work.
The affected implementation is in nltk/tokenize/legality_principle.py and is publicly exposed through nltk.tokenize. Exploitation requires the application to invoke this syllabification API on untrusted tokens; the default word-tokenization path does not call this class. The behavior depends on attacker-controlled token length and character content, not on a large or particular onset corpus, and is reproducible with a small onset source without downloading a corpus. Memory consumption remains linear while CPU consumption grows quadratically.