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

https://github.com/golang/go/issues/20227
https://github.com/golang/go/issues/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.