testing: successive integer and boolean mutations can be the same #48291

stevenjohnstone · 2021-09-09T16:45:15Z

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 😅

What did you see instead?

Mutations which are no-ops.

The text was updated successfully, but these errors were encountered:

Flip booleans when mutating rather than keeping the same value 50% of the time. Fixes part of golang#48291.

… mutating Flip booleans when mutating rather than keeping the same value 50% of the time. Fixes part of golang#48291.

stevenjohnstone · 2021-09-09T16:59:30Z

With change #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)

… mutating Flip booleans when mutating rather than keeping the same value 50% of the time. Updates golang#48291.

gopherbot · 2021-09-09T17:08:50Z

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

stevenjohnstone · 2021-09-09T17:58:07Z

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

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

The mutator is here:

go/src/internal/fuzz/mutator.go

Lines 165 to 197 in 7c648e2

    
           func (m *mutator) mutateUInt(v, maxValue uint64) uint64 { 
        
           	numIters := 1 + m.r.exp2() 
        
           	var max uint64 
        
           	for iter := 0; iter < numIters; iter++ { 
        
           		max = 100 
        
           		switch m.rand(2) { 
        
           		case 0: 
        
           			// Add a random number 
        
           			if v >= maxValue { 
        
           				iter-- 
        
           				continue 
        
           			} 
        
           			if v > 0 && maxValue-v < max { 
        
           				// Don't let v exceed maxValue 
        
           				max = maxValue - v 
        
           			} 
        
           			v += uint64(1 + m.rand(int(max))) 
        
           		case 1: 
        
           			// Subtract a random number 
        
           			if v <= 0 { 
        
           				iter-- 
        
           				continue 
        
           			} 
        
           			if v < max { 
        
           				// Don't let v drop below 0 
        
           				max = v 
        
           			} 
        
           			v -= uint64(1 + m.rand(int(max))) 
        
           		} 
        
           	} 
        
           	return v 
        
           }

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.

… mutating Flip booleans when mutating rather than keeping the same value 50% of the time. Updates golang#48291.

evanj · 2022-11-15T17:33:36Z

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

stevenjohnstone changed the title ~~[dev.fuzz] successive integer and boolean inputs can be the same~~ [dev.fuzz] successive integer and boolean mutations can be the same Sep 9, 2021

stevenjohnstone added a commit to stevenjohnstone/go that referenced this issue Sep 9, 2021

[dev.fuzz] internal/fuzz: perform not on booleans when mutating

a01b4b3

Flip booleans when mutating rather than keeping the same value 50% of the time. Fixes part of golang#48291.

stevenjohnstone added a commit to stevenjohnstone/go that referenced this issue Sep 9, 2021

[dev.fuzz] internal/fuzz: always perform logical not on booleans when…

ccae583

… mutating Flip booleans when mutating rather than keeping the same value 50% of the time. Fixes part of golang#48291.

stevenjohnstone mentioned this issue Sep 9, 2021

[dev.fuzz] internal/fuzz: always perform logical not on booleans when… #48292

Closed

stevenjohnstone added a commit to stevenjohnstone/go that referenced this issue Sep 9, 2021

[dev.fuzz] internal/fuzz: always perform logical not on booleans when…

7159d6e

… mutating Flip booleans when mutating rather than keeping the same value 50% of the time. Updates golang#48291.

stevenjohnstone added a commit to stevenjohnstone/go that referenced this issue Sep 9, 2021

[dev.fuzz] internal/fuzz: always perform logical not on booleans when…

5bf15b0

… mutating Flip booleans when mutating rather than keeping the same value 50% of the time. Updates golang#48291.

seankhliao added fuzz Issues related to native fuzzing support NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. labels Sep 10, 2021

katiehockman added this to the Backlog milestone Sep 14, 2021

rsc changed the title ~~[dev.fuzz] successive integer and boolean mutations can be the same~~ testing: successive integer and boolean mutations can be the same Sep 21, 2021

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

testing: successive integer and boolean mutations can be the same #48291

testing: successive integer and boolean mutations can be the same #48291

stevenjohnstone commented Sep 9, 2021

stevenjohnstone commented Sep 9, 2021

gopherbot commented Sep 9, 2021

stevenjohnstone commented Sep 9, 2021

evanj commented Nov 15, 2022

testing: successive integer and boolean mutations can be the same #48291

testing: successive integer and boolean mutations can be the same #48291

Comments

stevenjohnstone commented Sep 9, 2021

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

Does this issue reproduce with the latest release?

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

What did you do?

What did you expect to see?

What did you see instead?

stevenjohnstone commented Sep 9, 2021

gopherbot commented Sep 9, 2021

stevenjohnstone commented Sep 9, 2021

evanj commented Nov 15, 2022

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

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