Merge pull request #91 from xairy/minimize-args

Minimize progs based on individual args

5 files changed, 149 insertions, 22 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: