1 // Copyright 2017 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 4 package main 5 6 import ( 7 "bytes" 8 "fmt" 9 "math/rand" 10 "os" 11 "runtime/debug" 12 "sync/atomic" 13 "syscall" 14 "time" 15 16 "github.com/google/syzkaller/pkg/cover" 17 "github.com/google/syzkaller/pkg/hash" 18 "github.com/google/syzkaller/pkg/ipc" 19 "github.com/google/syzkaller/pkg/log" 20 "github.com/google/syzkaller/pkg/rpctype" 21 "github.com/google/syzkaller/pkg/signal" 22 "github.com/google/syzkaller/prog" 23 ) 24 25 const ( 26 programLength = 30 27 ) 28 29 // Proc represents a single fuzzing process (executor). 30 type Proc struct { 31 fuzzer *Fuzzer 32 pid int 33 env *ipc.Env 34 rnd *rand.Rand 35 execOpts *ipc.ExecOpts 36 execOptsCover *ipc.ExecOpts 37 execOptsComps *ipc.ExecOpts 38 execOptsNoCollide *ipc.ExecOpts 39 } 40 41 func newProc(fuzzer *Fuzzer, pid int) (*Proc, error) { 42 env, err := ipc.MakeEnv(fuzzer.config, pid) 43 if err != nil { 44 return nil, err 45 } 46 rnd := rand.New(rand.NewSource(time.Now().UnixNano() + int64(pid)*1e12)) 47 execOptsNoCollide := *fuzzer.execOpts 48 execOptsNoCollide.Flags &= ^ipc.FlagCollide 49 execOptsCover := execOptsNoCollide 50 execOptsCover.Flags |= ipc.FlagCollectCover 51 execOptsComps := execOptsNoCollide 52 execOptsComps.Flags |= ipc.FlagCollectComps 53 proc := &Proc{ 54 fuzzer: fuzzer, 55 pid: pid, 56 env: env, 57 rnd: rnd, 58 execOpts: fuzzer.execOpts, 59 execOptsCover: &execOptsCover, 60 execOptsComps: &execOptsComps, 61 execOptsNoCollide: &execOptsNoCollide, 62 } 63 return proc, nil 64 } 65 66 func (proc *Proc) loop() { 67 generatePeriod := 100 68 if proc.fuzzer.config.Flags&ipc.FlagSignal == 0 { 69 // If we don't have real coverage signal, generate programs more frequently 70 // because fallback signal is weak. 71 generatePeriod = 2 72 } 73 for i := 0; ; i++ { 74 item := proc.fuzzer.workQueue.dequeue() 75 if item != nil { 76 switch item := item.(type) { 77 case *WorkTriage: 78 proc.triageInput(item) 79 case *WorkCandidate: 80 proc.execute(proc.execOpts, item.p, item.flags, StatCandidate) 81 case *WorkSmash: 82 proc.smashInput(item) 83 default: 84 log.Fatalf("unknown work type: %#v", item) 85 } 86 continue 87 } 88 89 ct := proc.fuzzer.choiceTable 90 corpus := proc.fuzzer.corpusSnapshot() 91 if len(corpus) == 0 || i%generatePeriod == 0 { 92 // Generate a new prog. 93 p := proc.fuzzer.target.Generate(proc.rnd, programLength, ct) 94 log.Logf(1, "#%v: generated", proc.pid) 95 proc.execute(proc.execOpts, p, ProgNormal, StatGenerate) 96 } else { 97 // Mutate an existing prog. 98 p := corpus[proc.rnd.Intn(len(corpus))].Clone() 99 p.Mutate(proc.rnd, programLength, ct, corpus) 100 log.Logf(1, "#%v: mutated", proc.pid) 101 proc.execute(proc.execOpts, p, ProgNormal, StatFuzz) 102 } 103 } 104 } 105 106 func (proc *Proc) triageInput(item *WorkTriage) { 107 log.Logf(1, "#%v: triaging type=%x", proc.pid, item.flags) 108 109 call := item.p.Calls[item.call] 110 inputSignal := signal.FromRaw(item.info.Signal, signalPrio(item.p.Target, call, &item.info)) 111 newSignal := proc.fuzzer.corpusSignalDiff(inputSignal) 112 if newSignal.Empty() { 113 return 114 } 115 log.Logf(3, "triaging input for %v (new signal=%v)", call.Meta.CallName, newSignal.Len()) 116 var inputCover cover.Cover 117 const ( 118 signalRuns = 3 119 minimizeAttempts = 3 120 ) 121 // Compute input coverage and non-flaky signal for minimization. 122 notexecuted := 0 123 for i := 0; i < signalRuns; i++ { 124 info := proc.executeRaw(proc.execOptsCover, item.p, StatTriage) 125 if len(info) == 0 || len(info[item.call].Signal) == 0 || 126 item.info.Errno == 0 && info[item.call].Errno != 0 { 127 // The call was not executed or failed. 128 notexecuted++ 129 if notexecuted > signalRuns/2+1 { 130 return // if happens too often, give up 131 } 132 continue 133 } 134 inf := info[item.call] 135 thisSignal := signal.FromRaw(inf.Signal, signalPrio(item.p.Target, call, &inf)) 136 newSignal = newSignal.Intersection(thisSignal) 137 // Without !minimized check manager starts losing some considerable amount 138 // of coverage after each restart. Mechanics of this are not completely clear. 139 if newSignal.Empty() && item.flags&ProgMinimized == 0 { 140 return 141 } 142 inputCover.Merge(inf.Cover) 143 } 144 if item.flags&ProgMinimized == 0 { 145 item.p, item.call = prog.Minimize(item.p, item.call, false, 146 func(p1 *prog.Prog, call1 int) bool { 147 for i := 0; i < minimizeAttempts; i++ { 148 info := proc.execute(proc.execOptsNoCollide, p1, ProgNormal, StatMinimize) 149 if len(info) == 0 || len(info[call1].Signal) == 0 { 150 continue // The call was not executed. 151 } 152 inf := info[call1] 153 if item.info.Errno == 0 && inf.Errno != 0 { 154 // Don't minimize calls from successful to unsuccessful. 155 // Successful calls are much more valuable. 156 return false 157 } 158 prio := signalPrio(p1.Target, p1.Calls[call1], &inf) 159 thisSignal := signal.FromRaw(inf.Signal, prio) 160 if newSignal.Intersection(thisSignal).Len() == newSignal.Len() { 161 return true 162 } 163 } 164 return false 165 }) 166 } 167 168 data := item.p.Serialize() 169 sig := hash.Hash(data) 170 171 log.Logf(2, "added new input for %v to corpus:\n%s", call.Meta.CallName, data) 172 proc.fuzzer.sendInputToManager(rpctype.RPCInput{ 173 Call: call.Meta.CallName, 174 Prog: data, 175 Signal: inputSignal.Serialize(), 176 Cover: inputCover.Serialize(), 177 }) 178 179 proc.fuzzer.addInputToCorpus(item.p, inputSignal, sig) 180 181 if item.flags&ProgSmashed == 0 { 182 proc.fuzzer.workQueue.enqueue(&WorkSmash{item.p, item.call}) 183 } 184 } 185 186 func (proc *Proc) smashInput(item *WorkSmash) { 187 if proc.fuzzer.faultInjectionEnabled { 188 proc.failCall(item.p, item.call) 189 } 190 if proc.fuzzer.comparisonTracingEnabled { 191 proc.executeHintSeed(item.p, item.call) 192 } 193 corpus := proc.fuzzer.corpusSnapshot() 194 for i := 0; i < 100; i++ { 195 p := item.p.Clone() 196 p.Mutate(proc.rnd, programLength, proc.fuzzer.choiceTable, corpus) 197 log.Logf(1, "#%v: smash mutated", proc.pid) 198 proc.execute(proc.execOpts, p, ProgNormal, StatSmash) 199 } 200 } 201 202 func (proc *Proc) failCall(p *prog.Prog, call int) { 203 for nth := 0; nth < 100; nth++ { 204 log.Logf(1, "#%v: injecting fault into call %v/%v", proc.pid, call, nth) 205 opts := *proc.execOpts 206 opts.Flags |= ipc.FlagInjectFault 207 opts.FaultCall = call 208 opts.FaultNth = nth 209 info := proc.executeRaw(&opts, p, StatSmash) 210 if info != nil && len(info) > call && info[call].Flags&ipc.CallFaultInjected == 0 { 211 break 212 } 213 } 214 } 215 216 func (proc *Proc) executeHintSeed(p *prog.Prog, call int) { 217 log.Logf(1, "#%v: collecting comparisons", proc.pid) 218 // First execute the original program to dump comparisons from KCOV. 219 info := proc.execute(proc.execOptsComps, p, ProgNormal, StatSeed) 220 if info == nil { 221 return 222 } 223 224 // Then mutate the initial program for every match between 225 // a syscall argument and a comparison operand. 226 // Execute each of such mutants to check if it gives new coverage. 227 p.MutateWithHints(call, info[call].Comps, func(p *prog.Prog) { 228 log.Logf(1, "#%v: executing comparison hint", proc.pid) 229 proc.execute(proc.execOpts, p, ProgNormal, StatHint) 230 }) 231 } 232 233 func (proc *Proc) execute(execOpts *ipc.ExecOpts, p *prog.Prog, flags ProgTypes, stat Stat) []ipc.CallInfo { 234 info := proc.executeRaw(execOpts, p, stat) 235 for _, callIndex := range proc.fuzzer.checkNewSignal(p, info) { 236 info := info[callIndex] 237 // info.Signal points to the output shmem region, detach it before queueing. 238 info.Signal = append([]uint32{}, info.Signal...) 239 // None of the caller use Cover, so just nil it instead of detaching. 240 // Note: triage input uses executeRaw to get coverage. 241 info.Cover = nil 242 proc.fuzzer.workQueue.enqueue(&WorkTriage{ 243 p: p.Clone(), 244 call: callIndex, 245 info: info, 246 flags: flags, 247 }) 248 } 249 return info 250 } 251 252 func (proc *Proc) executeRaw(opts *ipc.ExecOpts, p *prog.Prog, stat Stat) []ipc.CallInfo { 253 if opts.Flags&ipc.FlagDedupCover == 0 { 254 log.Fatalf("dedup cover is not enabled") 255 } 256 257 // Limit concurrency window and do leak checking once in a while. 258 ticket := proc.fuzzer.gate.Enter() 259 defer proc.fuzzer.gate.Leave(ticket) 260 261 proc.logProgram(opts, p) 262 try := 0 263 retry: 264 atomic.AddUint64(&proc.fuzzer.stats[stat], 1) 265 output, info, failed, hanged, err := proc.env.Exec(opts, p) 266 if failed { 267 // BUG in output should be recognized by manager. 268 log.Logf(0, "BUG: executor-detected bug:\n%s", output) 269 // Don't return any cover so that the input is not added to corpus. 270 return nil 271 } 272 if err != nil { 273 if _, ok := err.(ipc.ExecutorFailure); ok || try > 10 { 274 log.Fatalf("executor %v failed %v times:\n%v", proc.pid, try, err) 275 } 276 try++ 277 log.Logf(4, "fuzzer detected executor failure='%v', retrying #%d\n", err, (try + 1)) 278 debug.FreeOSMemory() 279 time.Sleep(time.Second) 280 goto retry 281 } 282 log.Logf(2, "result failed=%v hanged=%v: %s\n", failed, hanged, output) 283 return info 284 } 285 286 func (proc *Proc) logProgram(opts *ipc.ExecOpts, p *prog.Prog) { 287 if proc.fuzzer.outputType == OutputNone { 288 return 289 } 290 291 data := p.Serialize() 292 strOpts := "" 293 if opts.Flags&ipc.FlagInjectFault != 0 { 294 strOpts = fmt.Sprintf(" (fault-call:%v fault-nth:%v)", opts.FaultCall, opts.FaultNth) 295 } 296 297 // The following output helps to understand what program crashed kernel. 298 // It must not be intermixed. 299 switch proc.fuzzer.outputType { 300 case OutputStdout: 301 now := time.Now() 302 proc.fuzzer.logMu.Lock() 303 fmt.Printf("%02v:%02v:%02v executing program %v%v:\n%s\n", 304 now.Hour(), now.Minute(), now.Second(), 305 proc.pid, strOpts, data) 306 proc.fuzzer.logMu.Unlock() 307 case OutputDmesg: 308 fd, err := syscall.Open("/dev/kmsg", syscall.O_WRONLY, 0) 309 if err == nil { 310 buf := new(bytes.Buffer) 311 fmt.Fprintf(buf, "syzkaller: executing program %v%v:\n%s\n", 312 proc.pid, strOpts, data) 313 syscall.Write(fd, buf.Bytes()) 314 syscall.Close(fd) 315 } 316 case OutputFile: 317 f, err := os.Create(fmt.Sprintf("%v-%v.prog", proc.fuzzer.name, proc.pid)) 318 if err == nil { 319 if strOpts != "" { 320 fmt.Fprintf(f, "#%v\n", strOpts) 321 } 322 f.Write(data) 323 f.Close() 324 } 325 default: 326 log.Fatalf("unknown output type: %v", proc.fuzzer.outputType) 327 } 328 } 329