hints: add new mutations and tests

2 files changed, 423 insertions, 15 deletions

diff --git a/prog/hints.go b/prog/hints.go
index ba5681d60..6be33c0bd 100644
--- a/prog/hints.go
+++ b/prog/hints.go
@@ -18,6 +18,12 @@ package prog
 // checks if new coverage is obtained.
 // For more insights on particular mutations please see prog/hints_test.go.
 
+import (
+	"encoding/binary"
+
+	"github.com/google/syzkaller/sys"
+)
+
 type uint64Set map[uint64]bool
 
 // Example: for comparisons {(op1, op2), (op1, op3), (op1, op4), (op2, op1)}
@@ -28,6 +34,10 @@ type uint64Set map[uint64]bool
 // }.
 type CompMap map[uint64]uint64Set
 
+const (
+	maxDataLength = 100
+)
+
 var (
 	specialIntsSet uint64Set
 
@@ -40,11 +50,6 @@ var (
 )
 
 func (m CompMap) AddComp(arg1, arg2 uint64) {
-	if _, ok := specialIntsSet[arg2]; ok {
-		// We don't want to add arg2 because it's in the set of
-		// "special" values, which the fuzzer will try anyways.
-		return
-	}
 	if _, ok := m[arg1]; !ok {
 		m[arg1] = make(uint64Set)
 	}
@@ -64,34 +69,155 @@ func (p *Prog) MutateWithHints(compMaps []CompMap, exec func(newP *Prog)) {
 	}
 }
 
-func generateHints(p *Prog, compMap CompMap, c *Call, arg Arg, exec func(newP *Prog)) {
-	candidate := func(newArg Arg) {
-		newP, argMap := p.cloneImpl(true)
-		oldArg := argMap[arg]
-		newP.replaceArg(c, oldArg, newArg, nil)
+func generateHints(p *Prog, compMap CompMap, c *Call, arg Arg, exec func(p *Prog)) {
+	newP, argMap := p.cloneImpl(true)
+	var originalArg Arg
+	validateExec := func() {
 		if err := newP.validate(); err != nil {
 			panic("a program generated with hints did not pass validation: " +
 				err.Error())
 		}
 		exec(newP)
 	}
+	constArgCandidate := func(newArg Arg) {
+		oldArg := argMap[arg]
+		newP.replaceArg(c, oldArg, newArg, nil)
+		validateExec()
+		newP.replaceArg(c, oldArg, originalArg, nil)
+	}
+
+	dataArgCandidate := func(newArg Arg) {
+		// Data arg mutations are done in-place. No need to restore the original
+		// value - it gets restored in checkDataArg().
+		// dataArgCandidate is only needed for unit tests.
+		validateExec()
+	}
+
 	switch a := arg.(type) {
 	case *ConstArg:
-		checkConstArg(a, compMap, candidate)
-		// case *DataArg:
-		// 	checkDataArg(a, compMap, candidate)
+		originalArg = constArg(a.Type(), a.Val)
+		checkConstArg(a, compMap, constArgCandidate)
+	case *DataArg:
+		originalArg = dataArg(a.Type(), a.Data)
+		checkDataArg(a, compMap, dataArgCandidate)
 	}
 }
 
 func checkConstArg(arg *ConstArg, compMap CompMap, cb func(newArg Arg)) {
-	for v, _ := range compMap[arg.Val] {
-		cb(constArg(arg.typ, v))
+	for replacer := range shrinkExpand(arg.Val, compMap) {
+		cb(constArg(arg.typ, replacer))
 	}
 }
 
+func checkDataArg(arg *DataArg, compMap CompMap, cb func(newArg Arg)) {
+	if arg.Type().Dir() != sys.DirIn && arg.Type().Dir() != sys.DirInOut {
+		// We only want to scan userspace->kernel data.
+		return
+	}
+	bytes := make([]byte, 8)
+	original := make([]byte, 8)
+	for i := 0; i < min(len(arg.Data), maxDataLength); i++ {
+		copy(original, arg.Data[i:])
+		val := sliceToUint64(arg.Data[i:])
+		for replacer := range shrinkExpand(val, compMap) {
+			binary.LittleEndian.PutUint64(bytes, replacer)
+			copy(arg.Data[i:], bytes)
+			cb(arg)
+			copy(arg.Data[i:], original)
+		}
+	}
+}
+
+// Shrink and expand mutations model the cases when the syscall arguments
+// are casted to narrower (and wider) integer types.
+// ======================================================================
+// Motivation for shrink:
+// void f(u16 x) {
+//		u8 y = (u8)x;
+//		if (y == 0xab) {...}
+// }
+// If we call f(0x1234), then we'll see a comparison 0x34 vs 0xab and we'll
+// be unable to match the argument 0x1234 with any of the comparison operands.
+// Thus we shrink 0x1234 to 0x34 and try to match 0x34.
+// If there's a match for the shrank value, then we replace the corresponding
+// bytes of the input (in the given example we'll get 0x12ab).
+// Sometimes the other comparison operand will be wider than the shrank value
+// (in the example above consider comparison if (y == 0xdeadbeef) {...}).
+// In this case we ignore such comparison because we couldn't come up with
+// any valid code example that does similar things. To avoid such comparisons
+// we check the sizes with leastSize().
+// ======================================================================
+// Motivation for expand:
+// void f(i8 x) {
+//		i16 y = (i16)x;
+//		if (y == -2) {...}
+// }
+// Suppose we call f(-1), then we'll see a comparison 0xffff vs 0xfffe and be
+// unable to match input vs any operands. Thus we sign extend the input and
+// check the extension.
+// As with shrink we ignore cases when the other operand is wider.
+// Note that executor sign extends all the comparison operands to int64.
+// ======================================================================
+func shrinkExpand(v uint64, compMap CompMap) uint64Set {
+	replacers := make(uint64Set)
+	// Map: key is shrank/extended value, value is the maximal number of bits
+	// that can be replaced.
+	res := make(map[uint64]uint)
+	for _, size := range []uint{8, 16, 32} {
+		res[v&((1<<size)-1)] = size
+		if v&(1<<(size-1)) != 0 {
+			res[v|^((1<<size)-1)] = size
+		}
+	}
+	res[v] = 64
+
+	for mutant, size := range res {
+		for newV := range compMap[mutant] {
+			mask := uint64(1<<size - 1)
+			if newHi := newV & ^mask; newHi == 0 || newHi^^mask == 0 {
+				if !specialIntsSet[newV&mask] {
+					// Replace size least significant bits of v with
+					// corresponding bits of newV. Leave the rest of v as it was.
+					replacer := (v &^ mask) | (newV & mask)
+					replacers[replacer] = true
+				}
+			}
+		}
+	}
+	return replacers
+}
+
 func init() {
 	specialIntsSet = make(uint64Set)
 	for _, v := range specialInts {
 		specialIntsSet[v] = true
 	}
 }
+
+// Transforms a slice of bytes into uint64 using Little Endian.
+// Works fine if len(s) != 8.
+func sliceToUint64(s []byte) uint64 {
+	padded := pad(s, 0x0, 8)
+	return binary.LittleEndian.Uint64(padded)
+}
+
+// If len(arr) >= size returns a subslice of arr.
+// Else creates a copy of arr padded with value to size.
+func pad(arr []byte, value byte, size int) []byte {
+	if len(arr) >= size {
+		return arr[0:size]
+	}
+	block := make([]byte, size)
+	copy(block, arr)
+	for j := len(arr); j < size; j++ {
+		block[j] = value
+	}
+	return block
+}
+
+func min(a, b int) int {
+	if a <= b {
+		return a
+	}
+	return b
+}
diff --git a/prog/hints_test.go b/prog/hints_test.go
new file mode 100644
index 000000000..1805c34a7
--- /dev/null
+++ b/prog/hints_test.go
@@ -0,0 +1,282 @@
+// Copyright 2017 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"
+	"reflect"
+	"testing"
+
+	"github.com/google/syzkaller/sys"
+)
+
+type ConstArgTest struct {
+	name  string
+	in    uint64
+	comps CompMap
+	res   uint64Set
+}
+
+type DataArgTest struct {
+	name  string
+	in    string
+	comps CompMap
+	res   map[string]bool
+}
+
+// Tests checkConstArg(). Is not intended to check correctness of any mutations.
+func TestHintsCheckConstArg(t *testing.T) {
+	var tests = []ConstArgTest{
+		{
+			"One replacer test",
+			0xdeadbeef,
+			CompMap{0xdeadbeef: uint64Set{0xcafebabe: true}},
+			uint64Set{0xcafebabe: true},
+		},
+		// Test for cases when there's multiple comparisons (op1, op2), (op1, op3), ...
+		// Checks that for every such operand a program is generated.
+		{
+			"Multiple replacers test",
+			0xabcd,
+			CompMap{0xabcd: uint64Set{0x2: true, 0x3: true}},
+			uint64Set{0x2: true, 0x3: true},
+		},
+		// Checks that special ints are not used.
+		{
+			"Special ints test",
+			0xabcd,
+			CompMap{0xabcd: uint64Set{0x1: true, 0x2: true}},
+			uint64Set{0x2: true},
+		},
+	}
+	for _, test := range tests {
+		t.Run(fmt.Sprintf("%v", test.name), func(t *testing.T) {
+			res := uint64Set{}
+			constArg := &ConstArg{ArgCommon{nil}, test.in}
+			checkConstArg(constArg, test.comps, func(arg Arg) {
+				res[arg.(*ConstArg).Val] = true
+			})
+			if !reflect.DeepEqual(res, test.res) {
+				t.Fatalf("\ngot : %v\nwant: %v", res, test.res)
+			}
+		})
+	}
+}
+
+// Tests checkDataArg(). Is not intended to check correctness of any mutations.
+func TestHintsCheckDataArg(t *testing.T) {
+	// All inputs are in Little-Endian.
+	var tests = []DataArgTest{
+		{
+			"One replacer test",
+			"\xef\xbe\xad\xde",
+			CompMap{0xdeadbeef: uint64Set{0xcafebabe: true}},
+			map[string]bool{
+				"\xbe\xba\xfe\xca": true,
+			},
+		},
+		// Test for cases when there's multiple comparisons (op1, op2), (op1, op3), ...
+		// Checks that for every such operand a program is generated.
+		{
+			"Multiple replacers test",
+			"\xcd\xab",
+			CompMap{0xabcd: uint64Set{0x2: true, 0x3: true}},
+			map[string]bool{
+				"\x02\x00": true, "\x03\x00": true,
+			},
+		},
+		// Checks that special ints are not used.
+		{
+			"Special ints test",
+			"\xcd\xab",
+			CompMap{0xabcd: uint64Set{0x1: true, 0x2: true}},
+			map[string]bool{
+				"\x02\x00": true,
+			},
+		},
+	}
+	for _, test := range tests {
+		t.Run(fmt.Sprintf("%v", test.name), func(t *testing.T) {
+			res := make(map[string]bool)
+			// Whatever type here. It's just needed to pass the
+			// dataArg.Type().Dir() == sys.DirIn check.
+			typ := sys.ArrayType{sys.TypeCommon{"", "", sys.DirIn, false}, nil, 0, 0, 0}
+			argCommon := ArgCommon{&typ}
+			dataArg := &DataArg{argCommon, []byte(test.in)}
+			checkDataArg(dataArg, test.comps, func(arg Arg) {
+				res[string(arg.(*DataArg).Data)] = true
+			})
+			if !reflect.DeepEqual(res, test.res) {
+				s := "\ngot: ["
+				for x := range res {
+					s += fmt.Sprintf("0x%x, ", x)
+				}
+				s += "]\nwant: ["
+				for x := range test.res {
+					s += fmt.Sprintf("0x%x, ", x)
+				}
+				s += "]\n"
+				t.Fatalf(s)
+			}
+		})
+	}
+}
+func TestHintsShrinkExpand(t *testing.T) {
+	// Naming conventions:
+	// b  - byte  variable (i8 or u8)
+	// w  - word  variable (i16 or u16)
+	// dw - dword variable (i32 or u32)
+	// qw - qword variable (i64 or u64)
+	// -----------------------------------------------------------------
+	// Shrink tests:
+	var tests = []ConstArgTest{
+		{
+			// Models the following code:
+			// void f(u16 w) {
+			//		u8 b = (u8) w;
+			//		if (b == 0xab) {...}
+			//		if (w == 0xcdcd) {...}
+			//  }; f(0x1234);
+			"Shrink 16 test",
+			0x1234,
+			CompMap{
+				0x34:   uint64Set{0xab: true},
+				0x1234: uint64Set{0xcdcd: true},
+			},
+			uint64Set{0x12ab: true, 0xcdcd: true},
+		},
+		{
+			// Models the following code:
+			// void f(u32 dw) {
+			//		u8 b = (u8) dw
+			//		i16 w = (i16) dw
+			//		if (a == 0xab) {...}
+			//		if (b == 0xcdcd) {...}
+			//		if (dw == 0xefefefef) {...}
+			//  }; f(0x12345678);
+			"Shrink 32 test",
+			0x12345678,
+			CompMap{
+				0x78:       uint64Set{0xab: true},
+				0x5678:     uint64Set{0xcdcd: true},
+				0x12345678: uint64Set{0xefefefef: true},
+			},
+			uint64Set{0x123456ab: true, 0x1234cdcd: true, 0xefefefef: true},
+		},
+		{
+			// Models the following code:
+			// void f(u64 qw) {
+			//		u8 b = (u8) qw
+			//		u16 w = (u16) qw
+			//		u32 dw = (u32) qw
+			//		if (a == 0xab) {...}
+			//		if (b == 0xcdcd) {...}
+			//		if (dw == 0xefefefef) {...}
+			//		if (qw == 0x0101010101010101) {...}
+			//  }; f(0x1234567890abcdef);
+			"Shrink 64 test",
+			0x1234567890abcdef,
+			CompMap{
+				0xef:               uint64Set{0xab: true},
+				0xcdef:             uint64Set{0xcdcd: true},
+				0x90abcdef:         uint64Set{0xefefefef: true},
+				0x1234567890abcdef: uint64Set{0x0101010101010101: true},
+			},
+			uint64Set{
+				0x1234567890abcdab: true,
+				0x1234567890abcdcd: true,
+				0x12345678efefefef: true,
+				0x0101010101010101: true,
+			},
+		},
+		{
+			// Models the following code:
+			// void f(i16 w) {
+			//		i8 b = (i8) w;
+			//		i16 other = 0xabab;
+			//		if (b == other) {...}
+			//  }; f(0x1234);
+			// In such code the comparison will never be true, so we don't
+			// generate a hint for it.
+			"Shrink with a wider replacer test1",
+			0x1234,
+			CompMap{0x34: uint64Set{0x1bab: true}},
+			uint64Set{},
+		},
+		{
+			// Models the following code:
+			// void f(i16 w) {
+			//		i8 b = (i8) w;
+			//		i16 other = 0xfffd;
+			//		if (b == other) {...}
+			//  }; f(0x1234);
+			// In such code b will be sign extended to 0xff34 and, if we replace
+			// the lower byte, then the if statement will be true.
+			// Note that executor sign extends all the comparison operands to
+			// int64, so we model this accordingly.
+			"Shrink with a wider replacer test2",
+			0x1234,
+			CompMap{0x34: uint64Set{0xfffffffffffffffd: true}},
+			uint64Set{0x12fd: true},
+		},
+		// -----------------------------------------------------------------
+		// Extend tests:
+		// Note that executor sign extends all the comparison operands to int64,
+		// so we model this accordingly.
+		{
+			// Models the following code:
+			// void f(i8 b) {
+			//		i64 qw = (i64) b;
+			//		if (qw == -2) {...};
+			// }; f(-1);
+			"Extend 8 test",
+			0xff,
+			CompMap{0xffffffffffffffff: uint64Set{0xfffffffffffffffe: true}},
+			uint64Set{0xfe: true},
+		},
+		{
+			// Models the following code:
+			// void f(i16 w) {
+			//		i64 qw = (i64) w;
+			//		if (qw == -2) {...};
+			// }; f(-1);
+			"Extend 16 test",
+			0xffff,
+			CompMap{0xffffffffffffffff: uint64Set{0xfffffffffffffffe: true}},
+			uint64Set{0xfffe: true},
+		},
+		{
+			// Models the following code:
+			// void f(i32 dw) {
+			//		i64 qw = (i32) dw;
+			//		if (qw == -2) {...};
+			// }; f(-1);
+			"Extend 32 test",
+			0xffffffff,
+			CompMap{0xffffffffffffffff: uint64Set{0xfffffffffffffffe: true}},
+			uint64Set{0xfffffffe: true},
+		},
+		{
+			// Models the following code:
+			// void f(i8 b) {
+			//		i16 w = (i16) b;
+			//		if (w == (i16) 0xfeff) {...};
+			// }; f(-1);
+			// There's no value for b that will make the comparison true,
+			// so we don't generate hints.
+			"Extend with a wider replacer test",
+			0xff,
+			CompMap{0xffffffffffffffff: uint64Set{0xfffffffffffffeff: true}},
+			uint64Set{},
+		},
+	}
+	for _, test := range tests {
+		t.Run(fmt.Sprintf("%v", test.name), func(t *testing.T) {
+			res := shrinkExpand(test.in, test.comps)
+			if !reflect.DeepEqual(res, test.res) {
+				t.Fatalf("\ngot : %v\nwant: %v", res, test.res)
+			}
+		})
+	}
+}