LegalitySyllableTokenizer.tokenize in the NLTK tokenizer package contains an unguarded O(n^2) processing loop. When the method is called on a single token that consists of a long run of vowels (for example "a" * n), it consumes CPU time proportional to the square of the token length. An attacker who can supply an untrusted token to this public tokenizer API can force a single request to saturate one CPU core for a prolonged period, degrading availability of any service that syllabifies attacker-controlled text. No authentication, special configuration, or user interaction is required.
The method walks the token in reverse and, on every iteration after the first vowel is seen, evaluates the membership test char_lower + current_onset[::-1] in self.legal_onsets. The set legal_onsets is built by onset(), which returns only the characters up to the first vowel, so every member is vowel-free. For an all-vowel token the first branch can therefore never match, onset never becomes True, and the reset branch that would clear current_onset is never reached. As a result current_onset grows by one character on every iteration. Building current_onset[::-1] and hashing the resulting string costs O(k) on iteration k, and this is repeated for k from 1 to n, giving total cost O(n^2). The security invariant that is violated is bounded per-token work: there is no length cap on this code path, so untrusted token length translates directly into quadratic CPU consumption.
Affected function: LegalitySyllableTokenizer.tokenize
Source: nltk/tokenize/legality_principle.py (membership-test sink at line 133; loop over token[::-1] beginning at line 126)
Helper establishing the vowel-free onset set: LegalitySyllableTokenizer.onset (nltk/tokenize/legality_principle.py, returns prefix up to first vowel)
An attacker who controls a token passed to LegalitySyllableTokenizer.tokenize can trigger quadratic CPU work. In the...
3.10.4Exploitability
AV:NAC:LPR:NUI:NScope
S:UImpact
C:NI:NA:L5.3/CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:LOther
Resource Management