From 68f80dec7aa2d7c4ae909b4b3eb0953bc3990701 Mon Sep 17 00:00:00 2001 From: Aleksandr Nogikh Date: Mon, 13 Feb 2023 20:36:16 +0100 Subject: prog: add a new DupCallCollide collide type It duplicates random calls in a program and makes the duplicated copies async. E.g. it could transform r0 = test() test2(r0) to r0 = test() test2(r0) (async) test2(r0) or test() (async) r0 = test() test2(r0) --- prog/clone.go | 26 +++++++++++++---------- prog/collide.go | 40 +++++++++++++++++++++++++++++++++++ prog/collide_test.go | 60 ++++++++++++++++++++++++++++++++++++++++++++++++++++ syz-fuzzer/proc.go | 11 ++++++++-- 4 files changed, 124 insertions(+), 13 deletions(-) diff --git a/prog/clone.go b/prog/clone.go index 9fa660e67..029cf94c4 100644 --- a/prog/clone.go +++ b/prog/clone.go @@ -20,21 +20,25 @@ func (p *Prog) Clone() *Prog { func cloneCalls(origCalls []*Call, newargs map[*ResultArg]*ResultArg) []*Call { calls := make([]*Call, len(origCalls)) for ci, c := range origCalls { - c1 := new(Call) - c1.Meta = c.Meta - if c.Ret != nil { - c1.Ret = clone(c.Ret, newargs).(*ResultArg) - } - c1.Args = make([]Arg, len(c.Args)) - for ai, arg := range c.Args { - c1.Args[ai] = clone(arg, newargs) - } - c1.Props = c.Props - calls[ci] = c1 + calls[ci] = cloneCall(c, newargs) } return calls } +func cloneCall(c *Call, newargs map[*ResultArg]*ResultArg) *Call { + c1 := new(Call) + c1.Meta = c.Meta + if c.Ret != nil { + c1.Ret = clone(c.Ret, newargs).(*ResultArg) + } + c1.Args = make([]Arg, len(c.Args)) + for ai, arg := range c.Args { + c1.Args[ai] = clone(arg, newargs) + } + c1.Props = c.Props + return c1 +} + func clone(arg Arg, newargs map[*ResultArg]*ResultArg) Arg { var arg1 Arg switch a := arg.(type) { diff --git a/prog/collide.go b/prog/collide.go index fea8cc146..67cca6ecb 100644 --- a/prog/collide.go +++ b/prog/collide.go @@ -97,3 +97,43 @@ func DoubleExecCollide(origProg *Prog, rand *rand.Rand) (*Prog, error) { prog.Calls = append(prog.Calls, dupCalls...) return prog, nil } + +// DupCallCollide duplicates some of the calls in the program and marks them async. +// This should hopefully trigger races in a more granular way than DoubleExecCollide. +func DupCallCollide(origProg *Prog, rand *rand.Rand) (*Prog, error) { + if len(origProg.Calls) < 2 { + // For 1-call programs the behavior is similar to DoubleExecCollide. + return nil, fmt.Errorf("the prog is too small for the transformation") + } + // By default let's duplicate 1/3 calls in the original program. + insert := len(origProg.Calls) / 3 + if insert == 0 { + // .. but always at least one. + insert = 1 + } + if insert > maxAsyncPerProg { + insert = maxAsyncPerProg + } + if insert+len(origProg.Calls) > MaxCalls { + insert = MaxCalls - len(origProg.Calls) + } + if insert == 0 { + return nil, fmt.Errorf("no calls could be duplicated") + } + duplicate := map[int]bool{} + for _, pos := range rand.Perm(len(origProg.Calls))[:insert] { + duplicate[pos] = true + } + prog := origProg.Clone() + var retCalls []*Call + for i, c := range prog.Calls { + if duplicate[i] { + dupCall := cloneCall(c, nil) + dupCall.Props.Async = true + retCalls = append(retCalls, dupCall) + } + retCalls = append(retCalls, c) + } + prog.Calls = retCalls + return prog, nil +} diff --git a/prog/collide_test.go b/prog/collide_test.go index 269b541ff..0e29777a7 100644 --- a/prog/collide_test.go +++ b/prog/collide_test.go @@ -6,6 +6,8 @@ package prog import ( "math/rand" "testing" + + "github.com/stretchr/testify/assert" ) func TestAssignRandomAsync(t *testing.T) { @@ -148,3 +150,61 @@ dup(r3) } } } + +func TestDupCallCollide(t *testing.T) { + tests := []struct { + os string + arch string + orig string + rets []string + }{ + { + "linux", "amd64", + `r0 = openat(0xffffffffffffff9c, &AUTO='./file1\x00', 0x42, 0x1ff) +r1 = dup(r0) +r2 = dup(r1) +dup(r2) +`, + []string{ + `r0 = openat(0xffffffffffffff9c, &(0x7f0000000040)='./file1\x00', 0x42, 0x1ff) +dup(r0) (async) +r1 = dup(r0) +r2 = dup(r1) +dup(r2) +`, + `r0 = openat(0xffffffffffffff9c, &(0x7f0000000040)='./file1\x00', 0x42, 0x1ff) +r1 = dup(r0) +r2 = dup(r1) +dup(r2) (async) +dup(r2) +`, + }, + }, + } + _, rs, iters := initTest(t) + if iters > 100 { + // Let's save resources -- we don't need that many for these small tests. + iters = 100 + } + r := rand.New(rs) + for _, test := range tests { + target, err := GetTarget(test.os, test.arch) + if err != nil { + t.Fatal(err) + } + p, err := target.Deserialize([]byte(test.orig), Strict) + if err != nil { + t.Fatal(err) + } + detected := map[string]struct{}{} + for i := 0; i < iters; i++ { + collided, err := DupCallCollide(p, r) + assert.NoError(t, err) + detected[string(collided.Serialize())] = struct{}{} + } + for _, variant := range test.rets { + _, exists := detected[variant] + assert.True(t, exists) + } + } +} diff --git a/syz-fuzzer/proc.go b/syz-fuzzer/proc.go index a215d81c8..00d8cec1e 100644 --- a/syz-fuzzer/proc.go +++ b/syz-fuzzer/proc.go @@ -294,13 +294,20 @@ func (proc *Proc) executeAndCollide(execOpts *ipc.ExecOpts, p *prog.Prog, flags } func (proc *Proc) randomCollide(origP *prog.Prog) *prog.Prog { - // Old-styl collide with a 33% probability. - if proc.rnd.Intn(3) == 0 { + if proc.rnd.Intn(5) == 0 { + // Old-style collide with a 20% probability. p, err := prog.DoubleExecCollide(origP, proc.rnd) if err == nil { return p } } + if proc.rnd.Intn(4) == 0 { + // Duplicate random calls with a 20% probability (25% * 80%). + p, err := prog.DupCallCollide(origP, proc.rnd) + if err == nil { + return p + } + } p := prog.AssignRandomAsync(origP, proc.rnd) if proc.rnd.Intn(2) != 0 { prog.AssignRandomRerun(p, proc.rnd) -- cgit mrf-deployment