pkg/fuzzer: deflake comparisons

Do two exec hints to only leave stable comparison argument pairs.
In local experiments, it allows to reduce their count by 30-40% (on
average).

3 files changed, 55 insertions, 9 deletions

diff --git a/pkg/fuzzer/job.go b/pkg/fuzzer/job.go
index 055e1f58b..5663b6723 100644
--- a/pkg/fuzzer/job.go
+++ b/pkg/fuzzer/job.go
@@ -385,20 +385,33 @@ func (job *hintsJob) priority() priority {
 }
 
 func (job *hintsJob) run(fuzzer *Fuzzer) {
-	// First execute the original program to dump comparisons from KCOV.
+	// First execute the original program twice to get comparisons from KCOV.
+	// The second execution lets us filter out flaky values, which seem to constitute ~30-40%.
 	p := job.p
-	result := fuzzer.exec(job, &Request{
-		Prog:      p,
-		NeedHints: true,
-		stat:      fuzzer.statExecSeed,
-	})
-	if result.Stop || result.Info == nil {
-		return
+	var comps prog.CompMap
+	for i := 0; i < 2; i++ {
+		result := fuzzer.exec(job, &Request{
+			Prog:      p,
+			NeedHints: true,
+			stat:      fuzzer.statExecSeed,
+		})
+		if result.Stop || result.Info == nil {
+			return
+		}
+		if i == 0 {
+			comps = result.Info.Calls[job.call].Comps
+			if len(comps) == 0 {
+				return
+			}
+		} else {
+			comps.InplaceIntersect(result.Info.Calls[job.call].Comps)
+		}
 	}
+
 	// Then mutate the initial program for every match between
 	// a syscall argument and a comparison operand.
 	// Execute each of such mutants to check if it gives new coverage.
-	p.MutateWithHints(job.call, result.Info.Calls[job.call].Comps,
+	p.MutateWithHints(job.call, comps,
 		func(p *prog.Prog) bool {
 			result := fuzzer.exec(job, &Request{
 				Prog:       p,
diff --git a/prog/hints.go b/prog/hints.go
index cbfe9c859..1dca452db 100644
--- a/prog/hints.go
+++ b/prog/hints.go
@@ -63,6 +63,20 @@ func (m CompMap) String() string {
 	return buf.String()
 }
 
+// InplaceIntersect() only leaves the value pairs that are also present in other.
+func (m CompMap) InplaceIntersect(other CompMap) {
+	for val1, nested := range m {
+		for val2 := range nested {
+			if !other[val1][val2] {
+				delete(nested, val2)
+			}
+		}
+		if len(nested) == 0 {
+			delete(m, val1)
+		}
+	}
+}
+
 // Mutates the program using the comparison operands stored in compMaps.
 // For each of the mutants executes the exec callback.
 // The callback must return whether we should continue substitution (true)
diff --git a/prog/hints_test.go b/prog/hints_test.go
index a4b8da7bf..8b15ae473 100644
--- a/prog/hints_test.go
+++ b/prog/hints_test.go
@@ -13,6 +13,7 @@ import (
 
 	"github.com/google/go-cmp/cmp"
 	"github.com/google/syzkaller/pkg/image"
+	"github.com/stretchr/testify/assert"
 )
 
 type ConstArgTest struct {
@@ -666,6 +667,24 @@ func TestHintsData(t *testing.T) {
 	}
 }
 
+func TestInplaceIntersect(t *testing.T) {
+	m1 := CompMap{
+		0xdead: compSet(0x1, 0x2),
+		0xbeef: compSet(0x3, 0x4),
+		0xffff: compSet(0x5),
+	}
+	m2 := CompMap{
+		0xdead: compSet(0x2),
+		0xbeef: compSet(0x3, 0x6),
+		0xeeee: compSet(0x6),
+	}
+	m1.InplaceIntersect(m2)
+	assert.Equal(t, CompMap{
+		0xdead: compSet(0x2),
+		0xbeef: compSet(0x3),
+	}, m1)
+}
+
 func BenchmarkHints(b *testing.B) {
 	target, cleanup := initBench(b)
 	defer cleanup()