Inefficient Algorithmic Complexity in Natural Language Toolkit - #VU159484
Published: November 5, 2026
Vulnerability details
The vulnerability allows an unauthenticated remote attacker to exhaust a CPU core and degrade availability in a network-reachable service that passes untrusted text to NLTK's TreebankWordTokenizer.span_tokenize. A single request containing a sufficiently long run of double-quote characters can cause prolonged processing, resulting in denial of service or increased latency. Concurrent requests could plausibly exhaust a worker pool, although this consequence was not demonstrated against a live deployment. There is no confidentiality or integrity impact.
The vulnerability exists due to an unguarded quadratic-time quote-restoration loop in nltk/tokenize/treebank.py. When input contains double quotes or repeated single quotes, the method constructs a matched list containing quote occurrences and reconstructs quote tokens by repeatedly calling matched.pop(0). Each removal shifts the remaining list elements and takes linear time. An all-double-quote input produces one quote token and one list entry per character, causing cumulative O(n^2) CPU work. A remote attacker can submit a long run of double quotes to a service exposing this span-tokenization API without authentication, special configuration, or user interaction.
Neither span_tokenize nor its underlying tokenize method imposes an input-length cap. The regular-expression timeout backstop in nltk/redos.py does not cover the pure-Python list-removal loop, so it does not bound this processing cost. The neighboring align_tokens call is linear and is not the source of quadratic behavior; memory usage also remains linear. Measurements reported approximately 1.76 seconds for 128,000 double quotes and 6.57 seconds for 256,000 on a single core, while an equal-token-count non-quote control avoided the vulnerable branch and processed substantially faster. No corpus download is required to reach the affected functionality.