This is family of bugs in the LLVM's implementation of __cxa_demangle, found by libFuzzer+AddressSanitizer

Reproduce: 

1. Checkout fresh llvm with all the subprojects
2. cd llvm/projects/libcxxabi/src
3. Put the following into cxa_demangle_fuzzer.cpp
#include <stdint.h>
#include <stddef.h>
#include <string.h>
extern "C" char *
__cxa_demangle(const char *mangled_name, char *buf, size_t *n, int *status);

extern "C" int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) {
  char *str = new char[size+1];
  memcpy(str, data, size);
  str[size] = 0;
  __cxa_demangle(str, 0, 0, 0);
  delete [] str;
  return 0;
}


4. Using the fresh clang build the fuzzer: 
clang++ -std=c++11 -g   cxa_demangle.cpp -I../include cxa_demangle_fuzzer.cpp  -fsanitize=address -fsanitize-coverage=edge  -o cxa_demangler_fuzzer  ../../../lib/Fuzzer/*.cpp

5. Run the fuzzer on 20 CPUs:
mkdir CORPUS
./cxa_demangler_fuzzer CORPUS -jobs=20

If you've done everything correctly, you should see something like this in fuzz-0.log:
#0      READ   units: 307 exec/s: 0
#307    INITED cov: 3142 units: 222 exec/s: 0
#308    NEW    cov: 3760 units: 223 exec/s: 0 L: 9 MS: 1 ChangeByte-
#323    NEW    cov: 3947 units: 224 exec/s: 0 L: 26 MS: 1 ChangeBit-
#398    NEW    cov: 4062 units: 225 exec/s: 0 L: 32 MS: 1 InsertByte-


Then very soon you will start seeing bug report like these:

==27016==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x6030001211af at pc 0x000000531239 bp 0x7ffc0ea04930 sp 0x7ffc0ea04928
READ of size 1 at 0x6030001211af thread T0
    #0 0x531238 in std::basic_string<char, std::char_traits<char>, __cxxabiv1::(anonymous namespace)::malloc_alloc<char> > __cxxabiv1::(anonymous namespace)::base_name<std::basic_string<char, std::char_traits<char>, __cxxabiv1::(anonymous namespace)::malloc_alloc<char> > >(std::basic_string<char, std::char_traits<char>, __cxxabiv1::(anonymous namespace)::malloc_alloc<char> >&) cxa_demangle.cpp:2902:13


==27111==ERROR: AddressSanitizer: heap-use-after-free on address 0x60800004ccb0 at pc 0x0000004e6546 bp 0x7ffe760079c0 sp 0x7ffe760079b8
WRITE of size 4 at 0x60800004ccb0 thread T0
    #0 0x4e6545 in __gnu_cxx::__exchange_and_add(int volatile*, int) /usr/lib/gcc/x86_64-linux-gnu/4.8/../../../../include/c++/4.8/ext/atomicity.h:49:12
    #1 0x4e6274 in __gnu_cxx::__exchange_and_add_dispatch(int*, int) /usr/lib/gcc/x86_64-linux-gnu/4.8/../../../../include/c++/4.8/ext/atomicity.h:82:14


==39153==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7ffdde2c91f0 at pc 0x00000049cee9 bp 0x7ffdde2c5180 sp 0x7ffdde2c4938
READ of size 22300696 at 0x7ffdde2c91f0 thread T0
    #0 0x49cee8 in __asan_memcpy /usr/local/google/home/kcc/llvm/projects/compiler-rt/lib/asan/asan_interceptors.cc:411:3
    #1 0x541795 in std::char_traits<char>::copy(char*, char const*, unsigned long) /usr/lib/gcc/x86_64-linux-gnu/4.8/../../../../include/c++/4.8/bits/char_traits.h:271:40


Attaching a small set of inputs that trigger different bugs

Deleted: dedups.tgz 882 bytes

dedups.tgz 882 bytes Download

One more case:
==17453==ERROR: AddressSanitizer: SEGV on unknown address 0x00000049d0dd (pc 0x0000004e654d bp 0x7ffe49f7ef50 sp 0x7ffe49f7ef10 T0)
==17453==The signal is caused by a WRITE memory access.
    #0 0x4e654c in __gnu_cxx::__exchange_and_add(int volatile*, int) /usr/lib/gcc/x86_64-linux-gnu/4.8/../../../../include/c++/4.8/ext/atomicity.h:49:12
    #1 0x4e6274 in __gnu_cxx::__exchange_and_add_dispatch(int*, int) /usr/lib/gcc/x86_64-linux-gnu/4.8/../../../../include/c++/4.8/ext/atomicity.h:82:14
    #2 0x4e6061 in std::basic_string<char, std::char_traits<char>, __cxxabiv1::(anonymous namespace)::malloc_alloc<char> >::_Rep::_M_dispose(__cxxabiv1::(anonymous namespace)::malloc_alloc<char> const&) /usr/lib/gcc/x86_64-linux-gnu/4.8/../../../../include/c++/4.8/bits/basic_string.h:245:12

Deleted: crash-78f87224eac502cac4299f0a50eba6d85f324aea 116 bytes

crash-78f87224eac502cac4299f0a50eba6d85f324aea 116 bytes View Download

I wonder what the right approach is to fixing these bugs.  In particular, Kate Stone is working on a "fast demangler" for LLDB.  A (possibly slightly out-of-date?) version of it is in tree at llvm.org, but apparently it fixes some stack overflows and is ~10x faster.

Should we move it to LLVM proper, aim to harden it, maybe build an llvm-c++filt using it, and share it somehow with libcxxabi, rather than hacking on the version currently in libcxxabi?  Also, how can/should we share the implementation between LLVM and libc++abi?

Clearly, having a single well tested and hardened implementation is preferable 
over having two poorly tested.
Otherwise I am afraid I don't have good recommendation here. 

+ganna@apple.com -- here is an example of libFuzzer usage. 

banty, dexonsmith, we will publicly disclose this set of bugs
~ 90 days from now (~Aug 8), please try to fix before that. 

There are several reasons for this strict deadline: 
* We are holding back other related fuzzing activities in order to not disclose these bugs accidentally. 
* Other users of __cxa_demangle have already disclosed the fact of the bug
which makes the bug easy to find, see CVE-2016-2430 and 
https://android.googlesource.com/platform/system/core/+/ad54cfed4516292654c997910839153264ae00a0

Attached is a tentative patch, can you resume some fuzzing after applying it?

Updated patch with another fix (I continue the fuzzing on my side as well).

I won't get back to it until next week, but I am pretty sure you can run fuzzing yourself (according to #11 -- you already do). 
If you find more bugs please attach the reproducers and the reports here, 
for bookkeeping and for regression tests)

+thakis, FYI (Context: https://github.com/nico/hack/tree/master/demumble)

New crashes

Deleted: new.tgz 838 bytes

new.tgz 838 bytes Download

Updated patch

Deleted: 0001-Fix-various-ASAN-failures-found-by-libfuzzer.patch 5.5 KB

0001-Fix-various-ASAN-failures-found-by-libfuzzer.patch 5.5 KB Download

dexonsmith: majnemer has opinions on demanglers (he doesn't like the one in libcxxabi much from what I understand). Maybe Kate wants to talk to him. I agree it'd be nice if the llvm project had just one demangler :-)

Before trying to fix the one in libcxxabi I considered the "fast" one in LLDB. On my machine it is ~8x faster, which makes it appealing.
However it does not handle as many cases as the existing one, and more concerning, fuzzing it with ASAN triggered more cases of failure than the libcxxabi one, and more quickly.

+majnemer for his opinions. 

>> fuzzing it with ASAN triggered more cases of failure than the libcxxabi one
ouch

Libc++'s structure is problematic, it is difficult for mangling experts to reason about changes to it. I'm not sure that refactoring it will be too different from rewriting it.

The LLDB demangler doesn't seem very careful, a cursory glance seems to find some bugs; I cannot see how this dereference has been checked apriori:
https://github.com/llvm-mirror/lldb/blob/2b5961c64746fbf68e8dc4d3ace3a938c4a98db3/source/Core/FastDemangle.cpp#L618

The LLDB demangler also observes it's own output:
https://github.com/llvm-mirror/lldb/blob/2b5961c64746fbf68e8dc4d3ace3a938c4a98db3/source/Core/FastDemangle.cpp#L415

I'm uneasy at the prospect it looking at what it's already emitted.  The libc++ demangler does similar things (https://github.com/llvm-mirror/libcxxabi/blob/master/src/cxa_demangle.cpp#L1922) and it makes me equally uneasy...

I believe we need to put together a new demangler which is continuously fuzz tested from the first line of code and structured so that it doesn't try to examine it's own output.

>> continuously fuzz tested from the first line of code
can't +1 hard enough.
It might actually be less effort than fixing the older ones. 

FYI, I've started working on a new implementation of __cxa_demangle.  No ETA on when it will be done, I'm doing this in my 20% time ;)

> FYI, I've started working on a new implementation of __cxa_demangle.  No ETA on when it will be done, I'm doing this in my 20% time ;)

This sounds great!  Ideally you'll be able to create something with the speed of LLDB, the scope of libc++abi, and the hardness of int main(){}.

Unfortunately, it's irrelevant for getting a fix to customers before kcc discloses the vulnerabilities.  We'll have to fix the old one in the meantime (at least internally).

kcc: Mehdi ran the fuzzer+asan overnight on the most recently attached patch and it seems clean.  Have you tried to run anything on it?  Is this fixed?

If so, I suggest you disclose other LLVM community members that vend libc++abi (if you haven't already) and they can test this patch as well.  Mehdi can commit the patch to ToT coincidently with disclosure (if majnemer hasn't ripped it out by then); in the meantime, we'll apply it internally and figure out how to get it to customers.

Did you run with lsan enabled (lsan does not work on Mac, so you have to use Linux). 
There are easy to find leak in llvm/projects/libcxxabi/src/cxa_demangle.cpp:4972:47

W/o lsan enabled I observe a SEGV (null deref) 

>> I suggest you disclose other LLVM community members that vend libc++abi (if you haven't already)
I don't know anyone outside of Google who uses this code and don't know how to reach them. 

>> Mehdi can commit the patch to ToT coincidently with disclosure
That's up to you.
It would be nice if you also create a cmake plumbing so that one can 
"make cxa_demangler_fuzzer" -- I will than add it to the llvm fuzzing bot. 

I don't have a linux box setup, so no I didn't run with lsan. I assume other tools should be able to find leaks though? Maybe the problem is that tools need to interact with libFuzzer?

If you have other tools (e.g. "leaks"?) you have two options: 

1. Run the tool on the corpus w/o fuzzing
(build the fuzz target in the build mode supported by the tool in question). 
2. Integrate such a tool with libFuzzer. 

For this case 1. should be enough. Try to see if "leaks" can find leaks for you on your existing corpus. And check if you see leaks on inputs from #24

I also observe another use-after-free, repro attached. 
Do you see any of these? 
Weren't you been able to find them with fuzzing? 
These are pretty shallow, I can see them after 2-3 minutes of fuzzing on 20 CPUs.

Deleted: crash-ae4a366bb4b78e9cf8ac3d30924ed4aede2ceeb8 132 bytes

crash-ae4a366bb4b78e9cf8ac3d30924ed4aede2ceeb8 132 bytes View Download

Ignore #28, I was apparently using an older patch. 
With the patch from #15 I still see NULL derefs and leaks 

> Ignore #28, I was apparently using an older patch. 

That makes sense of it!

> With the patch from #15 I still see NULL derefs and leaks 

These are bugs, but they aren't exploitable security flaws, are they?  (Not saying we shouldn't fix them; I'm just wondering about priority, given that majnemer is planning to write a new one from scratch.)

They are not easy to exploit (unless you have a DOS attack vector). 
But they also prevent us from doing efficient fuzzing.
It's up to you whether you want to deal with them ATM

I haven't seen the nullptr deref while fuzzing (I only have one core on my laptop to fuzz, and by the way I can't get more than one worker on Darwin anyway.)

I think I suffer from the leaks as after some time I see:

> Signal to main thread failed (non-linux?). Exiting.

which is triggered when we get more than 2GB of resident memory if I read the code correctly.

(I'm not sure why the #ifdef __linux__ was OK to be committed in LLVM like that, ISTM that the Fuzzer library wasn't carefully reviewed on the portability aspect)

>> I haven't seen the nullptr deref while fuzzing
Do you see it now on attached file?

==10766==ERROR: AddressSanitizer: SEGV on unknown address 0x000000000000 (pc 0x0000004fc7ae bp 0x7ffdb0542ab0 sp 0x7ffdb0542a80 T0)
==10766==The signal is caused by a READ memory access.
==10766==Hint: address points to the zero page.
    #0 0x4fc7ad in std::basic_string<char, std::char_traits<char>, __cxxabiv1::(anonymous namespace)::malloc_alloc<char> >::size() const /usr/lib/gcc/x86_64-linux-gnu/4.8/../../../../include/c++/4.8/bits/basic_string.h:716:26
    #1 0x4fa473 in std::basic_string<char, std::char_traits<char>, __cxxabiv1::(anonymous namespace)::malloc_alloc<char> >::empty() const /usr/lib/gcc/x86_64-linux-gnu/4.8/../../../../include/c++/4.8/bits/basic_string.h:812:22
    #2 0x4ff1aa in char const* __cxxabiv1::(anonymous namespace)::parse_nested_name<__cxxabiv1::(anonymous namespace)::Db>(char const*, char const*, __cxxabiv1::(anonymous namespace)::Db&, bool*) projects/libcxxabi/src/cxa_demangle.cpp:4049:48
    #3 0x4f9841 in char const* __cxxabiv1::(anonymous namespace)::parse_name<__cxxabiv1::(anonymous namespace)::Db>(char const*, char const*, __cxxabiv1::(anonymous namespace)::Db&, bool*) projects/libcxxabi/src/cxa_demangle.cpp:4202:30
    #4 0x4f0125 in char const* __cxxabiv1::(anonymous namespace)::parse_encoding<__cxxabiv1::(anonymous namespace)::Db>(char const*, char const*, __cxxabiv1::(anonymous namespace)::Db&) projects/libcxxabi/src/cxa_demangle.cpp:4524:29
    #5 0x4e4b69 in void __cxxabiv1::(anonymous namespace)::demangle<__cxxabiv1::(anonymous namespace)::Db>(char const*, char const*, __cxxabiv1::(anonymous namespace)::Db&, int&) projects/libcxxabi/src/cxa_demangle.cpp:4698:33
    #6 0x4e389d in __cxa_demangle projects/libcxxabi/src/cxa_demangle.cpp:4961:5
    #7 0x54457d in LLVMFuzzerTestOneInput projects/libcxxabi/src/cxa_demangle_fuzzer.cpp:11:3

Deleted: crash-a9b9028f1fe4d2bc32edcc9953fb5af8f27b3d4c 111 bytes

crash-a9b9028f1fe4d2bc32edcc9953fb5af8f27b3d4c 111 bytes View Download

>>  think I suffer from the leaks as after some time I see:
Of course. 

>  Signal to main thread failed (non-linux?). Exiting.
svn up.
This code has changed, it does not have ifdef linux any more, 
may just work on OSX. 


>> ISTM that the Fuzzer library wasn't carefully reviewed  on the portability aspect

I don't think it was. 
But now Dan Liew from Apple side is helping fix that. (see his patches upstream)

>> I only have one core on my laptop to fuzz
>> I don't have a linux box setup
Eeeeh. 
1) you can get a VM with as many CPUs as you wish, fast and cheap. 
2) as soon as you commit the changes upstream (and add a build rule for cxa_demangler_fuzzer) we'll run it on a public linux bot with 8 CPUs

I don't reproduce the nullptr deref with this file:

../../../../ninja-R/bin/clang++ -std=c++11    cxa_demangle.cpp -I../include   -fsanitize=address  -fsanitize-coverage=edge    -o cxa_demangler_fuzzer  cxa_demangle_fuzzer.cpp ../../../lib/Fuzzer/Fuzzer*.cpp -O0 -isysroot /Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX10.12.sdk -I../../../lib/Fuzzer

$ ./cxa_demangler_fuzzer ~/Downloads/crash-a9b9028f1fe4d2bc32edcc9953fb5af8f27b3d4c.txt 
INFO: Seed: 883929721
./cxa_demangler_fuzzer: Running 1 inputs 1 time(s) each.
/Users/amini/Downloads/crash-a9b9028f1fe4d2bc32edcc9953fb5af8f27b3d4c.txt ... 5 ms

Crashes reliably for me. 
Maybe you forgot to attach the latest patch? 
Or there is some difference between Mac and Linux or libc++ and libstdc++... 

I don't even get it to crash *without any patch* on this test case. So it can be a difference between our platform or the stdlib.

FYI: I am planing to make this bug public on Monday Aug 8. 

Please CC me when you do so, I have a patch to commit at this time.

Removing restrict-view. 

Committed r278579.

After the above fix: on linux I hit a leak right away: 
Direct leak of 12 byte(s) in 1 object(s) allocated from:
    #0 0x4c1afe in realloc
    #1 0x4f1663 in __cxa_demangle cxa_demangle.cpp:5012:47
    #2 0x5215f8 in LLVMFuzzerTestOneInput cxa_demangle_fuzzer.cpp:11:3

With lsan disabled the fuzzer is running for 3 minutes / 20 cores w/o new crashes. 
Great improvement!!! 

Yes I should have mentioned that I fixed *crasher* (ASAN) only (I don't believe LSAN does not work on OSX), and only on Darwin, and with libc++ only.

You don't need lsan to reproduce the leak, at least on linux: 

% cat leak.cpp 
#include <stddef.h>
extern "C" char *
__cxa_demangle(const char *mangled_name, char *buf, size_t *n, int *status);
int main() { while(true)  __cxa_demangle("a", 0, 0, 0); }

% clang++ -std=c++11 leak.cpp cxa_demangle.cpp -I ../include -o leak-repro && ./leak-repro


Watch the process in top, you will see that it will eat all RAM over time. 

Yes, I mentioned in comment 32 above that I was seeing the leak (the process stops at some point), but without LSAN it is not trivial to figure which cases leaks (I think)

Either https://developer.apple.com/library/ios/documentation/Performance/Conceptual/ManagingMemory/Articles/FindingLeaks.html
or see the stack trace in #43 
(if you care, of course)

But the Instruments leak checker will end for the process to finish, while here we'd like to run between each iteration of the fuzzier, which occurs in-process?
I'm missing a piece: I just assumed that libFuzzer had a special integration with LSAN.

If you want to find a leak with libFuzzer -- yes, you better use lsan.
Although it's often the case that the leak input is added to the corpus while fuzzing, and then you can run any leak detector on the inputs in the corpus w/o fuzzing. 
In this case the reproducer for the leak is "a"

the leak is still there. any interest in fixing it? 
Should I report it to the llvm bug tracker now? 

There are also inputs (<= 128 bytes) that take 4Gb to process. 
Are those interesting? 

It is not in my immediate list of priority. Reporting them on llvm.org seems appropriate anyway! 
Thanks

https://llvm.org/bugs/show_bug.cgi?id=31030
https://llvm.org/bugs/show_bug.cgi?id=31031

Declaring this one fixed.