TreebankWordTokenizer.span_tokenize in the NLTK tokenizer package contains an unguarded O(n^2) processing loop in its quote-restoration step. When the method is invoked on text containing a long run of double-quote characters (for example '"' * n), it performs a list.pop(0) operation once per quote token, and because list.pop(0) is O(length), the total cost grows with the square of the input length. An attacker who can supply untrusted text to this public span-tokenization API can force a single request to saturate one CPU core for a prolonged period, degrading availability. No authentication, special configuration, or user interaction is required.
Inside span_tokenize, when the input contains double or repeated quotes, the code builds matched, a list with one entry per quote occurrence, and then reconstructs tokens in a comprehension that calls matched.pop(0) for each token that is a quote. Removing the first element of a Python list is an O(len(list)) operation because all remaining elements are shifted. For an all-quote input the tokenizer produces n quote tokens and matched has n entries, so pop(0) is called n times, each time on a list of shrinking but still linear length, giving cumulative O(n^2) CPU work. The violated invariant is bounded per-input work: there is no length cap on span_tokenize or the underlying tokenize, so untrusted input length translates into quadratic processing time. The neighboring align_tokens call is linear and is not the quadratic term.
Affected function: TreebankWordTokenizer.span_tokenize
Source: nltk/tokenize/treebank.py
- branch selector at line 203
- matched list built at line 205
- quadratic sink matched.pop(0) at line 209
- linear align_tokens call at line 215
An attacker who controls text passed to TreebankWordTokenizer.span_tokenize can trigger quadratic CPU work. In the reviewed release, an all-quote input of 128,000 characters takes...
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