Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Open
stevenjohnstone opened this issue Sep 9, 2021 · 3 comments
Open

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

stevenjohnstone opened this issue Sep 9, 2021 · 3 comments

Comments

@stevenjohnstone
Copy link

@stevenjohnstone stevenjohnstone commented Sep 9, 2021

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.

@stevenjohnstone 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
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
… mutating

Flip booleans when mutating rather than keeping the same value
50% of the time.

Fixes part of golang#48291.
@stevenjohnstone
Copy link
Author

@stevenjohnstone stevenjohnstone commented Sep 9, 2021

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)

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

Flip booleans when mutating rather than keeping the same value
50% of the time.

Updates golang#48291.
@gopherbot
Copy link

@gopherbot gopherbot commented Sep 9, 2021

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

@stevenjohnstone
Copy link
Author

@stevenjohnstone stevenjohnstone commented Sep 9, 2021

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:

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.

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

Flip booleans when mutating rather than keeping the same value
50% of the time.

Updates golang#48291.
@katiehockman katiehockman added this to the Backlog milestone Sep 14, 2021
@rsc 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
4 participants