cmd/compile: coverage instrumentation for fuzzing

[dvyukov]

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):

1. go-fuzz mimics go tool build logic, which leads to constant breakages.
2. go-fuzz-build does not handle cgo, and it is hard to implement.
3. coverage instrumentation is source-to-source, which makes it very difficult to integrate with other build systems.
4. 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.
5. 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.

[dvyukov]

@kcc @khr @ianlancetaylor @dgryski

[mdempsky]

@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.

[kcc]

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.

[mdempsky]

@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?

[kcc]

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

[mdempsky]

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++; ... }

?

[kcc]

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.

[mdempsky]

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?

[kcc]

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.

[mdempsky]

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

[mdempsky]

@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?

[kcc]

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.