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

PackageAffected versionsFixed 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.

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

  1. Exposure: An application exposes NLTK regex search or tokenization to user input, for example a search feature built o

References

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.

or paste its content

Needed when you paste. package.json and pyproject.toml only have version ranges: use the lockfile next to them.

Only package names and versions are checked; the file itself is not kept. We use your email to send this report and nothing else unless you tick the box above. Privacy policy.

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.