1// Copyright 2015 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 "fmt" 8 "math/rand" 9 "unsafe" 10) 11 12const maxBlobLen = uint64(100 << 10) 13 14func (p *Prog) Mutate(rs rand.Source, ncalls int, ct *ChoiceTable, corpus []*Prog) { 15 r := newRand(p.Target, rs) 16 ctx := &mutator{ 17 p: p, 18 r: r, 19 ncalls: ncalls, 20 ct: ct, 21 corpus: corpus, 22 } 23 for stop, ok := false, false; !stop; stop = ok && r.oneOf(3) { 24 switch { 25 case r.oneOf(5): 26 // Not all calls have anything squashable, 27 // so this has lower priority in reality. 28 ok = ctx.squashAny() 29 case r.nOutOf(1, 100): 30 ok = ctx.splice() 31 case r.nOutOf(20, 31): 32 ok = ctx.insertCall() 33 case r.nOutOf(10, 11): 34 ok = ctx.mutateArg() 35 default: 36 ok = ctx.removeCall() 37 } 38 } 39 for _, c := range p.Calls { 40 p.Target.SanitizeCall(c) 41 } 42 p.debugValidate() 43} 44 45type mutator struct { 46 p *Prog 47 r *randGen 48 ncalls int 49 ct *ChoiceTable 50 corpus []*Prog 51} 52 53func (ctx *mutator) splice() bool { 54 p, r := ctx.p, ctx.r 55 if len(ctx.corpus) == 0 || len(p.Calls) == 0 { 56 return false 57 } 58 p0 := ctx.corpus[r.Intn(len(ctx.corpus))] 59 p0c := p0.Clone() 60 idx := r.Intn(len(p.Calls)) 61 p.Calls = append(p.Calls[:idx], append(p0c.Calls, p.Calls[idx:]...)...) 62 for i := len(p.Calls) - 1; i >= ctx.ncalls; i-- { 63 p.removeCall(i) 64 } 65 return true 66} 67 68func (ctx *mutator) squashAny() bool { 69 p, r := ctx.p, ctx.r 70 complexPtrs := p.complexPtrs() 71 if len(complexPtrs) == 0 { 72 return false 73 } 74 ptr := complexPtrs[r.Intn(len(complexPtrs))] 75 if !p.Target.isAnyPtr(ptr.Type()) { 76 p.Target.squashPtr(ptr, true) 77 } 78 var blobs []*DataArg 79 var bases []*PointerArg 80 ForeachSubArg(ptr, func(arg Arg, ctx *ArgCtx) { 81 if data, ok := arg.(*DataArg); ok && arg.Type().Dir() != DirOut { 82 blobs = append(blobs, data) 83 bases = append(bases, ctx.Base) 84 } 85 }) 86 if len(blobs) == 0 { 87 return false 88 } 89 // TODO(dvyukov): we probably want special mutation for ANY. 90 // E.g. merging adjacent ANYBLOBs (we don't create them, 91 // but they can appear in future); or replacing ANYRES 92 // with a blob (and merging it with adjacent blobs). 93 idx := r.Intn(len(blobs)) 94 arg := blobs[idx] 95 base := bases[idx] 96 baseSize := base.Res.Size() 97 arg.data = mutateData(r, arg.Data(), 0, maxBlobLen) 98 // Update base pointer if size has increased. 99 if baseSize < base.Res.Size() { 100 s := analyze(ctx.ct, p, p.Calls[0]) 101 newArg := r.allocAddr(s, base.Type(), base.Res.Size(), base.Res) 102 *base = *newArg 103 } 104 return true 105} 106 107func (ctx *mutator) insertCall() bool { 108 p, r := ctx.p, ctx.r 109 if len(p.Calls) >= ctx.ncalls { 110 return false 111 } 112 idx := r.biasedRand(len(p.Calls)+1, 5) 113 var c *Call 114 if idx < len(p.Calls) { 115 c = p.Calls[idx] 116 } 117 s := analyze(ctx.ct, p, c) 118 calls := r.generateCall(s, p) 119 p.insertBefore(c, calls) 120 return true 121} 122 123func (ctx *mutator) removeCall() bool { 124 p, r := ctx.p, ctx.r 125 if len(p.Calls) == 0 { 126 return false 127 } 128 idx := r.Intn(len(p.Calls)) 129 p.removeCall(idx) 130 return true 131} 132 133func (ctx *mutator) mutateArg() bool { 134 p, r := ctx.p, ctx.r 135 if len(p.Calls) == 0 { 136 return false 137 } 138 c := p.Calls[r.Intn(len(p.Calls))] 139 if len(c.Args) == 0 { 140 return false 141 } 142 s := analyze(ctx.ct, p, c) 143 updateSizes := true 144 for stop, ok := false, false; !stop; stop = ok && r.oneOf(3) { 145 ok = true 146 ma := &mutationArgs{target: p.Target} 147 ForeachArg(c, ma.collectArg) 148 if len(ma.args) == 0 { 149 return false 150 } 151 idx := r.Intn(len(ma.args)) 152 arg, ctx := ma.args[idx], ma.ctxes[idx] 153 calls, ok1 := p.Target.mutateArg(r, s, arg, ctx, &updateSizes) 154 if !ok1 { 155 ok = false 156 continue 157 } 158 p.insertBefore(c, calls) 159 if updateSizes { 160 p.Target.assignSizesCall(c) 161 } 162 p.Target.SanitizeCall(c) 163 } 164 return true 165} 166 167func (target *Target) mutateArg(r *randGen, s *state, arg Arg, ctx ArgCtx, updateSizes *bool) ([]*Call, bool) { 168 var baseSize uint64 169 if ctx.Base != nil { 170 baseSize = ctx.Base.Res.Size() 171 } 172 calls, retry, preserve := arg.Type().mutate(r, s, arg, ctx) 173 if retry { 174 return nil, false 175 } 176 if preserve { 177 *updateSizes = false 178 } 179 // Update base pointer if size has increased. 180 if base := ctx.Base; base != nil && baseSize < base.Res.Size() { 181 newArg := r.allocAddr(s, base.Type(), base.Res.Size(), base.Res) 182 replaceArg(base, newArg) 183 } 184 for _, c := range calls { 185 target.SanitizeCall(c) 186 } 187 return calls, true 188} 189 190func regenerate(r *randGen, s *state, arg Arg) (calls []*Call, retry, preserve bool) { 191 var newArg Arg 192 newArg, calls = r.generateArg(s, arg.Type()) 193 replaceArg(arg, newArg) 194 return 195} 196 197func mutateInt(r *randGen, s *state, arg Arg) (calls []*Call, retry, preserve bool) { 198 if r.bin() { 199 return regenerate(r, s, arg) 200 } 201 a := arg.(*ConstArg) 202 switch { 203 case r.nOutOf(1, 3): 204 a.Val += uint64(r.Intn(4)) + 1 205 case r.nOutOf(1, 2): 206 a.Val -= uint64(r.Intn(4)) + 1 207 default: 208 a.Val ^= 1 << uint64(r.Intn(64)) 209 } 210 return 211} 212 213func (t *IntType) mutate(r *randGen, s *state, arg Arg, ctx ArgCtx) (calls []*Call, retry, preserve bool) { 214 return mutateInt(r, s, arg) 215} 216 217func (t *FlagsType) mutate(r *randGen, s *state, arg Arg, ctx ArgCtx) (calls []*Call, retry, preserve bool) { 218 return mutateInt(r, s, arg) 219} 220 221func (t *LenType) mutate(r *randGen, s *state, arg Arg, ctx ArgCtx) (calls []*Call, retry, preserve bool) { 222 if !r.mutateSize(arg.(*ConstArg), *ctx.Parent) { 223 retry = true 224 return 225 } 226 preserve = true 227 return 228} 229 230func (t *ResourceType) mutate(r *randGen, s *state, arg Arg, ctx ArgCtx) (calls []*Call, retry, preserve bool) { 231 return regenerate(r, s, arg) 232} 233 234func (t *VmaType) mutate(r *randGen, s *state, arg Arg, ctx ArgCtx) (calls []*Call, retry, preserve bool) { 235 return regenerate(r, s, arg) 236} 237 238func (t *ProcType) mutate(r *randGen, s *state, arg Arg, ctx ArgCtx) (calls []*Call, retry, preserve bool) { 239 return regenerate(r, s, arg) 240} 241 242func (t *BufferType) mutate(r *randGen, s *state, arg Arg, ctx ArgCtx) (calls []*Call, retry, preserve bool) { 243 a := arg.(*DataArg) 244 switch t.Kind { 245 case BufferBlobRand, BufferBlobRange: 246 data := append([]byte{}, a.Data()...) 247 minLen, maxLen := uint64(0), maxBlobLen 248 if t.Kind == BufferBlobRange { 249 minLen, maxLen = t.RangeBegin, t.RangeEnd 250 } 251 a.data = mutateData(r, data, minLen, maxLen) 252 case BufferString: 253 data := append([]byte{}, a.Data()...) 254 if r.bin() { 255 minLen, maxLen := uint64(0), maxBlobLen 256 if t.TypeSize != 0 { 257 minLen, maxLen = t.TypeSize, t.TypeSize 258 } 259 a.data = mutateData(r, data, minLen, maxLen) 260 } else { 261 a.data = r.randString(s, t) 262 } 263 case BufferFilename: 264 a.data = []byte(r.filename(s, t)) 265 case BufferText: 266 data := append([]byte{}, a.Data()...) 267 a.data = r.mutateText(t.Text, data) 268 default: 269 panic("unknown buffer kind") 270 } 271 return 272} 273 274func (t *ArrayType) mutate(r *randGen, s *state, arg Arg, ctx ArgCtx) (calls []*Call, retry, preserve bool) { 275 // TODO: swap elements of the array 276 a := arg.(*GroupArg) 277 count := uint64(0) 278 switch t.Kind { 279 case ArrayRandLen: 280 for count == uint64(len(a.Inner)) { 281 count = r.randArrayLen() 282 } 283 case ArrayRangeLen: 284 if t.RangeBegin == t.RangeEnd { 285 panic("trying to mutate fixed length array") 286 } 287 for count == uint64(len(a.Inner)) { 288 count = r.randRange(t.RangeBegin, t.RangeEnd) 289 } 290 } 291 if count > uint64(len(a.Inner)) { 292 for count > uint64(len(a.Inner)) { 293 newArg, newCalls := r.generateArg(s, t.Type) 294 a.Inner = append(a.Inner, newArg) 295 calls = append(calls, newCalls...) 296 for _, c := range newCalls { 297 s.analyze(c) 298 } 299 } 300 } else if count < uint64(len(a.Inner)) { 301 for _, arg := range a.Inner[count:] { 302 removeArg(arg) 303 } 304 a.Inner = a.Inner[:count] 305 } 306 return 307} 308 309func (t *PtrType) mutate(r *randGen, s *state, arg Arg, ctx ArgCtx) (calls []*Call, retry, preserve bool) { 310 a := arg.(*PointerArg) 311 newArg := r.allocAddr(s, t, a.Res.Size(), a.Res) 312 replaceArg(arg, newArg) 313 return 314} 315 316func (t *StructType) mutate(r *randGen, s *state, arg Arg, ctx ArgCtx) (calls []*Call, retry, preserve bool) { 317 gen := r.target.SpecialTypes[t.Name()] 318 if gen == nil { 319 panic("bad arg returned by mutationArgs: StructType") 320 } 321 var newArg Arg 322 newArg, calls = gen(&Gen{r, s}, t, arg) 323 a := arg.(*GroupArg) 324 for i, f := range newArg.(*GroupArg).Inner { 325 replaceArg(a.Inner[i], f) 326 } 327 return 328} 329 330func (t *UnionType) mutate(r *randGen, s *state, arg Arg, ctx ArgCtx) (calls []*Call, retry, preserve bool) { 331 if gen := r.target.SpecialTypes[t.Name()]; gen != nil { 332 var newArg Arg 333 newArg, calls = gen(&Gen{r, s}, t, arg) 334 replaceArg(arg, newArg) 335 } else { 336 a := arg.(*UnionArg) 337 current := -1 338 for i, option := range t.Fields { 339 if a.Option.Type().FieldName() == option.FieldName() { 340 current = i 341 break 342 } 343 } 344 if current == -1 { 345 panic("can't find current option in union") 346 } 347 newIdx := r.Intn(len(t.Fields) - 1) 348 if newIdx >= current { 349 newIdx++ 350 } 351 optType := t.Fields[newIdx] 352 removeArg(a.Option) 353 var newOpt Arg 354 newOpt, calls = r.generateArg(s, optType) 355 replaceArg(arg, MakeUnionArg(t, newOpt)) 356 } 357 return 358} 359 360func (t *CsumType) mutate(r *randGen, s *state, arg Arg, ctx ArgCtx) (calls []*Call, retry, preserve bool) { 361 panic("CsumType can't be mutated") 362} 363 364func (t *ConstType) mutate(r *randGen, s *state, arg Arg, ctx ArgCtx) (calls []*Call, retry, preserve bool) { 365 panic("ConstType can't be mutated") 366} 367 368type mutationArgs struct { 369 target *Target 370 args []Arg 371 ctxes []ArgCtx 372 ignoreSpecial bool 373} 374 375func (ma *mutationArgs) collectArg(arg Arg, ctx *ArgCtx) { 376 ignoreSpecial := ma.ignoreSpecial 377 ma.ignoreSpecial = false 378 switch typ := arg.Type().(type) { 379 case *StructType: 380 if ma.target.SpecialTypes[typ.Name()] == nil || ignoreSpecial { 381 return // For structs only individual fields are updated. 382 } 383 // These special structs are mutated as a whole. 384 ctx.Stop = true 385 case *UnionType: 386 if ma.target.SpecialTypes[typ.Name()] == nil && len(typ.Fields) == 1 || ignoreSpecial { 387 return 388 } 389 ctx.Stop = true 390 case *ArrayType: 391 // Don't mutate fixed-size arrays. 392 if typ.Kind == ArrayRangeLen && typ.RangeBegin == typ.RangeEnd { 393 return 394 } 395 case *CsumType: 396 return // Checksum is updated when the checksummed data changes. 397 case *ConstType: 398 return // Well, this is const. 399 case *BufferType: 400 if typ.Kind == BufferString && len(typ.Values) == 1 { 401 return // string const 402 } 403 case *PtrType: 404 if arg.(*PointerArg).IsNull() { 405 // TODO: we ought to mutate this, but we don't have code for this yet. 406 return 407 } 408 } 409 typ := arg.Type() 410 if typ == nil || typ.Dir() == DirOut || !typ.Varlen() && typ.Size() == 0 { 411 return 412 } 413 ma.args = append(ma.args, arg) 414 ma.ctxes = append(ma.ctxes, *ctx) 415} 416 417func mutateData(r *randGen, data []byte, minLen, maxLen uint64) []byte { 418 for stop := false; !stop; stop = stop && r.oneOf(3) { 419 f := mutateDataFuncs[r.Intn(len(mutateDataFuncs))] 420 data, stop = f(r, data, minLen, maxLen) 421 } 422 return data 423} 424 425const maxInc = 35 426 427var mutateDataFuncs = [...]func(r *randGen, data []byte, minLen, maxLen uint64) ([]byte, bool){ 428 // TODO(dvyukov): duplicate part of data. 429 // Flip bit in byte. 430 func(r *randGen, data []byte, minLen, maxLen uint64) ([]byte, bool) { 431 if len(data) == 0 { 432 return data, false 433 } 434 byt := r.Intn(len(data)) 435 bit := r.Intn(8) 436 data[byt] ^= 1 << uint(bit) 437 return data, true 438 }, 439 // Insert random bytes. 440 func(r *randGen, data []byte, minLen, maxLen uint64) ([]byte, bool) { 441 if len(data) == 0 { 442 return data, false 443 } 444 n := r.Intn(16) + 1 445 if r := int(maxLen) - len(data); n > r { 446 n = r 447 } 448 pos := r.Intn(len(data)) 449 for i := 0; i < n; i++ { 450 data = append(data, 0) 451 } 452 copy(data[pos+n:], data[pos:]) 453 for i := 0; i < n; i++ { 454 data[pos+i] = byte(r.Int31()) 455 } 456 if uint64(len(data)) > maxLen || r.bin() { 457 data = data[:len(data)-n] // preserve original length 458 } 459 return data, true 460 }, 461 // Remove bytes. 462 func(r *randGen, data []byte, minLen, maxLen uint64) ([]byte, bool) { 463 if len(data) == 0 { 464 return data, false 465 } 466 n := r.Intn(16) + 1 467 if n > len(data) { 468 n = len(data) 469 } 470 pos := 0 471 if n < len(data) { 472 pos = r.Intn(len(data) - n) 473 } 474 copy(data[pos:], data[pos+n:]) 475 data = data[:len(data)-n] 476 if uint64(len(data)) < minLen || r.bin() { 477 for i := 0; i < n; i++ { 478 data = append(data, 0) // preserve original length 479 } 480 } 481 return data, true 482 }, 483 // Append a bunch of bytes. 484 func(r *randGen, data []byte, minLen, maxLen uint64) ([]byte, bool) { 485 if uint64(len(data)) >= maxLen { 486 return data, false 487 } 488 const max = 256 489 n := max - r.biasedRand(max, 10) 490 if r := int(maxLen) - len(data); n > r { 491 n = r 492 } 493 for i := 0; i < n; i++ { 494 data = append(data, byte(r.rand(256))) 495 } 496 return data, true 497 }, 498 // Replace int8/int16/int32/int64 with a random value. 499 func(r *randGen, data []byte, minLen, maxLen uint64) ([]byte, bool) { 500 width := 1 << uint(r.Intn(4)) 501 if len(data) < width { 502 return data, false 503 } 504 i := r.Intn(len(data) - width + 1) 505 storeInt(data[i:], r.Uint64(), width) 506 return data, true 507 }, 508 // Add/subtract from an int8/int16/int32/int64. 509 func(r *randGen, data []byte, minLen, maxLen uint64) ([]byte, bool) { 510 width := 1 << uint(r.Intn(4)) 511 if len(data) < width { 512 return data, false 513 } 514 i := r.Intn(len(data) - width + 1) 515 v := loadInt(data[i:], width) 516 delta := r.rand(2*maxInc+1) - maxInc 517 if delta == 0 { 518 delta = 1 519 } 520 if r.oneOf(10) { 521 v = swapInt(v, width) 522 v += delta 523 v = swapInt(v, width) 524 } else { 525 v += delta 526 } 527 storeInt(data[i:], v, width) 528 return data, true 529 }, 530 // Set int8/int16/int32/int64 to an interesting value. 531 func(r *randGen, data []byte, minLen, maxLen uint64) ([]byte, bool) { 532 width := 1 << uint(r.Intn(4)) 533 if len(data) < width { 534 return data, false 535 } 536 i := r.Intn(len(data) - width + 1) 537 value := r.randInt() 538 if r.oneOf(10) { 539 value = swap64(value) 540 } 541 storeInt(data[i:], value, width) 542 return data, true 543 }, 544} 545 546func swap16(v uint16) uint16 { 547 v0 := byte(v >> 0) 548 v1 := byte(v >> 8) 549 v = 0 550 v |= uint16(v1) << 0 551 v |= uint16(v0) << 8 552 return v 553} 554 555func swap32(v uint32) uint32 { 556 v0 := byte(v >> 0) 557 v1 := byte(v >> 8) 558 v2 := byte(v >> 16) 559 v3 := byte(v >> 24) 560 v = 0 561 v |= uint32(v3) << 0 562 v |= uint32(v2) << 8 563 v |= uint32(v1) << 16 564 v |= uint32(v0) << 24 565 return v 566} 567 568func swap64(v uint64) uint64 { 569 v0 := byte(v >> 0) 570 v1 := byte(v >> 8) 571 v2 := byte(v >> 16) 572 v3 := byte(v >> 24) 573 v4 := byte(v >> 32) 574 v5 := byte(v >> 40) 575 v6 := byte(v >> 48) 576 v7 := byte(v >> 56) 577 v = 0 578 v |= uint64(v7) << 0 579 v |= uint64(v6) << 8 580 v |= uint64(v5) << 16 581 v |= uint64(v4) << 24 582 v |= uint64(v3) << 32 583 v |= uint64(v2) << 40 584 v |= uint64(v1) << 48 585 v |= uint64(v0) << 56 586 return v 587} 588 589func swapInt(v uint64, size int) uint64 { 590 switch size { 591 case 1: 592 return v 593 case 2: 594 return uint64(swap16(uint16(v))) 595 case 4: 596 return uint64(swap32(uint32(v))) 597 case 8: 598 return swap64(v) 599 default: 600 panic(fmt.Sprintf("swapInt: bad size %v", size)) 601 } 602} 603 604func loadInt(data []byte, size int) uint64 { 605 p := unsafe.Pointer(&data[0]) 606 switch size { 607 case 1: 608 return uint64(*(*uint8)(p)) 609 case 2: 610 return uint64(*(*uint16)(p)) 611 case 4: 612 return uint64(*(*uint32)(p)) 613 case 8: 614 return *(*uint64)(p) 615 default: 616 panic(fmt.Sprintf("loadInt: bad size %v", size)) 617 } 618} 619 620func storeInt(data []byte, v uint64, size int) { 621 p := unsafe.Pointer(&data[0]) 622 switch size { 623 case 1: 624 *(*uint8)(p) = uint8(v) 625 case 2: 626 *(*uint16)(p) = uint16(v) 627 case 4: 628 *(*uint32)(p) = uint32(v) 629 case 8: 630 *(*uint64)(p) = v 631 default: 632 panic(fmt.Sprintf("storeInt: bad size %v", size)) 633 } 634} 635