NLTK: Quadratic-time DoS in PorterStemmer via long runs of 'y'

Exploitation

No confirmed exploitation recorded. Patch Next marks exploitation only from CISA KEV.

CVSS 4.0

6.9 · CVSS:4.0/AV:N/AC:L/AT:N/PR:N/UI:N/VC:N/VI:N/VA:L/SC:N/SI:N/SA:N · score source

EPSS

• CVE-2026-81722: 0.52% estimated exploitation activity in the next 30 days; percentile 44.30 (FIRST EPSS, 2026-11-03). This is a model estimate, not proof of exploitation or customer exposure.

As published by the source; long descriptions are shortened.

nltk.stem.PorterStemmer.stem() -- a ubiquitous public API applied to arbitrary, often untrusted, tokens -- runs in O(n^2) time on a token containing a long run of the letter 'y', letting a single ~20-50 KB token pin a CPU core (CWE-407). Root cause isconsonant(word, i) was made iterative (commit for #3633, GHSA/CWE-674) to fix an earlier unbounded-recursion RecursionError on 'y'10000. The iterative form walks backward over the whole run of 'y's on every call: measure() then calls isconsonant(stem, i) once for every position i of the stem. For a run of n 'y's that is sum{i} O(i) = O(n^2). The recursion fix therefore traded a CWE-674 RecursionError for a CWE-407 quadratic-time DoS. Proof of concept Measured (Python 3.13): stem('y'5000 + 'ness') = 2.6s, stem('y'10000 + 'ness') = 11.3s (2x input - ~4.3x time = quadratic), stem('y'20000 + 'ness') 20s. A pure run of 'y' with no matching suffix is fast because the stemmer rules that call measure do not fire; a real suffix such as 'ness'…

Published by the source

2 Sep 2026, 14:36 UTC

Last modified by the source

2 Sep 2026, 14:36 UTC

Source last checked

26 Oct 2026, 13:51 UTC

1. Revision 1 · created · 26 Oct 2026

   Published from ghsa record GHSA-ww6m-cw3f-q94g

Preview the exact text before you copy it. Commands are read-only suggestions; review them before running anything.

# Patch Next advisory brief: CVE-2026-81722

Advisory: NLTK: Quadratic-time DoS in PorterStemmer via long runs of 'y'
IDs: CVE-2026-81722, GHSA-ww6m-cw3f-q94g
Record: https://patchnext.com/advisories/cve-2026-81722 (revision 1, source checked 26 Oct 2026, 13:51 UTC)
Inventory: none attached. This brief comes from a public page and does not say whether any deployment is affected.
Severity: Medium (CVSS 6.9)
Exploitation: no confirmed exploitation recorded. Patch Next confirms exploitation only from CISA KEV.
Vendor response: Vendor fix available; fixed versions by package: nltk 3.10.3. A vendor fix does not mean a deployment is fixed.

## Affected components
- PyPI nltk: affected <= 3.10.2; fixed in 3.10.3

## Suggested inspection (read-only)
- `python -m pip show nltk`: prints the installed version. Run with the environment that serves production active.

## Supported action
Upgrade each affected component to a fixed version on its release line. For a transitive dependency, upgrade the parent package or add an override or constraint, then regenerate the lockfile. Redeploy every environment that ran an affected version.

## Required regression checks
- Run the test suite and a production build.
- Exercise the features that depend on nltk.
- Repeat the inspection and confirm that only fixed versions remain installed.

## Rollback considerations
- Keep the previous lockfile and deployment artifact. Rolling back reinstates the vulnerable version, so apply any documented mitigation while you fix forward.

## Unresolved questions
- Which deployments run an affected version?
- Exploitation status can change. Check again before lowering the priority.
- Mark the work resolved only after the fixed version is verified in production.

## Sources
- Verified: https://github.com/advisories/GHSA-ww6m-cw3f-q94g (GitHub-reviewed advisory GHSA-ww6m-cw3f-q94g lists affected ranges: PyPI nltk >=0 <=3.10.2)

Commands are suggestions: review each one before running it.