---
id: "GHSA-gpwc-27cw-rh9r"
page: "https://infrastack.ai/live/GHSA-gpwc-27cw-rh9r"
kind: "vulnerability"
aliases: ["GHSA-gpwc-27cw-rh9r"]
title: "NLTK: Quadratic CPU exhaustion in LegalitySyllableTokenizer.tokenize via unguarded onset reversal loop"
severity: "medium"
cvss: 5.3
epss: null
exploited: false
status: "open"
category: "package"
products: [{"name": "nltk", "fixed": ["3.10.4"], "affected": ">= 3.6, <= 3.10.3", "ecosystem": "pypi"}]
ecosystems: ["pypi"]
tags: ["cwe-400", "cwe-407", "nlp", "nltk", "package", "python", "text-processing"]
not_affected_if: ["default-word-tokenizer", "no-legality-syllable-tokenizer", "trusted-input-only"]
published_at: "2026-11-13T21:16:34+00:00"
first_seen_at: "2026-11-13T21:19:52+00:00"
updated_at: "2026-11-13T21:21:11+00:00"
sources: [{"source": "ghsa", "url": "https://github.com/advisories/GHSA-gpwc-27cw-rh9r", "first_seen_at": "2026-11-13T21:19:52+00:00"}]
exploit_sources: []
---

# NLTK: Quadratic CPU exhaustion in LegalitySyllableTokenizer.tokenize via unguarded onset reversal loop

Link for people: https://infrastack.ai/live/GHSA-gpwc-27cw-rh9r (this .md is for agents)

NLTK's LegalitySyllableTokenizer.tokenize does quadratic work on a single token made of a long run of vowels, so one crafted input can pin a CPU core. An attacker who can submit text to a service that syllabifies it can cause denial of service, with no confidentiality or integrity impact.

_Summary, check and fix written by a model from the sources; labelled as such._

## Affected

- pypi:nltk affected >= 3.6, <= 3.10.3 fixed 3.10.4

## How to check

- Check the installed version with `pip show nltk` and whether it falls in `>= 3.6, <= 3.10.3`.
- Search your code for `LegalitySyllableTokenizer` to see whether untrusted input reaches it.
- The default word-tokenization path does not call this class, per the advisory.

## Fix

- `nltk` `3.10.4` is listed as the fixed version in the product data.
- A fix commit (e20c40e26) caps tokens at 4096 characters in the referenced patch work, but the fix status note says the PR is still open and develop remains vulnerable, so confirm the released version rather than relying on the patch.

## Timeline

- 2026-11-13T21:19:52+00:00 ghsa https://github.com/advisories/GHSA-gpwc-27cw-rh9r

## Documents

- [advisory] Maintainer's advisory: api.github.com https://api.github.com/repos/nltk/nltk/security-advisories/GHSA-gpwc-27cw-rh9r
- [advisory] Vendor advisory: github.com https://github.com/nltk/nltk/security/advisories/GHSA-gpwc-27cw-rh9r
- [fix] Patch: github.com https://github.com/nltk/nltk/pull/3895
- [fix] Patch: github.com https://github.com/nltk/nltk/commit/78781ba4575d536fb1540897f27baca0fb40617c
- [fix] Patch: github.com https://github.com/nltk/nltk/commit/e20c40e26ec9306de885703f6e53250695f1f49b
- [fix] Release: github.com https://github.com/nltk/nltk/releases/tag/v3.10.4

## From the sources

## Summary

`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.

## Root Cause

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.

```text
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)
```

## Impact

An attacker who controls a token passed to `LegalitySyllableTokenizer.tokenize` can trigger quadratic CPU work. In the reviewed release a token of roughly 64,000 vowel characters takes about 1.8 seconds on a single core, and the cost grows with the square of the length, so a token in the hundreds of kilobytes to megabyte range consumes a core for many seconds to minutes. Memory use is linear. The demonstrated capability is single-core CPU exhaustion leading to denial of service or latency degradation in any network-reachable component that syllabifies untrusted input. There is no confidentiality or integrity impact; the effect is availability degradation of the affected process. The plausible operational consequence, where multiple concurrent requests are used, is exhaustion of the available worker pool; this is inferred from the per-request cost and was not itself executed against a live deployment.

## Proof of Concept

`Requires only the released nltk package; no corpus download is needed because the quadratic behavior is driven entirely by the attacker token, not by the size of the legal-onset set.`

1. Construct a tokenizer with any small onset source.
2. Call `tokenize` with an all-vowel token of increasing length and time each call.
3. Compare against a consonant-alternating control token of equal length.

```python
import time
from nltk.tokenize import LegalitySyllableTokenizer

