cmd/compile: coverage instrumentation for fuzzing

Go-fuzz (https://github.com/dvyukov/go-fuzz) is quite successful at finding bugs in Go code and reasonably widely used in Go community. However there are several problems with the current go-fuzz implementation that hinder wider adoption (in particular internal adoption at Google):

go-fuzz mimics go tool build logic, which leads to constant breakages.
go-fuzz-build does not handle cgo, and it is hard to implement.
coverage instrumentation is source-to-source, which makes it very difficult to integrate with other build systems.
source-to-source transformation can't handle all cases and has limited transformation capabilities (e.g. instrumenting && is tough). Some code patterns can be mishandled or lead to build failures.
source-to-source transformation produces slow code (lots of closures).

Ideally we have coverage instrumentation in compiler, and corresponding support in go tool. Something similar to -race flag, which triggers compiler instrumentation and adds race build tag.

@kcc

@kcc @khr @ianlancetaylor @dgryski

@dvyukov

@dvyukov Do you have any references for how other toolchains implement this?

Eg, I assume for cgo support, we'd want to do something that interoperates well with whatever the C compiler does.

LLVM does this:
https://clang.llvm.org/docs/SanitizerCoverage.html#inline-8bit-counters
It would be great if the Go's instrumentation is compatible with LLVM's so that they can interoperate.

In addition, we also do
https://clang.llvm.org/docs/SanitizerCoverage.html#tracing-data-flow
which provides additional signal to fuzzing. It can be implemented in a second iteration.

@kcc

@kcc Thanks. A bunch of clarifying questions:

What's the expected behavior when an 8-bit counter overflows? Should it saturate or wrap around?

Do the increments need to be atomic? (I seem to recall suggesting LLVM should make them atomic, but then that turning out to be a performance hit.)

Do I understand that the basic idea is the compiler should transform every

func f() {
    if foo { ... } else { ... }
}

into

var f.counters [2]uint8

func f() {
    if foo { f.counters[0]++; ... } else { f.counters[1]++; ... }
}

? (I.e., for every branch point, we just need to increment a counter to indicate whether we took the true or false branch.) Or are there other cases we need to track, or maybe cases where we don't need to track?

Do we need to do anything for goto/labels? (Intuitively I'd think no.)

What about indirect function calls? I suppose we can hash (CALL instruction's PC, target instruction's PC) and increment some large indirect calls table.

What about panics? If there's f(); f(), I'd guess you want to distinguish whether the first or second f() panicked?

Does LLVM do any special linker stuff to ensure all the counters end up consecutively? E.g., put them in some ELF section?

Do users care about knowing which counter maps to which source location? (Intuitively, I'm assuming you really only care that the coverage data is different than you've seen before.)

--

In fact, if that's true (i.e., you only care to identify whether we've triggered new code paths), would it suffice to just keep a running hash for each G of any indirect call or conditional branch it takes? And then deterministically hash these together at the end?

Should it saturate or wrap around?

either is fine, but wrap around is easier to implement.
With wrap around we have a potential to lose a bit of information if the counter value is k*256,
but on average it's not a problem.

Do the increments need to be atomic?

No. They will be racy, and for concurrent code will be imprecise. It's tolerable.
Most of the code we fuzz is single-threaded anyway.

if foo { f.counters[0]++; ... } else { f.counters[1]++; ... }

roughly -- yes.

E.g., put them in some ELF section?

Yes, we put the counters into a special ELF section so that for a given DSO all the counters are consecutive.

Do users care about knowing which counter maps to which source location?

libFuzzer does care about it for various reasons.
Mostly for visualization, but also for figuring our where the function begins, etc.
So yes, we need to map the counters to PCs. Here is how we do it:
https://clang.llvm.org/docs/SanitizerCoverage.html#pc-table

What about indirect function calls?

With an extra flag, indirect-calls we get a call to __sanitizer_cov_trace_pc_indirect(void *callee)
inserted for every indirect call, and it's the user responsibility to record the indirect call pair.
It's not exceptionally important, it can go in a second iteration.

Also note the trick we are using to instrument edges and not just basic blocks:
https://clang.llvm.org/docs/SanitizerCoverage.html#edge-coverage

Thanks, that was helpful.

Also note the trick we are using to instrument edges and not just basic blocks: https://clang.llvm.org/docs/SanitizerCoverage.html#edge-coverage

I saw that and read it a couple times, but I'm still a little unclear on what it's suggesting.

Do I understand correctly that it's just emphasizing that

if foo { ... }

has to be rewritten into

if foo { counter42++; ... } else { counter43++ }

and not simply into

if foo { counter42++; ... }

?

if foo { counter42++; ... } else { counter43++ }

Yes. It makes the signal for the fuzzing engine stronger.
Again, not absolutely necessary in the first iteration, but pretty useful.

So yes, we need to map the counters to PCs. Here is how we do it:
https://clang.llvm.org/docs/SanitizerCoverage.html#pc-table

What PC should be associated with each counter? The PC for the counter increment instruction?

In our implementation it is the PC of the first instruction of the basic block (the function address for the entry block). Doesn't matter much though as long as you can correctly symbolize the PC.

Okay. That sounds like enough info to get started with. Thanks!

@kcc

@kcc One more question: is there any preference for edges that are reported by instrumentation to more closely match the source language or the target language?

For example, we compile:

switch x {
case 0, 7, 8, 9, 10:
    one()
case 2, 11, 20:
    two()
}

as something like:

    if x <= 2 {
        if x == 0 { goto Lone }
        if x == 2 { goto Ltwo }
    } else {
        if uint(x - 7) <= 3 { goto Lone }
        if x == 11 { goto Ltwo }
        if x == 20 { goto Ltwo }
    }
    goto Ldone
Lone:
    one()
    goto Ldone
Ltwo:
    two()
    goto Ldone
Ldone:

go-fuzz currently only inserts three counters (one for each explicit case, and then one more for the implicit empty default case). Is that preferred, or should we report edges based on compiled form (so ~10 counters for the above example), or does it not matter?

Reporting more counters may increase the overhead a bit, but it may provide a bit more signal.
So, if the compiled form will have 10 edges, it's ok to have 10 edges.

I don't know if Go instrumentation already does this or not, but FWIW both go-fuzz and libfuzzer split critical CFG edges (go-fuzz by a very naive approach of adding missing else's to if's and default cases to all switches). this gives quite important signal too. This is not necessary if the fuzzer converts BBs to edges itself (e.g. AFL with limited binary instrumentation), but libfuzzer does not do this and relies on compiler to do good instrumentation.

@dvyukov

@dvyukov cmd/compile's libfuzzer mode does roughly the same approach as go-fuzz: it adds missing elses and default cases.

@mdempsky

Comparing LibFuzzers

With the previous new-libfuzzer container, I created a new one using the -use_value_profile=1 runtime option with some interesting results. From the documentation for value profile:

This feature has a potential to discover many interesting inputs, but there are two downsides. First, the extra instrumentation may bring up to 2x additional slowdown. Second, the corpus may grow by several times.

I've had these three containers ( not including old-go-fuzz from before ) running for ~2 days:

old-libfuzzer
new-libfuzzer
new-libfuzzer-trace-cmp-with-profile

Execs/s

The old-libfuzzer has significantly more execs/s (and iterations) compared to either new-libfuzzer.

After the weekend (~2 more days)

Features

libFuzzer uses different signals to evaluate the code coverage: edge coverage, edge counters, value profiles, indirect caller/callee pairs, etc. These signals combined are called features (ft:).

Interestingly, old-libfuzzer found significantly more features. Between the new-libfuzzer* variants, the value profile seemed to lead to more features... But, still far behind old-libfuzzer for some reason.

After the weekend (~2 more days)

Corpus Size ( Kb )

The new-libfuzzer* variants had a larger corpus size overall.

After the weekend (~2 more days).

Corpus Files

The new-libfuzzer* variants had more files being added to the corpus.

After the weekend (~2 more days)

Next Steps

~~I'm going to continue to let these cases run over the weekend and report back.~~ Just updated with drop-downs for the plots from after the weekend.
I'm then going to try out a new (perhaps more interesting?) fuzzing target than just image/png.

Interpreting Results

@mdempsky Unless I'm misinterpreting, or messing up my graphs... old-libfuzzer seems to be performing better than the new-libfuzzer* variants? With less corupus size/files (starting with the same), it seems the older tooling is able to discover more features faster than the newer instrumentation with far more exec/s. Super curious to hear your (or other's) thoughts on this!

