prog: mutate compressed images with hints

Images are very large so the generic algorithm for data arguments
can produce too many mutants. For images we consider only
4/8-byte aligned ints. This is enough to handle all magic
numbers and checksums. We also ignore 0 and ^uint64(0) source bytes,
because there are too many of these in lots of images.

With this change the fuzzer was able to get past magic checks
in all of the following functions with our fake images:

 - in fs/befs/super.c befs_check_sb()
 - in fs/freevxfs/vxfs_super.c vxfs_fill_super()
 - in fs/hpfs/super.c hpfs_fill_super()
 - in fs/omfs/inode.c omfs_fill_super()
 - in fs/qnx6/inode.c qnx6_check_first_superblock()
 - in fs/ufs/super.c ufs_fill_super()

And even successfully mounted sysv filesystem and triggered
"sleeping function called from invalid context in __getblk_gfp"
when opening a file in the mounted filesystem.

2 files changed, 147 insertions, 12 deletions

diff --git a/prog/hints.go b/prog/hints.go
index ef7ee17a5..0055e9005 100644
--- a/prog/hints.go
+++ b/prog/hints.go
@@ -23,6 +23,8 @@ import (
 	"encoding/binary"
 	"fmt"
 	"sort"
+
+	"github.com/google/syzkaller/pkg/image"
 )
 
 // Example: for comparisons {(op1, op2), (op1, op3), (op1, op4), (op2, op1)}
@@ -109,11 +111,6 @@ func generateHints(compMap CompMap, arg Arg, exec func()) {
 				// (and filter out file names).
 				return
 			}
-		case BufferCompressed:
-			// We can reconsider this in the future, e.g. by decompressing, applying
-			// hints, then re-compressing. We will need to ensure this doesn't
-			// produce too many mutants given the current handling of buffers.
-			return
 		}
 	}
 
@@ -121,7 +118,11 @@ func generateHints(compMap CompMap, arg Arg, exec func()) {
 	case *ConstArg:
 		checkConstArg(a, compMap, exec)
 	case *DataArg:
-		checkDataArg(a, compMap, exec)
+		if typ.(*BufferType).Kind == BufferCompressed {
+			checkCompressedArg(a, compMap, exec)
+		} else {
+			checkDataArg(a, compMap, exec)
+		}
 	}
 }
 
