prog: fix a bunch of bugs in parsing

Add fuzzer for Deserialize and fix 5 or so bugs it found.

Fixes #1086

7 files changed, 159 insertions, 19 deletions

diff --git a/fuzz.yaml b/fuzz.yaml
index 16d02b2c3..de65bbae8 100644
--- a/fuzz.yaml
+++ b/fuzz.yaml
@@ -18,3 +18,13 @@ targets:
       function: Fuzz
       package: github.com/google/syzkaller/tools/syz-trace2syz/proggen
       build_tags: syz_target syz_os_linux syz_arch_amd64
+  - name: prog.Deserialize
+    harness:
+      function: Deserialize
+      package: github.com/google/syzkaller/prog/fuzz
+      build_tags: syz_target,syz_os_test,syz_arch_64
+  - name: prog.ParseLog
+    harness:
+      function: ParseLog
+      package: github.com/google/syzkaller/prog/fuzz
+      build_tags: syz_target,syz_os_test,syz_arch_64
diff --git a/prog/alloc.go b/prog/alloc.go
index c47fc703d..344ec7a0e 100644
--- a/prog/alloc.go
+++ b/prog/alloc.go
@@ -57,7 +57,7 @@ func (ma *memAlloc) alloc(r *randGen, size0 uint64) uint64 {
 	}
 	size := (size0 + memAllocGranule - 1) / memAllocGranule
 	end := ma.size - size
