-sanitizer-coverage-prune-blocks=true and LibFuzzer

Hello LLVM devs,

I’m running lots of experiments with LibFuzzer these days – it’s an amazing tool!

I’ve noticed something weird while examining the effect of various coverage options: for one of my benchmarks, the fuzzer was achieving a higher total coverage before April 2016, when -sanitizer-coverage-prune-blocks became true by default (commit).

Here are the numbers from running the fuzzer with different options for a fixed amount of time.

#units #blocks #bits options
492 447 1666 -fsanitize-coverage=edge,indirect-calls,8bit-counters -mllvm -sanitizer-coverage-prune-blocks=false

135 447 754 -fsanitize-coverage=edge -mllvm -sanitizer-coverage-prune-blocks=false

58 103 185 -fsanitize-coverage=edge,indirect-calls,8bit-counters

135 447 754 -fsanitize-coverage=edge

Here, units is the number of test cases generated, blocks is the number of basic blocks covered (as measured by replaying the corpus using the -sanitizer-coverage-prune-blocks=false version), and bits is the number of bits from the 8bit-counters that were seen.

The outlier is the case where I use 8bit-counters and set -sanitizer-coverage-prune-blocks to true. There are two things I don’t understand: (1) why can the 8bit-counters perform worse than using edge coverage only, and (2) why does -sanitizer-coverage-prune-blocks affect the result so much?

Any ideas?

If needed, I can provide scripts to reproduce this (it’s a bit of work to clean them up, though). But maybe someone already has an idea why this could happen.

Cheers,
Jonas

Hello LLVM devs,

I'm running lots of experiments with LibFuzzer these days -- it's an
amazing tool!

Thank you!

I've noticed something weird while examining the effect of various
coverage options: for one of my benchmarks, the fuzzer was achieving a
higher total coverage before April 2016, when -sanitizer-coverage-prune-blocks
became true by default (commit
<https://github.com/llvm-mirror/llvm/commit/f593646d9ade6ab311cd6c55880bf3bdfc4b26a4&gt;
).

Here are the numbers from running the fuzzer with different options for a
fixed amount of time.

#units #blocks #bits options
492 447 1666 -fsanitize-coverage=edge,indirect-calls,8bit-counters
-mllvm -sanitizer-coverage-prune-blocks=false
135 447 754 -fsanitize-coverage=edge -mllvm
-sanitizer-coverage-prune-blocks=false
58 103 185 -fsanitize-coverage=edge,
indirect-calls,8bit-counters
135 447 754 -fsanitize-coverage=edge

Here, units is the number of test cases generated, blocks is the number of
basic blocks covered (as measured by replaying the corpus using the
-sanitizer-coverage-prune-blocks=false version), and bits is the number
of bits from the 8bit-counters that were seen.

The outlier is the case where I use 8bit-counters and set
-sanitizer-coverage-prune-blocks to true. There are two things I don't
understand: (1) why can the 8bit-counters perform worse than using edge
coverage only, and (2) why does -sanitizer-coverage-prune-blocks affect
the result so much?

Any ideas?

No idea out of the box, and we have not seen such effect.
But admittedly, our benchmarking is far from perfect.

Is this reproducible?
Fuzzing is a probabilistic business and one or even two runs don't prove
much.

If needed, I can provide scripts to reproduce this (it's a bit of work to
clean them up, though).

If you can do that, please do!

Note that I am going to change all of these coverage options soon.
The new thing will be
http://clang.llvm.org/docs/SanitizerCoverage.html#tracing-pcs-with-guards
It will replace regular (boolean) and 8-bit-counters coverage.

This will not affect sanitizer-coverage-prune-blocks

--kcc

Hello,

I’ve reproduced the behavior on two different machines. Attached is a script to do so. To use the script,

  • create an empty folder and copy both prune-blocks.sh and ff-http-parser.sh in there
  • ensure clang and clang++ are in your $PATH
  • cd /path/to/prune-blocks.sh
  • ./prune-blocks.sh

Let me know how it goes.

Yay, sounds exciting! I’ve done a couple experiments to measure the performance and effect of the different coverage options in the recent past. If you’re interested, I’d be happy to discuss off-list; simply send me an email.

Best,
Jonas

ff-http-parser.c (1.79 KB)

prune-blocks.sh (5.03 KB)

Exciting!

(btw, I’d prefer libfuzzer@googlegroups.com for such discussions, please start new topics there)

I can reproduce this too, but if i either increase FUZZER_TESTING_SECONDS to 600 or change seed=1 to seed=2 the problem is gone.
Looks like one of the binaries got simply unlucky with a particular seed.
You can observe it like this:

for S in 1 2 3 4 5 6; do ./target-asan-8bit-prune-build/fuzzer -seed=$S -runs=10000000 2>&1 | grep DONE &  done 

You mean a LLVM library has a separate mailing-list? Why?

Exciting!

(btw, I'd prefer libfuzzer@googlegroups.com for such discussions, please
start new topics there)

You mean a LLVM library has a separate mailing-list? Why?

Because the topic is very separate.

Can you clarify?

I thought is was about the development/debug/evolution/usability of http://llvm.org/svn/llvm-project/llvm/trunk/lib/Fuzzer/

Exciting!

(btw, I'd prefer libfuzzer@googlegroups.com for such discussions, please
start new topics there)

You mean a LLVM library has a separate mailing-list? Why?

Because the topic is very separate.

Can you clarify?

I thought is was about the development/debug/evolution/usability of
http://llvm.org/svn/llvm-project/llvm/trunk/lib/Fuzzer/

