1// Copyright 2015/2016 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 "bytes" 8 "fmt" 9 "math" 10 "math/rand" 11 "path/filepath" 12 "strings" 13 14 "github.com/google/syzkaller/pkg/ifuzz" 15 _ "github.com/google/syzkaller/pkg/ifuzz/generated" // pull in generated instruction descriptions 16) 17 18type randGen struct { 19 *rand.Rand 20 target *Target 21 inCreateResource bool 22 recDepth map[string]int 23} 24 25func newRand(target *Target, rs rand.Source) *randGen { 26 return &randGen{ 27 Rand: rand.New(rs), 28 target: target, 29 recDepth: make(map[string]int), 30 } 31} 32 33func (r *randGen) rand(n int) uint64 { 34 return uint64(r.Intn(n)) 35} 36 37func (r *randGen) randRange(begin, end uint64) uint64 { 38 return begin + uint64(r.Intn(int(end-begin+1))) 39} 40 41func (r *randGen) bin() bool { 42 return r.Intn(2) == 0 43} 44 45func (r *randGen) oneOf(n int) bool { 46 return r.Intn(n) == 0 47} 48 49func (r *randGen) rand64() uint64 { 50 v := uint64(r.Int63()) 51 if r.bin() { 52 v |= 1 << 63 53 } 54 return v 55} 56 57// Some potentially interesting integers. 58var specialInts = []uint64{ 59 0, 1, 31, 32, 63, 64, 127, 128, 60 129, 255, 256, 257, 511, 512, 61 1023, 1024, 1025, 2047, 2048, 4095, 4096, 62 (1 << 15) - 1, (1 << 15), (1 << 15) + 1, 63 (1 << 16) - 1, (1 << 16), (1 << 16) + 1, 64 (1 << 31) - 1, (1 << 31), (1 << 31) + 1, 65 (1 << 32) - 1, (1 << 32), (1 << 32) + 1, 66} 67 68func (r *randGen) randInt() uint64 { 69 v := r.rand64() 70 switch { 71 case r.nOutOf(100, 182): 72 v %= 10 73 case r.nOutOf(50, 82): 74 v = specialInts[r.Intn(len(specialInts))] 75 case r.nOutOf(10, 32): 76 v %= 256 77 case r.nOutOf(10, 22): 78 v %= 4 << 10 79 case r.nOutOf(10, 12): 80 v %= 64 << 10 81 default: 82 v %= 1 << 31 83 } 84 switch { 85 case r.nOutOf(100, 107): 86 case r.nOutOf(5, 7): 87 v = uint64(-int64(v)) 88 default: 89 v <<= uint(r.Intn(63)) 90 } 91 return v 92} 93 94func (r *randGen) randRangeInt(begin uint64, end uint64) uint64 { 95 if r.oneOf(100) { 96 return r.randInt() 97 } 98 return begin + (r.Uint64() % (end - begin + 1)) 99} 100 101// biasedRand returns a random int in range [0..n), 102// probability of n-1 is k times higher than probability of 0. 103func (r *randGen) biasedRand(n, k int) int { 104 nf, kf := float64(n), float64(k) 105 rf := nf * (kf/2 + 1) * r.Float64() 106 bf := (-1 + math.Sqrt(1+2*kf*rf/nf)) * nf / kf 107 return int(bf) 108} 109 110func (r *randGen) randArrayLen() uint64 { 111 const maxLen = 10 112 // biasedRand produces: 10, 9, ..., 1, 0, 113 // we want: 1, 2, ..., 9, 10, 0 114 return uint64(maxLen-r.biasedRand(maxLen+1, 10)+1) % (maxLen + 1) 115} 116 117func (r *randGen) randBufLen() (n uint64) { 118 switch { 119 case r.nOutOf(50, 56): 120 n = r.rand(256) 121 case r.nOutOf(5, 6): 122 n = 4 << 10 123 } 124 return 125} 126 127func (r *randGen) randPageCount() (n uint64) { 128 switch { 129 case r.nOutOf(100, 106): 130 n = r.rand(4) + 1 131 case r.nOutOf(5, 6): 132 n = r.rand(20) + 1 133 default: 134 n = (r.rand(3) + 1) * 512 135 } 136 return 137} 138 139func (r *randGen) flags(vv []uint64) (v uint64) { 140 switch { 141 case r.nOutOf(90, 111): 142 for stop := false; !stop; stop = r.bin() { 143 v |= vv[r.rand(len(vv))] 144 } 145 case r.nOutOf(10, 21): 146 v = vv[r.rand(len(vv))] 147 case r.nOutOf(10, 11): 148 v = 0 149 default: 150 v = r.rand64() 151 } 152 return 153} 154 155func (r *randGen) filename(s *state, typ *BufferType) string { 156 fn := r.filenameImpl(s) 157 if len(fn) != 0 && fn[len(fn)-1] == 0 { 158 panic(fmt.Sprintf("zero-terminated filename: %q", fn)) 159 } 160 if !typ.Varlen() { 161 size := typ.Size() 162 if uint64(len(fn)) < size { 163 fn += string(make([]byte, size-uint64(len(fn)))) 164 } 165 fn = fn[:size] 166 } else if !typ.NoZ { 167 fn += "\x00" 168 } 169 return fn 170} 171 172var specialFiles = []string{"", "."} 173 174func (r *randGen) filenameImpl(s *state) string { 175 if r.oneOf(100) { 176 return specialFiles[r.Intn(len(specialFiles))] 177 } 178 if len(s.files) == 0 || r.oneOf(10) { 179 // Generate a new name. 180 dir := "." 181 if r.oneOf(2) && len(s.files) != 0 { 182 files := make([]string, 0, len(s.files)) 183 for f := range s.files { 184 files = append(files, f) 185 } 186 dir = files[r.Intn(len(files))] 187 if len(dir) > 0 && dir[len(dir)-1] == 0 { 188 dir = dir[:len(dir)-1] 189 } 190 if r.oneOf(10) && filepath.Clean(dir)[0] != '.' { 191 dir += "/.." 192 } 193 } 194 for i := 0; ; i++ { 195 f := fmt.Sprintf("%v/file%v", dir, i) 196 if !s.files[f] { 197 return f 198 } 199 } 200 } 201 files := make([]string, 0, len(s.files)) 202 for f := range s.files { 203 files = append(files, f) 204 } 205 return files[r.Intn(len(files))] 206} 207 208func (r *randGen) randString(s *state, t *BufferType) []byte { 209 if len(t.Values) != 0 { 210 return []byte(t.Values[r.Intn(len(t.Values))]) 211 } 212 if len(s.strings) != 0 && r.bin() { 213 // Return an existing string. 214 // TODO(dvyukov): make s.strings indexed by string SubKind. 215 strings := make([]string, 0, len(s.strings)) 216 for s := range s.strings { 217 strings = append(strings, s) 218 } 219 return []byte(strings[r.Intn(len(strings))]) 220 } 221 punct := []byte{'!', '@', '#', '$', '%', '^', '&', '*', '(', ')', '-', '+', '\\', 222 '/', ':', '.', ',', '-', '\'', '[', ']', '{', '}'} 223 buf := new(bytes.Buffer) 224 for r.nOutOf(3, 4) { 225 switch { 226 case r.nOutOf(10, 21): 227 dict := r.target.StringDictionary 228 if len(dict) != 0 { 229 buf.WriteString(dict[r.Intn(len(dict))]) 230 } 231 case r.nOutOf(10, 11): 232 buf.Write([]byte{punct[r.Intn(len(punct))]}) 233 default: 234 buf.Write([]byte{byte(r.Intn(256))}) 235 } 236 } 237 if r.oneOf(100) == t.NoZ { 238 buf.Write([]byte{0}) 239 } 240 return buf.Bytes() 241} 242 243func (r *randGen) allocAddr(s *state, typ Type, size uint64, data Arg) *PointerArg { 244 return MakePointerArg(typ, s.ma.alloc(r, size), data) 245} 246 247func (r *randGen) allocVMA(s *state, typ Type, numPages uint64) *PointerArg { 248 page := s.va.alloc(r, numPages) 249 return MakeVmaPointerArg(typ, page*r.target.PageSize, numPages*r.target.PageSize) 250} 251 252func (r *randGen) createResource(s *state, res *ResourceType) (arg Arg, calls []*Call) { 253 if r.inCreateResource { 254 special := res.SpecialValues() 255 return MakeResultArg(res, nil, special[r.Intn(len(special))]), nil 256 } 257 r.inCreateResource = true 258 defer func() { r.inCreateResource = false }() 259 260 kind := res.Desc.Name 261 if r.oneOf(1000) { 262 // Spoof resource subkind. 263 var all []string 264 for kind1 := range r.target.resourceMap { 265 if r.target.isCompatibleResource(res.Desc.Kind[0], kind1) { 266 all = append(all, kind1) 267 } 268 } 269 kind = all[r.Intn(len(all))] 270 } 271 // Find calls that produce the necessary resources. 272 metas0 := r.target.resourceCtors[kind] 273 // TODO: reduce priority of less specialized ctors. 274 var metas []*Syscall 275 for _, meta := range metas0 { 276 if s.ct == nil || s.ct.run[meta.ID] == nil { 277 continue 278 } 279 metas = append(metas, meta) 280 } 281 if len(metas) == 0 { 282 return res.makeDefaultArg(), nil 283 } 284 285 // Now we have a set of candidate calls that can create the necessary resource. 286 for i := 0; i < 1e3; i++ { 287 // Generate one of them. 288 meta := metas[r.Intn(len(metas))] 289 calls := r.generateParticularCall(s, meta) 290 s1 := newState(r.target, s.ct) 291 s1.analyze(calls[len(calls)-1]) 292 // Now see if we have what we want. 293 var allres []*ResultArg 294 for kind1, res1 := range s1.resources { 295 if r.target.isCompatibleResource(kind, kind1) { 296 allres = append(allres, res1...) 297 } 298 } 299 if len(allres) != 0 { 300 // Bingo! 301 arg := MakeResultArg(res, allres[r.Intn(len(allres))], 0) 302 return arg, calls 303 } 304 // Discard unsuccessful calls. 305 // Note: s.ma/va have already noted allocations of the new objects 306 // in discarded syscalls, ideally we should recreate state 307 // by analyzing the program again. 308 for _, c := range calls { 309 ForeachArg(c, func(arg Arg, _ *ArgCtx) { 310 if a, ok := arg.(*ResultArg); ok && a.Res != nil { 311 delete(a.Res.uses, a) 312 } 313 }) 314 } 315 } 316 // Generally we can loop several times, e.g. when we choose a call that returns 317 // the resource in an array, but then generateArg generated that array of zero length. 318 // But we must succeed eventually. 319 var ctors []string 320 for _, meta := range metas { 321 ctors = append(ctors, meta.Name) 322 } 323 panic(fmt.Sprintf("failed to create a resource %v with %v", 324 res.Desc.Kind[0], strings.Join(ctors, ", "))) 325} 326 327func (r *randGen) generateText(kind TextKind) []byte { 328 switch kind { 329 case TextArm64: 330 // Just a stub, need something better. 331 text := make([]byte, 50) 332 for i := range text { 333 text[i] = byte(r.Intn(256)) 334 } 335 return text 336 default: 337 cfg := createIfuzzConfig(kind) 338 return ifuzz.Generate(cfg, r.Rand) 339 } 340} 341 342func (r *randGen) mutateText(kind TextKind, text []byte) []byte { 343 switch kind { 344 case TextArm64: 345 return mutateData(r, text, 40, 60) 346 default: 347 cfg := createIfuzzConfig(kind) 348 return ifuzz.Mutate(cfg, r.Rand, text) 349 } 350} 351 352func createIfuzzConfig(kind TextKind) *ifuzz.Config { 353 cfg := &ifuzz.Config{ 354 Len: 10, 355 Priv: true, 356 Exec: true, 357 MemRegions: []ifuzz.MemRegion{ 358 {Start: 0 << 12, Size: 1 << 12}, 359 {Start: 1 << 12, Size: 1 << 12}, 360 {Start: 2 << 12, Size: 1 << 12}, 361 {Start: 3 << 12, Size: 1 << 12}, 362 {Start: 4 << 12, Size: 1 << 12}, 363 {Start: 5 << 12, Size: 1 << 12}, 364 {Start: 6 << 12, Size: 1 << 12}, 365 {Start: 7 << 12, Size: 1 << 12}, 366 {Start: 8 << 12, Size: 1 << 12}, 367 {Start: 9 << 12, Size: 1 << 12}, 368 {Start: 0xfec00000, Size: 0x100}, // ioapic 369 }, 370 } 371 switch kind { 372 case TextX86Real: 373 cfg.Mode = ifuzz.ModeReal16 374 case TextX86bit16: 375 cfg.Mode = ifuzz.ModeProt16 376 case TextX86bit32: 377 cfg.Mode = ifuzz.ModeProt32 378 case TextX86bit64: 379 cfg.Mode = ifuzz.ModeLong64 380 } 381 return cfg 382} 383 384// nOutOf returns true n out of outOf times. 385func (r *randGen) nOutOf(n, outOf int) bool { 386 if n <= 0 || n >= outOf { 387 panic("bad probability") 388 } 389 v := r.Intn(outOf) 390 return v < n 391} 392 393func (r *randGen) generateCall(s *state, p *Prog) []*Call { 394 idx := 0 395 if s.ct == nil { 396 idx = r.Intn(len(r.target.Syscalls)) 397 } else { 398 call := -1 399 if len(p.Calls) != 0 { 400 call = p.Calls[r.Intn(len(p.Calls))].Meta.ID 401 } 402 idx = s.ct.Choose(r.Rand, call) 403 } 404 meta := r.target.Syscalls[idx] 405 return r.generateParticularCall(s, meta) 406} 407 408func (r *randGen) generateParticularCall(s *state, meta *Syscall) (calls []*Call) { 409 c := &Call{ 410 Meta: meta, 411 Ret: MakeReturnArg(meta.Ret), 412 } 413 c.Args, calls = r.generateArgs(s, meta.Args) 414 r.target.assignSizesCall(c) 415 calls = append(calls, c) 416 for _, c1 := range calls { 417 r.target.SanitizeCall(c1) 418 } 419 return calls 420} 421 422// GenerateAllSyzProg generates a program that contains all pseudo syz_ calls for testing. 423func (target *Target) GenerateAllSyzProg(rs rand.Source) *Prog { 424 p := &Prog{ 425 Target: target, 426 } 427 r := newRand(target, rs) 428 s := newState(target, nil) 429 handled := make(map[string]bool) 430 for _, meta := range target.Syscalls { 431 if !strings.HasPrefix(meta.CallName, "syz_") || handled[meta.CallName] { 432 continue 433 } 434 handled[meta.CallName] = true 435 calls := r.generateParticularCall(s, meta) 436 for _, c := range calls { 437 s.analyze(c) 438 p.Calls = append(p.Calls, c) 439 } 440 } 441 if err := p.validate(); err != nil { 442 panic(err) 443 } 444 return p 445} 446 447// GenerateSimpleProg generates the simplest non-empty program for testing 448// (e.g. containing a single mmap). 449func (target *Target) GenerateSimpleProg() *Prog { 450 return &Prog{ 451 Target: target, 452 Calls: []*Call{target.MakeMmap(0, target.PageSize)}, 453 } 454} 455 456func (target *Target) GenerateUberMmapProg() *Prog { 457 return &Prog{ 458 Target: target, 459 Calls: []*Call{target.MakeMmap(0, target.NumPages*target.PageSize)}, 460 } 461} 462 463func (r *randGen) generateArgs(s *state, types []Type) ([]Arg, []*Call) { 464 var calls []*Call 465 args := make([]Arg, len(types)) 466 467 // Generate all args. Size args have the default value 0 for now. 468 for i, typ := range types { 469 arg, calls1 := r.generateArg(s, typ) 470 if arg == nil { 471 panic(fmt.Sprintf("generated arg is nil for type '%v', types: %+v", typ.Name(), types)) 472 } 473 args[i] = arg 474 calls = append(calls, calls1...) 475 } 476 477 return args, calls 478} 479 480func (r *randGen) generateArg(s *state, typ Type) (arg Arg, calls []*Call) { 481 return r.generateArgImpl(s, typ, false) 482} 483 484func (r *randGen) generateArgImpl(s *state, typ Type, ignoreSpecial bool) (arg Arg, calls []*Call) { 485 if typ.Dir() == DirOut { 486 // No need to generate something interesting for output scalar arguments. 487 // But we still need to generate the argument itself so that it can be referenced 488 // in subsequent calls. For the same reason we do generate pointer/array/struct 489 // output arguments (their elements can be referenced in subsequent calls). 490 switch typ.(type) { 491 case *IntType, *FlagsType, *ConstType, *ProcType, 492 *VmaType, *ResourceType: 493 return typ.makeDefaultArg(), nil 494 } 495 } 496 497 if typ.Optional() && r.oneOf(5) { 498 if res, ok := typ.(*ResourceType); ok { 499 v := res.Desc.Values[r.Intn(len(res.Desc.Values))] 500 return MakeResultArg(typ, nil, v), nil 501 } 502 return typ.makeDefaultArg(), nil 503 } 504 505 // Allow infinite recursion for optional pointers. 506 if pt, ok := typ.(*PtrType); ok && typ.Optional() { 507 switch pt.Type.(type) { 508 case *StructType, *ArrayType, *UnionType: 509 name := pt.Type.Name() 510 r.recDepth[name]++ 511 defer func() { 512 r.recDepth[name]-- 513 if r.recDepth[name] == 0 { 514 delete(r.recDepth, name) 515 } 516 }() 517 if r.recDepth[name] >= 3 { 518 return MakeNullPointerArg(typ), nil 519 } 520 } 521 } 522 523 if !ignoreSpecial && typ.Dir() != DirOut { 524 switch typ.(type) { 525 case *StructType, *UnionType: 526 if gen := r.target.SpecialTypes[typ.Name()]; gen != nil { 527 return gen(&Gen{r, s}, typ, nil) 528 } 529 } 530 } 531 532 return typ.generate(r, s) 533} 534 535func (a *ResourceType) generate(r *randGen, s *state) (arg Arg, calls []*Call) { 536 switch { 537 case r.nOutOf(1000, 1011): 538 // Get an existing resource. 539 var allres []*ResultArg 540 for name1, res1 := range s.resources { 541 if r.target.isCompatibleResource(a.Desc.Name, name1) || 542 r.oneOf(20) && r.target.isCompatibleResource(a.Desc.Kind[0], name1) { 543 allres = append(allres, res1...) 544 } 545 } 546 if len(allres) != 0 { 547 arg = MakeResultArg(a, allres[r.Intn(len(allres))], 0) 548 } else { 549 arg, calls = r.createResource(s, a) 550 } 551 case r.nOutOf(10, 11): 552 // Create a new resource. 553 arg, calls = r.createResource(s, a) 554 default: 555 special := a.SpecialValues() 556 arg = MakeResultArg(a, nil, special[r.Intn(len(special))]) 557 } 558 return arg, calls 559} 560 561func (a *BufferType) generate(r *randGen, s *state) (arg Arg, calls []*Call) { 562 switch a.Kind { 563 case BufferBlobRand, BufferBlobRange: 564 sz := r.randBufLen() 565 if a.Kind == BufferBlobRange { 566 sz = r.randRange(a.RangeBegin, a.RangeEnd) 567 } 568 if a.Dir() == DirOut { 569 return MakeOutDataArg(a, sz), nil 570 } 571 data := make([]byte, sz) 572 for i := range data { 573 data[i] = byte(r.Intn(256)) 574 } 575 return MakeDataArg(a, data), nil 576 case BufferString: 577 data := r.randString(s, a) 578 if a.Dir() == DirOut { 579 return MakeOutDataArg(a, uint64(len(data))), nil 580 } 581 return MakeDataArg(a, data), nil 582 case BufferFilename: 583 if a.Dir() == DirOut { 584 var sz uint64 585 switch { 586 case !a.Varlen(): 587 sz = a.Size() 588 case r.nOutOf(1, 3): 589 sz = r.rand(100) 590 case r.nOutOf(1, 2): 591 sz = 108 // UNIX_PATH_MAX 592 default: 593 sz = 4096 // PATH_MAX 594 } 595 return MakeOutDataArg(a, sz), nil 596 } 597 return MakeDataArg(a, []byte(r.filename(s, a))), nil 598 case BufferText: 599 if a.Dir() == DirOut { 600 return MakeOutDataArg(a, uint64(r.Intn(100))), nil 601 } 602 return MakeDataArg(a, r.generateText(a.Text)), nil 603 default: 604 panic("unknown buffer kind") 605 } 606} 607 608func (a *VmaType) generate(r *randGen, s *state) (arg Arg, calls []*Call) { 609 npages := r.randPageCount() 610 if a.RangeBegin != 0 || a.RangeEnd != 0 { 611 npages = a.RangeBegin + uint64(r.Intn(int(a.RangeEnd-a.RangeBegin+1))) 612 } 613 return r.allocVMA(s, a, npages), nil 614} 615 616func (a *FlagsType) generate(r *randGen, s *state) (arg Arg, calls []*Call) { 617 return MakeConstArg(a, r.flags(a.Vals)), nil 618} 619 620func (a *ConstType) generate(r *randGen, s *state) (arg Arg, calls []*Call) { 621 return MakeConstArg(a, a.Val), nil 622} 623 624func (a *IntType) generate(r *randGen, s *state) (arg Arg, calls []*Call) { 625 v := r.randInt() 626 switch a.Kind { 627 case IntFileoff: 628 switch { 629 case r.nOutOf(90, 101): 630 v = 0 631 case r.nOutOf(10, 11): 632 v = r.rand(100) 633 default: 634 v = r.randInt() 635 } 636 case IntRange: 637 v = r.randRangeInt(a.RangeBegin, a.RangeEnd) 638 } 639 return MakeConstArg(a, v), nil 640} 641 642func (a *ProcType) generate(r *randGen, s *state) (arg Arg, calls []*Call) { 643 return MakeConstArg(a, r.rand(int(a.ValuesPerProc))), nil 644} 645 646func (a *ArrayType) generate(r *randGen, s *state) (arg Arg, calls []*Call) { 647 var count uint64 648 switch a.Kind { 649 case ArrayRandLen: 650 count = r.randArrayLen() 651 case ArrayRangeLen: 652 count = r.randRange(a.RangeBegin, a.RangeEnd) 653 } 654 var inner []Arg 655 for i := uint64(0); i < count; i++ { 656 arg1, calls1 := r.generateArg(s, a.Type) 657 inner = append(inner, arg1) 658 calls = append(calls, calls1...) 659 } 660 return MakeGroupArg(a, inner), calls 661} 662 663func (a *StructType) generate(r *randGen, s *state) (arg Arg, calls []*Call) { 664 args, calls := r.generateArgs(s, a.Fields) 665 group := MakeGroupArg(a, args) 666 return group, calls 667} 668 669func (a *UnionType) generate(r *randGen, s *state) (arg Arg, calls []*Call) { 670 optType := a.Fields[r.Intn(len(a.Fields))] 671 opt, calls := r.generateArg(s, optType) 672 return MakeUnionArg(a, opt), calls 673} 674 675func (a *PtrType) generate(r *randGen, s *state) (arg Arg, calls []*Call) { 676 inner, calls := r.generateArg(s, a.Type) 677 arg = r.allocAddr(s, a, inner.Size(), inner) 678 return arg, calls 679} 680 681func (a *LenType) generate(r *randGen, s *state) (arg Arg, calls []*Call) { 682 // Updated later in assignSizesCall. 683 return MakeConstArg(a, 0), nil 684} 685 686func (a *CsumType) generate(r *randGen, s *state) (arg Arg, calls []*Call) { 687 // Filled at runtime by executor. 688 return MakeConstArg(a, 0), nil 689} 690