| // 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. |
| |
| // Conservative resource-related analysis of programs. |
| // The analysis figures out what files descriptors are [potentially] opened |
| // at a particular point in program, what pages are [potentially] mapped, |
| // what files were already referenced in calls, etc. |
| |
| package prog |
| |
| import ( |
| "fmt" |
| ) |
| |
| type state struct { |
| target *Target |
| ct *ChoiceTable |
| files map[string]bool |
| resources map[string][]*ResultArg |
| strings map[string]bool |
| ma *memAlloc |
| va *vmaAlloc |
| } |
| |
| // analyze analyzes the program p up to but not including call c. |
| func analyze(ct *ChoiceTable, p *Prog, c *Call) *state { |
| s := newState(p.Target, ct) |
| resources := true |
| for _, c1 := range p.Calls { |
| if c1 == c { |
| resources = false |
| } |
| s.analyzeImpl(c1, resources) |
| } |
| return s |
| } |
| |
| func newState(target *Target, ct *ChoiceTable) *state { |
| s := &state{ |
| target: target, |
| ct: ct, |
| files: make(map[string]bool), |
| resources: make(map[string][]*ResultArg), |
| strings: make(map[string]bool), |
| ma: newMemAlloc(target.NumPages * target.PageSize), |
| va: newVmaAlloc(target.NumPages), |
| } |
| return s |
| } |
| |
| func (s *state) analyze(c *Call) { |
| s.analyzeImpl(c, true) |
| } |
| |
| func (s *state) analyzeImpl(c *Call, resources bool) { |
| ForeachArg(c, func(arg Arg, _ *ArgCtx) { |
| switch a := arg.(type) { |
| case *PointerArg: |
| switch { |
| case a.IsNull(): |
| case a.VmaSize != 0: |
| s.va.noteAlloc(a.Address/s.target.PageSize, a.VmaSize/s.target.PageSize) |
| default: |
| s.ma.noteAlloc(a.Address, a.Res.Size()) |
| } |
| } |
| switch typ := arg.Type().(type) { |
| case *ResourceType: |
| a := arg.(*ResultArg) |
| if resources && typ.Dir() != DirIn { |
| s.resources[typ.Desc.Name] = append(s.resources[typ.Desc.Name], a) |
| // TODO: negative PIDs and add them as well (that's process groups). |
| } |
| case *BufferType: |
| a := arg.(*DataArg) |
| if typ.Dir() != DirOut && len(a.Data()) != 0 { |
| val := string(a.Data()) |
| // Remove trailing zero padding. |
| for len(val) >= 2 && val[len(val)-1] == 0 && val[len(val)-2] == 0 { |
| val = val[:len(val)-1] |
| } |
| switch typ.Kind { |
| case BufferString: |
| s.strings[val] = true |
| case BufferFilename: |
| if len(val) < 3 { |
| // This is not our file, probalby one of specialFiles. |
| return |
| } |
| if val[len(val)-1] == 0 { |
| val = val[:len(val)-1] |
| } |
| s.files[val] = true |
| } |
| } |
| } |
| }) |
| } |
| |
| type ArgCtx struct { |
| Parent *[]Arg // GroupArg.Inner (for structs) or Call.Args containing this arg |
| Base *PointerArg // pointer to the base of the heap object containing this arg |
| Offset uint64 // offset of this arg from the base |
| Stop bool // if set by the callback, subargs of this arg are not visited |
| } |
| |
| func ForeachSubArg(arg Arg, f func(Arg, *ArgCtx)) { |
| foreachArgImpl(arg, ArgCtx{}, f) |
| } |
| |
| func ForeachArg(c *Call, f func(Arg, *ArgCtx)) { |
| ctx := ArgCtx{} |
| if c.Ret != nil { |
| foreachArgImpl(c.Ret, ctx, f) |
| } |
| ctx.Parent = &c.Args |
| for _, arg := range c.Args { |
| foreachArgImpl(arg, ctx, f) |
| } |
| } |
| |
| func foreachArgImpl(arg Arg, ctx ArgCtx, f func(Arg, *ArgCtx)) { |
| f(arg, &ctx) |
| if ctx.Stop { |
| return |
| } |
| switch a := arg.(type) { |
| case *GroupArg: |
| if _, ok := a.Type().(*StructType); ok { |
| ctx.Parent = &a.Inner |
| } |
| var totalSize uint64 |
| for _, arg1 := range a.Inner { |
| foreachArgImpl(arg1, ctx, f) |
| if !arg1.Type().BitfieldMiddle() { |
| size := arg1.Size() |
| ctx.Offset += size |
| totalSize += size |
| } |
| } |
| claimedSize := a.Size() |
| varlen := a.Type().Varlen() |
| if varlen && totalSize > claimedSize || !varlen && totalSize != claimedSize { |
| panic(fmt.Sprintf("bad group arg size %v, should be <= %v for %#v type %#v", |
| totalSize, claimedSize, a, a.Type())) |
| } |
| case *PointerArg: |
| if a.Res != nil { |
| ctx.Base = a |
| ctx.Offset = 0 |
| foreachArgImpl(a.Res, ctx, f) |
| } |
| case *UnionArg: |
| foreachArgImpl(a.Option, ctx, f) |
| } |
| } |
| |
| func RequiredFeatures(p *Prog) (bitmasks, csums bool) { |
| for _, c := range p.Calls { |
| ForeachArg(c, func(arg Arg, _ *ArgCtx) { |
| if a, ok := arg.(*ConstArg); ok { |
| if a.Type().BitfieldOffset() != 0 || a.Type().BitfieldLength() != 0 { |
| bitmasks = true |
| } |
| } |
| if _, ok := arg.Type().(*CsumType); ok { |
| csums = true |
| } |
| }) |
| } |
| return |
| } |
| |
| type CallFlags int |
| |
| const ( |
| CallExecuted CallFlags = 1 << iota // was started at all |
| CallFinished // finished executing (rather than blocked forever) |
| CallBlocked // finished but blocked during execution |
| ) |
| |
| type CallInfo struct { |
| Flags CallFlags |
| Errno int |
| Signal []uint32 |
| } |
| |
| const ( |
| fallbackSignalErrno = iota |
| fallbackSignalErrnoBlocked |
| fallbackSignalCtor |
| fallbackSignalFlags |
| fallbackCallMask = 0x1fff |
| ) |
| |
| func (p *Prog) FallbackSignal(info []CallInfo) { |
| resources := make(map[*ResultArg]*Call) |
| for i, c := range p.Calls { |
| inf := &info[i] |
| if inf.Flags&CallExecuted == 0 { |
| continue |
| } |
| id := c.Meta.ID |
| typ := fallbackSignalErrno |
| if inf.Flags&CallFinished != 0 && inf.Flags&CallBlocked != 0 { |
| typ = fallbackSignalErrnoBlocked |
| } |
| inf.Signal = append(inf.Signal, encodeFallbackSignal(typ, id, inf.Errno)) |
| if inf.Errno != 0 { |
| continue |
| } |
| ForeachArg(c, func(arg Arg, _ *ArgCtx) { |
| if a, ok := arg.(*ResultArg); ok { |
| resources[a] = c |
| } |
| }) |
| // Specifically look only at top-level arguments, |
| // deeper arguments can produce too much false signal. |
| flags := 0 |
| for _, arg := range c.Args { |
| switch a := arg.(type) { |
| case *ResultArg: |
| flags <<= 1 |
| if a.Res != nil { |
| ctor := resources[a.Res] |
| if ctor != nil { |
| inf.Signal = append(inf.Signal, |
| encodeFallbackSignal(fallbackSignalCtor, id, ctor.Meta.ID)) |
| } |
| } else { |
| if a.Val != a.Type().(*ResourceType).SpecialValues()[0] { |
| flags |= 1 |
| } |
| } |
| case *ConstArg: |
| const width = 3 |
| flags <<= width |
| switch typ := a.Type().(type) { |
| case *FlagsType: |
| if typ.BitMask { |
| for i, v := range typ.Vals { |
| if a.Val&v != 0 { |
| flags ^= 1 << (uint(i) % width) |
| } |
| } |
| } else { |
| for i, v := range typ.Vals { |
| if a.Val == v { |
| flags |= i % (1 << width) |
| break |
| } |
| } |
| } |
| case *LenType: |
| flags <<= 1 |
| if a.Val == 0 { |
| flags |= 1 |
| } |
| } |
| case *PointerArg: |
| flags <<= 1 |
| if a.IsNull() { |
| flags |= 1 |
| } |
| } |
| } |
| if flags != 0 { |
| inf.Signal = append(inf.Signal, |
| encodeFallbackSignal(fallbackSignalFlags, id, flags)) |
| } |
| } |
| } |
| |
| func DecodeFallbackSignal(s uint32) (callID, errno int) { |
| typ, id, aux := decodeFallbackSignal(s) |
| switch typ { |
| case fallbackSignalErrno, fallbackSignalErrnoBlocked: |
| return id, aux |
| case fallbackSignalCtor, fallbackSignalFlags: |
| return id, 0 |
| default: |
| panic(fmt.Sprintf("bad fallback signal type %v", typ)) |
| } |
| } |
| |
| func encodeFallbackSignal(typ, id, aux int) uint32 { |
| if typ & ^7 != 0 { |
| panic(fmt.Sprintf("bad fallback signal type %v", typ)) |
| } |
| if id & ^fallbackCallMask != 0 { |
| panic(fmt.Sprintf("bad call id in fallback signal %v", id)) |
| } |
| return uint32(typ) | uint32(id&fallbackCallMask)<<3 | uint32(aux)<<16 |
| } |
| |
| func decodeFallbackSignal(s uint32) (typ, id, aux int) { |
| return int(s & 7), int((s >> 3) & fallbackCallMask), int(s >> 16) |
| } |