Threats tagged 'ghsa-ffr9-mgrr-wcvr'

## Summary `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. ## Root Cause 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. ```text 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 ``` ## Impact 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 about 1.76 seconds and 256,000 characters about 6.57 seconds on a single core, with cost growing as the square of the length. Memory use is linear. The demonstrated capability is single-core CPU exhaustion producing denial of service or latency degradation in any network-reachable component that uses span tokenization on untrusted input, such as offset, annotation, or highlighting pipelines. There is no confidentiality or integrity impact. The plausible operational consequence, where multiple concurrent requests are used, is worker-pool exhaustion; this is inferred from the measured per-request cost and was not executed against a live deployment. ## Proof of Concept `Requires only the released nltk package; no corpus download is needed.` 1. Instantiate `TreebankWordTokenizer`. 2. Call `span_tokenize` on an all-double-quote string of increasing length and time each call. 3. Compare against an equal-token-count control input that avoids the quote branch. ```python import time from nltk.tokenize import TreebankWordTokenizer tok = TreebankWordTokenizer() for n in (32000, 64000, 128000, 256000): payload = '"' * n start = time.perf_counter() list(tok.span_tokenize(payload)) print("quote-run", n, round(time.perf_counter() - start, 3)) control = "a " * 128000 # comparable token count, avoids the pop(0) branch start = time.perf_counter() list(tok.span_tokenize(control)) print("control", round(time.perf_counter() - start, 3)) ``` ```text quote-run 32000 0.23 quote-run 64000 0.52 quote-run 128000 1.76 quote-run 256000 6.57 (about 4x per doubling => O(n^2)) control 0.16 (roughly 11x faster, isolates pop(0)) ``` ## Attack Chain 1. **Exposure:** `TreebankWordTokenizer` is exported from `nltk.tokenize` and `span_tokenize` is a public, documented method reachable by any service that span-tokenizes untrusted text. 2. **Control:** The attacker fully controls the `text` argument; a run of double-quote characters such as `'"' * n` survives to the quote branch unchanged. 3. **Path:** The branch selector at line 203 (`'"' in text` or `"''" in text`) is satisfied by the payload, entering the vulnerable branch; `matched` is built at line 205 with n entries and the reconstruction comprehension runs at line 209. 4. **Guard:** There is no length cap on `span_tokenize` or `tokenize`. The regex timeout backstop in `nltk/redos.py` only wraps regular-expression operations and does not cover the pure-Python `list.pop(0)` sink; a 256,000-character input ran to completion in 6.57 seconds with no timeout raised. 5. **Primitive:** `matched.pop(0)` executed once per quote token, each call O(len(matched)), yields cumulative O(n^2) CPU work. 6. **Result:** A single request with a large quote-run input exhausts one CPU core for a sustained period, degrading service availability. ## Bypass Evidence No guard blocks this path. Direct inspection found no `MAX_TOKEN_LEN` or length check in `nltk/tokenize/treebank.py`, in contrast to the sibling `sonority