From fa9c44b5689f6602b37b264245641d01f37ac4de Mon Sep 17 00:00:00 2001 From: Andrey Konovalov Date: Fri, 21 Oct 2016 18:24:33 +0200 Subject: prog: minimize based on individual args --- prog/mutation.go | 123 +++++++++++++++++++++++++++++++++++++++++++++++--- prog/mutation_test.go | 37 ++++++++++----- prog/prog.go | 3 ++ prog/rand.go | 2 +- prog/validation.go | 6 +-- repro/repro.go | 2 +- syz-fuzzer/fuzzer.go | 2 +- 7 files changed, 151 insertions(+), 24 deletions(-) diff --git a/prog/mutation.go b/prog/mutation.go index 272e9c8d8..9ea13d466 100644 --- a/prog/mutation.go +++ b/prog/mutation.go @@ -220,7 +220,7 @@ func (p *Prog) Mutate(rs rand.Source, ncalls int, ct *ChoiceTable, corpus []*Pro // predicate pred. It iteratively generates simpler programs and asks pred // whether it is equal to the orginal program or not. If it is equivalent then // the simplification attempt is committed and the process continues. -func Minimize(p0 *Prog, callIndex0 int, pred func(*Prog, int) bool) (*Prog, int) { +func Minimize(p0 *Prog, callIndex0 int, pred func(*Prog, int) bool, crash bool) (*Prog, int) { name0 := "" if callIndex0 != -1 { if callIndex0 < 0 || callIndex0 >= len(p0.Calls) { @@ -280,12 +280,121 @@ func Minimize(p0 *Prog, callIndex0 int, pred func(*Prog, int) bool) (*Prog, int) p0 = p callIndex0 = callIndex } - // TODO: simplify individual arguments: - // - replace constants with 0 - // - reset bits in constants - // - remove offsets from addresses - // - replace file descriptors with -1 - // etc + + var triedPaths map[string]bool + + var rec func(p *Prog, call *Call, arg *Arg, path string) bool + rec = func(p *Prog, call *Call, arg *Arg, path string) bool { + path += fmt.Sprintf("-%v", arg.Type.Name()) + switch typ := arg.Type.(type) { + case *sys.StructType: + for _, innerArg := range arg.Inner { + if rec(p, call, innerArg, path) { + return true + } + } + case *sys.UnionType: + if rec(p, call, arg.Option, path) { + return true + } + case *sys.PtrType: + // TODO: try to remove optional ptrs + if arg.Res != nil { + return rec(p, call, arg.Res, path) + } + case *sys.ArrayType: + for i, innerArg := range arg.Inner { + innerPath := fmt.Sprintf("%v-%v", path, i) + if !triedPaths[innerPath] && !crash { + if (typ.Kind == sys.ArrayRangeLen && len(arg.Inner) > int(typ.RangeBegin)) || + (typ.Kind == sys.ArrayRandLen) { + copy(arg.Inner[i:], arg.Inner[i+1:]) + arg.Inner = arg.Inner[:len(arg.Inner)-1] + p.removeArg(call, innerArg) + assignSizesCall(call) + + if pred(p, callIndex0) { + p0 = p + } else { + triedPaths[innerPath] = true + } + + return true + } + } + if rec(p, call, innerArg, innerPath) { + return true + } + } + case *sys.IntType, *sys.FlagsType, *sys.ResourceType: + // TODO: try to reset bits in ints + // TODO: try to set separate flags + if crash { + return false + } + if triedPaths[path] { + return false + } + triedPaths[path] = true + if arg.Val == typ.Default() { + return false + } + v0 := arg.Val + arg.Val = typ.Default() + if pred(p, callIndex0) { + p0 = p + return true + } else { + arg.Val = v0 + } + case *sys.BufferType: + // TODO: try to set individual bytes to 0 + if triedPaths[path] { + return false + } + triedPaths[path] = true + if typ.Kind != sys.BufferBlobRand && typ.Kind != sys.BufferBlobRange { + return false + } + minLen := int(typ.RangeBegin) + for step := len(arg.Data) - minLen; len(arg.Data) > minLen && step > 0; { + if len(arg.Data)-step >= minLen { + arg.Data = arg.Data[:len(arg.Data)-step] + assignSizesCall(call) + if pred(p, callIndex0) { + continue + } + arg.Data = arg.Data[:len(arg.Data)+step] + assignSizesCall(call) + } + step /= 2 + if crash { + break + } + } + p0 = p + case *sys.VmaType, *sys.LenType, *sys.ConstType: + // TODO: try to remove offset from vma + return false + default: + panic(fmt.Sprintf("unknown arg type '%+v'", typ)) + } + return false + } + + // Try to minimize individual args. + for i := 0; i < len(p0.Calls); i++ { + triedPaths = make(map[string]bool) + again: + p := p0.Clone() + call := p.Calls[i] + for j, arg := range call.Args { + if rec(p, call, arg, fmt.Sprintf("%v", j)) { + goto again + } + } + } + if callIndex0 != -1 { if callIndex0 < 0 || callIndex0 >= len(p0.Calls) || name0 != p0.Calls[callIndex0].Meta.Name { panic(fmt.Sprintf("bad call index after minimizatoin: ncalls=%v index=%v call=%v/%v", diff --git a/prog/mutation_test.go b/prog/mutation_test.go index 5770d247b..098115cf3 100644 --- a/prog/mutation_test.go +++ b/prog/mutation_test.go @@ -180,14 +180,14 @@ func TestMinimize(t *testing.T) { { "mmap(&(0x7f0000000000/0x1000)=nil, (0x1000), 0x3, 0x32, 0xffffffffffffffff, 0x0)\n" + "sched_yield()\n" + - "pipe2(&(0x7f0000000000)={0x0, 0x0}, 0x0)\n", + "pipe2(&(0x7f0000000000)={0xffffffffffffffff, 0xffffffffffffffff}, 0x0)\n", 2, func(p *Prog, callIndex int) bool { // Aim at removal of sched_yield. return len(p.Calls) == 2 && p.Calls[0].Meta.Name == "mmap" && p.Calls[1].Meta.Name == "pipe2" }, - "mmap(&(0x7f0000000000/0x1000)=nil, (0x1000), 0x3, 0x32, 0xffffffffffffffff, 0x0)\n" + - "pipe2(&(0x7f0000000000)={0x0, 0x0}, 0x0)\n", + "mmap(&(0x7f0000000000/0x1000)=nil, (0x1000), 0x0, 0x0, 0xffffffffffffffff, 0x0)\n" + + "pipe2(&(0x7f0000000000)={0xffffffffffffffff, 0xffffffffffffffff}, 0x0)\n", 1, }, // Remove two dependent calls. @@ -219,8 +219,8 @@ func TestMinimize(t *testing.T) { func(p *Prog, callIndex int) bool { return p.String() == "mmap-write-sched_yield" }, - "mmap(&(0x7f0000000000/0x1000)=nil, (0x1000), 0x3, 0x32, 0xffffffffffffffff, 0x0)\n" + - "write(0xffffffffffffffff, &(0x7f0000000000)=\"1155\", 0x2)\n" + + "mmap(&(0x7f0000000000/0x1000)=nil, (0x1000), 0x0, 0x0, 0xffffffffffffffff, 0x0)\n" + + "write(0xffffffffffffffff, &(0x7f0000000000)=\"\", 0x0)\n" + "sched_yield()\n", 2, }, @@ -234,8 +234,8 @@ func TestMinimize(t *testing.T) { func(p *Prog, callIndex int) bool { return p.String() == "mmap-write-sched_yield" }, - "mmap(&(0x7f0000000000/0x1000)=nil, (0x1000), 0x3, 0x32, 0xffffffffffffffff, 0x0)\n" + - "write(0xffffffffffffffff, &(0x7f0000000000)=\"1155\", 0x2)\n" + + "mmap(&(0x7f0000000000/0x1000)=nil, (0x1000), 0x0, 0x0, 0xffffffffffffffff, 0x0)\n" + + "write(0xffffffffffffffff, &(0x7f0000000000)=\"\", 0x0)\n" + "sched_yield()\n", -1, }, @@ -250,7 +250,7 @@ func TestMinimize(t *testing.T) { func(p *Prog, callIndex int) bool { return p.String() == "mmap-sched_yield-getpid" }, - "mmap(&(0x7f0000000000/0x7000)=nil, (0x7000), 0x3, 0x32, 0xffffffffffffffff, 0x0)\n" + + "mmap(&(0x7f0000000000/0x7000)=nil, (0x7000), 0x0, 0x0, 0xffffffffffffffff, 0x0)\n" + "sched_yield()\n" + "getpid()\n", 2, @@ -261,7 +261,7 @@ func TestMinimize(t *testing.T) { if err != nil { t.Fatalf("failed to deserialize original program #%v: %v", ti, err) } - p1, ci := Minimize(p, test.callIndex, test.pred) + p1, ci := Minimize(p, test.callIndex, test.pred, false) res := p1.Serialize() if string(res) != test.result { t.Fatalf("minimization produced wrong result #%v\norig:\n%v\nexpect:\n%v\ngot:\n%v\n", @@ -283,12 +283,27 @@ func TestMinimizeRandom(t *testing.T) { t.Fatalf("invalid program: %v", err) } return false - }) + }, true) + Minimize(p, len(p.Calls)-1, func(p1 *Prog, callIndex int) bool { + if err := p1.validate(); err != nil { + t.Fatalf("invalid program: %v", err) + } + return true + }, true) + } + for i := 0; i < iters; i++ { + p := Generate(rs, 10, nil) + Minimize(p, len(p.Calls)-1, func(p1 *Prog, callIndex int) bool { + if err := p1.validate(); err != nil { + t.Fatalf("invalid program: %v", err) + } + return false + }, false) Minimize(p, len(p.Calls)-1, func(p1 *Prog, callIndex int) bool { if err := p1.validate(); err != nil { t.Fatalf("invalid program: %v", err) } return true - }) + }, false) } } diff --git a/prog/prog.go b/prog/prog.go index e3a0febd2..7e2cfca31 100644 --- a/prog/prog.go +++ b/prog/prog.go @@ -162,6 +162,9 @@ func unionArg(t sys.Type, opt *Arg, typ sys.Type) *Arg { } func returnArg(t sys.Type) *Arg { + if t != nil { + return &Arg{Type: t, Kind: ArgReturn, Val: t.Default()} + } return &Arg{Type: t, Kind: ArgReturn} } diff --git a/prog/rand.go b/prog/rand.go index eb24dcc4d..99722f8d5 100644 --- a/prog/rand.go +++ b/prog/rand.go @@ -635,7 +635,7 @@ func (r *randGen) generateArg(s *state, typ sys.Type) (arg *Arg, calls []*Call) switch typ.(type) { case *sys.IntType, *sys.FlagsType, *sys.ConstType, *sys.ResourceType, *sys.VmaType: - return constArg(typ, 0), nil + return constArg(typ, typ.Default()), nil } } diff --git a/prog/validation.go b/prog/validation.go index 4ef514490..0bc01b91d 100644 --- a/prog/validation.go +++ b/prog/validation.go @@ -55,12 +55,12 @@ func (c *Call) validate(ctx *validCtx) error { return fmt.Errorf("syscall %v: type name mismatch: %v vs %v", c.Meta.Name, arg.Type.Name(), typ.Name()) } if arg.Type.Dir() == sys.DirOut { - if arg.Val != 0 || arg.AddrPage != 0 || arg.AddrOffset != 0 { + if (arg.Val != 0 && arg.Val != arg.Type.Default()) || arg.AddrPage != 0 || arg.AddrOffset != 0 { // We generate output len arguments, which makes sense // since it can be a length of a variable-length array // which is not known otherwise. if _, ok := arg.Type.(*sys.LenType); !ok { - return fmt.Errorf("syscall %v: output arg '%v' has data", c.Meta.Name, typ.Name()) + return fmt.Errorf("syscall %v: output arg '%v' has non default value '%v'", c.Meta.Name, typ.Name(), arg.Val) } } for _, v := range arg.Data { @@ -75,7 +75,7 @@ func (c *Call) validate(ctx *validCtx) error { case ArgResult: case ArgReturn: case ArgConst: - if arg.Type.Dir() == sys.DirOut && arg.Val != 0 { + if arg.Type.Dir() == sys.DirOut && (arg.Val != 0 && arg.Val != arg.Type.Default()) { return fmt.Errorf("syscall %v: out resource arg '%v' has bad const value %v", c.Meta.Name, typ.Name(), arg.Val) } default: diff --git a/repro/repro.go b/repro/repro.go index f8ae494ed..0b797a084 100644 --- a/repro/repro.go +++ b/repro/repro.go @@ -197,7 +197,7 @@ func (ctx *context) repro(entries []*prog.LogEntry, crashStart int) (*Result, er return false } return crashed - }) + }, true) // Try to "minimize" threaded/collide/sandbox/etc to find simpler reproducer. opts = res.Opts diff --git a/syz-fuzzer/fuzzer.go b/syz-fuzzer/fuzzer.go index 068877c6a..d795a28c8 100644 --- a/syz-fuzzer/fuzzer.go +++ b/syz-fuzzer/fuzzer.go @@ -419,7 +419,7 @@ func triageInput(pid int, env *ipc.Env, inp Input) { } minCover = cover.Intersection(minCover, cov) return true - }) + }, false) inp.cover = minCover atomic.AddUint64(&statNewInput, 1) -- cgit mrf-deployment