@@ -129,7 +130,7 @@ func checkConstArg(arg *ConstArg, compMap CompMap, exec func()) {
 	original := arg.Val
 	// Note: because shrinkExpand returns a map, order of programs is non-deterministic.
 	// This can affect test coverage reports.
-	for _, replacer := range shrinkExpand(original, compMap, arg.Type().TypeBitSize()) {
+	for _, replacer := range shrinkExpand(original, compMap, arg.Type().TypeBitSize(), false) {
 		arg.Val = replacer
 		exec()
 	}
@@ -147,13 +148,41 @@ func checkDataArg(arg *DataArg, compMap CompMap, exec func()) {
 		original := make([]byte, 8)
 		copy(original, data[i:])
 		val := binary.LittleEndian.Uint64(original)
-		for _, replacer := range shrinkExpand(val, compMap, 64) {
+		for _, replacer := range shrinkExpand(val, compMap, 64, false) {
+			binary.LittleEndian.PutUint64(bytes, replacer)
+			copy(data[i:], bytes)
+			exec()
+		}
+		copy(data[i:], original)
+	}
+}
+
+func checkCompressedArg(arg *DataArg, compMap CompMap, exec func()) {
+	data0 := arg.Data()
+	if len(data0) == 0 {
+		return
+	}
+	data, dtor := image.MustDecompress(data0)
+	defer dtor()
+	// Images are very large so the generic algorithm for data arguments
+	// can produce too many mutants. For images we consider only
+	// 4/8-byte aligned ints. This is enough to handle all magic
+	// numbers and checksums. We also ignore 0 and ^uint64(0) source bytes,
+	// because there are too many of these in lots of images.
+	bytes := make([]byte, 8)
+	for i := 0; i < len(data); i += 4 {
+		original := make([]byte, 8)
+		copy(original, data[i:])
+		val := binary.LittleEndian.Uint64(original)
+		for _, replacer := range shrinkExpand(val, compMap, 64, true) {
 			binary.LittleEndian.PutUint64(bytes, replacer)
 			copy(data[i:], bytes)
+			arg.SetData(image.Compress(data))
 			exec()
 		}
 		copy(data[i:], original)
 	}
+	arg.SetData(data0)
 }
 
 // Shrink and expand mutations model the cases when the syscall arguments
@@ -185,7 +214,7 @@ func checkDataArg(arg *DataArg, compMap CompMap, exec func()) {
 // 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, bitsize uint64) []uint64 {
+func shrinkExpand(v uint64, compMap CompMap, bitsize uint64, image bool) []uint64 {
 	v = truncateToBitSize(v, bitsize)
 	limit := uint64(1<<bitsize - 1)
 	var replacers map[uint64]bool
@@ -207,6 +236,15 @@ func shrinkExpand(v uint64, compMap CompMap, bitsize uint64) []uint64 {
 			}
 			mutant = v | ^((1 << size) - 1)
 		}
+		if image {
+			// For images we can produce too many mutants for small integers.
+			if width < 4 {
+				continue
+			}
+			if mutant == 0 || (mutant|^((1<<size)-1)) == ^uint64(0) {
+				continue
+			}
+		}
 		// Use big-endian match/replace for both blobs and ints.
 		// Sometimes we have unmarked blobs (no little/big-endian info);
 		// for ANYBLOBs we intentionally lose all marking;
@@ -236,7 +274,11 @@ func shrinkExpand(v uint64, compMap CompMap, bitsize uint64) []uint64 {
 				if bigendian {
 					newV = swapInt(newV, width)
 				}
-				if specialIntsSet[newV] {
+				// We insert special ints (like 0) with high probability,
+				// so we don't try to replace to special ints them here.
+				// Images are large so it's hard to guess even special
+				// ints with random mutations.
+				if !image && specialIntsSet[newV] {
 					continue
 				}
 				// Replace size least significant bits of v with
@@ -245,7 +287,6 @@ func shrinkExpand(v uint64, compMap CompMap, bitsize uint64) []uint64 {
 				if replacer == v {
 					continue
 				}
-
 				replacer = truncateToBitSize(replacer, bitsize)
 				// TODO(dvyukov): should we try replacing with arg+/-1?
 				// This could trigger some off-by-ones.
diff --git a/prog/hints_test.go b/prog/hints_test.go
index 5eec2724e..b01ac0204 100644
--- a/prog/hints_test.go
+++ b/prog/hints_test.go
@@ -10,6 +10,9 @@ import (
 	"reflect"
 	"sort"
 	"testing"
+
+	"github.com/google/go-cmp/cmp"
+	"github.com/google/syzkaller/pkg/image"
 )
 
 type ConstArgTest struct {
@@ -318,6 +321,97 @@ func TestHintsCheckDataArg(t *testing.T) {
 	}
 }
 
+func TestHintsCompressedImage(t *testing.T) {
+	target := initTargetTest(t, "test", "64")
+	type Test struct {
+		input  string
+		comps  CompMap
+		output []string
+	}
+	var tests = []Test{
+		{
+			"\x00\x11\x22\x33\x44\x55\x66\x77",
+			CompMap{
+				// 1/2-bytes must not be replaced.
+				0x00:   compSet(0xaa),
+				0x11:   compSet(0xaa),
+				0x1122: compSet(0xaabb),
+				0x4455: compSet(0xaabb),
+				// Aligned 4-byte values are replaced in both little/big endian.
+				0x00112233: compSet(0xaabbccdd),
+				0x33221100: compSet(0xaabbccdd),
+				0x44556677: compSet(0xaabbccdd),
+				0x77665544: compSet(0xaabbccdd),
+				// Same for 8-byte values.
+				0x0011223344556677: compSet(0xaabbccddeeff9988),
+				0x7766554433221100: compSet(0xaabbccddeeff9988),
+				// Unaligned 4-bytes are not replaced.
+				0x11223344: compSet(0xaabbccdd),
+				0x22334455: compSet(0xaabbccdd),
+			},
+			[]string{
+				// Mutants for 4-byte values.
+				"\xaa\xbb\xcc\xdd\x44\x55\x66\x77",
+				"\xdd\xcc\xbb\xaa\x44\x55\x66\x77",
+				"\x00\x11\x22\x33\xaa\xbb\xcc\xdd",
+				"\x00\x11\x22\x33\xdd\xcc\xbb\xaa",
+				// Mutants for 8-byte values.
+				"\xaa\xbb\xcc\xdd\xee\xff\x99\x88",
+				"\x88\x99\xff\xee\xdd\xcc\xbb\xaa",
+			},
+		},
+		{
+			"\x00\x11\x22\x33\x44\x55\x66\x77",
+			CompMap{
+				// Special values are used as replacers.
+				0x00112233: compSet(0, 0xffffffff),
+			},
+			[]string{
+				// Mutants for 4-byte values.
+				"\x00\x00\x00\x00\x44\x55\x66\x77",
+				"\xff\xff\xff\xff\x44\x55\x66\x77",
+			},
+		},
+		{
+			// All 0s and 0xff must not be replaced.
+			"\x00\x00\x00\x00\x00\x00\x00\x00\xff\xff\xff\xff\xff\xff\xff\xff\x00\x00\x00\x00\x00\x00\x00\x00",
+			CompMap{
+				0:                  compSet(0xaabbccdd),
+				0xffffffffffffffff: compSet(0xaabbccddaabbccdd),
+			},
+			nil,
+		},
+	}
+	typ := target.SyscallMap["serialize3"].Args[0].Type.(*PtrType).Elem.(*BufferType)
+	if typ.Kind != BufferCompressed {
+		panic("wrong arg type")
+	}
+	for i, test := range tests {
+		t.Run(fmt.Sprintf("%v", i), func(t *testing.T) {
+			var res []string
+			arg := MakeDataArg(typ, DirIn, image.Compress([]byte(test.input)))
+			generateHints(test.comps, arg, func() {
+				res = append(res, string(arg.Data()))
+			})
+			for i, compressed := range res {
+				data, dtor := image.MustDecompress([]byte(compressed))
+				res[i] = string(data)
+				dtor()
+			}
+			sort.Strings(res)
+			sort.Strings(test.output)
+			if diff := cmp.Diff(test.output, res); diff != "" {
+				t.Fatalf("got wrong mutants: %v", diff)
+			}
+			data, dtor := image.MustDecompress(arg.Data())
+			defer dtor()
+			if diff := cmp.Diff(test.input, string(data)); diff != "" {
+				t.Fatalf("argument got changed afterwards: %v", diff)
+			}
+		})
+	}
+}
+
 func TestHintsShrinkExpand(t *testing.T) {
 	t.Parallel()
 	// Naming conventions:
@@ -470,7 +564,7 @@ func TestHintsShrinkExpand(t *testing.T) {
 	}
 	for _, test := range tests {
 		t.Run(fmt.Sprintf("%v", test.name), func(t *testing.T) {
-			res := shrinkExpand(test.in, test.comps, 64)
+			res := shrinkExpand(test.in, test.comps, 64, false)
 			if !reflect.DeepEqual(res, test.res) {
 				t.Fatalf("\ngot : %v\nwant: %v", res, test.res)
 			}