diff options
| -rw-r--r-- | pkg/hash/hash.go | 6 | ||||
| -rw-r--r-- | prog/analysis.go | 20 | ||||
| -rw-r--r-- | prog/hints.go | 27 | ||||
| -rw-r--r-- | prog/hints_test.go | 102 | ||||
| -rw-r--r-- | prog/rand.go | 9 | ||||
| -rw-r--r-- | prog/target.go | 112 | ||||
| -rw-r--r-- | prog/types.go | 70 | ||||
| -rw-r--r-- | sys/test/related.txt | 32 |
8 files changed, 343 insertions, 35 deletions
diff --git a/pkg/hash/hash.go b/pkg/hash/hash.go index 246fc4b2f..5b325fa34 100644 --- a/pkg/hash/hash.go +++ b/pkg/hash/hash.go @@ -13,17 +13,17 @@ import ( type Sig [sha1.Size]byte -func Hash(pieces ...[]byte) Sig { +func Hash(pieces ...any) Sig { h := sha1.New() for _, data := range pieces { - h.Write(data) + binary.Write(h, binary.LittleEndian, data) } var sig Sig copy(sig[:], h.Sum(nil)) return sig } -func String(pieces ...[]byte) string { +func String(pieces ...any) string { sig := Hash(pieces...) return sig.String() } diff --git a/prog/analysis.go b/prog/analysis.go index 458b9455c..087a2b3dc 100644 --- a/prog/analysis.go +++ b/prog/analysis.go @@ -125,6 +125,7 @@ func popStack(ps parentStack) (parentStack, Arg) { type ArgCtx struct { Parent *[]Arg // GroupArg.Inner (for structs) or Call.Args containing this arg. Fields []Field // Fields of the parent struct/syscall. + Field *Field // Syscall field for this arg, nil if there it's not a field. 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. @@ -132,26 +133,26 @@ type ArgCtx struct { } func ForeachSubArg(arg Arg, f func(Arg, *ArgCtx)) { - foreachArgImpl(arg, &ArgCtx{}, f) + foreachArgImpl(arg, nil, &ArgCtx{}, f) } func foreachSubArgWithStack(arg Arg, f func(Arg, *ArgCtx)) { - foreachArgImpl(arg, &ArgCtx{parentStack: allocStack()}, f) + foreachArgImpl(arg, nil, &ArgCtx{parentStack: allocStack()}, f) } func ForeachArg(c *Call, f func(Arg, *ArgCtx)) { ctx := &ArgCtx{} if c.Ret != nil { - foreachArgImpl(c.Ret, ctx, f) + foreachArgImpl(c.Ret, nil, ctx, f) } ctx.Parent = &c.Args ctx.Fields = c.Meta.Args - for _, arg := range c.Args { - foreachArgImpl(arg, ctx, f) + for i, arg := range c.Args { + foreachArgImpl(arg, &ctx.Fields[i], ctx, f) } } -func foreachArgImpl(arg Arg, ctx *ArgCtx, f func(Arg, *ArgCtx)) { +func foreachArgImpl(arg Arg, field *Field, ctx *ArgCtx, f func(Arg, *ArgCtx)) { ctx0 := *ctx defer func() { *ctx = ctx0 }() @@ -161,6 +162,7 @@ func foreachArgImpl(arg Arg, ctx *ArgCtx, f func(Arg, *ArgCtx)) { ctx.parentStack = pushStack(ctx.parentStack, arg) } } + ctx.Field = field f(arg, ctx) if ctx.Stop { return @@ -178,7 +180,7 @@ func foreachArgImpl(arg Arg, ctx *ArgCtx, f func(Arg, *ArgCtx)) { if i == overlayField { ctx.Offset = ctx0.Offset } - foreachArgImpl(arg1, ctx, f) + foreachArgImpl(arg1, nil, ctx, f) size := arg1.Size() ctx.Offset += size if totalSize < ctx.Offset { @@ -197,10 +199,10 @@ func foreachArgImpl(arg Arg, ctx *ArgCtx, f func(Arg, *ArgCtx)) { if a.Res != nil { ctx.Base = a ctx.Offset = 0 - foreachArgImpl(a.Res, ctx, f) + foreachArgImpl(a.Res, nil, ctx, f) } case *UnionArg: - foreachArgImpl(a.Option, ctx, f) + foreachArgImpl(a.Option, nil, ctx, f) } } diff --git a/prog/hints.go b/prog/hints.go index 1dca452db..c2d5cd1e1 100644 --- a/prog/hints.go +++ b/prog/hints.go @@ -108,11 +108,11 @@ func (p *Prog) MutateWithHints(callIndex int, comps CompMap, exec func(p *Prog) ctx.Stop = true return } - generateHints(comps, arg, execValidate) + generateHints(comps, arg, ctx.Field, execValidate) }) } -func generateHints(compMap CompMap, arg Arg, exec func() bool) { +func generateHints(compMap CompMap, arg Arg, field *Field, exec func() bool) { typ := arg.Type() if typ == nil || arg.Dir() == DirOut { return @@ -146,8 +146,17 @@ func generateHints(compMap CompMap, arg Arg, exec func() bool) { switch a := arg.(type) { case *ConstArg: - checkConstArg(a, compMap, exec) + if arg.Type().TypeBitSize() <= 8 { + // Very small arg, hopefully we can guess it w/o hints help. + return + } + checkConstArg(a, field, compMap, exec) case *DataArg: + if arg.Size() <= 3 { + // Let's assume it either does not contain anything interesting, + // or we can guess everything eventually by brute force. + return + } if typ.(*BufferType).Kind == BufferCompressed { checkCompressedArg(a, compMap, exec) } else { @@ -156,11 +165,21 @@ func generateHints(compMap CompMap, arg Arg, exec func() bool) { } } -func checkConstArg(arg *ConstArg, compMap CompMap, exec func() bool) { +func checkConstArg(arg *ConstArg, field *Field, compMap CompMap, exec func() bool) { original := arg.Val // Note: because shrinkExpand returns a map, order of programs is non-deterministic. // This can affect test coverage reports. +replacerLoop: for _, replacer := range shrinkExpand(original, compMap, arg.Type().TypeBitSize(), false) { + if field != nil && len(field.relatedFields) != 0 { + for related := range field.relatedFields { + if related.(uselessHinter).uselessHint(replacer) { + continue replacerLoop + } + } + } else if arg.Type().(uselessHinter).uselessHint(replacer) { + continue + } arg.Val = replacer if !exec() { break diff --git a/prog/hints_test.go b/prog/hints_test.go index 8b15ae473..d5a5a1461 100644 --- a/prog/hints_test.go +++ b/prog/hints_test.go @@ -9,6 +9,7 @@ import ( "math/rand" "reflect" "sort" + "strings" "testing" "github.com/google/go-cmp/cmp" @@ -50,16 +51,16 @@ func TestHintsCheckConstArg(t *testing.T) { name: "multiple-replacers-test", in: 0xabcd, size: 2, - comps: CompMap{0xabcd: compSet(0x2, 0x3)}, - res: []uint64{0x2, 0x3}, + comps: CompMap{0xabcd: compSet(0x32, 0x33)}, + res: []uint64{0x32, 0x33}, }, // Checks that special ints are not used. { name: "special-ints-test", in: 0xabcd, size: 2, - comps: CompMap{0xabcd: compSet(0x1, 0x2)}, - res: []uint64{0x2}, + comps: CompMap{0xabcd: compSet(0x1, 0x2, 0x42)}, + res: []uint64{0x42}, }, // The following tests check the size limits for each replacer and for the initial value @@ -125,7 +126,7 @@ func TestHintsCheckConstArg(t *testing.T) { 0xffffffffffffffab: compSet(0x12, 0xffffffffffffff0a), 0xfffffffffffff8ab: compSet(0x13, 0xffffffffffffff00), }, - res: []uint64{0x11, 0x13, 0x80a, 0x812, 0xf00}, + res: []uint64{0x11, 0x13, 0x812, 0xf00}, }, { name: "int16-negative-invalid-value-bitsize-12", @@ -165,7 +166,7 @@ func TestHintsCheckConstArg(t *testing.T) { var res []uint64 typ := types[fmt.Sprintf("int%v_%v", test.size, test.bitsize)] constArg := MakeConstArg(typ, DirIn, test.in) - checkConstArg(constArg, test.comps, func() bool { + checkConstArg(constArg, nil, test.comps, func() bool { res = append(res, constArg.Val) return true }) @@ -198,19 +199,19 @@ func TestHintsCheckDataArg(t *testing.T) { // Checks that for every such operand a program is generated. { "multiple-replacers-test", - "\xcd\xab", - CompMap{0xabcd: compSet(0x2, 0x3)}, + "\xcd\xab\x42\x42", + CompMap{0xabcd: compSet(0x44, 0x45)}, map[string]bool{ - "\x02\x00": true, "\x03\x00": true, + "\x44\x00\x42\x42": true, "\x45\x00\x42\x42": true, }, }, // Checks that special ints are not used. { "special-ints-test", - "\xcd\xab", - CompMap{0xabcd: compSet(0x1, 0x2)}, + "\xcd\xab\x42\x42", + CompMap{0xabcd: compSet(0x1, 0x45)}, map[string]bool{ - "\x02\x00": true, + "\x45\x00\x42\x42": true, }, }, // Checks that ints of various sizes are extracted. @@ -393,7 +394,7 @@ func TestHintsCompressedImage(t *testing.T) { t.Run(fmt.Sprintf("%v", i), func(t *testing.T) { var res []string arg := MakeDataArg(typ, DirIn, image.Compress([]byte(test.input))) - generateHints(test.comps, arg, func() bool { + generateHints(test.comps, arg, nil, func() bool { res = append(res, string(arg.Data())) return true }) @@ -576,6 +577,77 @@ func TestHintsShrinkExpand(t *testing.T) { } } +func TestHintsCall(t *testing.T) { + target := initTargetTest(t, "test", "64") + type Test struct { + in string + comps CompMap + out []string + } + tests := []Test{ + { + in: `ioctl$1(0x0, 0x111, 0x0)`, + comps: CompMap{0x111: compSet(0x0, 0x111, 0x222, 0x333, 0x444, 0x666)}, + out: []string{ + `ioctl$1(0x0, 0x666, 0x0)`, + }, + }, + { + // For the generic syscall mutations should not be restricted by related calls. + // But we won't have 0x1000 and 0x10000 because they are special ints. + in: `socket$generic(0x1, 0x2, 0x3)`, + comps: CompMap{ + 0x1: compSet(0x111, 0x333), + 0x2: compSet(0x1000, 0x1100, 0x1200), + 0x3: compSet(0x10000, 0x10100, 0x10200), + }, + out: []string{ + `socket$generic(0x333, 0x2, 0x3)`, + }, + }, + { + in: `socket$inet6(0x111, 0x222, 0x333)`, + comps: CompMap{ + 0x111: compSet(0x211), + 0x222: compSet(0x1100, 0x1200, 0x1300), + 0x333: compSet(0x10000, 0x10100, 0x10200, 0x10300), + }, + out: []string{ + `socket$inet6(0x111, 0x222, 0x10100)`, + `socket$inet6(0x111, 0x222, 0x10200)`, + `socket$inet6(0x111, 0x222, 0x10300)`, + }, + }, + { + in: `socket$netlink(0x111, 0x222, 0x333)`, + comps: CompMap{ + 0x111: compSet(0x211), + 0x222: compSet(0x1100, 0x1200, 0x1300), + 0x333: compSet(0x10000, 0x10100, 0x10200, 0x10300), + }, + out: []string{ + `socket$netlink(0x111, 0x1100, 0x333)`, + `socket$netlink(0x111, 0x1200, 0x333)`, + `socket$netlink(0x111, 0x1300, 0x333)`, + }, + }, + } + for i, test := range tests { + t.Run(fmt.Sprint(i), func(t *testing.T) { + p, err := target.Deserialize([]byte(test.in), Strict) + if err != nil { + t.Fatal(err) + } + var got []string + p.MutateWithHints(0, test.comps, func(newP *Prog) bool { + got = append(got, strings.TrimSpace(string(newP.Serialize()))) + return true + }) + assert.ElementsMatch(t, test.out, got) + }) + } +} + func TestHintsRandom(t *testing.T) { target, rs, iters := initTest(t) ct := target.DefaultChoiceTable() @@ -643,8 +715,8 @@ func TestHintsData(t *testing.T) { tests := []Test{ { in: "0809101112131415", - comps: CompMap{0x12111009: compSet(0x10)}, - out: []string{"0810000000131415"}, + comps: CompMap{0x12111009: compSet(0x42)}, + out: []string{"0842000000131415"}, }, } for _, test := range tests { diff --git a/prog/rand.go b/prog/rand.go index c55d43a3f..b15871b8a 100644 --- a/prog/rand.go +++ b/prog/rand.go @@ -66,8 +66,8 @@ func (r *randGen) rand64() uint64 { var ( // Some potentially interesting integers. specialInts = []uint64{ - 0, 1, 31, 32, 63, 64, 127, 128, - 129, 255, 256, 257, 511, 512, + 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, + 64, 127, 128, 129, 255, 256, 257, 511, 512, 1023, 1024, 1025, 2047, 2048, 4095, 4096, (1 << 15) - 1, (1 << 15), (1 << 15) + 1, (1 << 16) - 1, (1 << 16), (1 << 16) + 1, @@ -153,11 +153,12 @@ func (r *randGen) biasedRand(n, k int) int { return int(bf) } +const maxArrayLen = 10 + func (r *randGen) randArrayLen() uint64 { - const maxLen = 10 // biasedRand produces: 10, 9, ..., 1, 0, // we want: 1, 2, ..., 9, 10, 0 - return uint64(maxLen-r.biasedRand(maxLen+1, 10)+1) % (maxLen + 1) + return uint64(maxArrayLen-r.biasedRand(maxArrayLen+1, 10)+1) % (maxArrayLen + 1) } func (r *randGen) randBufLen() (n uint64) { diff --git a/prog/target.go b/prog/target.go index d32d8a8ae..50fcecdbc 100644 --- a/prog/target.go +++ b/prog/target.go @@ -6,10 +6,13 @@ package prog import ( "fmt" "math/rand" + "slices" "sort" "strings" "sync" "sync/atomic" + + "github.com/google/syzkaller/pkg/hash" ) // Target describes target OS/arch pair. @@ -130,6 +133,8 @@ func (target *Target) lazyInit() { target.Neutralize = func(c *Call, fixStructure bool) error { return nil } target.AnnotateCall = func(c ExecCall) string { return "" } target.initTarget() + target.initUselessHints() + target.initRelatedFields() target.initArch(target) // Give these 2 known addresses fixed positions and prepend target-specific ones at the end. target.SpecialPointers = append([]uint64{ @@ -181,6 +186,113 @@ func (target *Target) initTarget() { } } +func (target *Target) initUselessHints() { + // Pre-compute useless hints for each type and deduplicate resulting maps + // (there will be lots of duplicates). + computed := make(map[Type]bool) + dedup := make(map[string]map[uint64]struct{}) + ForeachType(target.Syscalls, func(t Type, ctx *TypeCtx) { + hinter, ok := t.(uselessHinter) + if !ok || computed[t] { + return + } + computed[t] = true + hints := hinter.calcUselessHints() + if len(hints) == 0 { + return + } + slices.Sort(hints) + hints = slices.Compact(hints) + sig := hash.String(hints) + m := dedup[sig] + if m == nil { + m = make(map[uint64]struct{}) + for _, v := range hints { + m[v] = struct{}{} + } + dedup[sig] = m + } + hinter.setUselessHints(m) + }) +} + +func (target *Target) initRelatedFields() { + // Compute sets of related fields that are used to reduce amount of produced hint replacements. + // Related fields are sets of arguments to the same syscall, in the same position, that operate + // on the same resource. The best example of related fields is a set of ioctl commands on the same fd: + // + // ioctl$FOO1(fd fd_foo, cmd const[FOO1], ...) + // ioctl$FOO2(fd fd_foo, cmd const[FOO2], ...) + // ioctl$FOO3(fd fd_foo, cmd const[FOO3], ...) + // + // All cmd args related and we should not try to replace them with each other + // (e.g. try to morph ioctl$FOO1 into ioctl$FOO2). This is both unnecessary, leads to confusing reproducers, + // and in some cases to badly confused argument types, see e.g.: + // https://github.com/google/syzkaller/issues/502 + // https://github.com/google/syzkaller/issues/4939 + // + // However, notion of related fields is wider and includes e.g. socket syscall family/type/proto, + // setsockopt consts, and in some cases even openat flags/mode. + // + // Related fields can include const, flags and int types. + // + // Notion of "same resource" is also quite generic b/c syscalls can accept several resource types, + // and filenames/strings are also considered as a resource in this context. For example, openat syscalls + // that operate on the same file are related, but are not related to openat calls that operate on other files. + groups := make(map[string]map[Type]struct{}) + for _, call := range target.Syscalls { + // Id is used to identify related syscalls. + // We first collect all resources/strings/files. This needs to be done first b/c e.g. mmap has + // fd resource at the end, so we need to do this before the next loop. + id := call.CallName + for i, field := range call.Args { + switch arg := field.Type.(type) { + case *ResourceType: + id += fmt.Sprintf("-%v:%v", i, arg.Name()) + case *PtrType: + if typ, ok := arg.Elem.(*BufferType); ok && typ.Kind == BufferString && len(typ.Values) == 1 { + id += fmt.Sprintf("-%v:%v", i, typ.Values[0]) + } + } + } + // Now we group const/flags args together. + // But also if we see a const, we update id to include it. This is required for e.g. + // socket/socketpair/setsockopt calls. For these calls all families can be groups, but types should be + // grouped only for the same family, and protocols should be grouped only for the same family+type. + // We assume the "more important" discriminating arguments come first (this is not necessary true, + // but seems to be the case in real syscalls as it's unreasonable to pass less important things first). + for i, field := range call.Args { + switch field.Type.(type) { + case *ConstType: + case *FlagsType: + case *IntType: + default: + continue + } + argID := fmt.Sprintf("%v/%v", id, i) + group := groups[argID] + if group == nil { + group = make(map[Type]struct{}) + groups[argID] = group + } + call.Args[i].relatedFields = group + group[field.Type] = struct{}{} + switch arg := field.Type.(type) { + case *ConstType: + id += fmt.Sprintf("-%v:%v", i, arg.Val) + } + } + } + // Drop groups that consist of only a single field as they are not useful. + for _, call := range target.Syscalls { + for i := range call.Args { + if len(call.Args[i].relatedFields) == 1 { + call.Args[i].relatedFields = nil + } + } + } +} + func (target *Target) GetConst(name string) uint64 { v, ok := target.ConstMap[name] if !ok { diff --git a/prog/types.go b/prog/types.go index 1e2f4dcd4..50588cb19 100644 --- a/prog/types.go +++ b/prog/types.go @@ -78,6 +78,9 @@ type Field struct { HasDirection bool Direction Dir Condition Expression + + // See Target.initRelatedFields. + relatedFields map[Type]struct{} } func (f *Field) Dir(def Dir) Dir { @@ -365,6 +368,11 @@ type IntTypeCommon struct { BitfieldLen uint64 BitfieldUnit uint64 BitfieldUnitOff uint64 + + // Hint values that don't make sense to use for this type + // b/c they are expected to be easily guessed by generation/mutation. + // For example, flags values or combinations of few flags values. + uselessHints map[uint64]struct{} } func (t *IntTypeCommon) String() string { @@ -411,6 +419,21 @@ func (t *IntTypeCommon) IsBitfield() bool { return t.BitfieldLen != 0 } +func (t *IntTypeCommon) uselessHint(v uint64) bool { + _, ok := t.uselessHints[v] + return ok +} + +func (t *IntTypeCommon) setUselessHints(m map[uint64]struct{}) { + t.uselessHints = m +} + +type uselessHinter interface { + uselessHint(uint64) bool + calcUselessHints() []uint64 + setUselessHints(map[uint64]struct{}) +} + type ConstType struct { IntTypeCommon Val uint64 @@ -432,6 +455,10 @@ func (t *ConstType) String() string { return fmt.Sprintf("const[%v, %v]", t.Val, t.IntTypeCommon.String()) } +func (t *ConstType) calcUselessHints() []uint64 { + return []uint64{t.Val} +} + type IntKind int const ( @@ -455,6 +482,18 @@ func (t *IntType) isDefaultArg(arg Arg) bool { return arg.(*ConstArg).Val == 0 } +func (t *IntType) calcUselessHints() []uint64 { + res := specialInts[:len(specialInts):len(specialInts)] + align := max(1, t.Align) + rangeVals := (t.RangeEnd - t.RangeBegin) / align + if rangeVals != 0 && rangeVals <= 100 { + for v := t.RangeBegin; v <= t.RangeEnd; v += align { + res = append(res, v) + } + } + return res +} + type FlagsType struct { IntTypeCommon Vals []uint64 // compiler ensures that it's not empty @@ -469,6 +508,29 @@ func (t *FlagsType) isDefaultArg(arg Arg) bool { return arg.(*ConstArg).Val == 0 } +func (t *FlagsType) calcUselessHints() []uint64 { + // Combinations of up to 3 flag values + 0. + res := []uint64{0} + vals := t.Vals + for i0 := 0; i0 < len(vals); i0++ { + v0 := vals[i0] + res = append(res, v0) + if len(vals) <= 10 { + for i1 := i0 + 1; i1 < len(vals); i1++ { + v1 := v0 | vals[i1] + res = append(res, v1) + if len(vals) <= 7 { + for i2 := i1 + 1; i2 < len(vals); i2++ { + v2 := v1 | vals[i2] + res = append(res, v2) + } + } + } + } + } + return res +} + type LenType struct { IntTypeCommon BitSize uint64 // want size in multiple of bits instead of array size @@ -484,6 +546,14 @@ func (t *LenType) isDefaultArg(arg Arg) bool { return arg.(*ConstArg).Val == 0 } +func (t *LenType) calcUselessHints() []uint64 { + return nil +} + +func (t *LenType) uselessHint(v uint64) bool { + return v <= maxArrayLen || v > 1<<20 +} + type ProcType struct { IntTypeCommon ValuesStart uint64 diff --git a/sys/test/related.txt b/sys/test/related.txt new file mode 100644 index 000000000..4d0dfebb1 --- /dev/null +++ b/sys/test/related.txt @@ -0,0 +1,32 @@ +# Copyright 2024 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. + +ioctl(fd fd, cmd int32, arg intptr) +ioctl$1(fd fd, cmd const[0x111], arg intptr) +ioctl$2(fd fd, cmd const[0x222], arg intptr) +ioctl$4(fd fd, cmd flags[ioctl_commands], arg intptr) + +ioctl_commands = 0x333, 0x444 + +resource sock[fd] + +socket(domain flags[socket_domain], type flags[socket_type], protocol flags[socket_protocol]) sock +socket$generic(domain int32, type int32, protocol int32) sock +socket$inet6(domain const[0x111], type flags[socket_type], protocol const[0x10000]) sock +socket$inet6_tcp(domain const[0x111], type const[0x1000], protocol const[0x10000]) sock +socket$netlink(domain const[0x211], type const[0x1000], protocol flags[socket_protocol]) sock +socket$netlink2(domain const[0x211], type const[0x1000], protocol int32) sock +socket$netlink_foo(domain const[0x211], type const[0x1000], protocol const[0x10200]) sock +socket$foo(domain const[0x311], type const[0x1000], protocol const[0x10200]) sock +socket$foo2(domain const[0x311], type flags[socket_type], protocol const[0x10200]) sock +socket$foo3(domain const[0x311], type int32, protocol const[0x10200]) sock +socket$foo4(domain const[0x411], type int32, protocol const[0x10000]) sock +socket$foo5(domain const[0x411], type int32, protocol int32) sock +socket$foo6(domain int32, type int32, protocol int32) sock +socket$foo7(domain int32, type int32, protocol int32) sock + +listen(fd sock) + +socket_domain = 0x111, 0x211, 0x311 +socket_type = 0x1000, 0x1100, 0x1200 +socket_protocol = 0x10000, 0x10100, 0x10200 |
