cmd/go: adopt sonar techniques from dvyukov/go-fuzz for better fuzzing #76258
Description
Example fuzz test
Consider the following fuzz function:
func FuzzFoo(f *testing.F) {
f.Fuzz(func(t *testing.T, data []byte) {
if len(data) < 8 {
return
}
num := binary.LittleEndian.Uint64(data)
if num == 0xDEADBEEF {
panic("bingo")
}
})
}dvyukov/go-fuzz finds the problematic ("interesting") input almost instantly.
In contrast, the builtin cmd/go fuzzer would take a very, very long time to find an interesting input here.
This is obviously a simple example intended to illustrate the concept, but it shows what might be the largest overall current gap between the quality of results between dvyukov/go-fuzz and the builtin cmd/go fuzzer, which has not yet caught up to dvyukov/go-fuzz, especially on more complex examples.
dvyukov/go-fuzz approach
The very nice fuzzing efficiency dvyukov/go-fuzz displays in this example is due to the "sonar" technique in dvyukov/go-fuzz, where it instruments things like the comparison in the sample program above, and then does things like looking in the input for things that are similar to the operands used in the live program, and then tries things like replacing values in the input, which for example can then can make a previously failing comparison succeed on the next try.
The technique is proven and highly effective, and helps get past things like dynamically computed checksums, or specific strings or constants needed to meaningfully exercise some API under test, or magic numbers, or a variety of other types of "blockers" for a fuzzing engine.
In this example, it takes almost no time because it dynamically recognizes (a) 0xDEADBEEF is valuable to try in the input and (b) exactly where to try to place it in the input data stream. This is a material improvement over, say, scanning the source or binary for literals and trying them in random spots in the input data stream.
(It may be that Dmitry pioneered the technique -- in literature, I think it is sometimes credited to some published academic papers such as REDQUEEN, but to my knowledge at least, Dmitry implemented it well before REDQUEEN, though as far as I know he did not take the time to publish an academic paper about it.)
Updating the cmd/go fuzzer
I would like to adopt this technique in the builtin cmd/go fuzzing engine, which started as a partial port of dvyukov/go-fuzz.
(I have some experience here -- Dmitry added me as a co-maintainer on dvyukov/go-fuzz, and he also kindly added me as a co-author on the original "first class fuzzing" proposal).