diff options
| -rw-r--r-- | prog/minimization_test.go | 174 | ||||
| -rw-r--r-- | prog/mutation_test.go | 165 |
2 files changed, 174 insertions, 165 deletions
diff --git a/prog/minimization_test.go b/prog/minimization_test.go new file mode 100644 index 000000000..641b9a9b9 --- /dev/null +++ b/prog/minimization_test.go @@ -0,0 +1,174 @@ +// Copyright 2018 syzkaller project authors. All rights reserved. +// Use of this source code is governed by Apache 2 LICENSE that can be found in the LICENSE file. + +package prog + +import ( + "math/rand" + "testing" +) + +func TestMinimize(t *testing.T) { + tests := []struct { + orig string + callIndex int + pred func(*Prog, int) bool + result string + resultCallIndex int + }{ + // Predicate always returns false, so must get the same program. + { + "mmap(&(0x7f0000000000/0x1000)=nil, 0x1000, 0x3, 0x32, 0xffffffffffffffff, 0x0)\n" + + "sched_yield()\n" + + "pipe2(&(0x7f0000000000)={0x0, 0x0}, 0x0)\n", + 2, + func(p *Prog, callIndex int) bool { + if len(p.Calls) == 0 { + t.Fatalf("got an empty program") + } + if p.Calls[len(p.Calls)-1].Meta.Name != "pipe2" { + t.Fatalf("last call is removed") + } + return false + }, + "mmap(&(0x7f0000000000/0x1000)=nil, 0x1000, 0x3, 0x32, 0xffffffffffffffff, 0x0)\n" + + "sched_yield()\n" + + "pipe2(&(0x7f0000000000), 0x0)\n", + 2, + }, + // Remove a call. + { + "mmap(&(0x7f0000000000/0x1000)=nil, 0x1000, 0x3, 0x32, 0xffffffffffffffff, 0x0)\n" + + "sched_yield()\n" + + "pipe2(&(0x7f0000000000)={0xffffffffffffffff, 0xffffffffffffffff}, 0x0)\n", + 2, + func(p *Prog, callIndex int) bool { + // Aim at removal of sched_yield. + return len(p.Calls) == 2 && p.Calls[0].Meta.Name == "mmap" && p.Calls[1].Meta.Name == "pipe2" + }, + "mmap(&(0x7f0000000000/0x1000)=nil, 0x1000, 0x0, 0x0, 0xffffffffffffffff, 0x0)\n" + + "pipe2(&(0x7f0000000000)={0xffffffffffffffff, 0xffffffffffffffff}, 0x0)\n", + 1, + }, + // Remove two dependent calls. + { + "mmap(&(0x7f0000000000/0x1000)=nil, 0x1000, 0x3, 0x32, 0xffffffffffffffff, 0x0)\n" + + "pipe2(&(0x7f0000000000)={0x0, 0x0}, 0x0)\n" + + "sched_yield()\n", + 2, + func(p *Prog, callIndex int) bool { + // Aim at removal of pipe2 and then mmap. + if len(p.Calls) == 2 && p.Calls[0].Meta.Name == "mmap" && p.Calls[1].Meta.Name == "sched_yield" { + return true + } + if len(p.Calls) == 1 && p.Calls[0].Meta.Name == "sched_yield" { + return true + } + return false + }, + "sched_yield()\n", + 0, + }, + // Remove a call and replace results. + { + "mmap(&(0x7f0000000000/0x1000)=nil, 0x1000, 0x3, 0x32, 0xffffffffffffffff, 0x0)\n" + + "pipe2(&(0x7f0000000000)={<r0=>0x0, 0x0}, 0x0)\n" + + "write(r0, &(0x7f0000000000)=\"1155\", 0x2)\n" + + "sched_yield()\n", + 3, + func(p *Prog, callIndex int) bool { + return p.String() == "mmap-write-sched_yield" + }, + "mmap(&(0x7f0000000000/0x1000)=nil, 0x1000, 0x0, 0x0, 0xffffffffffffffff, 0x0)\n" + + "write(0xffffffffffffffff, &(0x7f0000000000), 0x0)\n" + + "sched_yield()\n", + 2, + }, + // Remove a call and replace results. + { + "mmap(&(0x7f0000000000/0x1000)=nil, 0x1000, 0x3, 0x32, 0xffffffffffffffff, 0x0)\n" + + "r0=open(&(0x7f0000000000)=\"1155\", 0x0, 0x0)\n" + + "write(r0, &(0x7f0000000000)=\"1155\", 0x2)\n" + + "sched_yield()\n", + -1, + func(p *Prog, callIndex int) bool { + return p.String() == "mmap-write-sched_yield" + }, + "mmap(&(0x7f0000000000/0x1000)=nil, 0x1000, 0x0, 0x0, 0xffffffffffffffff, 0x0)\n" + + "write(0xffffffffffffffff, &(0x7f0000000000), 0x0)\n" + + "sched_yield()\n", + -1, + }, + // Glue several mmaps together. + { + "sched_yield()\n" + + "mmap(&(0x7f0000010000/0x1000)=nil, 0x1000, 0x3, 0x32, 0xffffffffffffffff, 0x0)\n" + + "mmap(&(0x7f0000011000/0x1000)=nil, 0x1000, 0x3, 0x32, 0xffffffffffffffff, 0x0)\n" + + "getpid()\n" + + "mmap(&(0x7f0000015000/0x5000)=nil, 0x2000, 0x3, 0x32, 0xffffffffffffffff, 0x0)\n", + 3, + func(p *Prog, callIndex int) bool { + return p.String() == "mmap-sched_yield-getpid" + }, + "mmap(&(0x7f0000010000/0x7000)=nil, 0x7000, 0x0, 0x0, 0xffffffffffffffff, 0x0)\n" + + "sched_yield()\n" + + "getpid()\n", + 2, + }, + } + target, _, _ := initTest(t) + for ti, test := range tests { + p, err := target.Deserialize([]byte(test.orig)) + if err != nil { + t.Fatalf("failed to deserialize original program #%v: %v", ti, err) + } + p1, ci := Minimize(p, test.callIndex, false, test.pred) + res := p1.Serialize() + if string(res) != test.result { + t.Fatalf("minimization produced wrong result #%v\norig:\n%v\nexpect:\n%v\ngot:\n%v\n", + ti, test.orig, test.result, string(res)) + } + if ci != test.resultCallIndex { + t.Fatalf("minimization broke call index #%v: got %v, want %v", + ti, ci, test.resultCallIndex) + } + } +} + +func TestMinimizeRandom(t *testing.T) { + target, rs, iters := initTest(t) + iters /= 10 // Long test. + for i := 0; i < iters; i++ { + p := target.Generate(rs, 5, nil) + Minimize(p, len(p.Calls)-1, true, func(p1 *Prog, callIndex int) bool { + return false + }) + Minimize(p, len(p.Calls)-1, true, func(p1 *Prog, callIndex int) bool { + return true + }) + } + for i := 0; i < iters; i++ { + p := target.Generate(rs, 5, nil) + Minimize(p, len(p.Calls)-1, false, func(p1 *Prog, callIndex int) bool { + return false + }) + Minimize(p, len(p.Calls)-1, false, func(p1 *Prog, callIndex int) bool { + return true + }) + } +} + +func TestMinimizeCallIndex(t *testing.T) { + target, rs, iters := initTest(t) + r := rand.New(rs) + for i := 0; i < iters; i++ { + p := target.Generate(rs, 5, nil) + ci := r.Intn(len(p.Calls)) + p1, ci1 := Minimize(p, ci, r.Intn(2) == 0, func(p1 *Prog, callIndex int) bool { + return r.Intn(2) == 0 + }) + if ci1 < 0 || ci1 >= len(p1.Calls) || p.Calls[ci].Meta.Name != p1.Calls[ci1].Meta.Name { + t.Fatalf("bad call index after minimization") + } + } +} diff --git a/prog/mutation_test.go b/prog/mutation_test.go index 6452eddfa..5c5ac232a 100644 --- a/prog/mutation_test.go +++ b/prog/mutation_test.go @@ -187,171 +187,6 @@ mutate8(0xffffffffffffffff) } } -func TestMinimize(t *testing.T) { - tests := []struct { - orig string - callIndex int - pred func(*Prog, int) bool - result string - resultCallIndex int - }{ - // Predicate always returns false, so must get the same program. - { - "mmap(&(0x7f0000000000/0x1000)=nil, 0x1000, 0x3, 0x32, 0xffffffffffffffff, 0x0)\n" + - "sched_yield()\n" + - "pipe2(&(0x7f0000000000)={0x0, 0x0}, 0x0)\n", - 2, - func(p *Prog, callIndex int) bool { - if len(p.Calls) == 0 { - t.Fatalf("got an empty program") - } - if p.Calls[len(p.Calls)-1].Meta.Name != "pipe2" { - t.Fatalf("last call is removed") - } - return false - }, - "mmap(&(0x7f0000000000/0x1000)=nil, 0x1000, 0x3, 0x32, 0xffffffffffffffff, 0x0)\n" + - "sched_yield()\n" + - "pipe2(&(0x7f0000000000), 0x0)\n", - 2, - }, - // Remove a call. - { - "mmap(&(0x7f0000000000/0x1000)=nil, 0x1000, 0x3, 0x32, 0xffffffffffffffff, 0x0)\n" + - "sched_yield()\n" + - "pipe2(&(0x7f0000000000)={0xffffffffffffffff, 0xffffffffffffffff}, 0x0)\n", - 2, - func(p *Prog, callIndex int) bool { - // Aim at removal of sched_yield. - return len(p.Calls) == 2 && p.Calls[0].Meta.Name == "mmap" && p.Calls[1].Meta.Name == "pipe2" - }, - "mmap(&(0x7f0000000000/0x1000)=nil, 0x1000, 0x0, 0x0, 0xffffffffffffffff, 0x0)\n" + - "pipe2(&(0x7f0000000000)={0xffffffffffffffff, 0xffffffffffffffff}, 0x0)\n", - 1, - }, - // Remove two dependent calls. - { - "mmap(&(0x7f0000000000/0x1000)=nil, 0x1000, 0x3, 0x32, 0xffffffffffffffff, 0x0)\n" + - "pipe2(&(0x7f0000000000)={0x0, 0x0}, 0x0)\n" + - "sched_yield()\n", - 2, - func(p *Prog, callIndex int) bool { - // Aim at removal of pipe2 and then mmap. - if len(p.Calls) == 2 && p.Calls[0].Meta.Name == "mmap" && p.Calls[1].Meta.Name == "sched_yield" { - return true - } - if len(p.Calls) == 1 && p.Calls[0].Meta.Name == "sched_yield" { - return true - } - return false - }, - "sched_yield()\n", - 0, - }, - // Remove a call and replace results. - { - "mmap(&(0x7f0000000000/0x1000)=nil, 0x1000, 0x3, 0x32, 0xffffffffffffffff, 0x0)\n" + - "pipe2(&(0x7f0000000000)={<r0=>0x0, 0x0}, 0x0)\n" + - "write(r0, &(0x7f0000000000)=\"1155\", 0x2)\n" + - "sched_yield()\n", - 3, - func(p *Prog, callIndex int) bool { - return p.String() == "mmap-write-sched_yield" - }, - "mmap(&(0x7f0000000000/0x1000)=nil, 0x1000, 0x0, 0x0, 0xffffffffffffffff, 0x0)\n" + - "write(0xffffffffffffffff, &(0x7f0000000000), 0x0)\n" + - "sched_yield()\n", - 2, - }, - // Remove a call and replace results. - { - "mmap(&(0x7f0000000000/0x1000)=nil, 0x1000, 0x3, 0x32, 0xffffffffffffffff, 0x0)\n" + - "r0=open(&(0x7f0000000000)=\"1155\", 0x0, 0x0)\n" + - "write(r0, &(0x7f0000000000)=\"1155\", 0x2)\n" + - "sched_yield()\n", - -1, - func(p *Prog, callIndex int) bool { - return p.String() == "mmap-write-sched_yield" - }, - "mmap(&(0x7f0000000000/0x1000)=nil, 0x1000, 0x0, 0x0, 0xffffffffffffffff, 0x0)\n" + - "write(0xffffffffffffffff, &(0x7f0000000000), 0x0)\n" + - "sched_yield()\n", - -1, - }, - // Glue several mmaps together. - { - "sched_yield()\n" + - "mmap(&(0x7f0000010000/0x1000)=nil, 0x1000, 0x3, 0x32, 0xffffffffffffffff, 0x0)\n" + - "mmap(&(0x7f0000011000/0x1000)=nil, 0x1000, 0x3, 0x32, 0xffffffffffffffff, 0x0)\n" + - "getpid()\n" + - "mmap(&(0x7f0000015000/0x5000)=nil, 0x2000, 0x3, 0x32, 0xffffffffffffffff, 0x0)\n", - 3, - func(p *Prog, callIndex int) bool { - return p.String() == "mmap-sched_yield-getpid" - }, - "mmap(&(0x7f0000010000/0x7000)=nil, 0x7000, 0x0, 0x0, 0xffffffffffffffff, 0x0)\n" + - "sched_yield()\n" + - "getpid()\n", - 2, - }, - } - target, _, _ := initTest(t) - for ti, test := range tests { - p, err := target.Deserialize([]byte(test.orig)) - if err != nil { - t.Fatalf("failed to deserialize original program #%v: %v", ti, err) - } - p1, ci := Minimize(p, test.callIndex, false, test.pred) - res := p1.Serialize() - if string(res) != test.result { - t.Fatalf("minimization produced wrong result #%v\norig:\n%v\nexpect:\n%v\ngot:\n%v\n", - ti, test.orig, test.result, string(res)) - } - if ci != test.resultCallIndex { - t.Fatalf("minimization broke call index #%v: got %v, want %v", - ti, ci, test.resultCallIndex) - } - } -} - -func TestMinimizeRandom(t *testing.T) { - target, rs, iters := initTest(t) - iters /= 10 // Long test. - for i := 0; i < iters; i++ { - p := target.Generate(rs, 5, nil) - Minimize(p, len(p.Calls)-1, true, func(p1 *Prog, callIndex int) bool { - return false - }) - Minimize(p, len(p.Calls)-1, true, func(p1 *Prog, callIndex int) bool { - return true - }) - } - for i := 0; i < iters; i++ { - p := target.Generate(rs, 5, nil) - Minimize(p, len(p.Calls)-1, false, func(p1 *Prog, callIndex int) bool { - return false - }) - Minimize(p, len(p.Calls)-1, false, func(p1 *Prog, callIndex int) bool { - return true - }) - } -} - -func TestMinimizeCallIndex(t *testing.T) { - target, rs, iters := initTest(t) - r := rand.New(rs) - for i := 0; i < iters; i++ { - p := target.Generate(rs, 5, nil) - ci := r.Intn(len(p.Calls)) - p1, ci1 := Minimize(p, ci, r.Intn(2) == 0, func(p1 *Prog, callIndex int) bool { - return r.Intn(2) == 0 - }) - if ci1 < 0 || ci1 >= len(p1.Calls) || p.Calls[ci].Meta.Name != p1.Calls[ci1].Meta.Name { - t.Fatalf("bad call index after minimization") - } - } -} - func BenchmarkMutate(b *testing.B) { olddebug := debug debug = false |