CVE-2026-129229: NLTK: Compile-time regex DoS in NLTK search/tokenizer sinks: quadratic regex-engine compile bypasses the match-only timeout
High CVSS 7.5
- OSV id
- GHSA-32p6-cwhc-8r78
- Also known as
- CVE-2026-129229
- Published
- Last modified
Affected packages
| Package | Affected versions | Fixed in |
|---|---|---|
| nltk PyPI |
>= 3.10.0, < 3.10.4 | 3.10.4 |
How to fix it
Upgrade nltk to 3.10.4 or later.
# in requirements.txt: change the line to nltk==3.10.4
pip install -r requirements.txt
- If it is an indirect dependency, upgrade the package that depends on it, or add a minimum version constraint for it (e.g. in constraints.txt, or as a dependency in pyproject.toml).
- Check the changelog for breaking changes (especially across major versions), update the lockfile with the package manager, and run your tests.
Not sure whether your project uses an affected version? Check your lockfile below for free.
Details
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.
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.
- Build a pattern of many empty capturing groups.
- Pass it to any caller-supplied-pattern sink; measure the time spent before matching.
- Observe that the match timeout does not fire, because the cost is in compilation.
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"TimeoutError after {time.perf_counter()-start:.2f}s")
# Negative control: same length, zero groups, compiles in well under a second.
start = time.perf_counter()
regex.findall("a" * 50000, "<hello>", timeout=1.0)
print(f"control (0 groups) completed in {time.perf_counter()-start:.2f}s")
completed in 4.24s with NO TimeoutError
control (0 groups) completed in 0.16s
Additional measurements on the same host: regex.compile("()" * n) scaled 0.35s / 1.17s / 2.61s / 4.77s for n = 5000 / 10000 / 15000 / 20000 (clean quadratic); the standard library re.compile("()" * 20000) took 0.14s, confirming the cost is specific to the adopted regex engine and to group count, not to source length. Through the tokenizer sink, RegexpTokenizer("()" * 20000).tokenize("hello world") blocked about 5.1s entirely in compilation with no TimeoutError.
Attack Chain
- Exposure: An application exposes NLTK regex search or tokenization to user input, for example a search feature built o
References
- GHSA-32p6-cwhc-8r78 on OSV.dev
- Web: https://github.com/nltk/nltk/security/advisories/GHSA-32p6-cwhc-8r78
- Advisory: https://nvd.nist.gov/vuln/detail/CVE-2026-129229
- Web: https://github.com/nltk/nltk/pull/3895
- Web: https://github.com/nltk/nltk/commit/002bcf714ef8cb8baf94436f4be73e5516914412
- Package: https://github.com/nltk/nltk
- Web: https://github.com/nltk/nltk/releases/tag/v3.10.4
Am I affected?
Upload or paste your lockfile. We check every package version in it against OSV.dev, this advisory included, and email you the vulnerable ones with the version that fixes them. Free, and no account needed.
About this data
Source: GitHub Advisory Database via OSV.dev (CC-BY 4.0). Severity comes from the advisory's own rating when it has one, else from its CVSS score.