AI and data stack advisories

Severe, 6 weeks2431Projects328

2431 severe, 6 weeks · 328 projects

NLTKGHSA-32p6-cwhc-8r78

NLTK: denial of service

NLTK

CVE-2026-129229 · Published Nov 19, 2026 · updated Nov 20, 2026

High7.5
Fix: upgrade to 3.10.4 or later
GitHub advisory

Summary

NLTK exposes a compile-time regular-expression denial of service in its regex-search helpers. When an application passes untrusted text as the search pattern to TokenSearcher.findall() / Text.findall(), or as the tokenizer pattern to RegexpTokenizer, the pattern is handed to the third-party regex engine, whose compilation cost is roughly quadratic in the number of capturing groups. A short pattern of the form () repeated many times (for example "()" * 25000, about 50 KB) forces tens of seconds of synchronous CPU work before any match begins. The wall-clock timeout that NLTK added to guard matching does not apply during compilation, so a single small request pins a CPU core, and repeated or concurrent requests exhaust all cores and deny service.

Root Cause

The remediation for the earlier match-time backtracking issue (advisory GHSA-rrv8-h7p8-rx55 / CVE-2026-80205) switched the caller-supplied-pattern search path from the standard library re module to the third-party regex engine and wrapped matching in a wall-clock timeout. That timeout is a match-time limit only: it is applied while the compiled pattern scans the corpus. Compilation of the pattern happens first and synchronously, outside any timeout. The regex engine's compiler is approximately O(n^2) in the number of regex groups, so a caller-controlled pattern consisting of many empty...

Affected versions

PackageAffectedFixed in
nltk
PyPI
>= 3.10.0, < 3.10.43.10.4
Details and references

## Summary NLTK exposes a compile-time regular-expression denial of service in its regex-search helpers. When an application passes untrusted text as the search pattern to `TokenSearcher.findall()` / `Text.findall()`, or as the tokenizer pattern to `RegexpTokenizer`, the pattern is handed to the third-party `regex` engine, whose compilation cost is roughly quadratic in the number of capturing groups. A short pattern of the form `()` repeated many times (for example `"()" * 25000`, about 50 KB) forces tens of seconds of synchronous CPU work before any match begins. The wall-clock timeout that NLTK added to guard matching does not apply during compilation, so a single small request pins a CPU core, and repeated or concurrent requests exhaust all cores and deny service. ## Root Cause The remediation for the earlier match-time backtracking issue (advisory GHSA-rrv8-h7p8-rx55 / CVE-2026-80205) switched the caller-supplied-pattern search path from the standard library `re` module to the third-party `regex` engine and wrapped matching in a wall-clock timeout. That timeout is a match-time limit only: it is applied while the compiled pattern scans the corpus. Compilation of the pattern happens first and synchronously, outside any timeout. The `regex` engine's compiler is approximately O(n^2) in the number of regex groups, so a caller-controlled pattern consisting of many empty groups makes compilation, not matching, the expensive step. No control bounds the group count of a caller-supplied pattern before compilation. ```text Affected components / functions: - nltk.text.TokenSearcher.findall (nltk/text.py) -> regex.findall(pattern, corpus, timeout=...) On released 3.10.0-3.10.2 this sink calls regex.findall directly; on 3.10.3 and later it routes through nltk.redos.compile. Either way the regex engine compiles the caller pattern with no group-count bound, and the timeout guards only matching. - nltk.redos.compile (nltk/redos.py, introduced in 3.10.3) -> regex.compile(src, flags) Called synchronously before the timeout-bearing wrapper exists. On released 3.10.3 there is no pre-compile guard at all; on the current development tree a check_pattern bounds source length, nesting depth, and counted-repeat product, but not the number of groups. ``` ## Impact An unauthenticated attacker who can influence a regular-expression string that reaches one of these NLTK search or tokenizer entry points can force amplified CPU consumption. A single request carrying an approximately 50 KB pattern of empty groups blocks a worker for tens of seconds; because cost grows quadratically with group count, a larger pattern (unbounded on the released 3.10.3 artifact, which imposes no length cap) or a modest number of concurrent requests exhausts every available core and denies service to legitimate users. There is no confidentiality or integrity impact, and service recovers once compilation finishes or the worker is terminated. This is the same class of unauthenticated denial of service as the prior match-time ReDoS, but reached through the compilation path that the prior fix does not cover. ## Proof of Concept `Requires the nltk package (3.10.0 through 3.10.3) and its declared regex dependency. No corpus data or network access is needed.` 1. Build a pattern of many empty capturing groups. 2. Pass it to any caller-supplied-pattern sink; measure the time spent before matching. 3. Observe that the match timeout does not fire, because the cost is in compilation. ```python import time, regex # Exact released 3.10.0-3.10.2 code path of TokenSearcher.findall: # regex.findall(pattern, corpus, timeout=<wall-clock match limit>) pattern = "()" * 25000 # ~50 KB, 25000 capturing groups; survives the "<>." rewrites start = time.perf_counter() try: regex.findall(pattern, "<hello><world><foo>", timeout=1.0) print(f"completed in {time.perf_counter()-start:.2f}s with NO TimeoutError") except TimeoutError: print(f"Tim

CVSS 3.1
CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H
Severity from
GitHub (reviewed advisory)
Weakness
CWE-1333, CWE-400
Also known as
CVE-2026-129229

More NLTK advisories

All NLTK