Subject: Stack overflow when processing "0?{77}{770}" extended regexp

From: Anatoly Trosinenko <[email-masked]>
Date: Sat, 22 Sep 2018 17:55:20 +0300

Hello,

When fuzzing GNU grep, I have found a stack overflow on processing a
simple extended regexp. It is reproduced with the latest commit from
master branch 51dacfb (Sep 19).

$ export LC_ALL=C
$ gdb -q --args ./grep -E "0?{77}{770}"
Reading symbols from ./grep...(no debugging symbols found)...done.
(gdb) r
Starting program: /path/to/grep -E 0\?\{77\}\{770\}
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".

Program received signal SIGSEGV, Segmentation fault.
0x00007ffff760230e in _int_malloc (av=av@entry=0x7ffff7959c40
<main_arena>, bytes=bytes@entry=4) at malloc.c:3557
3557    malloc.c: No such file or directory.
(gdb) bt
#0  0x00007ffff760230e in _int_malloc (av=av@entry=0x7ffff7959c40
<main_arena>, bytes=bytes@entry=4) at malloc.c:3557
#1  0x00007ffff76050fc in __GI___libc_malloc (bytes=4) at malloc.c:3057
#2  0x00007ffff766177b in re_node_set_alloc (size=<optimized out>,
set=0x7fffff7ff0d0) at regex_internal.c:963
#3  calc_eclosure_iter (new_set=new_set@entry=0x7fffff7ff170,
dfa=dfa@entry=0x555555788e70, node=116418, root=root@entry=0) at
regcomp.c:1682
#4  0x00007ffff7661af7 in calc_eclosure_iter
(new_set=new_set@entry=0x7fffff7ff200, dfa=dfa@entry=0x555555788e70,
node=<optimized out>, root=root@entry=0) at regcomp.c:1719
#5  0x00007ffff7661af7 in calc_eclosure_iter
(new_set=new_set@entry=0x7fffff7ff290, dfa=dfa@entry=0x555555788e70,
node=<optimized out>, root=root@entry=0) at regcomp.c:1719
#6  0x00007ffff7661af7 in calc_eclosure_iter
(new_set=new_set@entry=0x7fffff7ff320, dfa=dfa@entry=0x555555788e70,
node=<optimized out>, root=root@entry=0) at regcomp.c:1719
#7  0x00007ffff7661af7 in calc_eclosure_iter
(new_set=new_set@entry=0x7fffff7ff3b0, dfa=dfa@entry=0x555555788e70,
node=<optimized out>, root=root@entry=0) at regcomp.c:1719
#8  0x00007ffff7661af7 in calc_eclosure_iter
(new_set=new_set@entry=0x7fffff7ff440, dfa=dfa@entry=0x555555788e70,
node=<optimized out>, root=root@entry=0) at regcomp.c:1719
#9  0x00007ffff7661af7 in calc_eclosure_iter
(new_set=new_set@entry=0x7fffff7ff4d0, dfa=dfa@entry=0x555555788e70,
node=<optimized out>, root=root@entry=0) at regcomp.c:1719
#10 0x00007ffff7661af7 in calc_eclosure_iter
(new_set=new_set@entry=0x7fffff7ff560, dfa=dfa@entry=0x555555788e70,
node=<optimized out>, root=root@entry=0) at regcomp.c:1719
#11 0x00007ffff7661af7 in calc_eclosure_iter
(new_set=new_set@entry=0x7fffff7ff5f0, dfa=dfa@entry=0x555555788e70,
node=<optimized out>, root=root@entry=0) at regcomp.c:1719
#12 0x00007ffff7661af7 in calc_eclosure_iter
(new_set=new_set@entry=0x7fffff7ff680, dfa=dfa@entry=0x555555788e70,
node=<optimized out>, root=root@entry=0) at regcomp.c:1719
#13 0x00007ffff7661af7 in calc_eclosure_iter
(new_set=new_set@entry=0x7fffff7ff710, dfa=dfa@entry=0x555555788e70,
node=<optimized out>, root=root@entry=0) at regcomp.c:1719
#14 0x00007ffff7661af7 in calc_eclosure_iter
(new_set=new_set@entry=0x7fffff7ff7a0, dfa=dfa@entry=0x555555788e70,
node=<optimized out>, root=root@entry=0) at regcomp.c:1719
... and so on

Best regards
Anatoly