pkg/compiler: verify validity of len targets

Update #217

6 files changed, 167 insertions, 65 deletions

diff --git a/pkg/compiler/check.go b/pkg/compiler/check.go
index d6db087c7..26898527e 100644
--- a/pkg/compiler/check.go
+++ b/pkg/compiler/check.go
@@ -13,14 +13,19 @@ import (
 )
 
 func (comp *compiler) check() {
-	// TODO: check len in syscall arguments referring to parent.
-	// TODO: incorrect name is referenced in len type
 	// TODO: no constructor for a resource
 
 	comp.checkNames()
 	comp.checkFields()
 	comp.checkTypes()
+	// The subsequent, more complex, checks expect basic validity of the tree,
+	// in particular corrent number of type arguments. If there were errors,
+	// don't proceed to avoid out-of-bounds references to type arguments.
+	if comp.errors != 0 {
+		return
+	}
 	comp.checkRecursion()
+	comp.checkLenTargets()
 }
 
 func (comp *compiler) checkNames() {
@@ -130,23 +135,89 @@ func (comp *compiler) checkTypes() {
 	for _, decl := range comp.desc.Nodes {
 		switch n := decl.(type) {
 		case *ast.Resource:
-			comp.checkType(n.Base, false, true)
+			comp.checkType(n.Base, false, false, true)
 		case *ast.Struct:
 			for _, f := range n.Fields {
-				comp.checkType(f.Type, false, false)
+				comp.checkType(f.Type, false, false, false)
 			}
 			comp.checkStruct(n)
 		case *ast.Call:
 			for _, a := range n.Args {
-				comp.checkType(a.Type, true, false)
+				comp.checkType(a.Type, true, false, false)
 			}
 			if n.Ret != nil {
-				comp.checkType(n.Ret, true, false)
+				comp.checkType(n.Ret, true, true, false)
 			}
 		}
 	}
 }
 
+func (comp *compiler) checkLenTargets() {
+	for _, decl := range comp.desc.Nodes {
+		switch n := decl.(type) {
+		case *ast.Call:
+			for _, arg := range n.Args {
+				comp.checkLenType(arg.Type, arg.Name.Name, n.Args, nil, make(map[string]bool), true)
+			}
+		}
+	}
+}
+
+func (comp *compiler) checkLenType(t *ast.Type, name string, fields []*ast.Field,
+	parents []*ast.Struct, checked map[string]bool, isArg bool) {
+	desc := comp.getTypeDesc(t)
+	if desc == typeStruct {
+		s := comp.structs[t.Ident]
+		// Prune recursion, can happen even on correct tree via opt pointers.
+		if checked[s.Name.Name] {
+			return
+		}
+		checked[s.Name.Name] = true
+		parents = append(parents, s)
+		for _, fld := range s.Fields {
+			comp.checkLenType(fld.Type, fld.Name.Name, s.Fields, parents, checked, false)
+		}
+		return
+	}
+	_, args, _ := comp.getArgsBase(t, "", sys.DirIn, isArg)
+	for i, arg := range args {
+		argDesc := desc.Args[i]
+		if argDesc.Type == typeArgLenTarget {
+			comp.checkLenTarget(t, name, arg.Ident, fields, parents)
+		} else if argDesc.Type == typeArgType {
+			comp.checkLenType(arg, name, fields, parents, checked, false)
+		}
+	}
+}
+
+func (comp *compiler) checkLenTarget(t *ast.Type, name, target string, fields []*ast.Field, parents []*ast.Struct) {
+	if target == name {
+		comp.error(t.Pos, "%v target %v refer to itself", t.Ident, target)
+		return
+	}
+	if target == "parent" {
+		if len(parents) == 0 {
+			comp.error(t.Pos, "%v target %v does not exist", t.Ident, target)
+		}
+		return
+	}
+	for _, fld := range fields {
+		if target != fld.Name.Name {
+			continue
+		}
+		if fld.Type == t {
+			comp.error(t.Pos, "%v target %v refer to itself", t.Ident, target)
+		}
+		return
+	}
+	for _, parent := range parents {
+		if target == parent.Name.Name {
+			return
+		}
+	}
+	comp.error(t.Pos, "%v target %v does not exist", t.Ident, target)
+}
+
 func (comp *compiler) checkRecursion() {
 	checked := make(map[string]bool)
 	for _, decl := range comp.desc.Nodes {
@@ -154,7 +225,8 @@ func (comp *compiler) checkRecursion() {
 		case *ast.Resource:
 			comp.checkResourceRecursion(n)
 		case *ast.Struct:
-			comp.checkStructRecursion(checked, n)
+			var path []pathElem
+			comp.checkStructRecursion(checked, n, path)
 		}
 	}
 }
@@ -182,12 +254,7 @@ type pathElem struct {
 	Field  string
 }
 
-func (comp *compiler) checkStructRecursion(checked map[string]bool, n *ast.Struct) {
-	var path []pathElem
-	comp.checkStructRecursion1(checked, n, path)
-}
-
-func (comp *compiler) checkStructRecursion1(checked map[string]bool, n *ast.Struct, path []pathElem) {
+func (comp *compiler) checkStructRecursion(checked map[string]bool, n *ast.Struct, path []pathElem) {
 	name := n.Name.Name
 	if checked[name] {
 		return
@@ -221,7 +288,7 @@ func (comp *compiler) checkStructRecursion1(checked map[string]bool, n *ast.Stru
 func (comp *compiler) recurseField(checked map[string]bool, t *ast.Type, path []pathElem) {
 	desc := comp.getTypeDesc(t)
 	if desc == typeStruct {
-		comp.checkStructRecursion1(checked, comp.structs[t.Ident], path)
+		comp.checkStructRecursion(checked, comp.structs[t.Ident], path)
 		return
 	}
 	_, args, base := comp.getArgsBase(t, "", sys.DirIn, false)
@@ -243,7 +310,7 @@ func (comp *compiler) checkStruct(n *ast.Struct) {
 	}
 }
 
-func (comp *compiler) checkType(t *ast.Type, isArg, isResourceBase bool) {
+func (comp *compiler) checkType(t *ast.Type, isArg, isRet, isResourceBase bool) {
 	if unexpected, _, ok := checkTypeKind(t, kindIdent); !ok {
 		comp.error(t.Pos, "unexpected %v, expect type", unexpected)
 		return
@@ -257,8 +324,12 @@ func (comp *compiler) checkType(t *ast.Type, isArg, isResourceBase bool) {
 		comp.error(t.Pos2, "unexpected ':'")
 		return
 	}
+	if isRet && (!desc.CanBeArg || desc.CantBeRet) {
+		comp.error(t.Pos, "%v can't be syscall return", t.Ident)
+		return
+	}
 	if isArg && !desc.CanBeArg {
-		comp.error(t.Pos, "%v can't be syscall argument/return", t.Ident)
+		comp.error(t.Pos, "%v can't be syscall argument", t.Ident)
 		return
 	}
 	if isResourceBase && !desc.ResourceBase {
@@ -293,7 +364,7 @@ func (comp *compiler) checkType(t *ast.Type, isArg, isResourceBase bool) {
 	err0 := comp.errors
 	for i, arg := range args {
 		if desc.Args[i].Type == typeArgType {
-			comp.checkType(arg, false, false)
+			comp.checkType(arg, false, isRet, false)
 		} else {
 			comp.checkTypeArg(t, arg, desc.Args[i])
 		}
diff --git a/pkg/compiler/compiler_test.go b/pkg/compiler/compiler_test.go
index 261cffe9c..40450f6a4 100644
--- a/pkg/compiler/compiler_test.go
+++ b/pkg/compiler/compiler_test.go
@@ -37,16 +37,20 @@ func TestErrors(t *testing.T) {
 		"C1":       1,
 		"C2":       2,
 	}
-	name := "errors.txt"
-	em := ast.NewErrorMatcher(t, filepath.Join("testdata", name))
-	desc := ast.Parse(em.Data, name, em.ErrorHandler)
-	if desc == nil {
-		em.DumpErrors(t)
-		t.Fatalf("parsing failed")
+	for _, name := range []string{"errors.txt", "recursion.txt", "len.txt"} {
+		name := name
+		t.Run(name, func(t *testing.T) {
+			em := ast.NewErrorMatcher(t, filepath.Join("testdata", name))
+			desc := ast.Parse(em.Data, name, em.ErrorHandler)
+			if desc == nil {
+				em.DumpErrors(t)
+				t.Fatalf("parsing failed")
+			}
+			ExtractConsts(desc, em.ErrorHandler)
+			Compile(desc, consts, em.ErrorHandler)
+			em.Check(t)
+		})
 	}
-	ExtractConsts(desc, em.ErrorHandler)
-	Compile(desc, consts, em.ErrorHandler)
-	em.Check(t)
 }
 
 func TestFuzz(t *testing.T) {
diff --git a/pkg/compiler/testdata/errors.txt b/pkg/compiler/testdata/errors.txt
index feb0fed35..11fc9a495 100644
--- a/pkg/compiler/testdata/errors.txt
+++ b/pkg/compiler/testdata/errors.txt
@@ -4,7 +4,7 @@
 foo$0(x fileoff, y int8, z buffer[in])
 foo$1(x "bar")			### unexpected string "bar", expect type
 foo$2(x 123, y "bar")		### unexpected int 123, expect type	### unexpected string "bar", expect type
-foo$3(x string)			### string can't be syscall argument/return
+foo$3(x string)			### string can't be syscall argument
 
 resource r0[int32]: 0, 0x1
 resource r1[string["foo"]]	### string can't be resource base (int types can)
@@ -66,9 +66,6 @@ resource r2[r0]: 2
 resource r3[int32:1]
 resource r4[int32[opt]]		### resource base can't be marked as opt
 resource r5[non_existent]	### unknown type non_existent
-resource r6[r6]			### recursive resource r6->r6
-resource r7[r8]			### recursive resource r7->r8->r7
-resource r8[r7]			### recursive resource r8->r7->r8
 resource r9["foo"]		### unexpected string "foo", expect type
 
 foo$7(a r0, a1 r2[opt])
@@ -108,6 +105,8 @@ foo$40(a len["a"])		### unexpected string "a" for len target argument of len typ
 foo$41(a vma[C1:C2])
 foo$42(a proc[20, 0])		### proc per-process values must not be 0
 foo$43(a ptr[in, string[1]])	### unexpected int 1, string arg must be a string literal or string flags
+foo$44(a int32) len[a]		### len can't be syscall return
+foo$45(a int32) len[b]		### len can't be syscall return
 
 bar()
 
@@ -152,34 +151,3 @@ define d1 `some C expression`
 define d2 some C expression
 define d2 SOMETHING		### duplicate define d2
 define d3 1
-
-sr1 {
-	f1	sr1		### recursive declaration: sr1.f1 -> sr1 (mark some pointers as opt)
-}
-
-sr2 {
-	f1	sr3
-	f2	sr4
-}
-
-sr3 {
-	f1	ptr[in, sr3]	### recursive declaration: sr3.f1 -> sr3 (mark some pointers as opt)
-}
-
-sr4 {
-	f1	ptr[in, sr3]
-	f2	array[ptr[in, sr5], 4]	### recursive declaration: sr4.f2 -> sr5.f2 -> sr6.f1 -> sr4 (mark some pointers as opt)
-}
-
-sr5 [
-	f1	int32
-	f2	sr6
-]
-
-sr6 {
-	f1	sr4
-}
-
-sr7 {
-	f1	ptr[in, sr7, opt]
-}
diff --git a/pkg/compiler/testdata/len.txt b/pkg/compiler/testdata/len.txt
new file mode 100644
index 000000000..2b7836bbd
--- /dev/null
+++ b/pkg/compiler/testdata/len.txt
@@ -0,0 +1,23 @@
+# 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.
+
+foo$0(a int32, b len[a])
+foo$1(a len[a])			### len target a refer to itself
+foo$2(a ptr[in, len[a, int32]])	### len target a refer to itself
+foo$3(a int32, b len[c])	### len target c does not exist
+foo$4(a len[parent])		### len target parent does not exist
+foo$5(a ptr[in, int32], b ptr[in, array[len[a, int32]]])
+
+foo$100(a int32, b ptr[in, csum[a, inet, int32]])
+foo$101(a int32, b ptr[in, csum[c, inet, int32]])	### csum target c does not exist
+
+s1 {
+	f1	len[s2, int32]	### len target s2 does not exist
+}
+
+s2 {
+	f1	s1
+}
+
+foo$200(a ptr[in, s2])
+foo$201(a ptr[in, s1])
diff --git a/pkg/compiler/testdata/recursion.txt b/pkg/compiler/testdata/recursion.txt
new file mode 100644
index 000000000..683049b91
--- /dev/null
+++ b/pkg/compiler/testdata/recursion.txt
@@ -0,0 +1,37 @@
+# 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.
+
+resource r6[r6]			### recursive resource r6->r6
+resource r7[r8]			### recursive resource r7->r8->r7
+resource r8[r7]			### recursive resource r8->r7->r8
+
+sr1 {
+	f1	sr1		### recursive declaration: sr1.f1 -> sr1 (mark some pointers as opt)
+}
+
+sr2 {
+	f1	sr3
+	f2	sr4
+}
+
+sr3 {
+	f1	ptr[in, sr3]	### recursive declaration: sr3.f1 -> sr3 (mark some pointers as opt)
+}
+
+sr4 {
+	f1	ptr[in, sr3]
+	f2	array[ptr[in, sr5], 4]	### recursive declaration: sr4.f2 -> sr5.f2 -> sr6.f1 -> sr4 (mark some pointers as opt)
+}
+
+sr5 [
+	f1	int32
+	f2	sr6
+]
+
+sr6 {
+	f1	sr4
+}
+
+sr7 {
+	f1	ptr[in, sr7, opt]
+}
diff --git a/pkg/compiler/types.go b/pkg/compiler/types.go
index d83f986f3..cd5102fcc 100644
--- a/pkg/compiler/types.go
+++ b/pkg/compiler/types.go
@@ -16,6 +16,7 @@ type typeDesc struct {
 	Names        []string
 	CanBeArg     bool       // can be argument of syscall?
 	CantBeOpt    bool       // can't be marked as opt?
+	CantBeRet    bool       // can't be syscall return (directly or indirectly)?
 	NeedBase     bool       // needs base type when used as field?
 	AllowColon   bool       // allow colon (int8:2)?
 	ResourceBase bool       // can be resource base type?
@@ -129,11 +130,9 @@ var typeLen = &typeDesc{
 	Names:     []string{"len", "bytesize", "bytesize2", "bytesize4", "bytesize8"},
 	CanBeArg:  true,
 	CantBeOpt: true,
+	CantBeRet: true,
 	NeedBase:  true,
 	Args:      []namedArg{{"len target", typeArgLenTarget}},
-	Check: func(comp *compiler, t *ast.Type, args []*ast.Type, base sys.IntTypeCommon) {
-		// TODO(dvyukov): check args[0].Ident as len target
-	},
 	Gen: func(comp *compiler, t *ast.Type, args []*ast.Type, base sys.IntTypeCommon) sys.Type {
 		var byteSize uint64
 		switch t.Ident {
@@ -263,13 +262,13 @@ var typeCsum = &typeDesc{
 	Names:     []string{"csum"},
 	NeedBase:  true,
 	CantBeOpt: true,
+	CantBeRet: true,
 	OptArgs:   1,
 	Args:      []namedArg{{"csum target", typeArgLenTarget}, {"kind", typeArgCsumType}, {"proto", typeArgInt}},
 	Check: func(comp *compiler, t *ast.Type, args []*ast.Type, base sys.IntTypeCommon) {
 		if len(args) > 2 && genCsumKind(args[1]) != sys.CsumPseudo {
 			comp.error(args[2].Pos, "only pseudo csum can have proto")
 		}
-		// TODO(dvyukov): check args[0].Ident as len target
 	},
 	Gen: func(comp *compiler, t *ast.Type, args []*ast.Type, base sys.IntTypeCommon) sys.Type {
 		var proto uint64