What's on the X axis (iterations)?

One "iteration" would be one line from a fuzzer's worker log output. Each variant has two workers/jobs, so I'm joining the log output (with tail -f) as as single line per fuzzer on the chart.

I assume it prints a line every 10 secs or so. What I was getting at is that in my experience fuzzing behavior over a short period of time does not matter much. If a bug is found within seconds, minutes or hours it does not matter much. There may be some difference between day and days for some use cases. But if we are talking about finding longer tail of bugs, this involves continuous fuzzing that runs for weeks/months/years. What matters then is the rooftop after months of fuzzing on fully saturated corpus. And this usually conflicts with raw speed, "fast and dumb" is important during first hours of fuzzing, but then it becomes more important how smart the fuzzer is. And being smarter generally means being slower.
Unfortunately there is no easy way to measure this. One thick I used is starting fuzzers with fully saturated corpus and then checking if they can progress any further.

@dvyukov

I really appreciate the insight @dvyukov!

To determine if a corpus has become fully saturated, would I monitor the features/coverage for a fuzzer and wait for it to plateau for prolonged period of time?

There is no strict procedure and "fully saturated" is not strictly defined anyway. But I would at least run a fuzzer overnight and, yes, not getting new coverage for some time.
For benchmarking purposes it can make sense to not "over saturate it" (e.g. running for a month on a cluster), because then no variation may discover any new coverage, and then benchmarking won't give any useful signal. Benchmarking fuzzers is a bit of black magic...

