User-Supplied Regex Passed to Python re Engine with No Timeout, One Pattern Hangs the Entire Process

Both sinks are in nltk/text.py. TokenSearcher.findall() at line 255 is the underlying engine; Text.findall() at line 620 delegates to it.

The method accepts a pattern in NLTK’s angle-bracket token syntax and rewrites it into standard regex group syntax before passing it to re.findall(). The rewrite is structural: it transforms delimiters but does not constrain backtracking complexity. A pattern such as <((a+)+)b> becomes (?:<(?:((a+)+)b)>) after preprocessing. The nested quantifiers remain intact and the resulting pattern is capable of catastrophic backtracking. The advisory confirms this directly:

The taint path runs from the caller’s pattern argument, through the angle-bracket rewriter, to re.compile() and re.findall() with no intermediate defense. Any application that passes user-controlled input to either method is vulnerable.

Proof of concept

The token string is 25 characters. The nested quantifiers ((a+)+) force the regex engine to explore an exponential number of ways to partition the leading run of a characters before reaching the conclusive mismatch at !. The process does not return. Longer inputs or deeper nesting make the hang permanent. The attack scales with the prefix length, not a fixed threshold.

Triggering via a network-exposed application

The vulnerability is a denial of service. A single request pins one CPU core and blocks the Python process or worker thread indefinitely. The impact depends on the deployment model:

In single-process deployments, one request makes the application completely unresponsive until the process is killed and restarted. In multi-worker deployments, attackers can exhaust the worker pool by sending one malicious request per worker. No authentication is required at the NLTK layer; the attack surface is any application that passes external input into either sink.

The CVSSv4 vector CVSS:4.0/AV:N/AC:L/AT:N/PR:N/UI:N/VC:N/VI:N/VA:H/SC:N/SI:N/SA:N (score 8.7) captures this precisely: network-reachable, no attack complexity, no attack requirements, no privileges, complete availability impact on the vulnerable component. The legacy CVSSv3.1 score (AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H) is 7.5.

re.findall() is not inherently dangerous; it appears in millions of safe programs. Useful detection requires confirming that user-controlled data reaches the pattern argument, that taint survives the angle-bracket preprocessing step without being treated as sanitization, and that the resulting pattern is structurally capable of catastrophic backtracking. That last step requires regex complexity analysis, which is separate from data-flow analysis and absent from most production SAST tools.

Application-level scanners never reach nltk/text.py. The application side may contain nothing more suspicious than text.findall(user_query), a single call on a trusted library object. SCA scanning flags the dependency once an advisory is published; SAST cannot reason about the interaction.

Kira traced the full data-flow path from caller input through the angle-bracket rewriter to the re engine, understood that the rewrite preserves rather than constrains backtracking complexity, and flagged the absence of any timeout or length check at the sink.

Upgrade to NLTK 3.10.0 or later. The fix, landed in 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 accept a configurable timeout argument defaulting to TOKENSEARCH_TIMEOUT (shared from nltk.redos.DEFAULT_TIMEOUT, a deliberate system-wide bound applied to every caller-supplied-pattern sink in NLTK). The call is wrapped in try-except: if the match exceeds the budget, TimeoutError is raised rather than allowing indefinite CPU saturation.

If an immediate upgrade is not possible, do not pass unsanitized user input to Text.findall() or TokenSearcher.findall(). Validate patterns against an allowlist or apply a timeout via Python’s signal module as a stopgap.