Affected: Homebrew: acronym

### 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/", [tre…

Affected: nltk

NLTK before 3.10.3 contains a regular expression denial of service (ReDoS) vulnerability in the tgrep module. The _tgrep_node_action 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 tgrep_positions() or tgrep_compile() exposed to external input) can supply a pattern that triggers catastrophic backtracking, causing indefinite CPU saturation that blocks the Python process.

Affected: PyPI: nltk

### 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/", [tre…