User-Supplied Regex in tgrep Module Compiled Without Timeout, One Pattern Saturates CPU

Productnltk (pip)

Locationnltk/tgrep.py

CWECWE-1333

CVSS7.5 HIGH

Affected≤ 3.10.2

Fixed3.10.3

Disclosed2026-08-12

Auth RequiredNone

StatusPatched

NLTK’s tgrep module implements a tree search pattern language. Within a tgrep pattern, node labels can be matched with embedded regular expressions enclosed in forward slashes (e.g. /NP.*/). Those regex patterns are passed directly to Python’s re module with no timeout and no backtracking complexity check. An attacker who controls the tgrep pattern argument can embed a catastrophically backtracking regex, saturating a CPU core indefinitely with a single call. No authentication is required.

01 Root Cause

The tgrep pattern parser in nltk/tgrep.py extracts regex literals enclosed in forward slashes from the pattern and compiles them via re.compile(). The compiled pattern is then used in re.match() calls against every node label in the tree during traversal. No timeout, no complexity check, and no pattern length limit is applied at any stage.

# nltk/tgrep.py (simplified) -- vulnerable path
node_regex = re.compile(node_lit)   # node_lit is attacker-controlled; no timeout

# During tree traversal, executed against every node label:
if node_regex.match(node.label()):  # no timeout; CPython NFA backtracks indefinitely
    ...

All NLTK releases prior to 3.10.3 are affected. Version 3.10.0 fixed CVE-2026-80205 in Text.findall() and TokenSearcher.findall() but did not patch the tgrep module. An application that upgraded to 3.10.0 specifically to address the first NLTK ReDoS remained exposed to this second one.

02 Reproduction

A tgrep pattern embedding a nested-quantifier regex is sufficient to trigger indefinite CPU saturation:

from nltk.tree import Tree
from nltk.tgrep import tgrep_nodes

# Root node label: 24 'a' characters followed by '!'
tree = Tree.fromstring("(aaaaaaaaaaaaaaaaaaaaaaaa! (DT the))")

# /((a+)+)b/ embeds a catastrophically backtracking pattern.
# Matched against "aaaaaaaaaaaaaaaaaaaaaaaa!" the NFA explores
# exponentially many partial states before failing at '!'.
# Result: CPU @ 100%, process blocked indefinitely.
list(tgrep_nodes("/((a+)+)b/", [tree]))

03 Impact

Any service that accepts user-supplied tgrep patterns and processes them in a request-handling thread is vulnerable. One crafted pattern hangs the process indefinitely, denying service to all other requests. The attack requires no authentication and no special permissions beyond the ability to submit a tgrep pattern to the service.

Affected public API surfaces: tgrep_nodes(), tgrep_positions(), and tgrep_sents(). Any application that passes user-supplied strings to these functions over a network interface is exploitable with a single request.

04 CVSS Breakdown

CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H Base Score: 7.5 HIGH (CVSSv3.1) AV:N: exploitable over any network reaching the NLTK-powered service AC:L: single crafted pattern string; no special conditions PR:N: no authentication required UI:N: no user interaction needed S:U: scope unchanged; impact is to the hosting process C:N: no data is disclosed I:N: no data is modified A:H: indefinite CPU saturation; process blocked for all callers

05 Recommended Fix

Upgrade to nltk ≥ 3.10.3. Version 3.10.3 applies the same timeout-based mitigation to tgrep.py that 3.10.0 applied to Text.findall(): user-supplied regex patterns are executed with a configurable timeout via the regex library, and a TimeoutError is raised rather than allowing indefinite backtracking.

pip install "nltk>=3.10.3"
# Covers both CVE-2026-80205 (Text.findall) and CVE-2026-80206 (tgrep)

Patched in nltk 3.10.3. Advisory: GHSA-w3v8-gmh9-3wv7 ↗.