math/big, go/constant: fuzz with go-fuzz

[josharian]

go-fuzz found a few math/big and go/constant bugs indirectly, via go/types and cmd/compile:

#20227
#20228

That's a pretty inefficient way to find them, though. We should run it on them directly and flush out a few more.

@ALTree @dvyukov

[AlekSi]

In Go tree I found a few fuzz tests using testing/quick or just testing, but zero go-fuzz-compatible ones. Are they stored separately?

[dvyukov]

I wrote some go-fuzz test for std lib at:
https://github.com/dvyukov/go-fuzz/tree/master/examples
It makes sense to move them to std lib once we resolve #19109.

[mdempsky]

We've had a couple issues with math/big assembly code routines (e.g., #31084, #42838), so it's probably worth revisiting this issue and seeing if we can get some basic fuzzing tests implemented. There's a rather minimal set of low-level arithmetic routines to worry about (https://github.com/golang/go/blob/master/src/math/big/arith_decl.go), and they all have known-good reference implementations that can be easily compared against.

/cc @griesemer @FiloSottile @katiehockman @mundaym

[randall77]

I think the tricky part here is getting full coverage of the assembly routines. Can the fuzzer fuzz assembly? Getting full coverage on the reference Go implementation is a good start, but might miss some paths through the assembly.

[mdempsky]

I was thinking as a start just randomly/exhaustively generating inputs (e.g., random word values, but probably exhaustive shift values from 0 through 63), feeding them through both the reference and assembly implementations, and making sure they produce identical outputs.

Edit: I'm suggesting we just write some manual differential fuzzers as regular Go tests. Using go-fuzz or something would be nice, but I don't think it's necessary.

[mdempsky]

Here's a very basic differential test that would have found the s390x bug:

func fuzzWords(n int) []Word {
	x := make([]Word, n)
	for i := range x {
		x[i] = Word(i) * 8675309 // TODO: Actual randomness.
	}
	return x
}

func dupWords(x []Word) []Word {
	return append([]Word(nil), x...)
}

func eqWords(a, b []Word) bool {
	for i := range a {
		if a[i] != b[i] {
			return false
		}
	}
	return true
}

func TestFuzzShlVU(t *testing.T) {
	for s := uint(0); s <= 4*_W; s++ {
		n := s / _W
		in := fuzzWords(8)

		ref := dupWords(in)
		refC := shlVU_g(ref[n:], ref[:8-n], s%_W)

		asm := dupWords(in)
		asmC := shlVU(asm[n:], asm[:8-n], s%_W)

		if refC != asmC || !eqWords(ref, asm) {
			t.Errorf("%v,%v: %v,%v != %v,%v", s, in, refC, ref, asmC, asm)
		}
	}
}

func TestFuzzShrVU(t *testing.T) {
	for s := uint(0); s <= 4*_W; s++ {
		n := s / _W
		in := fuzzWords(8)

		ref := dupWords(in)
		refC := shrVU_g(ref[:8-n], ref[n:], s%_W)

		asm := dupWords(in)
		asmC := shrVU(asm[:8-n], asm[n:], s%_W)

		if refC != asmC || !eqWords(ref, asm) {
			t.Errorf("%v,%v: %v,%v != %v,%v", s, in, refC, ref, asmC, asm)
		}
	}
}

I tried running it on a handful of other arches available through gomote (arm, arm64, ppc64le, mips64le) and didn't find any other failures except s390x's shl implementation.

[odeke-em]

@mdempsky could you please send a change to https://github.com/google/oss-fuzz/blob/master/projects/golang/math_big_fuzzer.go or another file with the appropriate build tags/guards? Thank you

[mdempsky]

@odeke-em Sorry, this hasn't been a priority for me. I welcome if anyone else wants to submit extra tests along the lines that I described though.