Circumventing Fuzzing Roadblocks with Compiler Transformations

[laf....@gmail.com]

We published a blog post about the idea of using an LLVM pass to increase code coverage by rewriting comparisons.

Most importantly, we rewrite the code generated for integer comparisons in a way which lets afl figure out the constant on its on.

Furthermore, we make the discovery of paths in the presence of memcmp/strcmp calls and switch statements easier.

Checkout the blog post here https://lafintel.wordpress.com/2016/08/15/circumventing-fuzzing-roadblocks-with-compiler-transformations/

and the source code here https://gitlab.com/laf-intel/laf-llvm-pass

[Michal Zalewski]

> https://lafintel.wordpress.com/2016/08/15/circumventing-fuzzing-roadblocks-with-compiler-transformations/
> and the source code here https://gitlab.com/laf-intel/laf-llvm-pass

Very cool :-)

Do you wish the code to get integrated with afl-clang-fast, or do you
prefer to maintain it as a separate project?

Cheers,
/mz

[laf....@gmail.com]

Integrating the code with afl-clang-fast is the preferred option for us.

[Konstantin Serebryany]

This blog post inspired me to implement something similar but simpler in Clang/libFuzzer:

* instrument all cmp instructions with a callback that receives both cmp arguments

* in the callback compute (caller_pc&4095) | (popcnt(Arg1 ^ Arg2) << 12) and use this value to set a bit in a bitset

* every new observed bit in the bitset is treated as new coverage. 

(this is some form of value profiling, so the flag is called -use_value_profile=1)

http://llvm.org/viewvc/llvm-project?view=revision&revision=278839

The results are very nice. 

This approach cracks several puzzles that most other approaches don't.

E.g. these 3 puzzles are solved w/o path profiling and w/o auto-generated dictionaries:

https://github.com/llvm-mirror/llvm/blob/master/lib/Fuzzer/test/FullCoverageSetTest.cpp

https://github.com/llvm-mirror/llvm/blob/master/lib/Fuzzer/test/SimpleCmpTest.cpp 

https://github.com/llvm-mirror/llvm/blob/master/lib/Fuzzer/test/MemcmpTest.cpp

(The first one is especially hard)

I've also tried it on the libpng fuzzer seeded with a single small png file (no dictionary, no crc bypass)

After 30 minutes of fuzzing on 10 CPUs the difference in edge coverage was almost 50%.  

The instrumentation is available in fresh clang with  -fsanitize-coverage=edge,trace-cmp

http://clang.llvm.org/docs/SanitizerCoverage.html#tracing-data-flow

AFL should be able to use this instrumentation too. 

All you need to do is to implement 4 functions in AFL:
void __sanitizer_cov_trace_cmp1(uint8_t Arg1, uint8_t Arg2);
void __sanitizer_cov_trace_cmp2(uint16_t Arg1, uint16_t Arg2);
void __sanitizer_cov_trace_cmp4(uint32_t Arg1, uint32_t Arg2);
void __sanitizer_cov_trace_cmp8(uint64_t Arg1, uint64_t Arg2);
and instrument the code with the above flag. 
 

--kcc 

--
You received this message because you are subscribed to the Google Groups "afl-users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to afl-users+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Michal Zalewski]

Hah :-) Thanks, this sounds interesting indeed (and pretty easy to integrate).

>> email to afl-users+...@googlegroups.com.

>> For more options, visit https://groups.google.com/d/optout.
>
>

> --
> You received this message because you are subscribed to the Google Groups
> "afl-users" group.
> To unsubscribe from this group and stop receiving emails from it, send an

> email to afl-users+...@googlegroups.com.

[Konstantin Serebryany]

Correction: for AFL you will need -fsanitize-coverage=trace-cmp,trace-pc

% head cmpmain.cc trace.c 

==> cmpmain.cc <==

int main(int argc, char **argv) { return argc == 3; }

==> trace.c <==

#include <stdio.h>

void __sanitizer_cov_trace_pc() {

  printf("PC: %p\n", __builtin_return_address(0));

}

void __sanitizer_cov_trace_cmp4(unsigned a, unsigned b) {

  printf("CMP: %u %u; PC=%p\n", a, b, __builtin_return_address(0));

}

