ReDoS in substitute() via :s command — user-supplied regex causes catastrophic backtracking (CWE-1333)

[gnsehfvlr]

Summary

pyvim's :s (substitute) command passes the user-typed search pattern directly to re.sub() without any validation. A user can type a catastrophic regex pattern (e.g. (a+)+$) that causes Python's regex engine to backtrack exponentially, freezing the editor process indefinitely.

Affected Version

pyvim 3.0.3 (latest)

Vulnerable Code

pyvim/commands/commands.py, line 723–726:

def get_transform_callback(search, replace, flags):
    SUBSTITUTE_ALL, SUBSTITUTE_ONE = 0, 1
    sub_count = SUBSTITUTE_ALL if 'g' in flags else SUBSTITUTE_ONE
    return lambda s: re.sub(search, replace, s, count=sub_count)  # ← search is raw user input

pyvim/commands/handler.py, line 33–35:

elif command in ('s', 'substitute'):
    flags = flags.lstrip('/')
    substitute(editor, range_start, range_end, search, replace, flags)

The search variable is parsed directly from what the user types in the : command line and passed to re.sub() with no validation or timeout.

Root Cause

re.sub() in Python's re module uses a backtracking NFA engine that exhibits exponential time complexity for certain regex patterns (nested quantifiers, alternation) on carefully crafted input. No timeout or safe-regex check is applied before executing the substitution.

Proof of Concept

Open pyvim and enter any file with aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa (30+ a characters) on a line. Then type the substitute command:

:s/(a+)+$/x

Measured freeze times (Python re.sub benchmark):

Input length	Time
20 as	0.09s
25 as	2.73s
30 as	88s
35 as	>1000s (estimated)

The editor process freezes completely and becomes unresponsive.

Other catastrophic patterns:

• ([a-zA-Z]+)*$
• (a|a?)+$
• (\w+\s?)+$

Impact

Any user of pyvim can accidentally (or intentionally) freeze their editor session by typing a substitute command with an ambiguous regex pattern. In a shared environment (e.g. a pyvim-based coding tool), this constitutes a local denial of service.

CVSS Score

5.5 MEDIUM — CVSS:3.1/AV:L/AC:L/PR:N/UI:R/S:U/C:N/I:N/A:H

Suggested Fix

Use the re2 library (linear-time regex engine) or apply a per-call timeout using signal.alarm / a thread-based timeout:

import re2  # linear-time, no backtracking
return lambda s: re2.sub(search, replace, s, count=sub_count)

Or validate the pattern before use:

import re2
def get_transform_callback(search, replace, flags):
    try:
        re2.compile(search)  # raises if pattern is unsafe/complex
    except re2.error:
        raise ValueError(f"Unsafe regex pattern: {search}")
    ...

Reporter

Younghun Lee — PYPI supply-chain vulnerability research