| // Copyright 2015 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 ( |
| "fmt" |
| "math/rand" |
| "unsafe" |
| ) |
| |
| const maxBlobLen = uint64(100 << 10) |
| |
| func (p *Prog) Mutate(rs rand.Source, ncalls int, ct *ChoiceTable, corpus []*Prog) { |
| r := newRand(p.Target, rs) |
| ctx := &mutator{ |
| p: p, |
| r: r, |
| ncalls: ncalls, |
| ct: ct, |
| corpus: corpus, |
| } |
| for stop, ok := false, false; !stop; stop = ok && r.oneOf(3) { |
| switch { |
| case r.oneOf(5): |
| // Not all calls have anything squashable, |
| // so this has lower priority in reality. |
| ok = ctx.squashAny() |
| case r.nOutOf(1, 100): |
| ok = ctx.splice() |
| case r.nOutOf(20, 31): |
| ok = ctx.insertCall() |
| case r.nOutOf(10, 11): |
| ok = ctx.mutateArg() |
| default: |
| ok = ctx.removeCall() |
| } |
| } |
| for _, c := range p.Calls { |
| p.Target.SanitizeCall(c) |
| } |
| p.debugValidate() |
| } |
| |
| type mutator struct { |
| p *Prog |
| r *randGen |
| ncalls int |
| ct *ChoiceTable |
| corpus []*Prog |
| } |
| |
| func (ctx *mutator) splice() bool { |
| p, r := ctx.p, ctx.r |
| if len(ctx.corpus) == 0 || len(p.Calls) == 0 { |
| return false |
| } |
| p0 := ctx.corpus[r.Intn(len(ctx.corpus))] |
| p0c := p0.Clone() |
| idx := r.Intn(len(p.Calls)) |
| p.Calls = append(p.Calls[:idx], append(p0c.Calls, p.Calls[idx:]...)...) |
| for i := len(p.Calls) - 1; i >= ctx.ncalls; i-- { |
| p.removeCall(i) |
| } |
| return true |
| } |
| |
| func (ctx *mutator) squashAny() bool { |
| p, r := ctx.p, ctx.r |
| complexPtrs := p.complexPtrs() |
| if len(complexPtrs) == 0 { |
| return false |
| } |
| ptr := complexPtrs[r.Intn(len(complexPtrs))] |
| if !p.Target.isAnyPtr(ptr.Type()) { |
| p.Target.squashPtr(ptr, true) |
| } |
| var blobs []*DataArg |
| var bases []*PointerArg |
| ForeachSubArg(ptr, func(arg Arg, ctx *ArgCtx) { |
| if data, ok := arg.(*DataArg); ok && arg.Type().Dir() != DirOut { |
| blobs = append(blobs, data) |
| bases = append(bases, ctx.Base) |
| } |
| }) |
| if len(blobs) == 0 { |
| return false |
| } |
| // TODO(dvyukov): we probably want special mutation for ANY. |
| // E.g. merging adjacent ANYBLOBs (we don't create them, |
| // but they can appear in future); or replacing ANYRES |
| // with a blob (and merging it with adjacent blobs). |
| idx := r.Intn(len(blobs)) |
| arg := blobs[idx] |
| base := bases[idx] |
| baseSize := base.Res.Size() |
| arg.data = mutateData(r, arg.Data(), 0, maxBlobLen) |
| // Update base pointer if size has increased. |
| if baseSize < base.Res.Size() { |
| s := analyze(ctx.ct, p, p.Calls[0]) |
| newArg := r.allocAddr(s, base.Type(), base.Res.Size(), base.Res) |
| *base = *newArg |
| } |
| return true |
| } |
| |
| func (ctx *mutator) insertCall() bool { |
| p, r := ctx.p, ctx.r |
| if len(p.Calls) >= ctx.ncalls { |
| return false |
| } |
| idx := r.biasedRand(len(p.Calls)+1, 5) |
| var c *Call |
| if idx < len(p.Calls) { |
| c = p.Calls[idx] |
| } |
| s := analyze(ctx.ct, p, c) |
| calls := r.generateCall(s, p) |
| p.insertBefore(c, calls) |
| return true |
| } |
| |
| func (ctx *mutator) removeCall() bool { |
| p, r := ctx.p, ctx.r |
| if len(p.Calls) == 0 { |
| return false |
| } |
| idx := r.Intn(len(p.Calls)) |
| p.removeCall(idx) |
| return true |
| } |
| |
| func (ctx *mutator) mutateArg() bool { |
| p, r := ctx.p, ctx.r |
| if len(p.Calls) == 0 { |
| return false |
| } |
| c := p.Calls[r.Intn(len(p.Calls))] |
| if len(c.Args) == 0 { |
| return false |
| } |
| s := analyze(ctx.ct, p, c) |
| updateSizes := true |
| for stop, ok := false, false; !stop; stop = ok && r.oneOf(3) { |
| ok = true |
| ma := &mutationArgs{target: p.Target} |
| ForeachArg(c, ma.collectArg) |
| if len(ma.args) == 0 { |
| return false |
| } |
| idx := r.Intn(len(ma.args)) |
| arg, ctx := ma.args[idx], ma.ctxes[idx] |
| calls, ok1 := p.Target.mutateArg(r, s, arg, ctx, &updateSizes) |
| if !ok1 { |
| ok = false |
| continue |
| } |
| p.insertBefore(c, calls) |
| if updateSizes { |
| p.Target.assignSizesCall(c) |
| } |
| p.Target.SanitizeCall(c) |
| } |
| return true |
| } |
| |
| func (target *Target) mutateArg(r *randGen, s *state, arg Arg, ctx ArgCtx, updateSizes *bool) ([]*Call, bool) { |
| var baseSize uint64 |
| if ctx.Base != nil { |
| baseSize = ctx.Base.Res.Size() |
| } |
| calls, retry, preserve := arg.Type().mutate(r, s, arg, ctx) |
| if retry { |
| return nil, false |
| } |
| if preserve { |
| *updateSizes = false |
| } |
| // Update base pointer if size has increased. |
| if base := ctx.Base; base != nil && baseSize < base.Res.Size() { |
| newArg := r.allocAddr(s, base.Type(), base.Res.Size(), base.Res) |
| replaceArg(base, newArg) |
| } |
| for _, c := range calls { |
| target.SanitizeCall(c) |
| } |
| return calls, true |
| } |
| |
| func regenerate(r *randGen, s *state, arg Arg) (calls []*Call, retry, preserve bool) { |
| var newArg Arg |
| newArg, calls = r.generateArg(s, arg.Type()) |
| replaceArg(arg, newArg) |
| return |
| } |
| |
| func mutateInt(r *randGen, s *state, arg Arg) (calls []*Call, retry, preserve bool) { |
| if r.bin() { |
| return regenerate(r, s, arg) |
| } |
| a := arg.(*ConstArg) |
| switch { |
| case r.nOutOf(1, 3): |
| a.Val += uint64(r.Intn(4)) + 1 |
| case r.nOutOf(1, 2): |
| a.Val -= uint64(r.Intn(4)) + 1 |
| default: |
| a.Val ^= 1 << uint64(r.Intn(64)) |
| } |
| return |
| } |
| |
| func (t *IntType) mutate(r *randGen, s *state, arg Arg, ctx ArgCtx) (calls []*Call, retry, preserve bool) { |
| return mutateInt(r, s, arg) |
| } |
| |
| func (t *FlagsType) mutate(r *randGen, s *state, arg Arg, ctx ArgCtx) (calls []*Call, retry, preserve bool) { |
| return mutateInt(r, s, arg) |
| } |
| |
| func (t *LenType) mutate(r *randGen, s *state, arg Arg, ctx ArgCtx) (calls []*Call, retry, preserve bool) { |
| if !r.mutateSize(arg.(*ConstArg), *ctx.Parent) { |
| retry = true |
| return |
| } |
| preserve = true |
| return |
| } |
| |
| func (t *ResourceType) mutate(r *randGen, s *state, arg Arg, ctx ArgCtx) (calls []*Call, retry, preserve bool) { |
| return regenerate(r, s, arg) |
| } |
| |
| func (t *VmaType) mutate(r *randGen, s *state, arg Arg, ctx ArgCtx) (calls []*Call, retry, preserve bool) { |
| return regenerate(r, s, arg) |
| } |
| |
| func (t *ProcType) mutate(r *randGen, s *state, arg Arg, ctx ArgCtx) (calls []*Call, retry, preserve bool) { |
| return regenerate(r, s, arg) |
| } |
| |
| func (t *BufferType) mutate(r *randGen, s *state, arg Arg, ctx ArgCtx) (calls []*Call, retry, preserve bool) { |
| a := arg.(*DataArg) |
| switch t.Kind { |
| case BufferBlobRand, BufferBlobRange: |
| data := append([]byte{}, a.Data()...) |
| minLen, maxLen := uint64(0), maxBlobLen |
| if t.Kind == BufferBlobRange { |
| minLen, maxLen = t.RangeBegin, t.RangeEnd |
| } |
| a.data = mutateData(r, data, minLen, maxLen) |
| case BufferString: |
| data := append([]byte{}, a.Data()...) |
| if r.bin() { |
| minLen, maxLen := uint64(0), maxBlobLen |
| if t.TypeSize != 0 { |
| minLen, maxLen = t.TypeSize, t.TypeSize |
| } |
| a.data = mutateData(r, data, minLen, maxLen) |
| } else { |
| a.data = r.randString(s, t) |
| } |
| case BufferFilename: |
| a.data = []byte(r.filename(s, t)) |
| case BufferText: |
| data := append([]byte{}, a.Data()...) |
| a.data = r.mutateText(t.Text, data) |
| default: |
| panic("unknown buffer kind") |
| } |
| return |
| } |
| |
| func (t *ArrayType) mutate(r *randGen, s *state, arg Arg, ctx ArgCtx) (calls []*Call, retry, preserve bool) { |
| // TODO: swap elements of the array |
| a := arg.(*GroupArg) |
| count := uint64(0) |
| switch t.Kind { |
| case ArrayRandLen: |
| for count == uint64(len(a.Inner)) { |
| count = r.randArrayLen() |
| } |
| case ArrayRangeLen: |
| if t.RangeBegin == t.RangeEnd { |
| panic("trying to mutate fixed length array") |
| } |
| for count == uint64(len(a.Inner)) { |
| count = r.randRange(t.RangeBegin, t.RangeEnd) |
| } |
| } |
| if count > uint64(len(a.Inner)) { |
| for count > uint64(len(a.Inner)) { |
| newArg, newCalls := r.generateArg(s, t.Type) |
| a.Inner = append(a.Inner, newArg) |
| calls = append(calls, newCalls...) |
| for _, c := range newCalls { |
| s.analyze(c) |
| } |
| } |
| } else if count < uint64(len(a.Inner)) { |
| for _, arg := range a.Inner[count:] { |
| removeArg(arg) |
| } |
| a.Inner = a.Inner[:count] |
| } |
| return |
| } |
| |
| func (t *PtrType) mutate(r *randGen, s *state, arg Arg, ctx ArgCtx) (calls []*Call, retry, preserve bool) { |
| a := arg.(*PointerArg) |
| newArg := r.allocAddr(s, t, a.Res.Size(), a.Res) |
| replaceArg(arg, newArg) |
| return |
| } |
| |
| func (t *StructType) mutate(r *randGen, s *state, arg Arg, ctx ArgCtx) (calls []*Call, retry, preserve bool) { |
| gen := r.target.SpecialTypes[t.Name()] |
| if gen == nil { |
| panic("bad arg returned by mutationArgs: StructType") |
| } |
| var newArg Arg |
| newArg, calls = gen(&Gen{r, s}, t, arg) |
| a := arg.(*GroupArg) |
| for i, f := range newArg.(*GroupArg).Inner { |
| replaceArg(a.Inner[i], f) |
| } |
| return |
| } |
| |
| func (t *UnionType) mutate(r *randGen, s *state, arg Arg, ctx ArgCtx) (calls []*Call, retry, preserve bool) { |
| if gen := r.target.SpecialTypes[t.Name()]; gen != nil { |
| var newArg Arg |
| newArg, calls = gen(&Gen{r, s}, t, arg) |
| replaceArg(arg, newArg) |
| } else { |
| a := arg.(*UnionArg) |
| current := -1 |
| for i, option := range t.Fields { |
| if a.Option.Type().FieldName() == option.FieldName() { |
| current = i |
| break |
| } |
| } |
| if current == -1 { |
| panic("can't find current option in union") |
| } |
| newIdx := r.Intn(len(t.Fields) - 1) |
| if newIdx >= current { |
| newIdx++ |
| } |
| optType := t.Fields[newIdx] |
| removeArg(a.Option) |
| var newOpt Arg |
| newOpt, calls = r.generateArg(s, optType) |
| replaceArg(arg, MakeUnionArg(t, newOpt)) |
| } |
| return |
| } |
| |
| func (t *CsumType) mutate(r *randGen, s *state, arg Arg, ctx ArgCtx) (calls []*Call, retry, preserve bool) { |
| panic("CsumType can't be mutated") |
| } |
| |
| func (t *ConstType) mutate(r *randGen, s *state, arg Arg, ctx ArgCtx) (calls []*Call, retry, preserve bool) { |
| panic("ConstType can't be mutated") |
| } |
| |
| type mutationArgs struct { |
| target *Target |
| args []Arg |
| ctxes []ArgCtx |
| ignoreSpecial bool |
| } |
| |
| func (ma *mutationArgs) collectArg(arg Arg, ctx *ArgCtx) { |
| ignoreSpecial := ma.ignoreSpecial |
| ma.ignoreSpecial = false |
| switch typ := arg.Type().(type) { |
| case *StructType: |
| if ma.target.SpecialTypes[typ.Name()] == nil || ignoreSpecial { |
| return // For structs only individual fields are updated. |
| } |
| // These special structs are mutated as a whole. |
| ctx.Stop = true |
| case *UnionType: |
| if ma.target.SpecialTypes[typ.Name()] == nil && len(typ.Fields) == 1 || ignoreSpecial { |
| return |
| } |
| ctx.Stop = true |
| case *ArrayType: |
| // Don't mutate fixed-size arrays. |
| if typ.Kind == ArrayRangeLen && typ.RangeBegin == typ.RangeEnd { |
| return |
| } |
| case *CsumType: |
| return // Checksum is updated when the checksummed data changes. |
| case *ConstType: |
| return // Well, this is const. |
| case *BufferType: |
| if typ.Kind == BufferString && len(typ.Values) == 1 { |
| return // string const |
| } |
| case *PtrType: |
| if arg.(*PointerArg).IsNull() { |
| // TODO: we ought to mutate this, but we don't have code for this yet. |
| return |
| } |
| } |
| typ := arg.Type() |
| if typ == nil || typ.Dir() == DirOut || !typ.Varlen() && typ.Size() == 0 { |
| return |
| } |
| ma.args = append(ma.args, arg) |
| ma.ctxes = append(ma.ctxes, *ctx) |
| } |
| |
| func mutateData(r *randGen, data []byte, minLen, maxLen uint64) []byte { |
| for stop := false; !stop; stop = stop && r.oneOf(3) { |
| f := mutateDataFuncs[r.Intn(len(mutateDataFuncs))] |
| data, stop = f(r, data, minLen, maxLen) |
| } |
| return data |
| } |
| |
| const maxInc = 35 |
| |
| var mutateDataFuncs = [...]func(r *randGen, data []byte, minLen, maxLen uint64) ([]byte, bool){ |
| // TODO(dvyukov): duplicate part of data. |
| // Flip bit in byte. |
| func(r *randGen, data []byte, minLen, maxLen uint64) ([]byte, bool) { |
| if len(data) == 0 { |
| return data, false |
| } |
| byt := r.Intn(len(data)) |
| bit := r.Intn(8) |
| data[byt] ^= 1 << uint(bit) |
| return data, true |
| }, |
| // Insert random bytes. |
| func(r *randGen, data []byte, minLen, maxLen uint64) ([]byte, bool) { |
| if len(data) == 0 { |
| return data, false |
| } |
| n := r.Intn(16) + 1 |
| if r := int(maxLen) - len(data); n > r { |
| n = r |
| } |
| pos := r.Intn(len(data)) |
| for i := 0; i < n; i++ { |
| data = append(data, 0) |
| } |
| copy(data[pos+n:], data[pos:]) |
| for i := 0; i < n; i++ { |
| data[pos+i] = byte(r.Int31()) |
| } |
| if uint64(len(data)) > maxLen || r.bin() { |
| data = data[:len(data)-n] // preserve original length |
| } |
| return data, true |
| }, |
| // Remove bytes. |
| func(r *randGen, data []byte, minLen, maxLen uint64) ([]byte, bool) { |
| if len(data) == 0 { |
| return data, false |
| } |
| n := r.Intn(16) + 1 |
| if n > len(data) { |
| n = len(data) |
| } |
| pos := 0 |
| if n < len(data) { |
| pos = r.Intn(len(data) - n) |
| } |
| copy(data[pos:], data[pos+n:]) |
| data = data[:len(data)-n] |
| if uint64(len(data)) < minLen || r.bin() { |
| for i := 0; i < n; i++ { |
| data = append(data, 0) // preserve original length |
| } |
| } |
| return data, true |
| }, |
| // Append a bunch of bytes. |
| func(r *randGen, data []byte, minLen, maxLen uint64) ([]byte, bool) { |
| if uint64(len(data)) >= maxLen { |
| return data, false |
| } |
| const max = 256 |
| n := max - r.biasedRand(max, 10) |
| if r := int(maxLen) - len(data); n > r { |
| n = r |
| } |
| for i := 0; i < n; i++ { |
| data = append(data, byte(r.rand(256))) |
| } |
| return data, true |
| }, |
| // Replace int8/int16/int32/int64 with a random value. |
| func(r *randGen, data []byte, minLen, maxLen uint64) ([]byte, bool) { |
| width := 1 << uint(r.Intn(4)) |
| if len(data) < width { |
| return data, false |
| } |
| i := r.Intn(len(data) - width + 1) |
| storeInt(data[i:], r.Uint64(), width) |
| return data, true |
| }, |
| // Add/subtract from an int8/int16/int32/int64. |
| func(r *randGen, data []byte, minLen, maxLen uint64) ([]byte, bool) { |
| width := 1 << uint(r.Intn(4)) |
| if len(data) < width { |
| return data, false |
| } |
| i := r.Intn(len(data) - width + 1) |
| v := loadInt(data[i:], width) |
| delta := r.rand(2*maxInc+1) - maxInc |
| if delta == 0 { |
| delta = 1 |
| } |
| if r.oneOf(10) { |
| v = swapInt(v, width) |
| v += delta |
| v = swapInt(v, width) |
| } else { |
| v += delta |
| } |
| storeInt(data[i:], v, width) |
| return data, true |
| }, |
| // Set int8/int16/int32/int64 to an interesting value. |
| func(r *randGen, data []byte, minLen, maxLen uint64) ([]byte, bool) { |
| width := 1 << uint(r.Intn(4)) |
| if len(data) < width { |
| return data, false |
| } |
| i := r.Intn(len(data) - width + 1) |
| value := r.randInt() |
| if r.oneOf(10) { |
| value = swap64(value) |
| } |
| storeInt(data[i:], value, width) |
| return data, true |
| }, |
| } |
| |
| func swap16(v uint16) uint16 { |
| v0 := byte(v >> 0) |
| v1 := byte(v >> 8) |
| v = 0 |
| v |= uint16(v1) << 0 |
| v |= uint16(v0) << 8 |
| return v |
| } |
| |
| func swap32(v uint32) uint32 { |
| v0 := byte(v >> 0) |
| v1 := byte(v >> 8) |
| v2 := byte(v >> 16) |
| v3 := byte(v >> 24) |
| v = 0 |
| v |= uint32(v3) << 0 |
| v |= uint32(v2) << 8 |
| v |= uint32(v1) << 16 |
| v |= uint32(v0) << 24 |
| return v |
| } |
| |
| func swap64(v uint64) uint64 { |
| v0 := byte(v >> 0) |
| v1 := byte(v >> 8) |
| v2 := byte(v >> 16) |
| v3 := byte(v >> 24) |
| v4 := byte(v >> 32) |
| v5 := byte(v >> 40) |
| v6 := byte(v >> 48) |
| v7 := byte(v >> 56) |
| v = 0 |
| v |= uint64(v7) << 0 |
| v |= uint64(v6) << 8 |
| v |= uint64(v5) << 16 |
| v |= uint64(v4) << 24 |
| v |= uint64(v3) << 32 |
| v |= uint64(v2) << 40 |
| v |= uint64(v1) << 48 |
| v |= uint64(v0) << 56 |
| return v |
| } |
| |
| func swapInt(v uint64, size int) uint64 { |
| switch size { |
| case 1: |
| return v |
| case 2: |
| return uint64(swap16(uint16(v))) |
| case 4: |
| return uint64(swap32(uint32(v))) |
| case 8: |
| return swap64(v) |
| default: |
| panic(fmt.Sprintf("swapInt: bad size %v", size)) |
| } |
| } |
| |
| func loadInt(data []byte, size int) uint64 { |
| p := unsafe.Pointer(&data[0]) |
| switch size { |
| case 1: |
| return uint64(*(*uint8)(p)) |
| case 2: |
| return uint64(*(*uint16)(p)) |
| case 4: |
| return uint64(*(*uint32)(p)) |
| case 8: |
| return *(*uint64)(p) |
| default: |
| panic(fmt.Sprintf("loadInt: bad size %v", size)) |
| } |
| } |
| |
| func storeInt(data []byte, v uint64, size int) { |
| p := unsafe.Pointer(&data[0]) |
| switch size { |
| case 1: |
| *(*uint8)(p) = uint8(v) |
| case 2: |
| *(*uint16)(p) = uint16(v) |
| case 4: |
| *(*uint32)(p) = uint32(v) |
| case 8: |
| *(*uint64)(p) = v |
| default: |
| panic(fmt.Sprintf("storeInt: bad size %v", size)) |
| } |
| } |
