From ffe7e17368d7ae6c2b40da2ce0703d8ad8a116ac Mon Sep 17 00:00:00 2001 From: Dmitry Vyukov Date: Tue, 5 Sep 2017 13:31:14 +0200 Subject: prog, sys: move types to prog Large overhaul moves syscalls and arg types from sys to prog. Sys package now depends on prog and contains only generated descriptions of syscalls. Introduce prog.Target type that encapsulates all targer properties, like syscall list, ptr/page size, etc. Also moves OS-dependent pieces like mmap call generation from prog to sys. Update #191 --- prog/analysis.go | 124 +------------ prog/checksum.go | 2 - prog/checksum_test.go | 11 +- prog/decl_test.go | 62 +++++++ prog/encoding.go | 24 ++- prog/encoding_test.go | 7 +- prog/encodingexec.go | 5 - prog/encodingexec_test.go | 13 +- prog/export_test.go | 47 +++++ prog/hints.go | 6 +- prog/hints_test.go | 2 - prog/mutation.go | 25 ++- prog/mutation_test.go | 27 +-- prog/prio.go | 2 - prog/prog.go | 26 ++- prog/prog_test.go | 35 +--- prog/rand.go | 141 +++----------- prog/size.go | 14 +- prog/size_test.go | 13 +- prog/target.go | 117 ++++++++++++ prog/types.go | 457 ++++++++++++++++++++++++++++++++++++++++++++++ prog/validation.go | 2 - 22 files changed, 805 insertions(+), 357 deletions(-) create mode 100644 prog/decl_test.go create mode 100644 prog/export_test.go create mode 100644 prog/target.go create mode 100644 prog/types.go (limited to 'prog') diff --git a/prog/analysis.go b/prog/analysis.go index 05837131a..009a15a21 100644 --- a/prog/analysis.go +++ b/prog/analysis.go @@ -10,8 +10,6 @@ package prog import ( "fmt" - - . "github.com/google/syzkaller/sys" ) const ( @@ -68,46 +66,18 @@ func (s *state) analyze(c *Call) { } } }) - switch c.Meta.Name { - case "mmap": - // Filter out only very wrong arguments. - length := c.Args[1].(*ConstArg) - if length.Val == 0 { - break + start, npages, mapped := analyzeMmap(c) + if npages != 0 { + if start+npages > uint64(len(s.pages)) { + panic(fmt.Sprintf("address is out of bounds: page=%v len=%v bound=%v", + start, npages, len(s.pages))) } - flags := c.Args[3].(*ConstArg) - fd := c.Args[4].(*ResultArg) - if flags.Val&MAP_ANONYMOUS == 0 && fd.Val == InvalidFD { - break - } - s.addressable(c.Args[0].(*PointerArg), length, true) - case "munmap": - s.addressable(c.Args[0].(*PointerArg), c.Args[1].(*ConstArg), false) - case "mremap": - s.addressable(c.Args[4].(*PointerArg), c.Args[2].(*ConstArg), true) - case "io_submit": - if arr := c.Args[2].(*PointerArg).Res; arr != nil { - for _, ptr := range arr.(*GroupArg).Inner { - p := ptr.(*PointerArg) - if p.Res != nil && p.Res.Type().Name() == "iocb" { - s.resources["iocbptr"] = append(s.resources["iocbptr"], ptr) - } - } + for i := uint64(0); i < npages; i++ { + s.pages[start+i] = mapped } } } -func (s *state) addressable(addr *PointerArg, size *ConstArg, ok bool) { - sizePages := size.Val / pageSize - if addr.PageIndex+sizePages > uint64(len(s.pages)) { - panic(fmt.Sprintf("address is out of bounds: page=%v len=%v bound=%v\naddr: %+v\nsize: %+v", - addr.PageIndex, sizePages, len(s.pages), addr, size)) - } - for i := uint64(0); i < sizePages; i++ { - s.pages[addr.PageIndex+i] = ok - } -} - func foreachSubargImpl(arg Arg, parent *[]Arg, f func(arg, base Arg, parent *[]Arg)) { var rec func(arg, base Arg, parent *[]Arg) rec = func(arg, base Arg, parent *[]Arg) { @@ -181,86 +151,6 @@ func foreachSubargOffset(arg Arg, f func(arg Arg, offset uint64)) { rec(arg, 0) } -func sanitizeCall(c *Call) { - switch c.Meta.CallName { - case "mmap": - // Add MAP_FIXED flag, otherwise it produces non-deterministic results. - _, ok := c.Args[0].(*PointerArg) - if !ok { - panic("mmap address is not ArgPointer") - } - _, ok = c.Args[1].(*ConstArg) - if !ok { - panic("mmap length is not ArgPageSize") - } - flags, ok := c.Args[3].(*ConstArg) - if !ok { - panic("mmap flag arg is not const") - } - flags.Val |= MAP_FIXED - case "mremap": - // Add MREMAP_FIXED flag, otherwise it produces non-deterministic results. - flags, ok := c.Args[3].(*ConstArg) - if !ok { - panic("mremap flag arg is not const") - } - if flags.Val&MREMAP_MAYMOVE != 0 { - flags.Val |= MREMAP_FIXED - } - case "mknod", "mknodat": - mode, ok1 := c.Args[1].(*ConstArg) - dev, ok2 := c.Args[2].(*ConstArg) - if c.Meta.CallName == "mknodat" { - mode, ok1 = c.Args[2].(*ConstArg) - dev, ok2 = c.Args[3].(*ConstArg) - } - if !ok1 || !ok2 { - panic("mknod mode is not const") - } - // Char and block devices read/write io ports, kernel memory and do other nasty things. - // TODO: not required if executor drops privileges. - switch mode.Val & (S_IFREG | S_IFCHR | S_IFBLK | S_IFIFO | S_IFSOCK) { - case S_IFREG, S_IFIFO, S_IFSOCK: - case S_IFBLK: - if dev.Val>>8 == 7 { - break // loop - } - mode.Val &^= S_IFBLK - mode.Val |= S_IFREG - case S_IFCHR: - mode.Val &^= S_IFCHR - mode.Val |= S_IFREG - } - case "syslog": - cmd := c.Args[0].(*ConstArg) - // These disable console output, but we need it. - if cmd.Val == SYSLOG_ACTION_CONSOLE_OFF || cmd.Val == SYSLOG_ACTION_CONSOLE_ON { - cmd.Val = SYSLOG_ACTION_SIZE_UNREAD - } - case "ioctl": - cmd := c.Args[1].(*ConstArg) - // Freeze kills machine. Though, it is an interesting functions, - // so we need to test it somehow. - // TODO: not required if executor drops privileges. - if uint32(cmd.Val) == FIFREEZE { - cmd.Val = FITHAW - } - case "ptrace": - req := c.Args[0].(*ConstArg) - // PTRACE_TRACEME leads to unkillable processes, see: - // https://groups.google.com/forum/#!topic/syzkaller/uGzwvhlCXAw - if req.Val == PTRACE_TRACEME { - req.Val = ^uint64(0) - } - case "exit", "exit_group": - code := c.Args[0].(*ConstArg) - // These codes are reserved by executor. - if code.Val%128 == 67 || code.Val%128 == 68 { - code.Val = 1 - } - } -} - func RequiresBitmasks(p *Prog) bool { result := false for _, c := range p.Calls { diff --git a/prog/checksum.go b/prog/checksum.go index 0c8f7210d..b5226e715 100644 --- a/prog/checksum.go +++ b/prog/checksum.go @@ -5,8 +5,6 @@ package prog import ( "fmt" - - . "github.com/google/syzkaller/sys" ) type CsumChunkKind int diff --git a/prog/checksum_test.go b/prog/checksum_test.go index 205450255..004769328 100644 --- a/prog/checksum_test.go +++ b/prog/checksum_test.go @@ -1,23 +1,26 @@ // Copyright 2016 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 +package prog_test import ( "testing" + + . "github.com/google/syzkaller/prog" + _ "github.com/google/syzkaller/sys" ) func TestChecksumCalcRandom(t *testing.T) { - rs, iters := initTest(t) + rs, iters := InitTest(t) for i := 0; i < iters; i++ { p := Generate(rs, 10, nil) for _, call := range p.Calls { - calcChecksumsCall(call, i%32) + CalcChecksumsCall(call, i%32) } for try := 0; try <= 10; try++ { p.Mutate(rs, 10, nil, nil) for _, call := range p.Calls { - calcChecksumsCall(call, i%32) + CalcChecksumsCall(call, i%32) } } } diff --git a/prog/decl_test.go b/prog/decl_test.go new file mode 100644 index 000000000..e716cdf5e --- /dev/null +++ b/prog/decl_test.go @@ -0,0 +1,62 @@ +// Copyright 2015 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 ( + "testing" +) + +func TestResourceCtors(t *testing.T) { + for _, c := range Syscalls { + for _, res := range c.InputResources() { + if len(calcResourceCtors(res.Desc.Kind, true)) == 0 { + t.Errorf("call %v requires input resource %v, but there are no calls that can create this resource", c.Name, res.Desc.Name) + } + } + } +} + +func TestTransitivelyEnabledCalls(t *testing.T) { + t.Parallel() + calls := make(map[*Syscall]bool) + for _, c := range Syscalls { + calls[c] = true + } + if trans := TransitivelyEnabledCalls(calls); len(calls) != len(trans) { + for c := range calls { + if !trans[c] { + t.Logf("disabled %v", c.Name) + } + } + t.Fatalf("can't create some resource") + } + delete(calls, SyscallMap["epoll_create"]) + if trans := TransitivelyEnabledCalls(calls); len(calls) != len(trans) { + t.Fatalf("still must be able to create epoll fd with epoll_create1") + } + delete(calls, SyscallMap["epoll_create1"]) + trans := TransitivelyEnabledCalls(calls) + if len(calls)-5 != len(trans) || + trans[SyscallMap["epoll_ctl$EPOLL_CTL_ADD"]] || + trans[SyscallMap["epoll_ctl$EPOLL_CTL_MOD"]] || + trans[SyscallMap["epoll_ctl$EPOLL_CTL_DEL"]] || + trans[SyscallMap["epoll_wait"]] || + trans[SyscallMap["epoll_pwait"]] { + t.Fatalf("epoll fd is not disabled") + } +} + +func TestClockGettime(t *testing.T) { + t.Parallel() + calls := make(map[*Syscall]bool) + for _, c := range Syscalls { + calls[c] = true + } + // Removal of clock_gettime should disable all calls that accept timespec/timeval. + delete(calls, SyscallMap["clock_gettime"]) + trans := TransitivelyEnabledCalls(calls) + if len(trans)+10 > len(calls) { + t.Fatalf("clock_gettime did not disable enough calls: before %v, after %v", len(calls), len(trans)) + } +} diff --git a/prog/encoding.go b/prog/encoding.go index 2081b1abb..a6ded73ca 100644 --- a/prog/encoding.go +++ b/prog/encoding.go @@ -10,8 +10,6 @@ import ( "fmt" "io" "strconv" - - . "github.com/google/syzkaller/sys" ) // String generates a very compact program description (mostly for debug output). @@ -146,7 +144,7 @@ func Deserialize(data []byte) (prog *Prog, err error) { } c := &Call{ Meta: meta, - Ret: returnArg(meta.Ret), + Ret: MakeReturnArg(meta.Ret), } prog.Calls = append(prog.Calls, c) p.Parse('(') @@ -213,13 +211,13 @@ func parseArg(typ Type, p *parser, vars map[string]Arg) (Arg, error) { } switch typ.(type) { case *ConstType, *IntType, *FlagsType, *ProcType, *LenType, *CsumType: - arg = constArg(typ, v) + arg = MakeConstArg(typ, v) case *ResourceType: - arg = resultArg(typ, nil, v) + arg = MakeResultArg(typ, nil, v) case *PtrType: - arg = pointerArg(typ, 0, 0, 0, nil) + arg = MakePointerArg(typ, 0, 0, 0, nil) case *VmaType: - arg = pointerArg(typ, 0, 0, 0, nil) + arg = MakePointerArg(typ, 0, 0, 0, nil) default: return nil, fmt.Errorf("bad const type %+v", typ) } @@ -229,7 +227,7 @@ func parseArg(typ Type, p *parser, vars map[string]Arg) (Arg, error) { if !ok || v == nil { return nil, fmt.Errorf("result %v references unknown variable (vars=%+v)", id, vars) } - arg = resultArg(typ, v, 0) + arg = MakeResultArg(typ, v, 0) if p.Char() == '/' { p.Parse('/') op := p.Ident() @@ -267,7 +265,7 @@ func parseArg(typ Type, p *parser, vars map[string]Arg) (Arg, error) { if err != nil { return nil, err } - arg = pointerArg(typ, page, off, size, inner) + arg = MakePointerArg(typ, page, off, size, inner) case '(': // This used to parse length of VmaType and return ArgPageSize, which is now removed. // Leaving this for now for backwards compatibility. @@ -275,7 +273,7 @@ func parseArg(typ Type, p *parser, vars map[string]Arg) (Arg, error) { if err != nil { return nil, err } - arg = constArg(typ, pages*pageSize) + arg = MakeConstArg(typ, pages*pageSize) case '"': p.Parse('"') val := "" @@ -301,7 +299,7 @@ func parseArg(typ Type, p *parser, vars map[string]Arg) (Arg, error) { } fld := t1.Fields[i] if IsPad(fld) { - inner = append(inner, constArg(fld, 0)) + inner = append(inner, MakeConstArg(fld, 0)) } else { arg, err := parseArg(fld, p, vars) if err != nil { @@ -317,7 +315,7 @@ func parseArg(typ Type, p *parser, vars map[string]Arg) (Arg, error) { for len(inner) < len(t1.Fields) { inner = append(inner, defaultArg(t1.Fields[len(inner)])) } - arg = groupArg(typ, inner) + arg = MakeGroupArg(typ, inner) case '[': t1, ok := typ.(*ArrayType) if !ok { @@ -336,7 +334,7 @@ func parseArg(typ Type, p *parser, vars map[string]Arg) (Arg, error) { } } p.Parse(']') - arg = groupArg(typ, inner) + arg = MakeGroupArg(typ, inner) case '@': t1, ok := typ.(*UnionType) if !ok { diff --git a/prog/encoding_test.go b/prog/encoding_test.go index f4036b458..c58fe7dc8 100644 --- a/prog/encoding_test.go +++ b/prog/encoding_test.go @@ -1,7 +1,7 @@ // Copyright 2016 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 +package prog_test import ( "fmt" @@ -9,6 +9,9 @@ import ( "regexp" "sort" "testing" + + . "github.com/google/syzkaller/prog" + _ "github.com/google/syzkaller/sys" ) func setToArray(s map[string]struct{}) []string { @@ -76,7 +79,7 @@ func TestCallSet(t *testing.T) { } func TestCallSetRandom(t *testing.T) { - rs, iters := initTest(t) + rs, iters := InitTest(t) for i := 0; i < iters; i++ { p := Generate(rs, 10, nil) calls0 := make(map[string]struct{}) diff --git a/prog/encodingexec.go b/prog/encodingexec.go index d50e4f3be..a4f41a694 100644 --- a/prog/encodingexec.go +++ b/prog/encodingexec.go @@ -9,8 +9,6 @@ package prog import ( "fmt" "sort" - - . "github.com/google/syzkaller/sys" ) const ( @@ -37,9 +35,6 @@ const ( const ( ExecBufferSize = 2 << 20 - - pageSize = 4 << 10 - dataOffset = 512 << 20 ) type Args []Arg diff --git a/prog/encodingexec_test.go b/prog/encodingexec_test.go index 37bfe04c0..9a2dd1d1e 100644 --- a/prog/encodingexec_test.go +++ b/prog/encodingexec_test.go @@ -1,7 +1,7 @@ // Copyright 2016 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 +package prog_test import ( "bytes" @@ -9,13 +9,12 @@ import ( "fmt" "testing" - . "github.com/google/syzkaller/sys" + . "github.com/google/syzkaller/prog" + _ "github.com/google/syzkaller/sys" ) -const ptrSize = 8 - func TestSerializeForExecRandom(t *testing.T) { - rs, iters := initTest(t) + rs, iters := InitTest(t) buf := make([]byte, ExecBufferSize) for i := 0; i < iters; i++ { p := Generate(rs, 10, nil) @@ -46,6 +45,10 @@ func TestSerializeForExec(t *testing.T) { argResult = uint64(ExecArgResult) argData = uint64(ExecArgData) ) + var ( + dataOffset = DataOffset() + ptrSize = PtrSize() + ) callID := func(name string) uint64 { c := SyscallMap[name] if c == nil { diff --git a/prog/export_test.go b/prog/export_test.go new file mode 100644 index 000000000..c5337d695 --- /dev/null +++ b/prog/export_test.go @@ -0,0 +1,47 @@ +// 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 ( + "math/rand" + "testing" + "time" +) + +// Export guts for testing. + +func init() { + debug = true +} + +var ( + CalcChecksumsCall = calcChecksumsCall + AssignSizesCall = assignSizesCall + DefaultArg = defaultArg + InitTest = initTest +) + +func PtrSize() uint64 { + return ptrSize +} + +func DataOffset() uint64 { + return dataOffset +} + +func PageSize() uint64 { + return pageSize +} + +func initTest(t *testing.T) (rand.Source, int) { + t.Parallel() + iters := 10000 + if testing.Short() { + iters = 100 + } + seed := int64(time.Now().UnixNano()) + rs := rand.NewSource(seed) + t.Logf("seed=%v", seed) + return rs, iters +} diff --git a/prog/hints.go b/prog/hints.go index ba8131081..e268d46a6 100644 --- a/prog/hints.go +++ b/prog/hints.go @@ -20,8 +20,6 @@ package prog import ( "encoding/binary" - - . "github.com/google/syzkaller/sys" ) type uint64Set map[uint64]bool @@ -95,7 +93,7 @@ func generateHints(p *Prog, compMap CompMap, c *Call, arg Arg, exec func(p *Prog switch a := arg.(type) { case *ConstArg: - originalArg = constArg(a.Type(), a.Val) + originalArg = MakeConstArg(a.Type(), a.Val) checkConstArg(a, compMap, constArgCandidate) case *DataArg: originalArg = dataArg(a.Type(), a.Data) @@ -105,7 +103,7 @@ func generateHints(p *Prog, compMap CompMap, c *Call, arg Arg, exec func(p *Prog func checkConstArg(arg *ConstArg, compMap CompMap, cb func(newArg Arg)) { for replacer := range shrinkExpand(arg.Val, compMap) { - cb(constArg(arg.typ, replacer)) + cb(MakeConstArg(arg.typ, replacer)) } } diff --git a/prog/hints_test.go b/prog/hints_test.go index 5409925bf..3f0a10726 100644 --- a/prog/hints_test.go +++ b/prog/hints_test.go @@ -7,8 +7,6 @@ import ( "fmt" "reflect" "testing" - - . "github.com/google/syzkaller/sys" ) type ConstArgTest struct { diff --git a/prog/mutation.go b/prog/mutation.go index a45a02fe1..e793e28e4 100644 --- a/prog/mutation.go +++ b/prog/mutation.go @@ -7,8 +7,6 @@ import ( "fmt" "math/rand" "unsafe" - - . "github.com/google/syzkaller/sys" ) func (p *Prog) Mutate(rs rand.Source, ncalls int, ct *ChoiceTable, corpus []*Prog) { @@ -178,11 +176,11 @@ func (p *Prog) Mutate(rs rand.Source, ncalls int, ct *ChoiceTable, corpus []*Pro arg1, calls1 := r.addr(s, t, size, a.Res) p.replaceArg(c, arg, arg1, calls1) case *StructType: - ctor := isSpecialStruct(t) - if ctor == nil { + gen := specialStructs[t.Name()] + if gen == nil { panic("bad arg returned by mutationArgs: StructType") } - arg1, calls1 := ctor(r, s) + arg1, calls1 := gen(&Gen{r, s}, t, arg.(*GroupArg)) for i, f := range arg1.(*GroupArg).Inner { p.replaceArg(c, arg.(*GroupArg).Inner[i], f, calls1) calls1 = nil @@ -255,7 +253,16 @@ func (p *Prog) Mutate(rs rand.Source, ncalls int, ct *ChoiceTable, corpus []*Pro // predicate pred. It iteratively generates simpler programs and asks pred // whether it is equal to the orginal program or not. If it is equivalent then // the simplification attempt is committed and the process continues. -func Minimize(p0 *Prog, callIndex0 int, pred func(*Prog, int) bool, crash bool) (*Prog, int) { +func Minimize(p0 *Prog, callIndex0 int, pred0 func(*Prog, int) bool, crash bool) (*Prog, int) { + pred := pred0 + if debug { + pred = func(p *Prog, callIndex int) bool { + if err := p.validate(); err != nil { + panic(err) + } + return pred0(p, callIndex) + } + } name0 := "" if callIndex0 != -1 { if callIndex0 < 0 || callIndex0 >= len(p0.Calls) { @@ -291,7 +298,7 @@ func Minimize(p0 *Prog, callIndex0 int, pred func(*Prog, int) bool, crash bool) } } // Prepend uber-mmap. - mmap := createMmapCall(uint64(lo), uint64(hi-lo)+1) + mmap := makeMmap(uint64(lo), uint64(hi-lo)+1) p.Calls = append([]*Call{mmap}, p.Calls...) if callIndex != -1 { callIndex++ @@ -496,7 +503,7 @@ func mutationArgs(c *Call) (args, bases []Arg) { foreachArg(c, func(arg, base Arg, _ *[]Arg) { switch typ := arg.Type().(type) { case *StructType: - if isSpecialStruct(typ) == nil { + if specialStructs[typ.Name()] == nil { // For structs only individual fields are updated. return } @@ -524,7 +531,7 @@ func mutationArgs(c *Call) (args, bases []Arg) { return } if base != nil { - if _, ok := base.Type().(*StructType); ok && isSpecialStruct(base.Type()) != nil { + if _, ok := base.Type().(*StructType); ok && specialStructs[base.Type().Name()] != nil { // These special structs are mutated as a whole. return } diff --git a/prog/mutation_test.go b/prog/mutation_test.go index 2f70e0a5d..060fe5f33 100644 --- a/prog/mutation_test.go +++ b/prog/mutation_test.go @@ -1,16 +1,19 @@ // Copyright 2015 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 +package prog_test import ( "bytes" "fmt" "testing" + + . "github.com/google/syzkaller/prog" + _ "github.com/google/syzkaller/sys" ) func TestClone(t *testing.T) { - rs, iters := initTest(t) + rs, iters := InitTest(t) for i := 0; i < iters; i++ { p := Generate(rs, 10, nil) p1 := p.Clone() @@ -23,7 +26,7 @@ func TestClone(t *testing.T) { } func TestMutate(t *testing.T) { - rs, iters := initTest(t) + rs, iters := InitTest(t) next: for i := 0; i < iters; i++ { p := Generate(rs, 10, nil) @@ -47,7 +50,7 @@ next: } func TestMutateCorpus(t *testing.T) { - rs, iters := initTest(t) + rs, iters := InitTest(t) var corpus []*Prog for i := 0; i < 100; i++ { p := Generate(rs, 10, nil) @@ -137,7 +140,7 @@ func TestMutateTable(t *testing.T) { "readv(r0, &(0x7f0000000000)=[{&(0x7f0000001000)=\"00\", 0x1}, {&(0x7f0000002000)=\"00\", 0x2}, {&(0x7f0000000000)=\"00\", 0x3}], 0x3)\n", }, } - rs, _ := initTest(t) + rs, _ := InitTest(t) nextTest: for ti, test := range tests { p, err := Deserialize([]byte(test[0])) @@ -288,35 +291,23 @@ func TestMinimize(t *testing.T) { } func TestMinimizeRandom(t *testing.T) { - rs, iters := initTest(t) + rs, iters := InitTest(t) iters /= 10 // Long test. for i := 0; i < iters; i++ { p := Generate(rs, 5, nil) Minimize(p, len(p.Calls)-1, func(p1 *Prog, callIndex int) bool { - if err := p1.validate(); err != nil { - t.Fatalf("invalid program: %v", err) - } return false }, true) Minimize(p, len(p.Calls)-1, func(p1 *Prog, callIndex int) bool { - if err := p1.validate(); err != nil { - t.Fatalf("invalid program: %v", err) - } return true }, true) } for i := 0; i < iters; i++ { p := Generate(rs, 5, nil) Minimize(p, len(p.Calls)-1, func(p1 *Prog, callIndex int) bool { - if err := p1.validate(); err != nil { - t.Fatalf("invalid program: %v", err) - } return false }, false) Minimize(p, len(p.Calls)-1, func(p1 *Prog, callIndex int) bool { - if err := p1.validate(); err != nil { - t.Fatalf("invalid program: %v", err) - } return true }, false) } diff --git a/prog/prio.go b/prog/prio.go index 92d2ea3db..c64ae319b 100644 --- a/prog/prio.go +++ b/prog/prio.go @@ -7,8 +7,6 @@ import ( "fmt" "math/rand" "sort" - - . "github.com/google/syzkaller/sys" ) // Calulation of call-to-call priorities. diff --git a/prog/prog.go b/prog/prog.go index 6e18f3a4a..579bac4e0 100644 --- a/prog/prog.go +++ b/prog/prog.go @@ -5,8 +5,6 @@ package prog import ( "fmt" - - . "github.com/google/syzkaller/sys" ) type Prog struct { @@ -224,11 +222,11 @@ func encodeValue(value uint64, size uint64, bigEndian bool) uint64 { } } -func constArg(t Type, v uint64) Arg { +func MakeConstArg(t Type, v uint64) Arg { return &ConstArg{ArgCommon: ArgCommon{typ: t}, Val: v} } -func resultArg(t Type, r Arg, v uint64) Arg { +func MakeResultArg(t Type, r Arg, v uint64) Arg { arg := &ResultArg{ArgCommon: ArgCommon{typ: t}, Res: r, Val: v} if r == nil { return arg @@ -249,11 +247,11 @@ func dataArg(t Type, data []byte) Arg { return &DataArg{ArgCommon: ArgCommon{typ: t}, Data: append([]byte{}, data...)} } -func pointerArg(t Type, page uint64, off int, npages uint64, obj Arg) Arg { +func MakePointerArg(t Type, page uint64, off int, npages uint64, obj Arg) Arg { return &PointerArg{ArgCommon: ArgCommon{typ: t}, PageIndex: page, PageOffset: off, PagesNum: npages, Res: obj} } -func groupArg(t Type, inner []Arg) Arg { +func MakeGroupArg(t Type, inner []Arg) Arg { return &GroupArg{ArgCommon: ArgCommon{typ: t}, Inner: inner} } @@ -261,16 +259,16 @@ func unionArg(t Type, opt Arg, typ Type) Arg { return &UnionArg{ArgCommon: ArgCommon{typ: t}, Option: opt, OptionType: typ} } -func returnArg(t Type) Arg { +func MakeReturnArg(t Type) Arg { return &ReturnArg{ArgCommon: ArgCommon{typ: t}} } func defaultArg(t Type) Arg { switch typ := t.(type) { case *IntType, *ConstType, *FlagsType, *LenType, *ProcType, *CsumType: - return constArg(t, t.Default()) + return MakeConstArg(t, t.Default()) case *ResourceType: - return resultArg(t, nil, typ.Desc.Type.Default()) + return MakeResultArg(t, nil, typ.Desc.Type.Default()) case *BufferType: var data []byte if typ.Kind == BufferString && typ.TypeSize != 0 { @@ -278,23 +276,23 @@ func defaultArg(t Type) Arg { } return dataArg(t, data) case *ArrayType: - return groupArg(t, nil) + return MakeGroupArg(t, nil) case *StructType: var inner []Arg for _, field := range typ.Fields { inner = append(inner, defaultArg(field)) } - return groupArg(t, inner) + return MakeGroupArg(t, inner) case *UnionType: return unionArg(t, defaultArg(typ.Fields[0]), typ.Fields[0]) case *VmaType: - return pointerArg(t, 0, 0, 1, nil) + return MakePointerArg(t, 0, 0, 1, nil) case *PtrType: var res Arg if !t.Optional() && t.Dir() != DirOut { res = defaultArg(typ.Type) } - return pointerArg(t, 0, 0, 0, res) + return MakePointerArg(t, 0, 0, 0, res) default: panic("unknown arg type") } @@ -364,7 +362,7 @@ func (p *Prog) removeArg(c *Call, arg0 Arg) { if _, ok := arg1.(*ResultArg); !ok { panic("use references not ArgResult") } - arg2 := resultArg(arg1.Type(), nil, arg1.Type().Default()) + arg2 := MakeResultArg(arg1.Type(), nil, arg1.Type().Default()) p.replaceArg(c, arg1, arg2, nil) } } diff --git a/prog/prog_test.go b/prog/prog_test.go index b377846fb..69aa9c166 100644 --- a/prog/prog_test.go +++ b/prog/prog_test.go @@ -6,47 +6,29 @@ package prog import ( "bytes" "fmt" - "math/rand" "testing" - "time" - - . "github.com/google/syzkaller/sys" + //. "github.com/google/syzkaller/prog" + //_ "github.com/google/syzkaller/sys" ) -func init() { - debug = true -} - -func initTest(t *testing.T) (rand.Source, int) { - t.Parallel() - iters := 10000 - if testing.Short() { - iters = 100 - } - seed := int64(time.Now().UnixNano()) - rs := rand.NewSource(seed) - t.Logf("seed=%v", seed) - return rs, iters -} - func TestGeneration(t *testing.T) { - rs, iters := initTest(t) + rs, iters := InitTest(t) for i := 0; i < iters; i++ { Generate(rs, 20, nil) } } func TestDefault(t *testing.T) { - initTest(t) + InitTest(t) for _, meta := range SyscallMap { for _, t := range meta.Args { - defaultArg(t) + DefaultArg(t) } } } func TestDefaultCallArgs(t *testing.T) { - initTest(t) + InitTest(t) for _, meta := range SyscallMap { // Ensure that we can restore all arguments of all calls. prog := fmt.Sprintf("%v()", meta.Name) @@ -61,7 +43,7 @@ func TestDefaultCallArgs(t *testing.T) { } func TestSerialize(t *testing.T) { - rs, iters := initTest(t) + rs, iters := InitTest(t) for i := 0; i < iters; i++ { p := Generate(rs, 10, nil) data := p.Serialize() @@ -83,9 +65,10 @@ func TestSerialize(t *testing.T) { } func TestVmaType(t *testing.T) { - rs, iters := initTest(t) + rs, iters := InitTest(t) meta := SyscallMap["syz_test$vma0"] r := newRand(rs) + pageSize := PageSize() for i := 0; i < iters; i++ { s := newState(nil) calls := r.generateParticularCall(s, meta) diff --git a/prog/rand.go b/prog/rand.go index 110436e37..1993d7461 100644 --- a/prog/rand.go +++ b/prog/rand.go @@ -12,7 +12,6 @@ import ( "sync" "github.com/google/syzkaller/pkg/ifuzz" - . "github.com/google/syzkaller/sys" ) var pageStartPool = sync.Pool{New: func() interface{} { return new([]uint64) }} @@ -224,102 +223,6 @@ func (r *randGen) randStringImpl(s *state, vals []string) []byte { return buf.Bytes() } -func isSpecialStruct(typ Type) func(r *randGen, s *state) (Arg, []*Call) { - a, ok := typ.(*StructType) - if !ok { - panic("must be a struct") - } - switch typ.Name() { - case "timespec": - return func(r *randGen, s *state) (Arg, []*Call) { - return r.timespec(s, a, false) - } - case "timeval": - return func(r *randGen, s *state) (Arg, []*Call) { - return r.timespec(s, a, true) - } - } - return nil -} - -func (r *randGen) timespec(s *state, typ *StructType, usec bool) (arg Arg, calls []*Call) { - // We need to generate timespec/timeval that are either (1) definitely in the past, - // or (2) definitely in unreachable fututre, or (3) few ms ahead of now. - // Note timespec/timeval can be absolute or relative to now. - switch { - case r.nOutOf(1, 4): - // now for relative, past for absolute - arg = groupArg(typ, []Arg{ - resultArg(typ.Fields[0], nil, 0), - resultArg(typ.Fields[1], nil, 0), - }) - case r.nOutOf(1, 3): - // few ms ahead for relative, past for absolute - nsec := uint64(10 * 1e6) - if usec { - nsec /= 1e3 - } - arg = groupArg(typ, []Arg{ - resultArg(typ.Fields[0], nil, 0), - resultArg(typ.Fields[1], nil, nsec), - }) - case r.nOutOf(1, 2): - // unreachable fututre for both relative and absolute - arg = groupArg(typ, []Arg{ - resultArg(typ.Fields[0], nil, 2e9), - resultArg(typ.Fields[1], nil, 0), - }) - default: - // few ms ahead for absolute - meta := SyscallMap["clock_gettime"] - ptrArgType := meta.Args[1].(*PtrType) - argType := ptrArgType.Type.(*StructType) - tp := groupArg(argType, []Arg{ - resultArg(argType.Fields[0], nil, 0), - resultArg(argType.Fields[1], nil, 0), - }) - var tpaddr Arg - tpaddr, calls = r.addr(s, ptrArgType, 16, tp) - gettime := &Call{ - Meta: meta, - Args: []Arg{ - constArg(meta.Args[0], CLOCK_REALTIME), - tpaddr, - }, - Ret: returnArg(meta.Ret), - } - calls = append(calls, gettime) - sec := resultArg(typ.Fields[0], tp.(*GroupArg).Inner[0], 0) - nsec := resultArg(typ.Fields[1], tp.(*GroupArg).Inner[1], 0) - if usec { - nsec.(*ResultArg).OpDiv = 1e3 - nsec.(*ResultArg).OpAdd = 10 * 1e3 - } else { - nsec.(*ResultArg).OpAdd = 10 * 1e6 - } - arg = groupArg(typ, []Arg{sec, nsec}) - } - return -} - -// createMmapCall creates a "normal" mmap call that maps [start, start+npages) page range. -func createMmapCall(start, npages uint64) *Call { - meta := SyscallMap["mmap"] - mmap := &Call{ - Meta: meta, - Args: []Arg{ - pointerArg(meta.Args[0], start, 0, npages, nil), - constArg(meta.Args[1], npages*pageSize), - constArg(meta.Args[2], PROT_READ|PROT_WRITE), - constArg(meta.Args[3], MAP_ANONYMOUS|MAP_PRIVATE|MAP_FIXED), - resultArg(meta.Args[4], nil, InvalidFD), - constArg(meta.Args[5], 0), - }, - Ret: returnArg(meta.Ret), - } - return mmap -} - func (r *randGen) addr1(s *state, typ Type, size uint64, data Arg) (Arg, []*Call) { npages := (size + pageSize - 1) / pageSize if npages == 0 { @@ -339,8 +242,8 @@ func (r *randGen) addr1(s *state, typ Type, size uint64, data Arg) (Arg, []*Call if !free { continue } - c := createMmapCall(i, npages) - return pointerArg(typ, i, 0, 0, data), []*Call{c} + c := makeMmap(i, npages) + return MakePointerArg(typ, i, 0, 0, data), []*Call{c} } return r.randPageAddr(s, typ, npages, data, false), nil } @@ -357,7 +260,7 @@ func (r *randGen) addr(s *state, typ Type, size uint64, data Arg) (Arg, []*Call) case r.nOutOf(50, 52): a.PageOffset = -int(size) case r.nOutOf(1, 2): - a.PageOffset = r.Intn(pageSize) + a.PageOffset = r.Intn(int(pageSize)) default: if size > 0 { a.PageOffset = -r.Intn(int(size)) @@ -395,13 +298,13 @@ func (r *randGen) randPageAddr(s *state, typ Type, npages uint64, data Arg, vma } *poolPtr = starts pageStartPool.Put(poolPtr) - return pointerArg(typ, page, 0, npages, data) + return MakePointerArg(typ, page, 0, npages, data) } func (r *randGen) createResource(s *state, res *ResourceType) (arg Arg, calls []*Call) { if r.inCreateResource { special := res.SpecialValues() - return resultArg(res, nil, special[r.Intn(len(special))]), nil + return MakeResultArg(res, nil, special[r.Intn(len(special))]), nil } r.inCreateResource = true defer func() { r.inCreateResource = false }() @@ -428,7 +331,7 @@ func (r *randGen) createResource(s *state, res *ResourceType) (arg Arg, calls [] metas = append(metas, meta) } if len(metas) == 0 { - return resultArg(res, nil, res.Default()), nil + return MakeResultArg(res, nil, res.Default()), nil } // Now we have a set of candidate calls that can create the necessary resource. @@ -447,7 +350,7 @@ func (r *randGen) createResource(s *state, res *ResourceType) (arg Arg, calls [] } if len(allres) != 0 { // Bingo! - arg := resultArg(res, allres[r.Intn(len(allres))], 0) + arg := MakeResultArg(res, allres[r.Intn(len(allres))], 0) return arg, calls } // Discard unsuccessful calls. @@ -550,7 +453,7 @@ func (r *randGen) generateCall(s *state, p *Prog) []*Call { func (r *randGen) generateParticularCall(s *state, meta *Syscall) (calls []*Call) { c := &Call{ Meta: meta, - Ret: returnArg(meta.Ret), + Ret: MakeReturnArg(meta.Ret), } c.Args, calls = r.generateArgs(s, meta.Args) assignSizesCall(c) @@ -629,7 +532,7 @@ func (r *randGen) generateArg(s *state, typ Type) (arg Arg, calls []*Call) { } }() if r.recDepth[str.Name()] >= 3 { - return pointerArg(typ, 0, 0, 0, nil), nil + return MakePointerArg(typ, 0, 0, 0, nil), nil } } } @@ -650,7 +553,7 @@ func (r *randGen) generateArg(s *state, typ Type) (arg Arg, calls []*Call) { } } if len(allres) != 0 { - arg = resultArg(a, allres[r.Intn(len(allres))], 0) + arg = MakeResultArg(a, allres[r.Intn(len(allres))], 0) } else { arg, calls = r.createResource(s, a) } @@ -659,7 +562,7 @@ func (r *randGen) generateArg(s *state, typ Type) (arg Arg, calls []*Call) { arg, calls = r.createResource(s, a) default: special := a.SpecialValues() - arg = resultArg(a, nil, special[r.Intn(len(special))]) + arg = MakeResultArg(a, nil, special[r.Intn(len(special))]) } return arg, calls case *BufferType: @@ -707,9 +610,9 @@ func (r *randGen) generateArg(s *state, typ Type) (arg Arg, calls []*Call) { arg := r.randPageAddr(s, a, npages, nil, true) return arg, nil case *FlagsType: - return constArg(a, r.flags(a.Vals)), nil + return MakeConstArg(a, r.flags(a.Vals)), nil case *ConstType: - return constArg(a, a.Val), nil + return MakeConstArg(a, a.Val), nil case *IntType: v := r.randInt() switch a.Kind { @@ -725,9 +628,9 @@ func (r *randGen) generateArg(s *state, typ Type) (arg Arg, calls []*Call) { case IntRange: v = r.randRangeInt(a.RangeBegin, a.RangeEnd) } - return constArg(a, v), nil + return MakeConstArg(a, v), nil case *ProcType: - return constArg(a, r.rand(int(a.ValuesPerProc))), nil + return MakeConstArg(a, r.rand(int(a.ValuesPerProc))), nil case *ArrayType: var count uint64 switch a.Kind { @@ -743,14 +646,14 @@ func (r *randGen) generateArg(s *state, typ Type) (arg Arg, calls []*Call) { inner = append(inner, arg1) calls = append(calls, calls1...) } - return groupArg(a, inner), calls + return MakeGroupArg(a, inner), calls case *StructType: - if ctor := isSpecialStruct(a); ctor != nil && a.Dir() != DirOut { - arg, calls = ctor(r, s) + if gen := specialStructs[a.Name()]; gen != nil && a.Dir() != DirOut { + arg, calls = gen(&Gen{r, s}, a, nil) return } args, calls := r.generateArgs(s, a.Fields) - group := groupArg(a, args) + group := MakeGroupArg(a, args) return group, calls case *UnionType: optType := a.Fields[r.Intn(len(a.Fields))] @@ -763,7 +666,7 @@ func (r *randGen) generateArg(s *state, typ Type) (arg Arg, calls []*Call) { // So try to reuse a previously used address. addrs := s.resources["iocbptr"] addr := addrs[r.Intn(len(addrs))].(*PointerArg) - arg = pointerArg(a, addr.PageIndex, addr.PageOffset, addr.PagesNum, inner) + arg = MakePointerArg(a, addr.PageIndex, addr.PageOffset, addr.PagesNum, inner) return arg, calls } arg, calls1 := r.addr(s, a, inner.Size(), inner) @@ -771,9 +674,9 @@ func (r *randGen) generateArg(s *state, typ Type) (arg Arg, calls []*Call) { return arg, calls case *LenType: // Return placeholder value of 0 while generating len arg. - return constArg(a, 0), nil + return MakeConstArg(a, 0), nil case *CsumType: - return constArg(a, 0), nil + return MakeConstArg(a, 0), nil default: panic("unknown argument type") } diff --git a/prog/size.go b/prog/size.go index b715f6f26..b9920c19b 100644 --- a/prog/size.go +++ b/prog/size.go @@ -5,32 +5,30 @@ package prog import ( "fmt" - - . "github.com/google/syzkaller/sys" ) func generateSize(arg Arg, lenType *LenType) Arg { if arg == nil { // Arg is an optional pointer, set size to 0. - return constArg(lenType, 0) + return MakeConstArg(lenType, 0) } switch arg.Type().(type) { case *VmaType: a := arg.(*PointerArg) - return constArg(lenType, a.PagesNum*pageSize) + return MakeConstArg(lenType, a.PagesNum*pageSize) case *ArrayType: a := arg.(*GroupArg) if lenType.ByteSize != 0 { - return constArg(lenType, a.Size()/lenType.ByteSize) + return MakeConstArg(lenType, a.Size()/lenType.ByteSize) } else { - return constArg(lenType, uint64(len(a.Inner))) + return MakeConstArg(lenType, uint64(len(a.Inner))) } default: if lenType.ByteSize != 0 { - return constArg(lenType, arg.Size()/lenType.ByteSize) + return MakeConstArg(lenType, arg.Size()/lenType.ByteSize) } else { - return constArg(lenType, arg.Size()) + return MakeConstArg(lenType, arg.Size()) } } } diff --git a/prog/size_test.go b/prog/size_test.go index c72e5283f..778725d49 100644 --- a/prog/size_test.go +++ b/prog/size_test.go @@ -1,21 +1,24 @@ // Copyright 2016 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 +package prog_test import ( "bytes" "strings" "testing" + + . "github.com/google/syzkaller/prog" + _ "github.com/google/syzkaller/sys" ) func TestAssignSizeRandom(t *testing.T) { - rs, iters := initTest(t) + rs, iters := InitTest(t) for i := 0; i < iters; i++ { p := Generate(rs, 10, nil) data0 := p.Serialize() for _, call := range p.Calls { - assignSizesCall(call) + AssignSizesCall(call) } if data1 := p.Serialize(); !bytes.Equal(data0, data1) { t.Fatalf("different lens assigned, initial: %v, new: %v", data0, data1) @@ -23,7 +26,7 @@ func TestAssignSizeRandom(t *testing.T) { p.Mutate(rs, 10, nil, nil) data0 = p.Serialize() for _, call := range p.Calls { - assignSizesCall(call) + AssignSizesCall(call) } if data1 := p.Serialize(); !bytes.Equal(data0, data1) { t.Fatalf("different lens assigned, initial: %v, new: %v", data0, data1) @@ -128,7 +131,7 @@ func TestAssignSize(t *testing.T) { t.Fatalf("failed to deserialize prog %v: %v", i, err) } for _, call := range p.Calls { - assignSizesCall(call) + AssignSizesCall(call) } p1 := strings.TrimSpace(string(p.Serialize())) if p1 != test.sizedProg { diff --git a/prog/target.go b/prog/target.go new file mode 100644 index 000000000..f5dde79f4 --- /dev/null +++ b/prog/target.go @@ -0,0 +1,117 @@ +// 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" +) + +// Target describes target OS/arch pair. +type Target struct { + OS string + Arch string + PtrSize uint64 + PageSize uint64 + DataOffset uint64 + + Syscalls []*Syscall + Resources []*ResourceDesc + + // MakeMmap creates call that maps [start, start+npages) page range. + MakeMmap func(start, npages uint64) *Call + + // AnalyzeMmap analyzes the call c regarding mapping/unmapping memory. + // If it maps/unmaps any memory returns [start, start+npages) range, + // otherwise returns npages = 0. + AnalyzeMmap func(c *Call) (start, npages uint64, mapped bool) + + // SanitizeCall neutralizes harmful calls. + SanitizeCall func(c *Call) + + // SpecialStructs allows target to do custom generation/mutation for some struct types. + // Map key is struct name for which custom generation/mutation is required. + // Map value is custom generation/mutation function that will be called + // for the corresponding structs. g is helper object that allows generate random numbers, + // allocate memory, etc. typ is the struct type. old is the old value of the struct + // for mutation, or nil for generation. The function returns a new value of the struct, + // and optionally any calls that need to be inserted before the arg reference. + SpecialStructs map[string]func(g *Gen, typ *StructType, old *GroupArg) (Arg, []*Call) + + resourceMap map[string]*ResourceDesc + syscallMap map[string]*Syscall + resourceCtors map[string][]*Syscall +} + +type StructGen func(g *Gen, typ *StructType, old *GroupArg) (Arg, []*Call) + +var targets = make(map[string]*Target) + +func RegisterTarget(target *Target) { + key := target.OS + "/" + target.Arch + if targets[key] != nil { + panic(fmt.Sprintf("duplicate target %v", key)) + } + initTarget(target) + targets[key] = target + + // For now we copy target to global vars + // because majority of the code is not prepared for multiple targets. + if len(targets) > 1 { + panic("only 1 target is supported") + } + Syscalls = target.Syscalls + SyscallMap = target.syscallMap + Resources = target.resourceMap + resourceCtors = target.resourceCtors + ptrSize = target.PtrSize + pageSize = target.PageSize + dataOffset = target.DataOffset + + makeMmap = target.MakeMmap + analyzeMmap = target.AnalyzeMmap + sanitizeCall = target.SanitizeCall + specialStructs = target.SpecialStructs +} + +func initTarget(target *Target) { + target.syscallMap = make(map[string]*Syscall) + for _, c := range target.Syscalls { + target.syscallMap[c.Name] = c + } + target.resourceMap = make(map[string]*ResourceDesc) + target.resourceCtors = make(map[string][]*Syscall) + for _, r := range target.Resources { + target.resourceMap[r.Name] = r + target.resourceCtors[r.Name] = calcResourceCtors(r.Kind, false) + } +} + +type Gen struct { + r *randGen + s *state +} + +func (g *Gen) NOutOf(n, outOf int) bool { + return g.r.nOutOf(n, outOf) +} + +func (g *Gen) Alloc(ptrType Type, data Arg) (Arg, []*Call) { + return g.r.addr(g.s, ptrType, data.Size(), data) +} + +var ( + ptrSize uint64 + pageSize uint64 + dataOffset uint64 + + Syscalls []*Syscall + SyscallMap map[string]*Syscall + Resources map[string]*ResourceDesc + resourceCtors map[string][]*Syscall + + makeMmap func(start, npages uint64) *Call + analyzeMmap func(c *Call) (start, npages uint64, mapped bool) + sanitizeCall func(c *Call) + specialStructs map[string]func(g *Gen, typ *StructType, old *GroupArg) (Arg, []*Call) +) diff --git a/prog/types.go b/prog/types.go new file mode 100644 index 000000000..6fdc0d975 --- /dev/null +++ b/prog/types.go @@ -0,0 +1,457 @@ +// Copyright 2015/2016 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" +) + +type Syscall struct { + ID int + NR uint64 // kernel syscall number + Name string + CallName string + Args []Type + Ret Type +} + +type Dir int + +const ( + DirIn Dir = iota + DirOut + DirInOut +) + +type Type interface { + Name() string + FieldName() string + Dir() Dir + Optional() bool + Default() uint64 + Varlen() bool + Size() uint64 + BitfieldOffset() uint64 + BitfieldLength() uint64 + BitfieldMiddle() bool // returns true for all but last bitfield in a group +} + +func IsPad(t Type) bool { + if ct, ok := t.(*ConstType); ok && ct.IsPad { + return true + } + return false +} + +type TypeCommon struct { + TypeName string + FldName string // for struct fields and named args + TypeSize uint64 // static size of the type, or 0 for variable size types + ArgDir Dir + IsOptional bool +} + +func (t *TypeCommon) Name() string { + return t.TypeName +} + +func (t *TypeCommon) FieldName() string { + return t.FldName +} + +func (t *TypeCommon) Optional() bool { + return t.IsOptional +} + +func (t *TypeCommon) Default() uint64 { + return 0 +} + +func (t *TypeCommon) Size() uint64 { + if t.Varlen() { + panic(fmt.Sprintf("static type size is not known: %#v", t)) + } + return t.TypeSize +} + +func (t *TypeCommon) Varlen() bool { + return t.TypeSize == 0 +} + +func (t *TypeCommon) BitfieldOffset() uint64 { + return 0 +} + +func (t *TypeCommon) BitfieldLength() uint64 { + return 0 +} + +func (t *TypeCommon) BitfieldMiddle() bool { + return false +} + +func (t TypeCommon) Dir() Dir { + return t.ArgDir +} + +type ResourceDesc struct { + Name string + Type Type + Kind []string + Values []uint64 +} + +type ResourceType struct { + TypeCommon + Desc *ResourceDesc +} + +func (t *ResourceType) Default() uint64 { + return t.Desc.Values[0] +} + +func (t *ResourceType) SpecialValues() []uint64 { + return t.Desc.Values +} + +type IntTypeCommon struct { + TypeCommon + BitfieldOff uint64 + BitfieldLen uint64 + BigEndian bool + BitfieldMdl bool +} + +func (t *IntTypeCommon) BitfieldOffset() uint64 { + return t.BitfieldOff +} + +func (t *IntTypeCommon) BitfieldLength() uint64 { + return t.BitfieldLen +} + +func (t *IntTypeCommon) BitfieldMiddle() bool { + return t.BitfieldMdl +} + +type ConstType struct { + IntTypeCommon + Val uint64 + IsPad bool +} + +type IntKind int + +const ( + IntPlain IntKind = iota + IntFileoff // offset within a file + IntRange +) + +type IntType struct { + IntTypeCommon + Kind IntKind + RangeBegin uint64 + RangeEnd uint64 +} + +type FlagsType struct { + IntTypeCommon + Vals []uint64 +} + +type LenType struct { + IntTypeCommon + ByteSize uint64 // want size in multiple of bytes instead of array size + Buf string +} + +type ProcType struct { + IntTypeCommon + ValuesStart uint64 + ValuesPerProc uint64 +} + +type CsumKind int + +const ( + CsumInet CsumKind = iota + CsumPseudo +) + +type CsumType struct { + IntTypeCommon + Kind CsumKind + Buf string + Protocol uint64 // for CsumPseudo +} + +type VmaType struct { + TypeCommon + RangeBegin uint64 // in pages + RangeEnd uint64 +} + +type BufferKind int + +const ( + BufferBlobRand BufferKind = iota + BufferBlobRange + BufferString + BufferFilename + BufferText +) + +type TextKind int + +const ( + Text_x86_real TextKind = iota + Text_x86_16 + Text_x86_32 + Text_x86_64 + Text_arm64 +) + +type BufferType struct { + TypeCommon + Kind BufferKind + RangeBegin uint64 // for BufferBlobRange kind + RangeEnd uint64 // for BufferBlobRange kind + Text TextKind // for BufferText + SubKind string + Values []string // possible values for BufferString kind +} + +type ArrayKind int + +const ( + ArrayRandLen ArrayKind = iota + ArrayRangeLen +) + +type ArrayType struct { + TypeCommon + Type Type + Kind ArrayKind + RangeBegin uint64 + RangeEnd uint64 +} + +type PtrType struct { + TypeCommon + Type Type +} + +type StructType struct { + Key StructKey + FldName string + *StructDesc +} + +func (t *StructType) FieldName() string { + return t.FldName +} + +type UnionType struct { + Key StructKey + FldName string + *StructDesc +} + +func (t *UnionType) FieldName() string { + return t.FldName +} + +type StructDesc struct { + TypeCommon + Fields []Type + AlignAttr uint64 +} + +func (t *StructDesc) FieldName() string { + panic("must not be called") +} + +type StructKey struct { + Name string + Dir Dir +} + +type KeyedStruct struct { + Key StructKey + Desc *StructDesc +} + +// ResourceConstructors returns a list of calls that can create a resource of the given kind. +func ResourceConstructors(name string) []*Syscall { + return resourceCtors[name] +} + +func calcResourceCtors(kind []string, precise bool) []*Syscall { + // Find calls that produce the necessary resources. + var metas []*Syscall + for _, meta := range Syscalls { + // Recurse into arguments to see if there is an out/inout arg of necessary type. + ok := false + ForeachType(meta, func(typ Type) { + if ok { + return + } + switch typ1 := typ.(type) { + case *ResourceType: + if typ1.Dir() != DirIn && isCompatibleResource(kind, typ1.Desc.Kind, precise) { + ok = true + } + } + }) + if ok { + metas = append(metas, meta) + } + } + return metas +} + +// IsCompatibleResource returns true if resource of kind src can be passed as an argument of kind dst. +func IsCompatibleResource(dst, src string) bool { + dstRes := Resources[dst] + if dstRes == nil { + panic(fmt.Sprintf("unknown resource '%v'", dst)) + } + srcRes := Resources[src] + if srcRes == nil { + panic(fmt.Sprintf("unknown resource '%v'", src)) + } + return isCompatibleResource(dstRes.Kind, srcRes.Kind, false) +} + +// isCompatibleResource returns true if resource of kind src can be passed as an argument of kind dst. +// If precise is true, then it does not allow passing a less specialized resource (e.g. fd) +// as a more specialized resource (e.g. socket). Otherwise it does. +func isCompatibleResource(dst, src []string, precise bool) bool { + if len(dst) > len(src) { + // dst is more specialized, e.g dst=socket, src=fd. + if precise { + return false + } + dst = dst[:len(src)] + } + if len(src) > len(dst) { + // src is more specialized, e.g dst=fd, src=socket. + src = src[:len(dst)] + } + for i, k := range dst { + if k != src[i] { + return false + } + } + return true +} + +func (c *Syscall) InputResources() []*ResourceType { + var resources []*ResourceType + ForeachType(c, func(typ Type) { + switch typ1 := typ.(type) { + case *ResourceType: + if typ1.Dir() != DirOut && !typ1.IsOptional { + resources = append(resources, typ1) + } + } + }) + return resources +} + +func TransitivelyEnabledCalls(enabled map[*Syscall]bool) map[*Syscall]bool { + supported := make(map[*Syscall]bool) + for c := range enabled { + supported[c] = true + } + inputResources := make(map[*Syscall][]*ResourceType) + ctors := make(map[string][]*Syscall) + for c := range supported { + inputs := c.InputResources() + inputResources[c] = inputs + for _, res := range inputs { + if _, ok := ctors[res.Desc.Name]; ok { + continue + } + ctors[res.Desc.Name] = calcResourceCtors(res.Desc.Kind, true) + } + } + for { + n := len(supported) + haveGettime := supported[SyscallMap["clock_gettime"]] + for c := range supported { + canCreate := true + for _, res := range inputResources[c] { + noctors := true + for _, ctor := range ctors[res.Desc.Name] { + if supported[ctor] { + noctors = false + break + } + } + if noctors { + canCreate = false + break + } + } + // We need to support structs as resources, + // but for now we just special-case timespec/timeval. + if canCreate && !haveGettime { + ForeachType(c, func(typ Type) { + if a, ok := typ.(*StructType); ok && a.Dir() != DirOut && (a.Name() == "timespec" || a.Name() == "timeval") { + canCreate = false + } + }) + } + if !canCreate { + delete(supported, c) + } + } + if n == len(supported) { + break + } + } + return supported +} + +func ForeachType(meta *Syscall, f func(Type)) { + seen := make(map[*StructDesc]bool) + var rec func(t Type) + rec = func(t Type) { + f(t) + switch a := t.(type) { + case *PtrType: + rec(a.Type) + case *ArrayType: + rec(a.Type) + case *StructType: + if seen[a.StructDesc] { + return // prune recursion via pointers to structs/unions + } + seen[a.StructDesc] = true + for _, f := range a.Fields { + rec(f) + } + case *UnionType: + if seen[a.StructDesc] { + return // prune recursion via pointers to structs/unions + } + seen[a.StructDesc] = true + for _, opt := range a.Fields { + rec(opt) + } + case *ResourceType, *BufferType, *VmaType, *LenType, + *FlagsType, *ConstType, *IntType, *ProcType, *CsumType: + default: + panic("unknown type") + } + } + for _, t := range meta.Args { + rec(t) + } + if meta.Ret != nil { + rec(meta.Ret) + } +} diff --git a/prog/validation.go b/prog/validation.go index 51520b29b..d5b4a4c04 100644 --- a/prog/validation.go +++ b/prog/validation.go @@ -5,8 +5,6 @@ package prog import ( "fmt" - - . "github.com/google/syzkaller/sys" ) var debug = false // enabled in tests -- cgit mrf-deployment