Second Regex, Same Outcome: ReDoS in NLTK’s tgrep Module

Related: This is the second ReDoS found in NLTK during the same audit. The first, CVE-2026-80205, affects Text.findall() and was fixed in 3.10.0. CVE-2026-80206 affects the tgrep module and requires a separate upgrade to 3.10.3. Both were discovered by Kira.

What happened

NLTK’s tgrep module implements a tree search pattern language modelled on tgrep2, used for querying parse trees by their structural and label properties. Within a tgrep pattern, node labels can be matched using embedded regular expressions: a pattern like /NP.*/ matches any node whose label begins with NP.

Those embedded regex patterns are compiled and executed using Python’s re module with no timeout and no backtracking complexity check. An attacker who controls the tgrep pattern argument can embed a catastrophically backtracking regex as a node label filter, saturating a CPU core indefinitely with a single call.

The affected versions are 3.10.0–3.10.2 inclusive. This is notable: 3.10.0 fixed CVE-2026-80205 in Text.findall() and TokenSearcher.findall(), but the tgrep module was not part of that fix. An application that upgraded to 3.10.0 specifically to address the first NLTK ReDoS remained exposed to this second one.

Attack vector: Network, no authentication, no user interaction. Any application that passes user-supplied input to tgrep_nodes(), tgrep_positions(), or tgrep_sents() over a network interface is exploitable with a single request.

The vulnerable code

The tgrep pattern parser in nltk/tgrep.py recognises node label expressions enclosed in forward slashes as regex literals. When the parser encounters such a literal, it extracts the pattern string and passes it to re.compile() to create a compiled regex object used for node label matching.

There is no timeout on this compilation or on the subsequent match calls. The parser performs structural validation (the slashes must be present and balanced), but that validation has no effect on the backtracking complexity of the pattern inside. A structurally valid tgrep pattern can contain an arbitrarily complex regex.

Python — vulnerable path in nltk/tgrep.py (simplified)

# When the tgrep parser encounters /.../ node label syntax:
node_regex = re.compile(node_lit)  # node_lit is attacker-controlled
                                        # no timeout, no complexity check

# Later, during tree traversal:
if node_regex.match(node.label()):   # executed against every node label
    ...

The re.compile() step itself is not the danger: pattern compilation is fast. The danger is the subsequent match() call executed against node labels in the tree. When the pattern contains nested quantifiers like ((a+)+), CPython’s backtracking NFA explores an exponential number of partial match states before reaching a conclusive failure. With a long-enough node label and a carefully constructed pattern, that exploration never terminates within any practical bound.

Proof of concept

Python

from nltk.tree import Tree
from nltk.tgrep import tgrep_nodes

# Build a parse tree whose root node label has a long prefix of 'a' characters.
# The tgrep pattern /((a+)+)b/ embeds a catastrophically backtracking regex
# as the node label filter. It will be matched against every node label
# in the tree using Python's re engine, with no timeout.
tree = Tree.fromstring("(aaaaaaaaaaaaaaaaaaaaaaaa! (DT the))")

# Input tgrep pattern: /((a+)+)b/
# The regex engine must match ((a+)+)b against "aaaaaaaaaaaaaaaaaaaaaaaa!"
# Nested quantifiers force 2^n backtrack states before failing at '!'
# Result: CPU @ 100%, process blocked indefinitely
list(tgrep_nodes("/((a+)+)b/", [tree]))

The tgrep pattern /((a+)+)b/ contains the canonical nested quantifier structure for catastrophic backtracking. When matched against the node label aaaaaaaaaaaaaaaaaaaaaaaa! (24 a characters followed by !), the NFA must explore every possible way to partition the leading run of as between the inner and outer + quantifiers before reaching the conclusive mismatch at !. The number of states explored is exponential in the length of the a prefix.

The attack scales with node label length and quantifier depth. Longer labels or deeper nesting extend the hang exponentially. A 30-character prefix already produces a hang measurable in minutes on modern hardware.

The gap between CVE-2026-80205 and CVE-2026-80206

