One Regex to Freeze Them All: ReDoS in NLTK’s Text.findall()

What happened

Most ReDoS vulnerabilities follow a familiar pattern: a developer hardcodes a catastrophically backtracking regex, an attacker sends a crafted input string. CVE-2026-80205 is the inversion. Here, the attacker controls the pattern, not the input. That single difference is why conventional ReDoS tooling misses it entirely, and why it survived undetected in a widely-deployed library.

NLTK (Natural Language Toolkit) is one of the most widely deployed Python libraries for natural language processing, present in research codebases, data pipelines, and production systems worldwide. In all versions up to and including 3.9.4, two methods in nltk/text.py accept user-supplied regular expression patterns and pass them, after a syntactic transformation, directly to Python’s re engine with no timeout and no validation of backtracking complexity.

The result is a Regular Expression Denial of Service (ReDoS). An attacker who controls the pattern argument can craft a regex that causes CPython’s backtracking NFA to explore an exponential number of partial match states before conclusively failing, saturating a CPU core and blocking the entire process indefinitely.

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

The vulnerable code

Both sinks are in nltk/text.py. TokenSearcher.findall() is the underlying engine; Text.findall() delegates to it. The control flow:

1. The caller supplies a pattern in NLTK’s angle-bracket token syntax, e.g. <((a+)+)b>.
2. The method rewrites angle-bracket markers into standard regex group syntax.
3. The transformed pattern is passed directly to Python’s re engine with no timeout and no check for catastrophic backtracking potential.

The advisory is explicit on this point:

“Preprocessing does NOT prevent catastrophic backtracking.”

The transformation is purely structural; it rewrites syntax but has no ability to reason about the complexity of the patterns it produces.

Proof of concept

from nltk.text import Text

# Pass tokens as a list -- word_tokenize("aaaaaaaaaaaaaaaaaaaaaaaa!")
# splits the trailing "!" into a separate token, changing the raw string.
text = Text(["aaaaaaaaaaaaaaaaaaaaaaaa!"])

# Input pattern:    <((a+)+)b>
# After transform:  (?:<(?:((a+)+)b)>)
# Internal raw:     "<aaaaaaaaaaaaaaaaaaaaaaaa!>"  (one token, 25 chars)
# Result:           CPU @ 100%, process blocked indefinitely
text.findall(r"<((a+)+)b>")

Once the angle-bracket markers are rewritten, the engine receives (?:<(?:((a+)+)b)>) and must match it against the 27-character internal string <aaaaaaaaaaaaaaaaaaaaaaaa!> (25-char token wrapped in angle brackets). The nested quantifiers ((a+)+) force CPython’s backtracking NFA to enumerate an exponential number of ways to partition the leading run of a characters before reaching the conclusive mismatch at !. One request, one core, indefinite saturation.

The attack is not length-gated; it scales with how many ways the nested groups can partition the prefix. Longer inputs or deeper quantifier nesting extend the hang exponentially.

Why SAST almost never catches this

ReDoS is one of the vulnerability classes most systematically missed by conventional static analysis. This finding is a clean case study in why.

The sink is not inherently dangerous

re.findall() appears in millions of safe programs. SAST tools that flag every regex call produce unusable noise. Useful rules require a second condition: user-controlled data flowing into the pattern argument. That taint must survive the full call path.

Taint is laundered through preprocessing

The user’s input does not reach re directly; it is first rewritten by NLTK’s angle-bracket parser. Many SAST engines lose taint across string-transforming functions, or conservatively treat any transformation as potential sanitization. Neither is correct here. The rewrite is purely structural, not defensive, but a taint rule that does not model what the transformation does cannot tell the difference.

The key point is that NLTK’s transform is bijective for the attacker’s purposes: any catastrophic pattern in the input produces a catastrophic pattern in the output. The angle-bracket delimiters are rewritten one-for-one; quantifier structure is preserved entirely. The transformation offers zero mitigation.

User-controlled patterns are a different threat model than hardcoded bad regexes

Most ReDoS tooling is built to catch the opposite problem: a developer writes a hardcoded pattern like re.match(r"((a+)+)b", user_input) where the regex is static and the input string is attacker-controlled. For that class, SAST can analyze the pattern’s structure for catastrophic quantifier nesting. Here the situation is inverted: the attacker controls the pattern, not the input string. When user data reaches the pattern argument, any pattern they supply is potentially malicious. The required check is not structural regex analysis but a simpler question: does untrusted input reach the pattern slot of a regex engine call without a timeout? That is a taint-and-API-usage question, and the reason it is still missed is the taint-tracking challenge described above, not complexity analysis.

