From 18ea8213dd4178e6671728ec06cbed72cc06b41d Mon Sep 17 00:00:00 2001 From: Aleksandr Nogikh Date: Fri, 5 Apr 2024 14:38:08 +0200 Subject: pkg/fuzzer: make deflake() more flexible Demand that at least 3 out of 5 runs share common signal. Exit early if it's not feasible. --- pkg/fuzzer/fuzzer_test.go | 6 +-- pkg/fuzzer/job.go | 55 +++++++++++++++------------ pkg/fuzzer/job_test.go | 94 +++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 129 insertions(+), 26 deletions(-) create mode 100644 pkg/fuzzer/job_test.go (limited to 'pkg') diff --git a/pkg/fuzzer/fuzzer_test.go b/pkg/fuzzer/fuzzer_test.go index 5c0920109..a43629c06 100644 --- a/pkg/fuzzer/fuzzer_test.go +++ b/pkg/fuzzer/fuzzer_test.go @@ -117,6 +117,8 @@ func BenchmarkFuzzer(b *testing.B) { }) } +const anyTestProg = `syz_compare(&AUTO="00000000", 0x4, &AUTO=@conditional={0x0, @void, @void}, AUTO)` + func TestRotate(t *testing.T) { target, err := prog.GetTarget(targets.TestOS, targets.TestArch64Fuzz) if err != nil { @@ -144,9 +146,7 @@ func TestRotate(t *testing.T) { return signal.FromRaw(pc, 0) } - prog, err := target.Deserialize( - []byte(`syz_compare(&AUTO="00000000", 0x4, &AUTO=@conditional={0x0, @void, @void}, AUTO)`), - prog.NonStrict) + prog, err := target.Deserialize([]byte(anyTestProg), prog.NonStrict) assert.NoError(t, err) corpusObj.Save(corpus.NewInput{ Prog: prog, diff --git a/pkg/fuzzer/job.go b/pkg/fuzzer/job.go index b5c8b9f32..e287b9599 100644 --- a/pkg/fuzzer/job.go +++ b/pkg/fuzzer/job.go @@ -134,7 +134,7 @@ func (job *triageJob) run(fuzzer *Fuzzer) { callName := fmt.Sprintf("call #%v %v", job.call, job.p.CallName(job.call)) fuzzer.Logf(3, "triaging input for %v (new signal=%v)", callName, job.newSignal.Len()) // Compute input coverage and non-flaky signal for minimization. - info, stop := job.deflake(fuzzer) + info, stop := job.deflake(fuzzer.exec, fuzzer.Config.FetchRawCover) if stop || info.newStableSignal.Empty() { return } @@ -171,15 +171,31 @@ type deflakedCover struct { rawCover []uint32 } -func (job *triageJob) deflake(fuzzer *Fuzzer) (info deflakedCover, stop bool) { - const signalRuns = 3 - var notExecuted int - for i := 0; i < signalRuns; i++ { - result := fuzzer.exec(job, &Request{ +func (job *triageJob) deflake(exec func(job, *Request) *Result, rawCover bool) (info deflakedCover, stop bool) { + // As demonstrated in #4639, programs reproduce with a very high, but not 100% probability. + // The triage algorithm must tolerate this, so let's pick the signal that is common + // to 3 out of 5 runs. + // By binomial distribution, a program that reproduces 80% of time will pass deflake() + // with a 94% probability. If it reproduces 90% of time, it passes in 99% of cases. + const ( + needRuns = 3 + maxRuns = 5 + ) + signals := make([]signal.Signal, needRuns) + for i := 0; i < maxRuns; i++ { + if signals[needRuns-1].Len() > 0 { + // We've already got signal common to needRuns. + break + } + if left := maxRuns - i; left < needRuns && signals[needRuns-left-1].Len() == 0 { + // There's no chance to get coverage common to needRuns. + break + } + result := exec(job, &Request{ Prog: job.p, NeedSignal: rpctype.AllSignal, NeedCover: true, - NeedRawCover: fuzzer.Config.FetchRawCover, + NeedRawCover: rawCover, stat: statTriage, flags: progInTriage, }) @@ -189,29 +205,22 @@ func (job *triageJob) deflake(fuzzer *Fuzzer) (info deflakedCover, stop bool) { } if !reexecutionSuccess(result.Info, &job.info, job.call) { // The call was not executed or failed. - notExecuted++ - if notExecuted >= signalRuns/2+1 { - stop = true - return // if happens too often, give up - } continue } thisSignal, thisCover := getSignalAndCover(job.p, result.Info, job.call) - if len(info.rawCover) == 0 && fuzzer.Config.FetchRawCover { + if len(info.rawCover) == 0 && rawCover { info.rawCover = thisCover } - if i == 0 { - info.stableSignal = thisSignal - info.newStableSignal = job.newSignal.Intersection(thisSignal) - } else { - info.stableSignal = info.stableSignal.Intersection(thisSignal) - info.newStableSignal = info.newStableSignal.Intersection(thisSignal) - } - if info.newStableSignal.Empty() { - return - } info.cover.Merge(thisCover) + for j := len(signals) - 1; j > 0; j-- { + intersect := signals[j-1].Intersection(thisSignal) + signals[j].Merge(intersect) + } + signals[0].Merge(thisSignal) } + + info.stableSignal = signals[needRuns-1] + info.newStableSignal = job.newSignal.Intersection(info.stableSignal) return } diff --git a/pkg/fuzzer/job_test.go b/pkg/fuzzer/job_test.go new file mode 100644 index 000000000..d9f7873dc --- /dev/null +++ b/pkg/fuzzer/job_test.go @@ -0,0 +1,94 @@ +// 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. + +package fuzzer + +import ( + "testing" + + "github.com/google/syzkaller/pkg/ipc" + "github.com/google/syzkaller/pkg/signal" + "github.com/google/syzkaller/prog" + "github.com/google/syzkaller/sys/targets" + "github.com/stretchr/testify/assert" +) + +func TestDeflakeFail(t *testing.T) { + target, err := prog.GetTarget(targets.TestOS, targets.TestArch64Fuzz) + if err != nil { + t.Fatal(err) + } + prog, err := target.Deserialize([]byte(anyTestProg), prog.NonStrict) + assert.NoError(t, err) + + testJob := &triageJob{ + p: prog, + info: ipc.CallInfo{}, + newSignal: signal.FromRaw([]uint32{0, 1, 2}, 0), + } + + run := 0 + ret, stop := testJob.deflake(func(_ job, _ *Request) *Result { + run++ + // For first, we return 0 and 1. For second, 1 and 2. And so on. + return fakeResult(0, []uint32{uint32(run), uint32(run + 1)}, []uint32{10, 20}) + }, false) + assert.False(t, stop) + assert.Equal(t, 5, run) + assert.Empty(t, ret.stableSignal.ToRaw()) + assert.Empty(t, ret.newStableSignal.ToRaw()) +} + +func TestDeflakeSuccess(t *testing.T) { + target, err := prog.GetTarget(targets.TestOS, targets.TestArch64Fuzz) + if err != nil { + t.Fatal(err) + } + prog, err := target.Deserialize([]byte(anyTestProg), prog.NonStrict) + assert.NoError(t, err) + + testJob := &triageJob{ + p: prog, + info: ipc.CallInfo{}, + newSignal: signal.FromRaw([]uint32{0, 1, 2}, 0), + } + run := 0 + ret, stop := testJob.deflake(func(_ job, _ *Request) *Result { + run++ + switch run { + case 1: + return fakeResult(0, []uint32{0, 2, 4, 6, 8}, []uint32{10, 20}) + case 2: + // This one should be ignored -- it has a different errno. + return fakeResult(1, []uint32{0, 1, 2}, []uint32{100}) + case 3: + return fakeResult(0, []uint32{0, 2, 4, 6, 8}, []uint32{20, 30}) + case 4: + return fakeResult(0, []uint32{0, 2, 6}, []uint32{30, 40}) + } + // We expect it to have finished earlier. + t.Fatal("only 4 runs were expected") + return nil + }, false) + assert.False(t, stop) + // Cover is a union of all coverages. + assert.ElementsMatch(t, []uint32{10, 20, 30, 40}, ret.cover.Serialize()) + // 0, 2, 6 were in three resuls. + assert.ElementsMatch(t, []uint32{0, 2, 6}, ret.stableSignal.ToRaw()) + // 0, 2 were also in newSignal. + assert.ElementsMatch(t, []uint32{0, 2}, ret.newStableSignal.ToRaw()) +} + +func fakeResult(errno int, signal, cover []uint32) *Result { + return &Result{ + Info: &ipc.ProgInfo{ + Calls: []ipc.CallInfo{ + { + Errno: errno, + Signal: signal, + Cover: cover, + }, + }, + }, + } +} -- cgit mrf-deployment