tok = LegalitySyllableTokenizer("tr c d".split())  # tiny 3-word onset source
for n in (8000, 16000, 32000):
    payload = "a" * n
    start = time.perf_counter()
    tok.tokenize(payload)
    print("vowel-run", n, round(time.perf_counter() - start, 3))

control = "ba" * 32000  # equal-length linear control
start = time.perf_counter()
tok.tokenize(control)
print("control", 64000, round(time.perf_counter() - start, 3))
```

```text
vowel-run 8000 0.031
vowel-run 16000 0.120
vowel-run 32000 0.468   (about 4x per doubling => O(n^2))
control 64000 0.004     (linear, roughly 130x faster at larger size)
```

## Attack Chain

1. **Exposure:** `LegalitySyllableTokenizer` is exported from `nltk.tokenize` and `tokenize` is a public, documented method reachable by any service that syllabifies untrusted text.
2. **Control:** The attacker fully controls the `token` argument, including its length and character content; a run of vowels such as `"a" * n` survives with no normalization or length reduction.
3. **Path:** The token flows into the reverse walk at `nltk/tokenize/legality_principle.py:126` and reaches the membership-test at line 133 on every iteration past the first vowel.
4. **Guard:** There is no length cap on this path. The sibling `SyllableTokenizer` received a `MAX_TOKEN_LEN` cap during the project hardening work, but `legality_principle.py` received no such guard.
5. **Primitive:** Repeated O(k) construction and hashing of `current_onset[::-1]` inside the loop yields cumulative O(n^2) CPU work.
6. **Result:** A single request with a large vowel-run token exhausts one CPU core for a sustained period, degrading service availability.

## Bypass Evidence

No guard blocks this path. Membership-set analysis shows the first branch at line 133 cannot fire for a vowel character because `legal_onsets` is provably vowel-free (it is derived from `onset()`, which stops at the first vowel), so `onset` never becomes `True` and `current_onset` is never reset. The strongest refutations were attempted and failed: (1) the hypothesis that the quadratic depends on a large or specific onset corpus was disproven by reproducing the same O(n^2) growth with a three-word onset source, showing the cost is driven solely by the attacker token; (2) the hypothesis that an upstream length cap neutralizes long tokens was disproven by direct source inspection, which found no `MAX_TOKEN_LEN` or equivalent clamp on this class and confirmed the default word-tokenization path does not call this class; (3) the hypothesis that this is covered by existing hardening was disproven, since the project quadratic-DoS test suite exercises the sibling `SyllableTokenizer` but contains no test for `LegalitySyllableTokenizer`, and no commit added a cap to this file. This is a fix-missed sibling of the accepted algorithmic-complexity class, not a previously remediated issue.

## Affected Versions

- `Ecosystem: pip`
- `Package: nltk`
- `Confirmed affected range: >= 3.6, <= 3.10.3`
- `Latest release checked: 3.10.3 (PyPI)`
- `Fix status: not fixed`

The vulnerable loop is present and unguarded in the current released artifact 3.10.3, verified by direct source inspection and by reproducing the quadratic curve. The lower bound of 3.6 reflects when the affected module first shipped; the disclosure-relevant fact is that the latest published release is affected and no fix has been released.

## Suggested Fix

Enforce a bound on per-token work in `LegalitySyllableTokenizer.tokenize`, consistent with the `MAX_TOKEN_LEN` guard already applied to the sibling `SyllableTokenizer`. Options include rejecting or truncating tokens above a configurable maximum length before the reverse walk, or restructuring the onset accumulation so the loop does not repeatedly build and hash a growing reversed string (for example by maintaining the onset in its final orientation and comparing without an O(k) reversal each iteration). The remediation should cover any caller that passes untrusted tokens, not just the default word-tokenization path. As an interim mitigation, deployments that expose syllabification of untrusted input can cap request and token sizes at the application boundary to bound the worst-case token length.

Reported by zx (GitHub: @manus-pi).

## Fix status (2026-09-28)

PR: #3895 "[WIP] Bound algorithmic-DoS and uncontrolled-recursion vectors (CWE-400/407/674/1333)", open, head b22ebe144.

Fix commit: e20c40e26 "Bound tokenizer/parser algorithmic DoS (ffr9/gpwc/8fx7)" (LegalitySyllableTokenizer.tokenize refuses a token longer than MAX_TOKEN_LEN=4096 with ValueError naming CWE-407).

No probe. The advisory PoC re-run: on the PR head the 32k vowel token is refused and under the cap the tokeniz

---

_Free to read, with fair use of about 60 pages a minute. For higher limits or API access: sales@infrastack.ai_