Yes, and this topic is substantially different from most other topics
discussed on llvm-dev.
We also have separate maliing lists for asan/tsan/msan

--kcc

Can you clarify?

I thought is was about the development/debug/evolution/usability of http://llvm.org/svn/llvm-project/llvm/trunk/lib/Fuzzer/

Yes, and this topic is substantially different from most other topics discussed on llvm-dev.

How so? If discussion on the development of a LLVM sub-library does not belong to llvm-dev, I wonder if the library belong to LLVM in the first place (add to this that libFuzzer does not use anything else in LLVM…).

We also have separate maliing lists for asan/tsan/msan

Is it for more anything else than historical reasons?

Exciting!

(btw, I'd prefer libfuzzer@googlegroups.com for such discussions,
please start new topics there)

You mean a LLVM library has a separate mailing-list? Why?

Because the topic is very separate.

Can you clarify?

I thought is was about the development/debug/evolution/usability of
http://llvm.org/svn/llvm-project/llvm/trunk/lib/Fuzzer/

Yes, and this topic is substantially different from most other topics
discussed on llvm-dev.

How so? If discussion on the development of a LLVM sub-library does not
belong to llvm-dev, I wonder if the library belong to LLVM in the first
place (add to this that libFuzzer does not use anything else in LLVM…).

There are users of libFuzzer that don't know much about LLVM and don't
need/want to.
They may want to subscribe to a mailing list that talks precisely about the
topic they want.

(I will clearly happy to answer any user on this, or any other maliing
list, if I see such message.

We also have separate maliing lists for asan/tsan/msan

Is it for more anything else than historical reasons?

Not only. there are asan/tsan users that don't use nor depend on LLVM.
(not true for msan though)

Please stop discussing this topic here -- we already hijacked the thread
from Jonas.
If you have further concerns, please start a new thread.

--kcc

Can you clarify?

I thought is was about the development/debug/evolution/usability of http://llvm.org/svn/llvm-project/llvm/trunk/lib/Fuzzer/

Yes, and this topic is substantially different from most other topics discussed on llvm-dev.

How so? If discussion on the development of a LLVM sub-library does not belong to llvm-dev, I wonder if the library belong to LLVM in the first place (add to this that libFuzzer does not use anything else in LLVM…).

There are users of libFuzzer that don’t know much about LLVM and don’t need/want to.
They may want to subscribe to a mailing list that talks precisely about the topic they want.

Right, so basically libFuzzer should not be in the LLVM repo.

(I will clearly happy to answer any user on this, or any other maliing list, if I see such message.

We also have separate maliing lists for asan/tsan/msan

Is it for more anything else than historical reasons?

Not only. there are asan/tsan users that don’t use nor depend on LLVM. (not true for msan though)

Please stop discussing this topic here – we already hijacked the thread from Jonas.

Well, no, you killed this thread by saying that it should be continued on a different mailing list.

Note that we’re talking here about the internals and the development of the library, not really about “how to use it", for instance we have a mailing list for people not interested in the development of clang: http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-users (i.e. users).

Exciting!

(btw, I'd prefer libfuzzer@googlegroups.com for such discussions,
please start new topics there)

You mean a LLVM library has a separate mailing-list? Why?

Because the topic is very separate.

Can you clarify?

I thought is was about the development/debug/evolution/usability of
http://llvm.org/svn/llvm-project/llvm/trunk/lib/Fuzzer/

Yes, and this topic is substantially different from most other topics
discussed on llvm-dev.

How so? If discussion on the development of a LLVM sub-library does not
belong to llvm-dev, I wonder if the library belong to LLVM in the first
place (add to this that libFuzzer does not use anything else in LLVM…).

There are users of libFuzzer that don't know much about LLVM and don't
need/want to.
They may want to subscribe to a mailing list that talks precisely about
the topic they want.

Right, so basically libFuzzer should not be in the LLVM repo.

For libFuzzer *development* having it in LLVM tree makes lots of sense
because
* libFuzzer is closely tied to the sanitizer coverage currently available
only in LLVM
* The LLVM testing infrastructure (lit+FileCheck) is very convenient.
But If there is a consensus that libFuzzer does not belong to the LLVM tree
I can delete it from here, no problem.

(I will clearly happy to answer any user on this, or any other maliing
list, if I see such message.

We also have separate maliing lists for asan/tsan/msan

Is it for more anything else than historical reasons?

Not only. there are asan/tsan users that don't use nor depend on LLVM.
(not true for msan though)

Please stop discussing this topic here -- we already hijacked the thread
from Jonas.

Well, no, you killed this thread by saying that it should be continued on
a different mailing list.

No, please re-read what I've said.

Hi,

Thanks a lot for the tests and the info!

Looks like one of the binaries got simply unlucky with a particular seed.

Ouch… I should have tried :confused:

Conclusions:

  • testing a fuzzing engine is not trivial :frowning:
  • testing it on a very short run with a single seed may be misleading

Yup. I’ll try to be more careful with this in the future.

And if I’ll have time, I’ll try to analyze that coverage plateau a bit. It would be insightful to know which mutation takes the fuzzer beyond the 60 basic blocks, and which of the coverage counters picks up the change – even if it’s just one specific case for one specific benchmark.

BTW, I am also looking into more automation of libFuzzer testing.
With trace-pc-guard we now have libFuzzer’s flag -print_coverage=1 that will print all the covered lines.
My hope is that this feature can be used for more detailed analysis of coverage differences.

Cool. I’ll give this a try too. I have some ideas about testing and analyzing coverage… will post them on libfuzzer@ once they are more mature.

Cheers,
Jonas