1// Copyright 2018 syzkaller project authors. All rights reserved. 2// Use of this source code is governed by Apache 2 LICENSE that can be found in the LICENSE file. 3 4package prog 5 6import ( 7 "math/rand" 8 "testing" 9) 10 11func TestMinimize(t *testing.T) { 12 tests := []struct { 13 orig string 14 callIndex int 15 pred func(*Prog, int) bool 16 result string 17 resultCallIndex int 18 }{ 19 // Predicate always returns false, so must get the same program. 20 { 21 "mmap(&(0x7f0000000000/0x1000)=nil, 0x1000, 0x3, 0x32, 0xffffffffffffffff, 0x0)\n" + 22 "sched_yield()\n" + 23 "pipe2(&(0x7f0000000000), 0x0)\n", 24 2, 25 func(p *Prog, callIndex int) bool { 26 if len(p.Calls) == 0 { 27 t.Fatalf("got an empty program") 28 } 29 if p.Calls[len(p.Calls)-1].Meta.Name != "pipe2" { 30 t.Fatalf("last call is removed") 31 } 32 return false 33 }, 34 "mmap(&(0x7f0000000000/0x1000)=nil, 0x1000, 0x3, 0x32, 0xffffffffffffffff, 0x0)\n" + 35 "sched_yield()\n" + 36 "pipe2(&(0x7f0000000000), 0x0)\n", 37 2, 38 }, 39 // Remove a call. 40 { 41 "mmap(&(0x7f0000000000/0x1000)=nil, 0x1000, 0x3, 0x32, 0xffffffffffffffff, 0x0)\n" + 42 "sched_yield()\n" + 43 "pipe2(&(0x7f0000000000)={0xffffffffffffffff, 0xffffffffffffffff}, 0x0)\n", 44 2, 45 func(p *Prog, callIndex int) bool { 46 // Aim at removal of sched_yield. 47 return len(p.Calls) == 2 && p.Calls[0].Meta.Name == "mmap" && p.Calls[1].Meta.Name == "pipe2" 48 }, 49 "mmap(&(0x7f0000000000/0x1000)=nil, 0x1000, 0x0, 0x10, 0xffffffffffffffff, 0x0)\n" + 50 "pipe2(&(0x7f0000000000), 0x0)\n", 51 1, 52 }, 53 // Remove two dependent calls. 54 { 55 "mmap(&(0x7f0000000000/0x1000)=nil, 0x1000, 0x3, 0x32, 0xffffffffffffffff, 0x0)\n" + 56 "pipe2(&(0x7f0000000000)={0x0, 0x0}, 0x0)\n" + 57 "sched_yield()\n", 58 2, 59 func(p *Prog, callIndex int) bool { 60 // Aim at removal of pipe2 and then mmap. 61 if len(p.Calls) == 2 && p.Calls[0].Meta.Name == "mmap" && p.Calls[1].Meta.Name == "sched_yield" { 62 return true 63 } 64 if len(p.Calls) == 1 && p.Calls[0].Meta.Name == "sched_yield" { 65 return true 66 } 67 return false 68 }, 69 "sched_yield()\n", 70 0, 71 }, 72 // Remove a call and replace results. 73 { 74 "mmap(&(0x7f0000000000/0x1000)=nil, 0x1000, 0x3, 0x32, 0xffffffffffffffff, 0x0)\n" + 75 "pipe2(&(0x7f0000000000)={<r0=>0x0, 0x0}, 0x0)\n" + 76 "write(r0, &(0x7f0000000000)=\"1155\", 0x2)\n" + 77 "sched_yield()\n", 78 3, 79 func(p *Prog, callIndex int) bool { 80 return p.String() == "mmap-write-sched_yield" 81 }, 82 "mmap(&(0x7f0000000000/0x1000)=nil, 0x1000, 0x0, 0x10, 0xffffffffffffffff, 0x0)\n" + 83 "write(0xffffffffffffffff, &(0x7f0000000000), 0x0)\n" + 84 "sched_yield()\n", 85 2, 86 }, 87 // Remove a call and replace results. 88 { 89 "mmap(&(0x7f0000000000/0x1000)=nil, 0x1000, 0x3, 0x32, 0xffffffffffffffff, 0x0)\n" + 90 "r0=open(&(0x7f0000000000)=\"1155\", 0x0, 0x0)\n" + 91 "write(r0, &(0x7f0000000000)=\"1155\", 0x2)\n" + 92 "sched_yield()\n", 93 -1, 94 func(p *Prog, callIndex int) bool { 95 return p.String() == "mmap-write-sched_yield" 96 }, 97 "mmap(&(0x7f0000000000/0x1000)=nil, 0x1000, 0x0, 0x10, 0xffffffffffffffff, 0x0)\n" + 98 "write(0xffffffffffffffff, &(0x7f0000000000), 0x0)\n" + 99 "sched_yield()\n", 100 -1, 101 }, 102 } 103 target, _, _ := initTest(t) 104 for ti, test := range tests { 105 p, err := target.Deserialize([]byte(test.orig)) 106 if err != nil { 107 t.Fatalf("failed to deserialize original program #%v: %v", ti, err) 108 } 109 p1, ci := Minimize(p, test.callIndex, false, test.pred) 110 res := p1.Serialize() 111 if string(res) != test.result { 112 t.Fatalf("minimization produced wrong result #%v\norig:\n%v\nexpect:\n%v\ngot:\n%v\n", 113 ti, test.orig, test.result, string(res)) 114 } 115 if ci != test.resultCallIndex { 116 t.Fatalf("minimization broke call index #%v: got %v, want %v", 117 ti, ci, test.resultCallIndex) 118 } 119 } 120} 121 122func TestMinimizeRandom(t *testing.T) { 123 target, rs, iters := initTest(t) 124 iters /= 10 // Long test. 125 for i := 0; i < iters; i++ { 126 for _, crash := range []bool{false, true} { 127 p := target.Generate(rs, 5, nil) 128 Minimize(p, len(p.Calls)-1, crash, func(p1 *Prog, callIndex int) bool { 129 return false 130 }) 131 Minimize(p, len(p.Calls)-1, crash, func(p1 *Prog, callIndex int) bool { 132 return true 133 }) 134 } 135 } 136} 137 138func TestMinimizeCallIndex(t *testing.T) { 139 target, rs, iters := initTest(t) 140 r := rand.New(rs) 141 for i := 0; i < iters; i++ { 142 p := target.Generate(rs, 5, nil) 143 ci := r.Intn(len(p.Calls)) 144 p1, ci1 := Minimize(p, ci, r.Intn(2) == 0, func(p1 *Prog, callIndex int) bool { 145 return r.Intn(2) == 0 146 }) 147 if ci1 < 0 || ci1 >= len(p1.Calls) || p.Calls[ci].Meta.Name != p1.Calls[ci1].Meta.Name { 148 t.Fatalf("bad call index after minimization") 149 } 150 } 151} 152