diff options
| -rw-r--r-- | prog/mutation.go | 384 |
1 files changed, 194 insertions, 190 deletions
diff --git a/prog/mutation.go b/prog/mutation.go index 358a2b104..cbf1f53d5 100644 --- a/prog/mutation.go +++ b/prog/mutation.go @@ -15,220 +15,224 @@ import ( func (p *Prog) Mutate(rs rand.Source, ncalls int, ct *ChoiceTable, corpus []*Prog) { r := newRand(rs) - if r.oneOf(100) && corpus != nil { - // Splice with another prog from corpus. - p0 := corpus[r.Intn(len(corpus))] - p0c := p0.Clone() - idx := r.Intn(len(p.Calls)) - p.Calls = append(p.Calls[:idx], append(p0c.Calls, p.Calls[idx:]...)...) - } else { - // Mutate current prog without splicing. - retry := false - for stop := false; !stop || retry; stop = r.oneOf(3) { - retry = false - switch { - case r.nOutOf(20, 31): - // Insert a new call. - if len(p.Calls) >= ncalls { - retry = true - continue - } - idx := r.biasedRand(len(p.Calls)+1, 5) - var c *Call - if idx < len(p.Calls) { - c = p.Calls[idx] - } - s := analyze(ct, p, c) - calls := r.generateCall(s, p) - p.insertBefore(c, calls) - case r.nOutOf(10, 11): - // Change args of a call. - if len(p.Calls) == 0 { - retry = true - continue - } - c := p.Calls[r.Intn(len(p.Calls))] - if len(c.Args) == 0 { + retry := false + for stop := false; !stop || retry; stop = r.oneOf(3) { + retry = false + switch { + case r.nOutOf(1, 100): + // Splice with another prog from corpus. + if len(corpus) == 0 || len(p.Calls) == 0 { + retry = true + continue + } + p0 := corpus[r.Intn(len(corpus))] + p0c := p0.Clone() + idx := r.Intn(len(p.Calls)) + p.Calls = append(p.Calls[:idx], append(p0c.Calls, p.Calls[idx:]...)...) + if len(p.Calls) > ncalls { + p.Calls = p.Calls[:ncalls] + } + case r.nOutOf(20, 31): + // Insert a new call. + if len(p.Calls) >= ncalls { + retry = true + continue + } + idx := r.biasedRand(len(p.Calls)+1, 5) + var c *Call + if idx < len(p.Calls) { + c = p.Calls[idx] + } + s := analyze(ct, p, c) + calls := r.generateCall(s, p) + p.insertBefore(c, calls) + case r.nOutOf(10, 11): + // Change args of a call. + if len(p.Calls) == 0 { + retry = true + continue + } + c := p.Calls[r.Intn(len(p.Calls))] + if len(c.Args) == 0 { + retry = true + continue + } + s := analyze(ct, p, c) + for stop := false; !stop; stop = r.oneOf(3) { + args, bases := mutationArgs(c) + if len(args) == 0 { retry = true continue } - s := analyze(ct, p, c) - for stop := false; !stop; stop = r.oneOf(3) { - args, bases := mutationArgs(c) - if len(args) == 0 { - retry = true - continue + idx := r.Intn(len(args)) + arg, base := args[idx], bases[idx] + var baseSize uintptr + if base != nil { + if base.Kind != ArgPointer || base.Res == nil { + panic("bad base arg") } - idx := r.Intn(len(args)) - arg, base := args[idx], bases[idx] - var baseSize uintptr - if base != nil { - if base.Kind != ArgPointer || base.Res == nil { - panic("bad base arg") + baseSize = base.Res.Size() + } + switch a := arg.Type.(type) { + case *sys.IntType, *sys.FlagsType: + if r.bin() { + arg1, calls1 := r.generateArg(s, arg.Type) + p.replaceArg(c, arg, arg1, calls1) + } else { + switch { + case r.nOutOf(1, 3): + arg.Val += uintptr(r.Intn(4)) + 1 + case r.nOutOf(1, 2): + arg.Val -= uintptr(r.Intn(4)) + 1 + default: + arg.Val ^= 1 << uintptr(r.Intn(64)) } - baseSize = base.Res.Size() } - switch a := arg.Type.(type) { - case *sys.IntType, *sys.FlagsType: - if r.bin() { - arg1, calls1 := r.generateArg(s, arg.Type) - p.replaceArg(c, arg, arg1, calls1) - } else { - switch { - case r.nOutOf(1, 3): - arg.Val += uintptr(r.Intn(4)) + 1 - case r.nOutOf(1, 2): - arg.Val -= uintptr(r.Intn(4)) + 1 - default: - arg.Val ^= 1 << uintptr(r.Intn(64)) + case *sys.ResourceType, *sys.VmaType, *sys.ProcType: + arg1, calls1 := r.generateArg(s, arg.Type) + p.replaceArg(c, arg, arg1, calls1) + case *sys.BufferType: + switch a.Kind { + case sys.BufferBlobRand, sys.BufferBlobRange: + var data []byte + switch arg.Kind { + case ArgData: + data = append([]byte{}, arg.Data...) + case ArgConst: + // 0 is OK for optional args. + if arg.Val != 0 { + panic(fmt.Sprintf("BufferType has non-zero const value: %v", arg.Val)) } + default: + panic(fmt.Sprintf("bad arg kind for BufferType: %v", arg.Kind)) } - case *sys.ResourceType, *sys.VmaType, *sys.ProcType: - arg1, calls1 := r.generateArg(s, arg.Type) - p.replaceArg(c, arg, arg1, calls1) - case *sys.BufferType: - switch a.Kind { - case sys.BufferBlobRand, sys.BufferBlobRange: - var data []byte - switch arg.Kind { - case ArgData: - data = append([]byte{}, arg.Data...) - case ArgConst: - // 0 is OK for optional args. - if arg.Val != 0 { - panic(fmt.Sprintf("BufferType has non-zero const value: %v", arg.Val)) - } - default: - panic(fmt.Sprintf("bad arg kind for BufferType: %v", arg.Kind)) - } + minLen := int(0) + maxLen := math.MaxInt32 + if a.Kind == sys.BufferBlobRange { + minLen = int(a.RangeBegin) + maxLen = int(a.RangeEnd) + } + arg.Data = mutateData(r, data, minLen, maxLen) + case sys.BufferString: + if r.bin() { minLen := int(0) maxLen := math.MaxInt32 - if a.Kind == sys.BufferBlobRange { - minLen = int(a.RangeBegin) - maxLen = int(a.RangeEnd) - } - arg.Data = mutateData(r, data, minLen, maxLen) - case sys.BufferString: - if r.bin() { - minLen := int(0) - maxLen := math.MaxInt32 - if a.Length != 0 { - minLen = int(a.Length) - maxLen = int(a.Length) - } - arg.Data = mutateData(r, append([]byte{}, arg.Data...), minLen, maxLen) - } else { - arg.Data = r.randString(s, a.Values, a.Dir()) + if a.Length != 0 { + minLen = int(a.Length) + maxLen = int(a.Length) } - case sys.BufferFilename: - arg.Data = []byte(r.filename(s)) - case sys.BufferText: - arg.Data = r.mutateText(a.Text, arg.Data) - default: - panic("unknown buffer kind") + arg.Data = mutateData(r, append([]byte{}, arg.Data...), minLen, maxLen) + } else { + arg.Data = r.randString(s, a.Values, a.Dir()) } - case *sys.ArrayType: - count := uintptr(0) - switch a.Kind { - case sys.ArrayRandLen: - for count == uintptr(len(arg.Inner)) { - count = r.randArrayLen() - } - case sys.ArrayRangeLen: - if a.RangeBegin == a.RangeEnd { - panic("trying to mutate fixed length array") - } - for count == uintptr(len(arg.Inner)) { - count = r.randRange(int(a.RangeBegin), int(a.RangeEnd)) - } + case sys.BufferFilename: + arg.Data = []byte(r.filename(s)) + case sys.BufferText: + arg.Data = r.mutateText(a.Text, arg.Data) + default: + panic("unknown buffer kind") + } + case *sys.ArrayType: + count := uintptr(0) + switch a.Kind { + case sys.ArrayRandLen: + for count == uintptr(len(arg.Inner)) { + count = r.randArrayLen() } - if count > uintptr(len(arg.Inner)) { - var calls []*Call - for count > uintptr(len(arg.Inner)) { - arg1, calls1 := r.generateArg(s, a.Type) - arg.Inner = append(arg.Inner, arg1) - for _, c1 := range calls1 { - calls = append(calls, c1) - s.analyze(c1) - } - } - for _, c1 := range calls { - sanitizeCall(c1) - } - sanitizeCall(c) - p.insertBefore(c, calls) - } else if count < uintptr(len(arg.Inner)) { - for _, arg := range arg.Inner[count:] { - p.removeArg(c, arg) - } - arg.Inner = arg.Inner[:count] + case sys.ArrayRangeLen: + if a.RangeBegin == a.RangeEnd { + panic("trying to mutate fixed length array") } - // TODO: swap elements of the array - case *sys.PtrType: - // TODO: we don't know size for out args - size := uintptr(1) - if arg.Res != nil { - size = arg.Res.Size() + for count == uintptr(len(arg.Inner)) { + count = r.randRange(int(a.RangeBegin), int(a.RangeEnd)) } - arg1, calls1 := r.addr(s, a, size, arg.Res) - p.replaceArg(c, arg, arg1, calls1) - case *sys.StructType: - ctor := isSpecialStruct(a) - if ctor == nil { - panic("bad arg returned by mutationArgs: StructType") + } + if count > uintptr(len(arg.Inner)) { + var calls []*Call + for count > uintptr(len(arg.Inner)) { + arg1, calls1 := r.generateArg(s, a.Type) + arg.Inner = append(arg.Inner, arg1) + for _, c1 := range calls1 { + calls = append(calls, c1) + s.analyze(c1) + } } - arg1, calls1 := ctor(r, s) - for i, f := range arg1.Inner { - p.replaceArg(c, arg.Inner[i], f, calls1) - calls1 = nil + for _, c1 := range calls { + sanitizeCall(c1) } - case *sys.UnionType: - optType := a.Options[r.Intn(len(a.Options))] - maxIters := 1000 - for i := 0; optType.FieldName() == arg.OptionType.FieldName(); i++ { - optType = a.Options[r.Intn(len(a.Options))] - if i >= maxIters { - panic(fmt.Sprintf("couldn't generate a different union option after %v iterations, type: %+v", maxIters, a)) - } + sanitizeCall(c) + p.insertBefore(c, calls) + } else if count < uintptr(len(arg.Inner)) { + for _, arg := range arg.Inner[count:] { + p.removeArg(c, arg) } - p.removeArg(c, arg.Option) - opt, calls := r.generateArg(s, optType) - arg1 := unionArg(a, opt, optType) - p.replaceArg(c, arg, arg1, calls) - case *sys.LenType: - panic("bad arg returned by mutationArgs: LenType") - case *sys.CsumType: - panic("bad arg returned by mutationArgs: CsumType") - case *sys.ConstType: - panic("bad arg returned by mutationArgs: ConstType") - default: - panic(fmt.Sprintf("bad arg returned by mutationArgs: %#v, type=%#v", *arg, arg.Type)) + arg.Inner = arg.Inner[:count] } - - // Update base pointer if size has increased. - if base != nil && baseSize < base.Res.Size() { - arg1, calls1 := r.addr(s, base.Type, base.Res.Size(), base.Res) - for _, c1 := range calls1 { - sanitizeCall(c1) + // TODO: swap elements of the array + case *sys.PtrType: + // TODO: we don't know size for out args + size := uintptr(1) + if arg.Res != nil { + size = arg.Res.Size() + } + arg1, calls1 := r.addr(s, a, size, arg.Res) + p.replaceArg(c, arg, arg1, calls1) + case *sys.StructType: + ctor := isSpecialStruct(a) + if ctor == nil { + panic("bad arg returned by mutationArgs: StructType") + } + arg1, calls1 := ctor(r, s) + for i, f := range arg1.Inner { + p.replaceArg(c, arg.Inner[i], f, calls1) + calls1 = nil + } + case *sys.UnionType: + optType := a.Options[r.Intn(len(a.Options))] + maxIters := 1000 + for i := 0; optType.FieldName() == arg.OptionType.FieldName(); i++ { + optType = a.Options[r.Intn(len(a.Options))] + if i >= maxIters { + panic(fmt.Sprintf("couldn't generate a different union option after %v iterations, type: %+v", maxIters, a)) } - p.insertBefore(c, calls1) - arg.AddrPage = arg1.AddrPage - arg.AddrOffset = arg1.AddrOffset - arg.AddrPagesNum = arg1.AddrPagesNum } - - // Update all len fields. - assignSizesCall(c) + p.removeArg(c, arg.Option) + opt, calls := r.generateArg(s, optType) + arg1 := unionArg(a, opt, optType) + p.replaceArg(c, arg, arg1, calls) + case *sys.LenType: + panic("bad arg returned by mutationArgs: LenType") + case *sys.CsumType: + panic("bad arg returned by mutationArgs: CsumType") + case *sys.ConstType: + panic("bad arg returned by mutationArgs: ConstType") + default: + panic(fmt.Sprintf("bad arg returned by mutationArgs: %#v, type=%#v", *arg, arg.Type)) } - default: - // Remove a random call. - if len(p.Calls) == 0 { - retry = true - continue + + // Update base pointer if size has increased. + if base != nil && baseSize < base.Res.Size() { + arg1, calls1 := r.addr(s, base.Type, base.Res.Size(), base.Res) + for _, c1 := range calls1 { + sanitizeCall(c1) + } + p.insertBefore(c, calls1) + arg.AddrPage = arg1.AddrPage + arg.AddrOffset = arg1.AddrOffset + arg.AddrPagesNum = arg1.AddrPagesNum } - idx := r.Intn(len(p.Calls)) - p.removeCall(idx) + + // Update all len fields. + assignSizesCall(c) + } + default: + // Remove a random call. + if len(p.Calls) == 0 { + retry = true + continue } + idx := r.Intn(len(p.Calls)) + p.removeCall(idx) } } |