The fix for CVE-2026-80205 was targeted: it replaced re with the third-party regex library (which supports a timeout= parameter) specifically in TokenSearcher.findall() and Text.findall(). That fix was correct and complete for those two functions.

The tgrep module has the same root cause—user-controlled input reaching Python’s re engine without a timeout—but the code path is structurally different. Rather than a direct call where the user supplies the pattern argument, the user-controlled regex is embedded inside a tgrep pattern string and extracted by the tgrep parser before being passed to re.compile(). The input is one level of indirection away from the sink, which is why it was not caught by the same fix.

This is a common pattern in vulnerability remediation: a targeted fix closes the known instance, but the root cause (no timeout on user-controlled regex compilation) persists elsewhere in the codebase. A codebase-wide audit would have surfaced both sinks in the same pass. The two findings were identified during the same Kira audit; CVE-2026-80205 was disclosed and fixed first, with CVE-2026-80206 following in the next patch.

Why SAST misses this

The tgrep vulnerability adds one more challenge on top of those described for CVE-2026-80205: the regex is embedded inside a domain-specific language.

Taint is laundered through a DSL parser

The user’s input is a tgrep pattern string, not a regex. It reaches the code as a string argument to tgrep_nodes(). The tgrep parser extracts the /…/ node label literal and passes it to re.compile(). A taint analysis that does not model the tgrep parser’s extraction logic cannot connect the original user-supplied string to the final re.compile() call. Even a sophisticated interprocedural taint engine must understand what the parser does to track this flow correctly.

The regex is not user-visible at the sink

From the perspective of any individual function call, the tgrep functions accept a tgrep pattern string. Nothing at the call site indicates that this string will be parsed for embedded regexes. A SAST tool looking for re.compile(user_input) will not see it; the user_input has been transformed through several parsing steps by the time it reaches re.compile().

The DSL is trusted to constrain the pattern

A common mental model is that parsing and transforming user input is a sanitization step. The tgrep parser does validate the structural syntax of the pattern—ensuring / delimiters are present and the pattern is well-formed tgrep syntax—but this validation has no effect on regex complexity. Structural correctness and backtracking safety are orthogonal properties.

Detection method	Catches this?	Why / why not
Standard SAST (pattern-based rules)	No	Taint lost through DSL parser; no direct `re.compile(user_input)` pattern visible
Interprocedural SAST (taint-tracking)	Unlikely	Requires modeling the tgrep parser’s extraction of embedded regex literals
Specialized ReDoS analyzers	No	Analyze static pattern literals; attacker controls the pattern at runtime
SCA / dependency scanning	Yes (post-advisory)	Flags projects pinned to nltk ≤ 3.10.2 once advisory is published
Kira (Offgrid Security)	Yes	Traced the flow through the tgrep DSL parser; identified missing timeout at the regex compilation sink

How Kira found it

This vulnerability was discovered during the same NLTK audit that produced CVE-2026-80205. After finding and confirming the Text.findall() sink, Kira performed a systematic scan of all paths where user-controlled data reaches Python’s regex engine within the NLTK codebase.

The tgrep module surfaced as a separate finding because Kira traced the flow through the tgrep pattern parser rather than stopping at the DSL boundary. It recognised that:

The tgrep pattern string is accepted from the caller without validation of embedded regex complexity.
The parser extracts /…/ literals and passes them to re.compile() without any timeout mechanism.
The resulting compiled pattern is matched against node labels during tree traversal, creating a sink where attacker-controlled regex execution can run indefinitely.
The fix applied in 3.10.0 for CVE-2026-80205 did not touch nltk/tgrep.py, leaving this path unaddressed.

The finding was reported to the NLTK maintainers alongside the follow-up disclosure for CVE-2026-80205 and addressed in 3.10.3.

Remediation

Upgrade to nltk 3.10.3 or later. This version fixes both CVE-2026-80205 (Text.findall()) and CVE-2026-80206 (tgrep). If you upgraded to 3.10.0 for the first advisory, you still need this upgrade.

Shell

pip install "nltk>=3.10.3"

Verify your installed version: