Bug 23008

Summary: Stack Overflow(Stack Exhaustion) in demangle related functions
Product: binutils Reporter: Dongliang Mu <mudongliangabcd>
Component: binutilsAssignee: Not yet assigned to anyone <unassigned>
Status: RESOLVED FIXED    
Severity: normal CC: matz, nickc, wuyuan5
Priority: P2    
Version: 2.30   
Target Milestone: ---   
Host: Target:
Build: Last reconfirmed:
Attachments: PoC to trigger stack exhaustion
Dockerfile for Ubuntu 14.04(GCC with AddressSanitizer)
Dockerfile for Debian Stable (Clang with AddressSanitizer)
Dockerfile for Debian Stable (GCC with AddressSanitizer)

Description Dongliang Mu 2018-03-27 17:33:00 UTC
Created attachment 10917 [details]
PoC to trigger stack exhaustion

One Stack Exhausting issue found in binutils-2.29 and 2.30.

The configuration of binutils is :

CFLAGS="-g -fsanitize=address" LDFLAGS="-fsanitize=address" ./configure
make

The trigger method is :

cd <root directory of installation>
./binutils/cxxfilt < poc

Then you will see message log in binutils 2.29,

==3711==ERROR: AddressSanitizer: stack-overflow on address 0x7fffa0a43fc8 (pc 0x000000476e18 bp 0x7fffa0a44850 sp 0x7fffa0a43fd0 T0)
    #0 0x476e17  (/home/jun/revision/testsuites/binutils-2.29/binutils/cxxfilt+0x476e17)
    #1 0x91170e  (/home/jun/revision/testsuites/binutils-2.29/binutils/cxxfilt+0x91170e)
    #2 0x91f24e  (/home/jun/revision/testsuites/binutils-2.29/binutils/cxxfilt+0x91f24e)
    #3 0x921a47  (/home/jun/revision/testsuites/binutils-2.29/binutils/cxxfilt+0x921a47)
    #4 0x900f13  (/home/jun/revision/testsuites/binutils-2.29/binutils/cxxfilt+0x900f13)
    #5 0x921316  (/home/jun/revision/testsuites/binutils-2.29/binutils/cxxfilt+0x921316)
    #6 0x92020d  (/home/jun/revision/testsuites/binutils-2.29/binutils/cxxfilt+0x92020d)
    #7 0x921a47  (/home/jun/revision/testsuites/binutils-2.29/binutils/cxxfilt+0x921a47)
    #8 0x900f13  (/home/jun/revision/testsuites/binutils-2.29/binutils/cxxfilt+0x900f13)
    #9 0x921316  (/home/jun/revision/testsuites/binutils-2.29/binutils/cxxfilt+0x921316)
    #10 0x92020d  (/home/jun/revision/testsuites/binutils-2.29/binutils/cxxfilt+0x92020d)
    #11 0x921a47  (/home/jun/revision/testsuites/binutils-2.29/binutils/cxxfilt+0x921a47)
    #12 0x900f13  (/home/jun/revision/testsuites/binutils-2.29/binutils/cxxfilt+0x900f13)
    #13 0x921316  (/home/jun/revision/testsuites/binutils-2.29/binutils/cxxfilt+0x921316)
    #14 0x92020d  (/home/jun/revision/testsuites/binutils-2.29/binutils/cxxfilt+0x92020d)
    #15 0x921a47  (/home/jun/revision/testsuites/binutils-2.29/binutils/cxxfilt+0x921a47)
    #16 0x900f13  (/home/jun/revision/testsuites/binutils-2.29/binutils/cxxfilt+0x900f13)
    ......

and message log in binutils 2.30:

Program received signal SIGSEGV, Segmentation fault.
0x00007ffff4e6040c in malloc () from /usr/lib/x86_64-linux-gnu/libasan.so.0
(gdb) info stack
#0  0x00007ffff4e6040c in malloc () from /usr/lib/x86_64-linux-gnu/libasan.so.0
#1  0x00000000006c7465 in xmalloc (size=32) at ./xmalloc.c:147
#2  0x000000000069f731 in string_need (s=0x7fffff7ff950, n=32) at ./cplus-dem.c:4906
#3  0x000000000069fc5a in string_append (p=0x7fffff7ff950, s=0x753f60 "(") at ./cplus-dem.c:4961
#4  0x000000000069cf75 in demangle_args (work=0x7fffffffe3b0, mangled=0x7fffffffe2c0, declp=0x7fffff7ff950) at ./cplus-dem.c:4578
#5  0x000000000069da72 in demangle_nested_args (work=0x7fffffffe3b0, mangled=0x7fffffffe2c0, declp=0x7fffff7ff950) at ./cplus-dem.c:4713
#6  0x0000000000697c48 in do_type (work=0x7fffffffe3b0, mangled=0x7fffffffe2c0, result=0x6006000eb5d0) at ./cplus-dem.c:3719
#7  0x000000000069b798 in do_arg (work=0x7fffffffe3b0, mangled=0x7fffffffe2c0, result=0x7fffff7ffb40) at ./cplus-dem.c:4332
#8  0x000000000069d60c in demangle_args (work=0x7fffffffe3b0, mangled=0x7fffffffe2c0, declp=0x7fffff7ffcc0) at ./cplus-dem.c:4659
#9  0x000000000069da72 in demangle_nested_args (work=0x7fffffffe3b0, mangled=0x7fffffffe2c0, declp=0x7fffff7ffcc0) at ./cplus-dem.c:4713
#10 0x0000000000697c48 in do_type (work=0x7fffffffe3b0, mangled=0x7fffffffe2c0, result=0x6006000eb630) at ./cplus-dem.c:3719
#11 0x000000000069b798 in do_arg (work=0x7fffffffe3b0, mangled=0x7fffffffe2c0, result=0x7fffff7ffeb0) at ./cplus-dem.c:4332
#12 0x000000000069d60c in demangle_args (work=0x7fffffffe3b0, mangled=0x7fffffffe2c0, declp=0x7fffff800030) at ./cplus-dem.c:4659
#13 0x000000000069da72 in demangle_nested_args (work=0x7fffffffe3b0, mangled=0x7fffffffe2c0, declp=0x7fffff800030) at ./cplus-dem.c:4713
#14 0x0000000000697c48 in do_type (work=0x7fffffffe3b0, mangled=0x7fffffffe2c0, result=0x6006000eb690) at ./cplus-dem.c:3719

One interesting point: The address sanitizer in gcc is enabled, but it does not detect this stack overflow/exhaustion in binutils-2.30. The same to the current master branch in binutils git repo.
Comment 1 Nick Clifton 2018-03-28 09:49:06 UTC
Hi Dongliang,

  Sorry - I am unable to reproduce this bug, even using 2.29 and/or the
  2.30 branch sources.

  Are you running on a machine with a small amount of memory ?  Or maybe
  you have a stack limit set ?

  Also I should note that since this problem appears to be associated with
  the C++ demangling functions provided by the libiberty library, you may
  want to report the problem on the GCC bugzilla system.  (The libiberty
  library is maintained by GCC, rather than by binutils).

Cheers
  Nick
Comment 2 Dongliang Mu 2018-03-28 15:02:57 UTC
Hi Nick,

first let me show my concrete instructions to convince you it is reproducible. And then I will post it to GCC Bugzilla.

```
wget https://ftp.gnu.org/gnu/binutils/binutils-2.29.tar.gz
tar -xvf binutils-2.29.tar.gz 
cd binutils-2.29/
CC=clang CFLAGS="-g -fsanitize=address" LDFLAGS="-fsanitize=address" ./configure
make
cd binutils/
ls
./cxxfilt < ~/Downloads/poc
```
Then you will see :