Also: Design Draft: First Class Fuzzing https://go-review.googlesource.com/c/proposal/+/243947/4

Discussion(empty for now): https://golang.org/issue/40307

Change https://golang.org/cl/351314 mentions this issue: cmd/go: adjust comments on why fuzzing instrumentation is disabled

cmd/go: adjust comments on why fuzzing instrumentation is disabled

More improvements to instrumentation are already merged into master and are to be released in Go 1.19: https://github.com/golang/go/pulls?q=is%3Apr+author%3Akyakdan+is%3Aclosed

They mainly include:

Use libFuzzer 8-bit counters instead of extra counters: Newly covered edges are now properly reported as new coverage by libFuzzer, not only as new features. Also, the NeverZero strategy (https://www.usenix.org/system/files/woot20-paper-fioraldi.pdf) is used to ensure that coverage counters never become 0 again after having been positive once. This resolves issues encountered when fuzzing loops with iteration counts that are multiples of 256
Intercept string compares: Direct string compares as well as calls to string comparison functions such as strings.EqualFold are intercepted and the corresponding libFuzzer callbacks are invoked with the corresponding arguments.
Support libFuzzer value profiling mode for integer compares: This fixes an issue that made all integer compares in Go code appear as a single comparison to libFuzzer, which drastically
reduces the usefulness of value profiling.

Change https://go.dev/cl/802100 mentions this issue: runtime, internal/fuzz: add libFuzzer support on riscv64

Navigation Menu

Repository navigation

cmd/compile: coverage instrumentation for fuzzing #14565

22 remaining items

Comparing LibFuzzers

Execs/s

Features

Corpus Size ( Kb )

Corpus Files

Next Steps

Interpreting Results

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

cmd/compile: coverage instrumentation for fuzzing #14565

Description

Activity

dvyukov commented on Feb 29, 2016

mdempsky commented on Oct 11, 2019

kcc commented on Oct 11, 2019

mdempsky commented on Oct 11, 2019

kcc commented on Oct 11, 2019

mdempsky commented on Oct 11, 2019

kcc commented on Oct 12, 2019

mdempsky commented on Oct 12, 2019

kcc commented on Oct 12, 2019

mdempsky commented on Oct 12, 2019

mdempsky commented on Oct 18, 2019

kcc commented on Oct 18, 2019

22 remaining items

dvyukov commented on Mar 11, 2020

mdempsky commented on Mar 11, 2020

picatz commented on Mar 13, 2020

Comparing LibFuzzers

Execs/s

Features

Corpus Size ( Kb )

Corpus Files

Next Steps

Interpreting Results

dvyukov commented on Mar 14, 2020

picatz commented on Mar 14, 2020

dvyukov commented on Mar 15, 2020

picatz commented on Mar 15, 2020

dvyukov commented on Mar 16, 2020

cristaloleg commented on Jul 22, 2020

gopherbot commented on Sep 23, 2021

kyakdan commented on Jun 13, 2022

gopherbot commented on Jul 17, 2026

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions