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

What happened

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 NLP services 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 textbook Regular Expression Denial of Service (ReDoS). An attacker who controls the pattern argument can craft a regex that causes Python’s interpreter to explore an exponential number of partial match states before conclusively failing saturating a CPU core and blocking the entire process for as long as the input holds, which can be indefinite.

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() (lines 313–340 in 3.9.4) is the underlying engine; Text.findall() (lines 728–756) 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 a 25-character string ending in ! instead of b. The nested quantifiers ((a+)+) force the engine to enumerate an exponential number of ways to partition the leading run of a characters before reaching the conclusive mismatch. One request, one core, indefinite saturation.

The 25-character string is illustrative. Longer inputs or deeper quantifier nesting make the hang permanent in practice. The attack is not length-gated it scales with how greedily the nested groups can partition the prefix.

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.

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-assisted code security platform.

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 rewrite as sanitization, Kira understood it is a syntax translation that 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, identifying the 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.

This is the class of vulnerability that lives undetected in widely-deployed open-source libraries for years precisely because conventional tooling is not built to reason about it.

Remediation

Upgrade to nltk 3.10.0 or later.

pip install "nltk>=3.10.0"

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.

Verify your installed version with pip show nltk. If you use a lock file, check 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 7.5. 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

• Full advisory: GHSA-rrv8-h7p8-rx55 ↗
• CWE-1333: Inefficient Regular Expression Complexity
• OWASP: Regular Expression Denial of Service