Re: buffer overflow in regcomp and a way to find more of those

[Konstantin Serebryany <konstantin.s.serebryany@gmail.com>]

On Fri, Mar 20, 2015 at 7:20 PM, Rich Felker <dalias@libc.org> wrote:
> On Fri, Mar 20, 2015 at 07:14:33PM -0700, Konstantin Serebryany wrote:
>> >
>> > Sorry to keep bombarding you with questions.
>>
>> You are more than welcome!
>>
>> > One more: is it only asan
>> > that needs dynamic linking? If we're willing to drop asan for now and
>> > just rely on musl itself crashing for heap corruption (musl does a
>> > good job of detecting it usually), can the necessary coverage stuff
>> > still work with static linking?
>>
>> I think it can with a reasonable additional work, but not out of the box.
>> The compiler instrumentation in clang clearly does not care about
>> dynamic vs static linking.
>> If you build the source with "-fsanitize=leak -fsanitize-coverage=4
>> -O1" the compiler will not insert any of the asan instrumentation
>> and only insert calls to a couple of functions needed for coverage.
>> Then, instead of linking with the full asan+coverage run-time, you
>> will need a very simple re-implementation of coverage-only runtime.
>
> Could the existing runtime be used, just stripped down?

Yes, but for the basic functionality needed by the fuzzer it's simpler
to write it from scratch, see below:

========================================================
svn co http://llvm.org/svn/llvm-project/llvm/trunk/lib/Fuzzer
cat <<EOF >cov-minimal-rt.c
static long counter;
void __sanitizer_cov_with_check(int *guard) {
  if (*guard == 0) {
    counter++;
    *guard=1;
  }
}
long __sanitizer_get_total_unique_coverage() { return counter; }
void __sanitizer_cov_module_init() {}
void __sanitizer_reset_coverage(){}
void __sanitizer_get_coverage_guards(){}
void __sanitizer_get_number_of_counters(){}
void __sanitizer_update_counter_bitset_and_clear_counters(){}
void __sanitizer_set_death_callback(){}
EOF

clang -std=c++11 -c Fuzzer/Fuzzer*.cpp -I Fuzzer
clang -std=c++11  -fsanitize=leak -fsanitize-coverage=3 -mllvm
-sanitizer-coverage-block-threshold=0  Fuzzer/test/SimpleTest.cpp -c
clang -c cov-minimal-rt.c
clang++ *.o
./a.out
========================================================
Seed: 1285924057
Shuffle: Size: 1 prefer small: 1
#1      cov: 5  bits: 0 exec/s: 0
Shuffle done: 1 IC: 5
#2      cov: 7  bits: 0 exec/s: 0
#2      NEW: 7 B: 0 L: 64 S: 2 I: 0
#4      cov: 7  bits: 0 exec/s: 0
#8      cov: 7  bits: 0 exec/s: 0
#16     cov: 7  bits: 0 exec/s: 0
#32     cov: 7  bits: 0 exec/s: 0
#64     cov: 7  bits: 0 exec/s: 0
#128    cov: 7  bits: 0 exec/s: 0
#256    cov: 7  bits: 0 exec/s: 0
#512    cov: 7  bits: 0 exec/s: 0
#1024   cov: 7  bits: 0 exec/s: 0
#2048   cov: 7  bits: 0 exec/s: 0
#2107   NEW: 11 B: 0 L: 64 S: 3 I: 0
#2153   NEW: 12 B: 0 L: 1 S: 4 I: 1     H       1: 72
#4096   cov: 12 bits: 0 exec/s: 0
#8192   cov: 12 bits: 0 exec/s: 0
#16384  cov: 12 bits: 0 exec/s: 0
#18091  NEW: 15 B: 0 L: 2 S: 5 I: 4     Hi      2: 72 105
#18122  NEW: 17 B: 0 L: 4 S: 6 I: 0     Hi?i    4: 72 105 8 105
Found the target, exiting

The recently added afl-style counters
(https://code.google.com/p/address-sanitizer/wiki/AsanCoverage#Coverage_counters)
are a bit more involved, but the basic bool-per-edge is quite enough
in most cases.

The fuzzer itself is written in C++ and uses STL (probably, not the
best idea, but it makes the experiments simpler).
Can't tell if it will be a problem with musl, but after all the fuzzer
itself is also trivial (as well as the entire concept)

>
>> But, my previous experience with running fuzzers w/o memory bug
>> detectors (asan, or others)
>> suggests that this is a bad idea. Memory bugs tend to accumulate and
>> show up in the following iterations (if at all).
>
> Well static linking with musl does not impose any constraint on
> redefining functions, so you could easily use a debugging malloc that
> lines up each allocation to end on a page boundary with a guard page
> after it.

Yea... This will slowdown fuzzing and guard pages only protect you
from overflow in one direction (ether left, of right, but not both).
But this is better than nothing.

> This would of course be slow and use lots of memory but
> would catch all heap overflows. And -fstack-protector-all would catch
> most stack-based overflows.

Only stack-overflow-write by a small amount, but yes, better than nothing.

BTW, writing a minimalistic asan run-time as part of musl should be a
matter of a couple of hours.
Probably much faster than making the current monster work with static linking.
I'd be happy to help with such.

--kcc