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.

3 files changed, 129 insertions, 26 deletions

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,
+				},
+			},
+		},
+	}
+}