From e8dd2c6713522707b3b89884eb95601cdf9bc9be Mon Sep 17 00:00:00 2001 From: Dmitry Vyukov Date: Thu, 30 Aug 2018 14:17:47 -0700 Subject: prog: add concept of "special pointers" Currently we only generate either valid user-space pointers or NULL. Extend NULL to a set of special pointers that we will use in programs. All targets now contain 3 special values: - NULL - 0xfffffffffffffff (invalid kernel pointer) - 0x999999999999999 (non-canonical address) Each target can add additional special pointers on top of this. Also generate NULL/special pointers for non-opt ptr's. This restriction was always too restrictive. We may want to generate them with very low probability, but we do want to generate them. Also change pointers to NULL/special during mutation (but still not in the opposite direction). --- prog/analysis.go | 4 ++-- prog/encoding.go | 10 ++++------ prog/encoding_test.go | 36 ++++++++++++++++++++++++++++++++++-- prog/encodingexec.go | 7 ------- prog/encodingexec_test.go | 24 ++++++++++++++++++++++++ prog/mutation.go | 9 ++++++++- prog/prog.go | 32 +++++++++++++++++++------------- prog/rand.go | 6 +++++- prog/target.go | 14 ++++++++++++++ prog/types.go | 11 ++++++----- prog/validation.go | 25 ++++++++++++++----------- 11 files changed, 130 insertions(+), 48 deletions(-) (limited to 'prog') diff --git a/prog/analysis.go b/prog/analysis.go index 3ebfbda61..c26e14014 100644 --- a/prog/analysis.go +++ b/prog/analysis.go @@ -57,7 +57,7 @@ func (s *state) analyzeImpl(c *Call, resources bool) { switch a := arg.(type) { case *PointerArg: switch { - case a.IsNull(): + case a.IsSpecial(): case a.VmaSize != 0: s.va.noteAlloc(a.Address/s.target.PageSize, a.VmaSize/s.target.PageSize) default: @@ -273,7 +273,7 @@ func extractArgSignal(arg Arg, callID, flags int, inf *CallInfo, resources map[* } case *PointerArg: flags <<= 1 - if a.IsNull() { + if a.IsSpecial() { flags |= 1 } } diff --git a/prog/encoding.go b/prog/encoding.go index 92e2c47f0..c968fa0b7 100644 --- a/prog/encoding.go +++ b/prog/encoding.go @@ -85,8 +85,8 @@ func (a *ConstArg) serialize(ctx *serializer) { } func (a *PointerArg) serialize(ctx *serializer) { - if a.IsNull() { - ctx.printf("0x0") + if a.IsSpecial() { + ctx.printf("0x%x", a.Address) return } target := ctx.target @@ -345,10 +345,8 @@ func (target *Target) parseArgInt(typ Type, p *parser) (Arg, error) { case *ResourceType: return MakeResultArg(typ, nil, v), nil case *PtrType, *VmaType: - if typ.Optional() { - return MakeNullPointerArg(typ), nil - } - return typ.makeDefaultArg(), nil + index := -v % uint64(len(target.SpecialPointers)) + return MakeSpecialPointerArg(typ, index), nil default: eatExcessive(p, true) return typ.makeDefaultArg(), nil diff --git a/prog/encoding_test.go b/prog/encoding_test.go index 0b3364e63..1bb22228f 100644 --- a/prog/encoding_test.go +++ b/prog/encoding_test.go @@ -12,6 +12,8 @@ import ( "sort" "strings" "testing" + + "github.com/google/go-cmp/cmp" ) func setToArray(s map[string]struct{}) []string { @@ -160,7 +162,7 @@ func TestDeserialize(t *testing.T) { }, { input: `test$excessive_fields1(0x0)`, - output: `test$excessive_fields1(&(0x7f0000000000))`, + output: `test$excessive_fields1(0x0)`, }, { input: `test$excessive_fields1(r0)`, @@ -206,6 +208,26 @@ func TestDeserialize(t *testing.T) { input: `test$excessive_fields1(&(0x7f0000000000)=0x0)`, output: `test$excessive_fields1(&(0x7f0000000000))`, }, + { + input: `test$excessive_fields1(0x0)`, + output: `test$excessive_fields1(0x0)`, + }, + { + input: `test$excessive_fields1(0xffffffffffffffff)`, + output: `test$excessive_fields1(0xffffffffffffffff)`, + }, + { + input: `test$excessive_fields1(0xfffffffffffffffe)`, + output: `test$excessive_fields1(0xfffffffffffffffe)`, + }, + { + input: `test$excessive_fields1(0xfffffffffffffffd)`, + output: `test$excessive_fields1(0x0)`, + }, + { + input: `test$excessive_fields1(0xfffffffffffffffc)`, + output: `test$excessive_fields1(0xffffffffffffffff)`, + }, } buf := make([]byte, ExecBufferSize) for _, test := range tests { @@ -276,8 +298,18 @@ func TestSerializeDeserializeRandom(t *testing.T) { }) ok, n0, n1 := testSerializeDeserialize(t, p0, data0, data1) if ok { - t.Fatal("flaky?") + t.Log("flaky?") + } + decoded0, err := target.DeserializeExec(data0[:n0]) + if err != nil { + t.Fatal(err) + } + decoded1, err := target.DeserializeExec(data1[:n1]) + if err != nil { + t.Fatal(err) } + diff := cmp.Diff(decoded0, decoded1) + t.Logf("decoded diff: %v", diff) t.Fatalf("was: %q\ngot: %q\nprogram:\n%s", data0[:n0], data1[:n1], p0.Serialize()) } diff --git a/prog/encodingexec.go b/prog/encodingexec.go index 659f4be3f..651ecef51 100644 --- a/prog/encodingexec.go +++ b/prog/encodingexec.go @@ -100,13 +100,6 @@ func (w *execContext) serializeCall(c *Call) { w.writeCopyout(c) } -func (target *Target) PhysicalAddr(arg *PointerArg) uint64 { - if arg.IsNull() { - return 0 - } - return target.DataOffset + arg.Address -} - type execContext struct { target *Target buf []byte diff --git a/prog/encodingexec_test.go b/prog/encodingexec_test.go index 94064c317..5a0e35750 100644 --- a/prog/encodingexec_test.go +++ b/prog/encodingexec_test.go @@ -403,6 +403,30 @@ func TestSerializeForExec(t *testing.T) { }, nil, }, + { + "test$excessive_fields1(0x0)", + []uint64{ + callID("test$excessive_fields1"), ExecNoCopyout, 1, execArgConst, ptrSize, 0x0, + execInstrEOF, + }, + nil, + }, + { + "test$excessive_fields1(0xffffffffffffffff)", + []uint64{ + callID("test$excessive_fields1"), ExecNoCopyout, 1, execArgConst, ptrSize, 0xffffffffffffffff, + execInstrEOF, + }, + nil, + }, + { + "test$excessive_fields1(0xfffffffffffffffe)", + []uint64{ + callID("test$excessive_fields1"), ExecNoCopyout, 1, execArgConst, ptrSize, 0x9999999999999999, + execInstrEOF, + }, + nil, + }, } buf := make([]byte, ExecBufferSize) diff --git a/prog/mutation.go b/prog/mutation.go index ee25fb14a..86cf487aa 100644 --- a/prog/mutation.go +++ b/prog/mutation.go @@ -308,6 +308,13 @@ func (t *ArrayType) mutate(r *randGen, s *state, arg Arg, ctx ArgCtx) (calls []* func (t *PtrType) mutate(r *randGen, s *state, arg Arg, ctx ArgCtx) (calls []*Call, retry, preserve bool) { a := arg.(*PointerArg) + if r.oneOf(1000) { + removeArg(a.Res) + index := r.rand(len(r.target.SpecialPointers)) + newArg := MakeSpecialPointerArg(t, index) + replaceArg(arg, newArg) + return + } newArg := r.allocAddr(s, t, a.Res.Size(), a.Res) replaceArg(arg, newArg) return @@ -401,7 +408,7 @@ func (ma *mutationArgs) collectArg(arg Arg, ctx *ArgCtx) { return // string const } case *PtrType: - if arg.(*PointerArg).IsNull() { + if arg.(*PointerArg).IsSpecial() { // TODO: we ought to mutate this, but we don't have code for this yet. return } diff --git a/prog/prog.go b/prog/prog.go index 8d0e0f525..b7304ba5d 100644 --- a/prog/prog.go +++ b/prog/prog.go @@ -106,9 +106,13 @@ func MakeVmaPointerArg(t Type, addr, size uint64) *PointerArg { } } -func MakeNullPointerArg(t Type) *PointerArg { +func MakeSpecialPointerArg(t Type, index uint64) *PointerArg { + if index >= maxSpecialPointers { + panic("bad special pointer index") + } return &PointerArg{ ArgCommon: ArgCommon{typ: t}, + Address: -index, } } @@ -116,8 +120,15 @@ func (arg *PointerArg) Size() uint64 { return arg.typ.Size() } -func (arg *PointerArg) IsNull() bool { - return arg.Address == 0 && arg.VmaSize == 0 && arg.Res == nil +func (arg *PointerArg) IsSpecial() bool { + return arg.VmaSize == 0 && arg.Res == nil && -arg.Address < maxSpecialPointers +} + +func (target *Target) PhysicalAddr(arg *PointerArg) uint64 { + if arg.IsSpecial() { + return target.SpecialPointers[-arg.Address] + } + return target.DataOffset + arg.Address } // Used for BufferType. @@ -262,17 +273,12 @@ func (arg *ResultArg) Size() uint64 { // Returns inner arg for pointer args. func InnerArg(arg Arg) Arg { - if t, ok := arg.Type().(*PtrType); ok { - if a, ok := arg.(*PointerArg); ok { - if a.Res == nil { - if !t.Optional() { - panic(fmt.Sprintf("non-optional pointer is nil\narg: %+v\ntype: %+v", a, t)) - } - return nil - } - return InnerArg(a.Res) + if _, ok := arg.Type().(*PtrType); ok { + res := arg.(*PointerArg).Res + if res == nil { + return nil } - return nil // *ConstArg. + return InnerArg(res) } return arg // Not a pointer. } diff --git a/prog/rand.go b/prog/rand.go index 7bded23c6..7f5597f82 100644 --- a/prog/rand.go +++ b/prog/rand.go @@ -515,7 +515,7 @@ func (r *randGen) generateArgImpl(s *state, typ Type, ignoreSpecial bool) (arg A } }() if r.recDepth[name] >= 3 { - return MakeNullPointerArg(typ), nil + return MakeSpecialPointerArg(typ, 0), nil } } } @@ -673,6 +673,10 @@ func (a *UnionType) generate(r *randGen, s *state) (arg Arg, calls []*Call) { } func (a *PtrType) generate(r *randGen, s *state) (arg Arg, calls []*Call) { + if r.oneOf(1000) { + index := r.rand(len(r.target.SpecialPointers)) + return MakeSpecialPointerArg(a, index), nil + } inner, calls := r.generateArg(s, a.Type) arg = r.allocAddr(s, a, inner.Size(), inner) return arg, calls diff --git a/prog/target.go b/prog/target.go index 80a2665ae..631b756e8 100644 --- a/prog/target.go +++ b/prog/target.go @@ -44,6 +44,9 @@ type Target struct { // Used as fallback when string type does not have own dictionary. StringDictionary []string + // Additional special invalid pointer values besides NULL to use. + SpecialPointers []uint64 + // Filled by prog package: init sync.Once initArch func(target *Target) @@ -55,6 +58,8 @@ type Target struct { any anyTypes } +const maxSpecialPointers = 16 + var targets = make(map[string]*Target) func RegisterTarget(target *Target, initArch func(target *Target)) { @@ -101,6 +106,15 @@ func (target *Target) lazyInit() { target.initTarget() target.initArch(target) target.ConstMap = nil // currently used only by initArch + // Give these 2 known addresses fixed positions and prepend target-specific ones at the end. + target.SpecialPointers = append([]uint64{ + 0x0000000000000000, // NULL pointer (keep this first because code uses special index=0 as NULL) + 0xffffffffffffffff, // unmapped kernel address (keep second because serialized value will match actual pointer value) + 0x9999999999999999, // non-canonical address + }, target.SpecialPointers...) + if len(target.SpecialPointers) > maxSpecialPointers { + panic("too many special pointers") + } } func (target *Target) initTarget() { diff --git a/prog/types.go b/prog/types.go index 68c80e23c..3bb2fdbb4 100644 --- a/prog/types.go +++ b/prog/types.go @@ -321,11 +321,12 @@ func (t *VmaType) String() string { } func (t *VmaType) makeDefaultArg() Arg { - return MakeNullPointerArg(t) + return MakeSpecialPointerArg(t, 0) } func (t *VmaType) isDefaultArg(arg Arg) bool { - return arg.(*PointerArg).IsNull() + a := arg.(*PointerArg) + return a.IsSpecial() && a.Address == 0 } type BufferKind int @@ -450,7 +451,7 @@ func (t *PtrType) String() string { func (t *PtrType) makeDefaultArg() Arg { if t.Optional() { - return MakeNullPointerArg(t) + return MakeSpecialPointerArg(t, 0) } return MakePointerArg(t, 0, t.Type.makeDefaultArg()) } @@ -458,9 +459,9 @@ func (t *PtrType) makeDefaultArg() Arg { func (t *PtrType) isDefaultArg(arg Arg) bool { a := arg.(*PointerArg) if t.Optional() { - return a.IsNull() + return a.IsSpecial() && a.Address == 0 } - return a.Address == 0 && isDefault(a.Res) + return a.Address == 0 && a.Res != nil && isDefault(a.Res) } type StructType struct { diff --git a/prog/validation.go b/prog/validation.go index eaffac9b8..632f84509 100644 --- a/prog/validation.go +++ b/prog/validation.go @@ -241,9 +241,6 @@ func (arg *PointerArg) validate(ctx *validCtx) error { return fmt.Errorf("vma arg '%v' has data", typ.Name()) } case *PtrType: - if arg.Res == nil && !arg.Type().Optional() { - return fmt.Errorf("non optional pointer arg '%v' is nil", typ.Name()) - } if arg.Res != nil { if err := ctx.validateArg(arg.Res, typ.Type); err != nil { return err @@ -258,14 +255,20 @@ func (arg *PointerArg) validate(ctx *validCtx) error { default: return fmt.Errorf("ptr arg %v has bad type %v", arg, typ.Name()) } - maxMem := ctx.target.NumPages * ctx.target.PageSize - size := arg.VmaSize - if size == 0 && arg.Res != nil { - size = arg.Res.Size() - } - if arg.Address >= maxMem || arg.Address+size > maxMem { - return fmt.Errorf("ptr %v has bad address %v/%v/%v", - arg.Type().Name(), arg.Address, arg.VmaSize, size) + if arg.IsSpecial() { + if -arg.Address >= uint64(len(ctx.target.SpecialPointers)) { + return fmt.Errorf("special ptr arg %v has bad value 0x%x", arg.Type().Name(), arg.Address) + } + } else { + maxMem := ctx.target.NumPages * ctx.target.PageSize + size := arg.VmaSize + if size == 0 && arg.Res != nil { + size = arg.Res.Size() + } + if arg.Address >= maxMem || arg.Address+size > maxMem { + return fmt.Errorf("ptr %v has bad address %v/%v/%v", + arg.Type().Name(), arg.Address, arg.VmaSize, size) + } } return nil } -- cgit mrf-deployment