From b06c1bd324d3aff0f132381727c85940bcf93b2f Mon Sep 17 00:00:00 2001 From: Dmitry Vyukov Date: Mon, 4 Sep 2017 19:52:49 +0200 Subject: pkg/compiler: verify validity of len targets Update #217 --- pkg/compiler/check.go | 105 ++++++++++++++++++++++++++++++------ pkg/compiler/compiler_test.go | 22 ++++---- pkg/compiler/testdata/errors.txt | 38 ++----------- pkg/compiler/testdata/len.txt | 23 ++++++++ pkg/compiler/testdata/recursion.txt | 37 +++++++++++++ pkg/compiler/types.go | 7 ++- 6 files changed, 167 insertions(+), 65 deletions(-) create mode 100644 pkg/compiler/testdata/len.txt create mode 100644 pkg/compiler/testdata/recursion.txt 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 -- cgit mrf-deployment