diff options
| -rw-r--r-- | prog/hints.go | 34 | ||||
| -rw-r--r-- | prog/hints_test.go | 37 | ||||
| -rw-r--r-- | prog/rand.go | 33 | ||||
| -rw-r--r-- | prog/rand_test.go | 46 |
4 files changed, 109 insertions, 41 deletions
diff --git a/prog/hints.go b/prog/hints.go index 63199439c..8ac3ed735 100644 --- a/prog/hints.go +++ b/prog/hints.go @@ -22,27 +22,26 @@ import ( "bytes" "encoding/binary" "fmt" + "sort" ) -type uint64Set map[uint64]bool - // Example: for comparisons {(op1, op2), (op1, op3), (op1, op4), (op2, op1)} // this map will store the following: // m = { // op1: {map[op2]: true, map[op3]: true, map[op4]: true}, // op2: {map[op1]: true} // }. -type CompMap map[uint64]uint64Set +type CompMap map[uint64]map[uint64]bool const ( maxDataLength = 100 ) -var specialIntsSet uint64Set +var specialIntsSet map[uint64]bool func (m CompMap) AddComp(arg1, arg2 uint64) { if _, ok := m[arg1]; !ok { - m[arg1] = make(uint64Set) + m[arg1] = make(map[uint64]bool) } m[arg1][arg2] = true } @@ -106,7 +105,9 @@ func generateHints(compMap CompMap, arg Arg, exec func()) { func checkConstArg(arg *ConstArg, compMap CompMap, exec func()) { original := arg.Val - for replacer := range shrinkExpand(original, compMap) { + // Note: because shrinkExpand returns a map, order of programs is non-deterministic. + // This can affect test coverage reports. + for _, replacer := range shrinkExpand(original, compMap) { arg.Val = replacer exec() } @@ -124,7 +125,7 @@ func checkDataArg(arg *DataArg, compMap CompMap, exec func()) { original := make([]byte, 8) copy(original, data[i:]) val := binary.LittleEndian.Uint64(original) - for replacer := range shrinkExpand(val, compMap) { + for _, replacer := range shrinkExpand(val, compMap) { binary.LittleEndian.PutUint64(bytes, replacer) copy(data[i:], bytes) exec() @@ -163,7 +164,8 @@ func checkDataArg(arg *DataArg, compMap CompMap, exec func()) { // As with shrink we ignore cases when the other operand is wider. // Note that executor sign extends all the comparison operands to int64. // ====================================================================== -func shrinkExpand(v uint64, compMap CompMap) (replacers uint64Set) { +func shrinkExpand(v uint64, compMap CompMap) []uint64 { + var replacers map[uint64]bool for _, iwidth := range []int{8, 4, 2, 1, -4, -2, -1} { var width int var size, mutant uint64 @@ -210,17 +212,27 @@ func shrinkExpand(v uint64, compMap CompMap) (replacers uint64Set) { // TODO(dvyukov): should we try replacing with arg+/-1? // This could trigger some off-by-ones. if replacers == nil { - replacers = make(uint64Set) + replacers = make(map[uint64]bool) } replacers[replacer] = true } } } - return + if replacers == nil { + return nil + } + res := make([]uint64, 0, len(replacers)) + for v := range replacers { + res = append(res, v) + } + sort.Slice(res, func(i, j int) bool { + return res[i] < res[j] + }) + return res } func init() { - specialIntsSet = make(uint64Set) + specialIntsSet = make(map[uint64]bool) for _, v := range specialInts { specialIntsSet[v] = true } diff --git a/prog/hints_test.go b/prog/hints_test.go index 7cbabd992..873a3d73a 100644 --- a/prog/hints_test.go +++ b/prog/hints_test.go @@ -12,11 +12,13 @@ import ( "testing" ) +type uint64Set map[uint64]bool + type ConstArgTest struct { name string in uint64 comps CompMap - res uint64Set + res []uint64 } type DataArgTest struct { @@ -35,7 +37,7 @@ func TestHintsCheckConstArg(t *testing.T) { "One replacer test", 0xdeadbeef, CompMap{0xdeadbeef: uint64Set{0xcafebabe: true}}, - uint64Set{0xcafebabe: true}, + []uint64{0xcafebabe}, }, // Test for cases when there's multiple comparisons (op1, op2), (op1, op3), ... // Checks that for every such operand a program is generated. @@ -43,23 +45,23 @@ func TestHintsCheckConstArg(t *testing.T) { "Multiple replacers test", 0xabcd, CompMap{0xabcd: uint64Set{0x2: true, 0x3: true}}, - uint64Set{0x2: true, 0x3: true}, + []uint64{0x2, 0x3}, }, // Checks that special ints are not used. { "Special ints test", 0xabcd, CompMap{0xabcd: uint64Set{0x1: true, 0x2: true}}, - uint64Set{0x2: true}, + []uint64{0x2}, }, } for _, test := range tests { t.Run(fmt.Sprintf("%v", test.name), func(t *testing.T) { t.Parallel() - res := uint64Set{} + var res []uint64 constArg := &ConstArg{ArgCommon{nil}, test.in} checkConstArg(constArg, test.comps, func() { - res[constArg.Val] = true + res = append(res, constArg.Val) }) if !reflect.DeepEqual(res, test.res) { t.Fatalf("\ngot : %v\nwant: %v", res, test.res) @@ -236,7 +238,7 @@ func TestHintsShrinkExpand(t *testing.T) { 0x34: uint64Set{0xab: true}, 0x1234: uint64Set{0xcdcd: true}, }, - uint64Set{0x12ab: true, 0xcdcd: true}, + []uint64{0x12ab, 0xcdcd}, }, { // Models the following code: @@ -254,7 +256,7 @@ func TestHintsShrinkExpand(t *testing.T) { 0x5678: uint64Set{0xcdcd: true}, 0x12345678: uint64Set{0xefefefef: true}, }, - uint64Set{0x123456ab: true, 0x1234cdcd: true, 0xefefefef: true}, + []uint64{0x123456ab, 0x1234cdcd, 0xefefefef}, }, { // Models the following code: @@ -275,11 +277,11 @@ func TestHintsShrinkExpand(t *testing.T) { 0x90abcdef: uint64Set{0xefefefef: true}, 0x1234567890abcdef: uint64Set{0x0101010101010101: true}, }, - uint64Set{ - 0x1234567890abcdab: true, - 0x1234567890abcdcd: true, - 0x12345678efefefef: true, - 0x0101010101010101: true, + []uint64{ + 0x1234567890abcdab, + 0x1234567890abcdcd, + 0x12345678efefefef, + 0x0101010101010101, }, }, { @@ -310,7 +312,7 @@ func TestHintsShrinkExpand(t *testing.T) { "Shrink with a wider replacer test2", 0x1234, CompMap{0x34: uint64Set{0xfffffffffffffffd: true}}, - uint64Set{0x12fd: true}, + []uint64{0x12fd}, }, // ----------------------------------------------------------------- // Extend tests: @@ -325,7 +327,7 @@ func TestHintsShrinkExpand(t *testing.T) { "Extend 8 test", 0xff, CompMap{0xffffffffffffffff: uint64Set{0xfffffffffffffffe: true}}, - uint64Set{0xfe: true}, + []uint64{0xfe}, }, { // Models the following code: @@ -336,7 +338,7 @@ func TestHintsShrinkExpand(t *testing.T) { "Extend 16 test", 0xffff, CompMap{0xffffffffffffffff: uint64Set{0xfffffffffffffffe: true}}, - uint64Set{0xfffe: true}, + []uint64{0xfffe}, }, { // Models the following code: @@ -347,7 +349,7 @@ func TestHintsShrinkExpand(t *testing.T) { "Extend 32 test", 0xffffffff, CompMap{0xffffffffffffffff: uint64Set{0xfffffffffffffffe: true}}, - uint64Set{0xfffffffe: true}, + []uint64{0xfffffffe}, }, { // Models the following code: @@ -426,6 +428,7 @@ func extractValues(c *Call) map[uint64]bool { } } }) + delete(vals, 0) // replacing 0 can yield too many condidates return vals } diff --git a/prog/rand.go b/prog/rand.go index c3b7c2352..c1ac76776 100644 --- a/prog/rand.go +++ b/prog/rand.go @@ -9,6 +9,7 @@ import ( "math" "math/rand" "path/filepath" + "sort" "strings" "github.com/google/syzkaller/pkg/ifuzz" @@ -188,11 +189,7 @@ func (r *randGen) filenameImpl(s *state) string { // Generate a new name. dir := "." if r.oneOf(2) && len(s.files) != 0 { - files := make([]string, 0, len(s.files)) - for f := range s.files { - files = append(files, f) - } - dir = files[r.Intn(len(files))] + dir = r.randFromMap(s.files) if len(dir) > 0 && dir[len(dir)-1] == 0 { dir = dir[:len(dir)-1] } @@ -207,10 +204,15 @@ func (r *randGen) filenameImpl(s *state) string { } } } - files := make([]string, 0, len(s.files)) - for f := range s.files { + return r.randFromMap(s.files) +} + +func (r *randGen) randFromMap(m map[string]bool) string { + files := make([]string, 0, len(m)) + for f := range m { files = append(files, f) } + sort.Strings(files) return files[r.Intn(len(files))] } @@ -221,11 +223,7 @@ func (r *randGen) randString(s *state, t *BufferType) []byte { if len(s.strings) != 0 && r.bin() { // Return an existing string. // TODO(dvyukov): make s.strings indexed by string SubKind. - strings := make([]string, 0, len(s.strings)) - for s := range s.strings { - strings = append(strings, s) - } - return []byte(strings[r.Intn(len(strings))]) + return []byte(r.randFromMap(s.strings)) } punct := []byte{'!', '@', '#', '$', '%', '^', '&', '*', '(', ')', '-', '+', '\\', '/', ':', '.', ',', '-', '\'', '[', ']', '{', '}'} @@ -275,6 +273,7 @@ func (r *randGen) createResource(s *state, res *ResourceType) (arg Arg, calls [] all = append(all, kind1) } } + sort.Strings(all) kind = all[r.Intn(len(all))] } // Find calls that produce the necessary resources. @@ -585,8 +584,16 @@ func (a *ResourceType) generate(r *randGen, s *state) (arg Arg, calls []*Call) { switch { case r.nOutOf(1000, 1011): // Get an existing resource. + alltypes := make([][]*ResultArg, 0, len(s.resources)) + for _, res1 := range s.resources { + alltypes = append(alltypes, res1) + } + sort.Slice(alltypes, func(i, j int) bool { + return alltypes[i][0].Type().Name() < alltypes[j][0].Type().Name() + }) var allres []*ResultArg - for name1, res1 := range s.resources { + for _, res1 := range alltypes { + name1 := res1[0].Type().Name() if r.target.isCompatibleResource(a.Desc.Name, name1) || r.oneOf(20) && r.target.isCompatibleResource(a.Desc.Kind[0], name1) { allres = append(allres, res1...) diff --git a/prog/rand_test.go b/prog/rand_test.go index 1771a0052..d96d96260 100644 --- a/prog/rand_test.go +++ b/prog/rand_test.go @@ -24,3 +24,49 @@ func TestNotEscaping(t *testing.T) { } } } + +func TestDeterminism(t *testing.T) { + target, rs, iters := initTest(t) + iters /= 10 // takes too long + for i := 0; i < iters; i++ { + seed := rs.Int63() + rs1 := rand.NewSource(seed) + p1 := generateProg(t, target, rs1) + rs2 := rand.NewSource(seed) + p2 := generateProg(t, target, rs2) + ps1 := string(p1.Serialize()) + ps2 := string(p2.Serialize()) + r1 := rs1.Int63() + r2 := rs2.Int63() + if r1 != r2 || ps1 != ps2 { + t.Errorf("seed=%v\nprog 1 (%v):\n%v\nprog 2 (%v):\n%v", seed, r1, ps1, r2, ps2) + } + } +} + +func generateProg(t *testing.T, target *Target, rs rand.Source) *Prog { + p := target.Generate(rs, 5, nil) + p.Mutate(rs, 10, nil, nil) + for i, c := range p.Calls { + comps := make(CompMap) + for v := range extractValues(c) { + comps.AddComp(v, v+1) + comps.AddComp(v, v+10) + } + p.MutateWithHints(i, comps, func(p1 *Prog) { + p = p1.Clone() + }) + } + for _, crash := range []bool{false, true} { + p, _ = Minimize(p, -1, crash, func(*Prog, int) bool { + return rs.Int63()%10 == 0 + }) + } + data := p.Serialize() + var err error + p, err = target.Deserialize(data, NonStrict) + if err != nil { + t.Fatal(err) + } + return p +} |