% clang -fsanitize-coverage=trace-cmp,trace-pc cmpmain.cc -O2 -c && clang cmpmain.o trace.c  && ./a.out 

PC: 0x400518

CMP: 1 3; PC=0x400524

--kcc 

>> email to afl-users+unsubscribe@googlegroups.com.

>> For more options, visit https://groups.google.com/d/optout.
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "afl-users" group.
> To unsubscribe from this group and stop receiving emails from it, send an

> email to afl-users+unsubscribe@googlegroups.com.

> For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "afl-users" group.

To unsubscribe from this group and stop receiving emails from it, send an email to afl-users+unsubscribe@googlegroups.com.

[Tyler Nighswander]

For what it's worth, ForAllSecure has been using something like the following instrumentation for handling comparisons, it's similar to the popcnt but only compares matching bytes (rather than matching bits):

(assume ARG1 and ARG2 are the comparison args, and XMM1,XMM2 are saved off or free, and let's say EAX is a free register)

xor ARG1, ARG2
movd XMM1, ARG1
xor ARG1, ARG2
pxor XMM2, XMM2
pcmpeqb XMM1, XMM2
movd EAX, XMM1
and EAX, 0x01018080
shr EAX, 7
shl AX, 6
shr EAX, 6
xor [__afl_pref_loc], EAX

Not sure if that's useful, but might be worth seeing how that compares to the popcnt method. It is positional (matching the first byte is different from matching the last byte) which might be a win, though I'd guess they'd perform about the same.

(Will probably write this up in a blog or something soon, but thought it might be relevant)

To unsubscribe from this group and stop receiving emails from it, send an email to afl-users+...@googlegroups.com.

[Michal Zalewski]

Hey all,

Sorry for taking forever to get to this. Busy with real life :-(

Question for kcc - have you been seeing major coverage improvements
against real-world targets with that cmp instrumentation?

I've been playing with your trace-cmp feature with djpeg and readpng,
but in my admittedly crappy benchmarks, they go neck-to-neck in AFL,
at least for the first several hours. Tracing comparisons has a
noticeable perf impact (~15%), so I guess it actually gives us
something, but just enough to cancel out the drop? Or maybe I'm
testing wrong =)

It gets slightly ahead in some experiments, such as seeding djpeg /
readpng with a dummy (non-image) file in the starting corpus.

I'm compiling with -fsanitize-coverage=bb,trace-pc,trace-cmp. I'm
hooking all callbacks to code that compares every byte of the
parameters separately, and if the byte matches, sets some distinct
offset in the map. It does work with a sample puzzle program, and
afl-showmap is showing trace changes depending on how many bytes in a
32-bit cmp match.

The changes I made are based on the assumption that fuzzers don't have
a particularly hard time solving one-byte comparisons, and that it
keeps the bitmap density low (whereas popcnt or its positional
equivalent is more noisy). Maybe that's a bad assumption.

/mz

>> >> email to afl-users+...@googlegroups.com.

>> >> For more options, visit https://groups.google.com/d/optout.
>> >
>> >
>> > --
>> > You received this message because you are subscribed to the Google Groups
>> > "afl-users" group.
>> > To unsubscribe from this group and stop receiving emails from it, send an

>> > email to afl-users+...@googlegroups.com.

>> > For more options, visit https://groups.google.com/d/optout.
>>
>> --
>> You received this message because you are subscribed to the Google Groups "afl-users" group.

>> To unsubscribe from this group and stop receiving emails from it, send an email to afl-users+...@googlegroups.com.

>> For more options, visit https://groups.google.com/d/optout.
>
>
> --
> You received this message because you are subscribed to the Google Groups "afl-users" group.

> To unsubscribe from this group and stop receiving emails from it, send an email to afl-users+...@googlegroups.com.

[Konstantin Serebryany]

I've observed the most distinct result on libpng-1.2.56.

The exact repro steps: https://github.com/google/libfuzzer-bot/blob/master/libpng/png-clean-experiment.sh

I've tried fuzzing w/o any seeds and with one trivial valid png as a seed. 

With value profile it grows faster in the first seconds and after a night of running the difference in edge coverage is  > 50%. 

I've seen much less impressive, but reproducible improvements on some of the boringssl targets, capstone, and some others. 

And yes, my benchmarking is equally crappy. 

My hope is that soon we will be able to make more scientific

A/B experiments on all of the targets we have in Chromium. 

 

I've also tried other metrics instead of popcnt and they've all performed worse on my set of micro puzzles (which, of course, tells very little).

BTW, I've added another flavor of value profile: for division and array dereferences.

They perform very well on their respective micro puzzles: 

https://github.com/llvm-mirror/llvm/blob/master/lib/Fuzzer/test/DivTest.cpp

https://github.com/llvm-mirror/llvm/blob/master/lib/Fuzzer/test/LoadTest.cpp

But I have no evidence so far that they are useful for real targets (just did not have time to test properly)

 --kcc 

>> >> email to afl-users+unsubscribe@googlegroups.com.

>> >> For more options, visit https://groups.google.com/d/optout.
>> >
>> >
>> > --
>> > You received this message because you are subscribed to the Google Groups
>> > "afl-users" group.
>> > To unsubscribe from this group and stop receiving emails from it, send an

>> > email to afl-users+unsubscribe@googlegroups.com.

>> > For more options, visit https://groups.google.com/d/optout.
>>
>> --
>> You received this message because you are subscribed to the Google Groups "afl-users" group.

>> To unsubscribe from this group and stop receiving emails from it, send an email to afl-users+unsubscribe@googlegroups.com.

>> For more options, visit https://groups.google.com/d/optout.
>
>
> --
> You received this message because you are subscribed to the Google Groups "afl-users" group.

> To unsubscribe from this group and stop receiving emails from it, send an email to afl-users+unsubscribe@googlegroups.com.

> For more options, visit https://groups.google.com/d/optout.

--
You received this message because you are subscribed to the Google Groups "afl-users" group.

To unsubscribe from this group and stop receiving emails from it, send an email to afl-users+unsubscribe@googlegroups.com.

[Konstantin Serebryany]

One more real-life example where value profiling seems to change the game: woff2. 

Build instructions attached. 

libFuzzer and AFL are not capable of finding any interesting coverage w/o value profile and w/o initial corpus.

With value profiling both find quite a few edges in shot time.

./fuzzer-lf 

#0      READ units: 1
#1      INITED cov: 17 bits: 15 units: 1 exec/s: 0
#2      NEW    cov: 20 bits: 16 units: 2 exec/s: 0 L: 64 MS: 0 
#524288 pulse  cov: 24 bits: 16 units: 2 exec/s: 262144
#1048576        pulse  cov: 24 bits: 16 units: 2 exec/s: 209715
#2097152        pulse  cov: 24 bits: 16 units: 2 exec/s: 190650

./fuzzer-lf -use_value_profile=1
#1097712        NEW    cov: 156 vp: 960 bits: 201 units: 574 exec/s: 5461 L: 64 MS: 1 ChangeBinInt-
#1098937        NEW    cov: 156 vp: 961 bits: 201 units: 575 exec/s: 5467 L: 64 MS: 1 ChangeByte-
#1099677        NEW    cov: 158 vp: 966 bits: 213 units: 576 exec/s: 5443 L: 64 MS: 1 ChangeByte-
#1103587        NEW    cov: 173 vp: 989 bits: 228 units: 577 exec/s: 5436 L: 64 MS: 1 CopyPart-
#1105297        NEW    cov: 173 vp: 990 bits: 228 units: 578 exec/s: 5444 L: 64 MS: 1 ChangeBinInt-
#1105669        NEW    cov: 173 vp: 998 bits: 228 units: 579 exec/s: 5446 L: 64 MS: 3 ChangeBinInt-ChangeByte-ChangeBinInt-

rm -rf IN OUT; mkdir IN OUT; echo z > IN/z; ./afl/afl-fuzz -m none -i IN -o OUT ./fuzzer-afl-plain 

rm -rf IN OUT; mkdir IN OUT; echo z > IN/z; ./afl/afl-fuzz -m none -i IN -o OUT ./fuzzer-afl-vp