highCVE-2026-80206Sep 8, 2026

CVE-2026-80206: NLTK tgrep Regular Expression Denial of Service

Shubham Kandhare
Security Engagement Manager, SecureLayer7

NLTK's tgrep module passes user-supplied regex patterns directly to Python's re engine with no timeout, letting an attacker hang the entire process with a single crafted tree-search query.

Packagenltk
Ecosystempip
Affected<= 3.10.2
Fixed in3.10.3
CVE-2026-80206: NLTK tgrep Regular Expression Denial of Service

The problem

In nltk/tgrep.py, the function _tgrep_node_action() extracts the regex literal from a /regex/ node pattern and calls re.compile() on it with no validation or execution timeout. The compiled pattern is then run via r.search() against every matching tree node label.

Anyone who can supply a tgrep pattern string, whether through a web API, a Jupyter notebook, or any multi-tenant NLP pipeline, controls the regex entirely. A single ambiguous pattern against a carefully chosen input string triggers catastrophic backtracking and pins the Python process at 100% CPU indefinitely.

Proof of concept

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

python
import nltk
from nltk.tgrep import tgrep_positions
import time

def test_n(n):
    # Root node label is n repeated 'a' characters.
    # tgrep /regex/ branch compiles and runs ((a+)+)b against that label.
    # No 'b' is present, so CPython backtracks exponentially.
    tree = nltk.Tree.fromstring("(" + "a" * n + " (NP (DT the)))")
    pattern = r"/((a+)+)b/"
    start = time.perf_counter()
    list(tgrep_positions(pattern, [tree]))
    return time.perf_counter() - start

for n in [18, 20, 22, 24, 26, 28]:
    t = test_n(n)
    print(f"n={n}: {t:.3f}s")
# n >= 35 hangs indefinitely on NLTK <= 3.10.2

The root cause is CWE-1333: the regex ((a+)+) contains nested quantifiers over the same character class. When the subject string is all 'a' characters with no trailing 'b', the engine explores an exponential number of ways to partition the repetitions before failing, a classic catastrophic-backtracking pattern.

Because _tgrep_node_action() calls re.compile(node_lit) and immediately invokes r.search() with no signal-based timeout, threading timeout, or re2/regex engine substitution, a single tgrep_positions() or tgrep_compile() call with this pattern never returns. The 3.10.3 patch (commit 0072ea2fb8be22e038a36e887b7061bb6b9339d9) wraps regex execution in a timeout-guarded mechanism so that runaway matches raise an error rather than blocking the process.

The fix

Upgrade to nltk >= 3.10.3. The patch is commit 0072ea2fb8be22e038a36e887b7061bb6b9339d9. If you cannot upgrade immediately, reject or sanitize tgrep pattern strings before they reach tgrep_positions() or tgrep_compile(), or run tgrep calls in a worker process with an enforced wall-clock timeout so a hung match cannot block your main process.

Reported by Kira by Offgrid Security.

References: [1][2][3][4][5][6]

Related research