[vim/vim] Fix C stack overflow in deeply nested regexp patterns (PR #20731)

2 views

Skip to first unread message

stevens

unread,

6:59 AM (4 hours ago) 6:59 AM

to vim/vim, Subscribed

###Problem
Deeply nested regexp groups can cause uncontrolled recursion in the regexp compiler and exhaust the C stack.

Details

The backtracking regexp compiler recursively parses parenthesized atoms without a depth limit.

Relevant code paths:

src/regexp_bt.c
- regatom() handles non-capturing groups:
```
case Magic('%'):
    ...
    case '(':
        ret = reg(REG_NPAREN, &flags);
```
- reg() recursively parses the group body.
- Capturing groups are bounded by NSUBEXP, but REG_NPAREN / \%(...\) groups do not consume a capture slot and therefore are not limited by that check.

The relevant distinction in reg() is:

if (paren == REG_PAREN)
{
    if (regnpar >= NSUBEXP)
        ...
}
else if (paren == REG_NPAREN)
{
    ret = regnode(NOPEN);
}

As a result, a pattern containing thousands of nested \%( groups causes repeated recursive calls:

regatom()
  -> reg(REG_NPAREN)
       -> regbranch()
          -> regpiece()
             -> regatom()
                -> reg(REG_NPAREN)
                   ...

This eventually exhausts the C stack before the existing size-based regexp checks can reliably reject the pattern.

I also observed the same vulnerability class in the NFA compiler:

src/regexp_nfa.c
- nfa_regatom() handles \%( by calling nfa_reg(REG_NPAREN).
- nfa_reg() also recursively parses nested groups without a depth limit.

So this is not only a backtracking-engine fallback issue; explicitly using regexpengine=2 can also be affected by the same class of input depending on build and runtime conditions.

PoC

Create /tmp/vim-regexp-stack-overflow-poc.vim:

set nomore
set regexpengine=1

call setline(1, 'x')
let nested = repeat('\%(', 20000) .. 'x' .. repeat('\)', 20000)
call search(nested)

qa!

./vim -Nu NONE --noplugin -n -es -S /tmp/vim-regexp-stack-overflow-poc.vim

###Solution
Limit recursive regexp parsing depth in both the backtracking and NFA compilers,

You can view, comment on, or merge this pull request online at:

https://github.com/vim/vim/pull/20731

Commit Summary

d673237 fix deeply nested regexp patterns may overflow the C stack

File Changes

(4 files)

Patch Links:

—
Reply to this email directly, view it on GitHub, or unsubscribe.
Triage notifications, keep track of coding agent tasks and review pull requests on the go with GitHub Mobile for iOS and Android. Download it today!
You are receiving this because you are subscribed to this thread.

Reply all

Reply to author

Forward

0 new messages