Most teams only scan their own code

Application-level SAST scanning your project’s source does not reach into nltk/text.py. The application may contain nothing more suspicious than text.findall(user_query), a single innocuous-looking call on a trusted library object. Without scanning the library’s internals or modeling its behavior, there is nothing at the call site to flag.

How Kira found it

This vulnerability was reported by infycore, analyzed by ekaf, and discovered using Kira, Offgrid Security’s AI-driven code security platform.

Kira named in the official advisory. When the NLTK maintainers published GHSA-rrv8-h7p8-rx55, Kira by Offgrid Security was listed by name in the formal attribution under “Tool: Kira by Offgrid Security.” The credit appears alongside the human reporter and analyst in the GHSA record.

The finding illustrates the practical gap between rule-based static analysis and semantic code understanding. Kira does not rely on a catalog of dangerous sinks. It reasons about what functions actually do:

• Kira tracked that Text.findall() and TokenSearcher.findall() accept external input and route it toward Python’s regex engine, following the flow through the intermediate angle-bracket preprocessing step.
• Rather than treating the angle-bracket rewrite as sanitization, Kira understood it is a pure syntax translation; it transforms delimiters but preserves, not constrains, the backtracking complexity of the original input.
• Kira flagged the complete absence of any timeout, length limit, or complexity check before the pattern is compiled and executed by re.findall(), identifying all conditions for a ReDoS sink.
• The finding was validated with the proof-of-concept above and reported to the NLTK maintainers, who shipped the fix in 3.10.0 (commit d8e4753).

This is the class of vulnerability that can go undetected in widely-deployed open-source libraries for extended periods, precisely because conventional tooling is not designed to reason about user-controlled pattern arguments.

Remediation

Upgrade to nltk 3.10.0 or later.

pip install "nltk>=3.10.0"

What the fix actually does

The patch (commit d8e4753) replaces Python’s stdlib re module (which has no timeout support) with the third-party regex library, which natively accepts a timeout= parameter. Both TokenSearcher.findall() and Text.findall() now take an explicit timeout argument defaulting to TOKENSEARCH_TIMEOUT (sourced from nltk.redos.DEFAULT_TIMEOUT, a deliberate system-wide bound applied to every caller-supplied-pattern sink in NLTK). The match call is wrapped in try-except: a TimeoutError is raised and propagated rather than allowing indefinite CPU saturation.

import regex  # replaces re; natively supports timeout=

TOKENSEARCH_TIMEOUT = nltk.redos.DEFAULT_TIMEOUT  # deliberate, tight bound

def findall(self, regexp, timeout=TOKENSEARCH_TIMEOUT):
    # ... angle-bracket preprocessing (unchanged) ...
    try:
        hits = regex.findall(regexp, self._raw, timeout=timeout)
    except TimeoutError:
        raise TimeoutError(
            f"TokenSearcher.findall exceeded its {timeout}s time limit"
        )
    return hits

If you cannot upgrade immediately, avoid passing user-supplied strings directly to Text.findall() or TokenSearcher.findall(). Apply an allowlist or pattern complexity check before input reaches NLTK, or wrap the call with Python’s signal-based timeout as a stopgap.

Verify your installed version with pip show nltk. If you use a lock file, confirm it does not pin an affected version transitively.

Key takeaways

• ReDoS is systematically underdetected. It doesn’t fit the injection or memory-safety patterns SAST was built for. Taint survives through preprocessing. The exploit is in regex structure, not data flow alone.
• Library code is part of your attack surface. The vulnerability is in NLTK, not your application, but your application inherits the risk. SCA scanning must be part of every pipeline.
• One request is enough. No auth required, no user interaction, CVSS 8.7 (CVSSv4). This is not a theoretical edge case.
• Upgrade to nltk 3.10.0. The fix is available and the path is a single pip upgrade.

References

• CVE: CVE-2026-80205 ↗
• Full advisory: GHSA-rrv8-h7p8-rx55 ↗
• Fix commit: d8e4753 ↗
• CWE-1333: Inefficient Regular Expression Complexity
• OWASP: Regular Expression Denial of Service (ReDoS)