testing: successive integer and boolean mutations can be the same

stevenjohnstone commented 3 years ago

What version of Go are you using (`go version`)?

$ go version
go version devel go1.17-e5247f7886a Thu Sep 2 21:43:52 2021 +0000 linux/amd64

Does this issue reproduce with the latest release?

n/a

What operating system and processor architecture are you using (`go env`)?

go env Output

$ go env
GO111MODULE=""
GOARCH="amd64"
GOBIN=""
GOCACHE="/home/stevie/.cache/go-build"
GOENV="/home/stevie/.config/go/env"
GOEXE=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="linux"
GOINSECURE=""
GOMODCACHE="/home/stevie/go/pkg/mod"
GONOPROXY=""
GONOSUMDB=""
GOOS="linux"
GOPATH="/home/stevie/go"
GOPRIVATE=""
GOPROXY="https://proxy.golang.org,direct"
GOROOT="/home/stevie/sdk/gotip"
GOSUMDB="sum.golang.org"
GOTMPDIR=""
GOTOOLDIR="/home/stevie/sdk/gotip/pkg/tool/linux_amd64"
GOVCS=""
GOVERSION="devel go1.17-e5247f7886a Thu Sep 2 21:43:52 2021 +0000"
GCCGO="gccgo"
AR="ar"
CC="gcc"
CXX="g++"
CGO_ENABLED="1"
GOMOD="/home/stevie/bool/go.mod"
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -m64 -pthread -fmessage-length=0 -fdebug-prefix-map=/tmp/go-build3145646393=/tmp/go-build -gno-record-gcc-switches"

What did you do?

Ran this fuzz test:

// +build gofuzzbeta

package bool

import "testing"

//go:noinline
func nadaInt(int) {
}

//go:noinline
func nadaInt16(int16) {
}

//go:noinline
func nadaInt8(int8) {
}

//go:noinline
func nadaBool(bool) {
}

func FuzzInt(f *testing.F) {
    f.Fuzz(func(t *testing.T, on int) {
        nadaInt(on)
    })
}

func FuzzInt16(f *testing.F) {
    f.Fuzz(func(t *testing.T, on int16) {
        nadaInt16(on)
    })
}

func FuzzInt8(f *testing.F) {
    f.Fuzz(func(t *testing.T, on int8) {
        nadaInt8(on)
    })
}

func FuzzBool(f *testing.F) {
    f.Fuzz(func(t *testing.T, on bool) {
        nadaBool(on)
    })
}

I have a bpftrace script:

uprobe:/home/stevie/bool/bool.test:"bool.nada*" {
          $on = reg("ax");
          if (@prev[pid] == $on) {
            // repeated value
            @repeats[pid] = count();
          }
          @total[pid] = count();
          @prev[pid] = $on;
}

END {
  clear(@prev);
}

Using that during runs of FuzzInt etc I can see that I get successive inputs to the fuzzer which are the same. For the boolean it's ~50% of the time, for uint8 about 0.3% and the rest 0.2%. I was taking a look because I had a test with this signature

func(t *testing.T, b []byte, on bool)

and I'd see about 1/4 of the time it was executing the same test case as the previous run.

What did you expect to see?

I'd expect a mutation of a boolean to just flip the value true->false, false->true. There's no need for anything probabilistic here. For the ints, it's not as obvious of a problem but if my test signature was

func(t *testing.T, b []byte, i int)

the fuzzer would be doing the same work twice ~0.1% of the time. Not a massive amount but multiplied over all golang CIs, it's significant. My attempt at keeping CO2 in the ground :sweat_smile:

What did you see instead?

Mutations which are no-ops.

stevenjohnstone commented 3 years ago

With change https://github.com/golang/go/pull/48292 I see a 25% reduction in work done by the fuzzer when the signature of the function under test is

func(t *testing.T, b []byte, on bool)

gopherbot commented 3 years ago

Change https://golang.org/cl/348849 mentions this issue: [dev.fuzz] internal/fuzz: always perform logical not on booleans when…

stevenjohnstone commented 3 years ago

The int mutators are actually really interesting from a mathematical point of view. They are random walks with non-local conditions (the probability of a jump depends on the distance from the extreme points of the integer). This gives quite strange probability distributions. Here's what a sample of the distribution (starting a zero) looks like for uint8 (forgive the gnuplot purple):

byte

uin32 looks like a slow shuffle relatively close to zero but eventually it'd probably look something like uint8

uint32

The mutator is here:

https://github.com/golang/go/blob/7c648e2acb31363ea128b754503343cf2c82ba6f/src/internal/fuzz/mutator.go#L165-L197

Some properties of the mutator which are undesirable:

it can be a no-op because the walk can turn back on itself when numIters > 1
with low probability, it can loop for a long time (numIters could be large with low probability)
when at 0 or maxValue, 50% of the iterations do nothing and the loop repeats
the chances of staying close to the extreme values is greater than elsewhere in the range (see the uint8 distribution sample)

A more straight forward way to mutate an int would be to pick a random bit and flip it. That gives a uniform distribution of values, will never leave the integer unchanged and probably be good for things like flags.

evanj commented 1 year ago

I think I just ran into this bug. I wrote a test function that panics if an input int is > 5000. Without any corpus (e.g. calls to f.Add), it won't find this "bug" within 60 seconds on my machine, which reported approximately 30M executions. This surprises me. This shouldn't be hard to find.

I found two workarounds that work for me:

Seed the corpus with f.Add by calling it with a range of integers (e.g. every 500 or something?). This works if the seeds are "close" to the trigger values.
Use []byte argument and convert it to an integer. This seems to work very well for values close to 0. For example, this even finds arg == 12345 very quickly, but does not find arg == 12345679

See https://github.com/evanj/gofuzztesting for a reproduction

golang / go