```
ASAN:DEADLYSIGNAL
=================================================================
==25076==ERROR: AddressSanitizer: stack-overflow on address 0x7ffeaf715ff8 (pc 0x00000042315c bp 0x7ffeaf716890 sp 0x7ffeaf716000 T0)
    #0 0x42315b in __asan::asan_malloc(unsigned long, __sanitizer::BufferedStackTrace*) (/home/mdl/Downloads/binutils-2.29/binutils/cxxfilt+0x42315b)
    #1 0x4d23cb in malloc (/home/mdl/Downloads/binutils-2.29/binutils/cxxfilt+0x4d23cb)
    #2 0x9289c7 in xmalloc /home/mdl/Downloads/binutils-2.29/libiberty/./xmalloc.c:147:12
    #3 0x8dfe15 in string_need /home/mdl/Downloads/binutils-2.29/libiberty/./cplus-dem.c:4906:21
    #4 0x8de7b8 in string_append /home/mdl/Downloads/binutils-2.29/libiberty/./cplus-dem.c:4961:3
    #5 0x8ebd1f in demangle_args /home/mdl/Downloads/binutils-2.29/libiberty/./cplus-dem.c:4578:7
    #6 0x8ee467 in demangle_nested_args /home/mdl/Downloads/binutils-2.29/libiberty/./cplus-dem.c:4713:12
    #7 0x8ce628 in do_type /home/mdl/Downloads/binutils-2.29/libiberty/./cplus-dem.c:3719:9
    #8 0x8edd4d in do_arg /home/mdl/Downloads/binutils-2.29/libiberty/./cplus-dem.c:4332:8
    #9 0x8eccac in demangle_args /home/mdl/Downloads/binutils-2.29/libiberty/./cplus-dem.c:4659:9
    #10 0x8ee467 in demangle_nested_args /home/mdl/Downloads/binutils-2.29/libiberty/./cplus-dem.c:4713:12
    #11 0x8ce628 in do_type /home/mdl/Downloads/binutils-2.29/libiberty/./cplus-dem.c:3719:9
    #12 0x8edd4d in do_arg /home/mdl/Downloads/binutils-2.29/libiberty/./cplus-dem.c:4332:8
    #13 0x8eccac in demangle_args /home/mdl/Downloads/binutils-2.29/libiberty/./cplus-dem.c:4659:9
    #14 0x8ee467 in demangle_nested_args /home/mdl/Downloads/binutils-2.29/libiberty/./cplus-dem.c:4713:12
```

Originally I reproduced this issue in Ubuntu 14.04.5 LTS. Now I test and successfully reproduce it in Debian Testing.

The same method to reproduce it in binutils-2.30. You will get the following error message:

```
ASAN:DEADLYSIGNAL
=================================================================
==25373==ERROR: AddressSanitizer: stack-overflow on address 0x7fff177ecff8 (pc 0x0000008dfe9b bp 0x7fff177ed3b0 sp 0x7fff177ed000 T0)
    #0 0x8dfe9a in demangle_args /home/mdl/Downloads/binutils-2.30/libiberty/./cplus-dem.c:4578:22
    #1 0x8e25e7 in demangle_nested_args /home/mdl/Downloads/binutils-2.30/libiberty/./cplus-dem.c:4713:12
    #2 0x8c27a8 in do_type /home/mdl/Downloads/binutils-2.30/libiberty/./cplus-dem.c:3719:9
    #3 0x8e1ecd in do_arg /home/mdl/Downloads/binutils-2.30/libiberty/./cplus-dem.c:4332:8
    #4 0x8e0e2c in demangle_args /home/mdl/Downloads/binutils-2.30/libiberty/./cplus-dem.c:4659:9
    #5 0x8e25e7 in demangle_nested_args /home/mdl/Downloads/binutils-2.30/libiberty/./cplus-dem.c:4713:12
    #6 0x8c27a8 in do_type /home/mdl/Downloads/binutils-2.30/libiberty/./cplus-dem.c:3719:9
    #7 0x8e1ecd in do_arg /home/mdl/Downloads/binutils-2.30/libiberty/./cplus-dem.c:4332:8
    #8 0x8e0e2c in demangle_args /home/mdl/Downloads/binutils-2.30/libiberty/./cplus-dem.c:4659:9
    #9 0x8e25e7 in demangle_nested_args /home/mdl/Downloads/binutils-2.30/libiberty/./cplus-dem.c:4713:12
    #10 0x8c27a8 in do_type /home/mdl/Downloads/binutils-2.30/libiberty/./cplus-dem.c:3719:9
    #11 0x8e1ecd in do_arg /home/mdl/Downloads/binutils-2.30/libiberty/./cplus-dem.c:4332:8
    #12 0x8e0e2c in demangle_args /home/mdl/Downloads/binutils-2.30/libiberty/./cplus-dem.c:4659:9
    #13 0x8e25e7 in demangle_nested_args /home/mdl/Downloads/binutils-2.30/libiberty/./cplus-dem.c:4713:12
```

If you have any problem to reproduce this issue, please let me know.
Comment 3 Nick Clifton 2018-03-28 15:26:43 UTC
Hi Dongliang,

> first let me show my concrete instructions to convince you it is reproducible.
> And then I will post it to GCC Bugzilla.
> 
> ```
> wget https://ftp.gnu.org/gnu/binutils/binutils-2.29.tar.gz
> tar -xvf binutils-2.29.tar.gz 
> cd binutils-2.29/
> CC=clang CFLAGS="-g -fsanitize=address" LDFLAGS="-fsanitize=address"
> ./configure
> make
> cd binutils/
> ls
> ./cxxfilt < ~/Downloads/poc

I followed this outline almost exactly and the problem did not occur.
The difference was that I used "CC=gcc" rather than "CC=clang".  I did
try using clang, but it would not run with the -fsanitize=address option.
Possibly something to do with the sanitization libraries that I have
installed on my machine.

Anyway - it looks like you have stumbled across a clang bug.  If possible,
please could you check that compiling with gcc does work for you, and if
so, please can you report this problem to the clang developers ?

Cheers
  Nick
Comment 4 Dongliang Mu 2018-03-28 17:53:10 UTC
Created attachment 10921 [details]
Dockerfile for Ubuntu 14.04(GCC with AddressSanitizer)

Dockerfile for Ubuntu 14.04LTS to prove it is reproducible
Comment 5 Dongliang Mu 2018-03-28 17:54:48 UTC
Created attachment 10922 [details]
Dockerfile for Debian Stable (Clang with AddressSanitizer)

Dockerfile to prove it is reproducible with Address Sanitizer in clang
Comment 6 Dongliang Mu 2018-03-28 17:59:33 UTC
When I try to reproduce this problem with Address Sanitizer in GCC, there are some wired errors when I compiled binutils:

```
/usr/bin/ld: ../bfd/.libs/libbfd.a(plugin.o): undefined reference to symbol 'dlsym@@GLIBC_2.2.5'
//lib/x86_64-linux-gnu/libdl.so.2: error adding symbols: DSO missing from command line
collect2: error: ld returned 1 exit status
```
And "Dockerfile for Ubuntu 14.04" is related with Address Sanitizer in GCC,
"Dockerfile for Debian Stable" is related with Address Sanitizer in Clang.
Comment 7 Nick Clifton 2018-03-29 07:12:17 UTC
Hi Dongliang,

> When I try to reproduce this problem with Address Sanitizer in GCC, there
> are some wired errors when I compiled binutils:

> /usr/bin/ld: ../bfd/.libs/libbfd.a(plugin.o): undefined reference to symbol
> 'dlsym@@GLIBC_2.2.5'

This is because the address sanitizer needs the "dl" library.  Change your
configure command line so that LDLFLAGS is defined as:

  LDFLAGS="-fsanitize=address -ldl"

That should fix the problem.

Cheers
  Nick
Comment 8 H.J. Lu 2018-03-29 12:51:58 UTC
(In reply to Nick Clifton from comment #7)
> Hi Dongliang,
> 
> > When I try to reproduce this problem with Address Sanitizer in GCC, there
> > are some wired errors when I compiled binutils:
> 
> > /usr/bin/ld: ../bfd/.libs/libbfd.a(plugin.o): undefined reference to symbol
> > 'dlsym@@GLIBC_2.2.5'

This is PR 22318 and the patch is at

https://gcc.gnu.org/ml/gcc-patches/2018-03/msg00647.html
Comment 9 Dongliang Mu 2018-03-29 14:47:07 UTC
Created attachment 10925 [details]
Dockerfile for Debian Stable (GCC with AddressSanitizer)
Comment 10 Dongliang Mu 2018-03-29 14:50:57 UTC
Hi, Nick:

Thank you for pointing out that issue. I have tested that issue on Debian Stable(GCC + AddressSanitizer, and Clang + AddressSanitizer) and attached three Dockerfiles to prove it is reproducible.

Now I will try to report this bug in GCC Bugzilla.

Finally, thanks for your good work, Nick.
Comment 11 Michael Matz 2018-04-04 12:59:10 UTC
All seems to work as designed.  The testcase contains a large number of 'F' characters, and demangling each one of them entails:

5  0x00000000005ec0f8 in demangle_nested_args (work=0x7fffffffd540, mangled=0x7fffffffd2a0, 
    declp=0x7fffff800050) at ../../libiberty/cplus-dem.c:4713
4713      result = demangle_args (work, mangled, declp);
#4  0x00000000005ea8f9 in demangle_args (work=0x7fffffffd540, mangled=0x7fffffffd2a0, declp=0x7fffff800050)
    at ../../libiberty/cplus-dem.c:4659
4659              if (!do_arg (work, mangled, &arg))
#3  0x00000000005eb99e in do_arg (work=0x7fffffffd540, mangled=0x7fffffffd2a0, result=0x7fffff7ffbe0)
    at ../../libiberty/cplus-dem.c:4332
4332      if (!do_type (work, mangled, work->previous_argument))
#2  0x00000000005cbf15 in do_type (work=0x7fffffffd540, mangled=0x7fffffffd2a0, result=0x6030000318d0)
    at ../../libiberty/cplus-dem.c:3719
3719              if (!demangle_nested_args (work, mangled, &decl)
#1  0x00000000005ec0f8 in demangle_nested_args (work=0x7fffffffd540, mangled=0x7fffffffd2a0, 
    declp=0x7fffff7ff370) at ../../libiberty/cplus-dem.c:4713
4713      result = demangle_args (work, mangled, declp);

That progresses *mangled by one character.  When compiled with clang, the above
sequence of five calls needs 3296 bytes on the stack.  The testcase
contains more than 2542 'F' characters in a row, and together that needs more
than 8MB of stack, leading to the abort.

When compiled with GCC -fsanitize-address the above sequence only needs 912
bytes on stack (per 'F' character), so it progresses until 
(gdb) p *mangled
$10 = 0x78b6cc <mbuffer+9196> 'F' <repeats 200 times>...
before segfaulting due to stack overflow (with clang it only gets until mbuffer+2550).

When compiled without sanitizer (with GCC) the above sequence of calls only
needs 400 bytes per stack.  The testcase contains 11586 'F' characters, so that
is within the normal stack limit and no problem occurs.

If the compiler is more clever (the above is with gcc-6 and -O0) then the
sequence of calls will need less stack space, and hence not reproduce the
problem.  I'm not sure if anything needs fixing, the demangler works as designed, you ask it to demangle a nested structure that's 11000 levels deep,
and a stack overflow occurs.  As expected.
Comment 12 yuanwu 2018-05-04 01:33:04 UTC
Hi Dongliang,
  my question is "Does this vulnerability affects binutils 2.26 ".  so I run your test program in Binutils version 2.26 ,the program result has no stack-overflow.

  but using 2.29 branch sources,the program result also has no stack-overflow (I am unable to reproduce this bug with the same linux system as you). so I am not sure whether this vulnerability affects binutils 2.26. Looking forward to your help
,thinks.
  my mother tongue is not English, sorry about my English , 
Cheers
  yuanwu
Comment 13 yuanwu 2018-05-04 01:33:12 UTC
Hi Dongliang,
  my question is "Does this vulnerability affects binutils 2.26 ".  so I run your test program in Binutils version 2.26 ,the program result has no stack-overflow.

  but using 2.29 branch sources,the program result also has no stack-overflow (I am unable to reproduce this bug with the same linux system as you). so I am not sure whether this vulnerability affects binutils 2.26. Looking forward to your help
,thinks.
  my mother tongue is not English, sorry about my English , 
Cheers
  yuanwu
Comment 14 Nick Clifton 2018-12-07 13:37:08 UTC
Fixed by recent merge with gcc libiberty sources.