-	for start := uint64(0); start < end; start++ {
+	for start := uint64(0); start <= end; start++ {
 		empty := true
 		for i := uint64(0); i < size; i++ {
 			if ma.get(start + i) {
diff --git a/prog/analysis.go b/prog/analysis.go
index f03f828b9..383ba15d1 100644
--- a/prog/analysis.go
+++ b/prog/analysis.go
@@ -60,7 +60,7 @@ func (s *state) analyzeImpl(c *Call, resources bool) {
 			case a.IsSpecial():
 			case a.VmaSize != 0:
 				s.va.noteAlloc(a.Address/s.target.PageSize, a.VmaSize/s.target.PageSize)
-			default:
+			case a.Res != nil:
 				s.ma.noteAlloc(a.Address, a.Res.Size())
 			}
 		}
diff --git a/prog/encoding.go b/prog/encoding.go
index 81c06313c..fce608908 100644
--- a/prog/encoding.go
+++ b/prog/encoding.go
@@ -108,14 +108,20 @@ func (a *DataArg) serialize(ctx *serializer) {
 		return
 	}
 	data := a.Data()
-	if !typ.Varlen() {
-		// Statically typed data will be padded with 0s during
-		// deserialization, so we can strip them here for readability.
-		for len(data) >= 2 && data[len(data)-1] == 0 && data[len(data)-2] == 0 {
-			data = data[:len(data)-1]
-		}
+	// Statically typed data will be padded with 0s during deserialization,
+	// so we can strip them here for readability always. For variable-size
+	// data we strip trailing 0s only if we strip enough of them.
+	sz := len(data)
+	for len(data) >= 2 && data[len(data)-1] == 0 && data[len(data)-2] == 0 {
+		data = data[:len(data)-1]
+	}
+	if typ.Varlen() && len(data)+8 >= sz {
+		data = data[:sz]
 	}
 	serializeData(ctx.buf, data, isReadableDataType(typ))
+	if typ.Varlen() && sz != len(data) {
+		ctx.printf("/%v", sz)
+	}
 }
 
 func (a *GroupArg) serialize(ctx *serializer) {
@@ -324,6 +330,9 @@ func (p *parser) parseArg(typ Type) (Arg, error) {
 }
 
 func (p *parser) parseArgImpl(typ Type) (Arg, error) {
+	if typ == nil && p.Char() != 'n' {
+		return nil, fmt.Errorf("non-nil argument for nil type")
+	}
 	switch p.Char() {
 	case '0':
 		return p.parseArgInt(typ)
@@ -464,6 +473,10 @@ func (p *parser) parseArgAddr(typ Type) (Arg, error) {
 		}
 	}
 	if typ1 == nil {
+		if addr%p.target.PageSize != 0 {
+			p.strictFailf("unaligned vma address 0x%x", addr)
+			addr &= ^(p.target.PageSize - 1)
+		}
 		return MakeVmaPointerArg(typ, addr, vmaSize), nil
 	}
 	if inner == nil {
@@ -493,6 +506,11 @@ func (p *parser) parseArgString(typ Type) (Arg, error) {
 		if err != nil {
 			return nil, fmt.Errorf("failed to parse buffer size: %q", sizeStr)
 		}
+		maxMem := p.target.NumPages * p.target.PageSize
+		if size > maxMem {
+			p.strictFailf("too large string argument %v", size)
+			size = maxMem
+		}
 	}
 	if !typ.Varlen() {
 		size = typ.Size()
@@ -613,9 +631,7 @@ func (p *parser) parseArgUnion(typ Type) (Arg, error) {
 
 // Eats excessive call arguments and struct fields to recover after description changes.
 func (p *parser) eatExcessive(stopAtComma bool, what string, args ...interface{}) {
-	if p.strict {
-		p.failf(what, args...)
-	}
+	p.strictFailf(what, args...)
 	paren, brack, brace := 0, 0, 0
 	for !p.EOF() && p.e == nil {
 		ch := p.Char()
@@ -843,7 +859,11 @@ func (p *parser) deserializeData() ([]byte, error) {
 			case 'x':
 				hi := p.consume()
 				lo := p.consume()
-				data = append(data, hexToByte(lo, hi))
+				v, ok := hexToByte(lo, hi)
+				if !ok {
+					return nil, fmt.Errorf("invalid hex \\x%v%v in data arg", hi, lo)
+				}
+				data = append(data, v)
 			case 'a':
 				data = append(data, '\a')
 			case 'b':
@@ -881,8 +901,10 @@ func byteToHex(v byte) (lo, hi byte) {
 	return toHexChar(v & 0xf), toHexChar(v >> 4)
 }
 
-func hexToByte(lo, hi byte) byte {
-	return fromHexChar(hi)<<4 + fromHexChar(lo)
+func hexToByte(lo, hi byte) (byte, bool) {
+	h, ok1 := fromHexChar(hi)
+	l, ok2 := fromHexChar(lo)
+	return h<<4 + l, ok1 && ok2
 }
 
 func toHexChar(v byte) byte {
@@ -895,14 +917,14 @@ func toHexChar(v byte) byte {
 	return 'a' + v - 10
 }
 
-func fromHexChar(v byte) byte {
+func fromHexChar(v byte) (byte, bool) {
 	if v >= '0' && v <= '9' {
-		return v - '0'
+		return v - '0', true
 	}
 	if v >= 'a' && v <= 'f' {
-		return v - 'a' + 10
+		return v - 'a' + 10, true
 	}
-	panic("bad hex char")
+	return 0, false
 }
 
 type parser struct {
diff --git a/prog/fuzz/fuzz.go b/prog/fuzz/fuzz.go
new file mode 100644
index 000000000..3a9c23359
--- /dev/null
+++ b/prog/fuzz/fuzz.go
@@ -0,0 +1,74 @@
+// Copyright 2019 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 fuzz
+
+import (
+	"bytes"
+	"fmt"
+	"math/rand"
+
+	"github.com/google/syzkaller/prog"
+	_ "github.com/google/syzkaller/sys/test/gen" // import the target we use for fuzzing
+)
+
+func Deserialize(data []byte) int {
+	p0, err0 := fuzzTarget.Deserialize(data, prog.NonStrict)
+	p1, err1 := fuzzTarget.Deserialize(data, prog.Strict)
+	if p0 == nil {
+		if p1 != nil {
+			panic("NonStrict is stricter than Strict")
+		}
+		if err0 == nil || err1 == nil {
+			panic("no error")
+		}
+		return 0
+	}
+	if err0 != nil {
+		panic("got program and error")
+	}
+	data0 := p0.Serialize()
+	if p1 != nil {
+		if err1 != nil {
+			panic("got program and error")
+		}
+		if !bytes.Equal(data0, p1.Serialize()) {
+			panic("got different data")
+		}
+	}
+	p2, err2 := fuzzTarget.Deserialize(data0, prog.NonStrict)
+	if err2 != nil {
+		panic(fmt.Sprintf("failed to parse serialized: %v\n%s", err2, data0))
+	}
+	if !bytes.Equal(data0, p2.Serialize()) {
+		panic("got different data")
+	}
+	p3 := p0.Clone()
+	if !bytes.Equal(data0, p3.Serialize()) {
+		panic("got different data")
+	}
+	if n, err := p0.SerializeForExec(fuzzBuffer); err == nil {
+		if _, err := fuzzTarget.DeserializeExec(fuzzBuffer[:n]); err != nil {
+			panic(err)
+		}
+	}
+	p3.Mutate(rand.NewSource(0), 3, nil, nil)
+	return 0
+}
+
+func ParseLog(data []byte) int {
+	if len(fuzzTarget.ParseLog(data)) != 0 {
+		return 1
+	}
+	return 0
+}
+
+var fuzzBuffer = make([]byte, prog.ExecBufferSize)
+var fuzzTarget = func() *prog.Target {
+	prog.Debug()
+	target, err := prog.GetTarget("test", "64")
+	if err != nil {
+		panic(err)
+	}
+	return target
+}()
diff --git a/prog/fuzz/fuzz_test.go b/prog/fuzz/fuzz_test.go
new file mode 100644
index 000000000..7b1426c7c
--- /dev/null
+++ b/prog/fuzz/fuzz_test.go
@@ -0,0 +1,30 @@
+// Copyright 2019 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 fuzz
+
+import (
+	"testing"
+)
+
+func TestFuzz(t *testing.T) {
+	for i, data := range []string{
+		`test$length10(&200000000000009`,
+		`test$str0(&(0x7f0000000000)='\xz+')`,
+		`syz_compare(&AUTO=""/81546506777")`,
+		`syz_compare(&AUTO=""/190734863281259)`,
+		`syz_compare(&AUTO=""/500000)`,
+		`test$vma0(&(0x7f0000000000)=0)`,
+		`test$vma0(&(0x7f0000000000)=')`,
+		`test$length10(&(0x7f0000009000),AUTO)`,
+		`syz_compare(&AUTO=""/2712404)
+mutate4()
+mutate7()
+mutate8()
+`,
+	} {
+		t.Logf("test #%v: %q", i, string(data))
+		Deserialize([]byte(data))
+		ParseLog([]byte(data))
+	}
+}
diff --git a/prog/validation.go b/prog/validation.go
index e7a015c64..c8c030aa7 100644
--- a/prog/validation.go
+++ b/prog/validation.go
@@ -7,7 +7,11 @@ import (
 	"fmt"
 )
 
-var debug = false // enabled in tests
+var debug = false // enabled in tests and fuzzers
+
+func Debug() {
+	debug = true
+}
 
 func (p *Prog) debugValidate() {
 	if debug {