pkg/fuzzer: implement basic max signal rotation

Once in 15 minutes, drop 1000 elements of the pure max signal (that is,
max signal minus corpus signal).

It seems to have a positive effect on the total fuzzing performance.

3 files changed, 101 insertions, 6 deletions

diff --git a/pkg/fuzzer/cover.go b/pkg/fuzzer/cover.go
index 5af00f167..31d1fee1b 100644
--- a/pkg/fuzzer/cover.go
+++ b/pkg/fuzzer/cover.go
@@ -11,16 +11,19 @@ import (
 
 // Cover keeps track of the signal known to the fuzzer.
 type Cover struct {
-	mu        sync.RWMutex
-	maxSignal signal.Signal // max signal ever observed (including flakes)
-	newSignal signal.Signal // newly identified max signal
+	mu         sync.RWMutex
+	maxSignal  signal.Signal // max signal ever observed (including flakes)
+	newSignal  signal.Signal // newly identified max signal
+	dropSignal signal.Signal // the newly dropped max signal
 }
 
 // Signal that should no longer be chased after.
+// It is not returned in GrabSignalDelta().
 func (cover *Cover) AddMaxSignal(sign signal.Signal) {
 	cover.mu.Lock()
 	defer cover.mu.Unlock()
 	cover.maxSignal.Merge(sign)
+	cover.dropSignal.Subtract(sign)
 }
 
 func (cover *Cover) addRawMaxSignal(signal []uint32, prio uint8) signal.Signal {
@@ -32,21 +35,30 @@ func (cover *Cover) addRawMaxSignal(signal []uint32, prio uint8) signal.Signal {
 	}
 	cover.maxSignal.Merge(diff)
 	cover.newSignal.Merge(diff)
+	cover.dropSignal.Subtract(diff)
 	return diff
 }
 
+func (cover *Cover) pureMaxSignal(corpus signal.Signal) signal.Signal {
+	cover.mu.RLock()
+	defer cover.mu.RUnlock()
+	return corpus.Diff(cover.maxSignal)
+}
+
 func (cover *Cover) CopyMaxSignal() signal.Signal {
 	cover.mu.RLock()
 	defer cover.mu.RUnlock()
 	return cover.maxSignal.Copy()
 }
 
-func (cover *Cover) GrabNewSignal() signal.Signal {
+func (cover *Cover) GrabSignalDelta() (plus, minus signal.Signal) {
 	cover.mu.Lock()
 	defer cover.mu.Unlock()
-	sign := cover.newSignal
+	plus = cover.newSignal
 	cover.newSignal = nil
-	return sign
+	minus = cover.dropSignal
+	cover.dropSignal = nil
+	return
 }
 
 type CoverStats struct {
@@ -60,3 +72,11 @@ func (cover *Cover) Stats() CoverStats {
 		MaxSignal: len(cover.maxSignal),
 	}
 }
+
+func (cover *Cover) subtract(delta signal.Signal) {
+	cover.mu.Lock()
+	defer cover.mu.Unlock()
+	cover.maxSignal.Subtract(delta)
+	cover.newSignal.Subtract(delta)
+	cover.dropSignal.Merge(delta)
+}
diff --git a/pkg/fuzzer/fuzzer.go b/pkg/fuzzer/fuzzer.go
index 14c3f5902..8ce2ebe26 100644
--- a/pkg/fuzzer/fuzzer.go
+++ b/pkg/fuzzer/fuzzer.go
@@ -323,3 +323,15 @@ func (fuzzer *Fuzzer) logCurrentStats() {
 		fuzzer.Logf(0, "%s", str)
 	}
 }
+
+func (fuzzer *Fuzzer) RotateMaxSignal(items int) {
+	corpusSignal := fuzzer.Config.Corpus.Signal()
+	pureMaxSignal := fuzzer.Cover.pureMaxSignal(corpusSignal)
+	if pureMaxSignal.Len() < items {
+		items = pureMaxSignal.Len()
+	}
+	fuzzer.Logf(1, "rotate %d max signal elements", items)
+
+	delta := pureMaxSignal.RandomSubset(fuzzer.rand(), items)
+	fuzzer.Cover.subtract(delta)
+}
diff --git a/pkg/fuzzer/fuzzer_test.go b/pkg/fuzzer/fuzzer_test.go
index bd6d9a8fe..5c0920109 100644
--- a/pkg/fuzzer/fuzzer_test.go
+++ b/pkg/fuzzer/fuzzer_test.go
@@ -23,6 +23,7 @@ import (
 	"github.com/google/syzkaller/pkg/ipc"
 	"github.com/google/syzkaller/pkg/ipc/ipcconfig"
 	"github.com/google/syzkaller/pkg/rpctype"
+	"github.com/google/syzkaller/pkg/signal"
 	"github.com/google/syzkaller/pkg/testutil"
 	"github.com/google/syzkaller/prog"
 	"github.com/google/syzkaller/sys/targets"
@@ -116,6 +117,68 @@ func BenchmarkFuzzer(b *testing.B) {
 	})
 }
 
+func TestRotate(t *testing.T) {
+	target, err := prog.GetTarget(targets.TestOS, targets.TestArch64Fuzz)
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	ctx, cancel := context.WithCancel(context.Background())
+	defer cancel()
+
+	corpusObj := corpus.NewCorpus(ctx)
+	fuzzer := NewFuzzer(ctx, &Config{
+		Debug:    true,
+		Corpus:   corpusObj,
+		Coverage: true,
+		EnabledCalls: map[*prog.Syscall]bool{
+			target.SyscallMap["syz_compare"]: true,
+		},
+	}, rand.New(testutil.RandSource(t)), target)
+
+	fakeSignal := func(size int) signal.Signal {
+		var pc []uint32
+		for i := 0; i < size; i++ {
+			pc = append(pc, uint32(i))
+		}
+		return signal.FromRaw(pc, 0)
+	}
+
+	prog, err := target.Deserialize(
+		[]byte(`syz_compare(&AUTO="00000000", 0x4, &AUTO=@conditional={0x0, @void, @void}, AUTO)`),
+		prog.NonStrict)
+	assert.NoError(t, err)
+	corpusObj.Save(corpus.NewInput{
+		Prog:   prog,
+		Call:   0,
+		Signal: fakeSignal(100),
+	})
+	fuzzer.Cover.AddMaxSignal(fakeSignal(1000))
+
+	stats := fuzzer.Stats()
+	assert.Equal(t, 1000, stats.MaxSignal)
+	assert.Equal(t, 100, stats.Signal)
+
+	// Rotate some of the signal.
+	fuzzer.RotateMaxSignal(200)
+	stats = fuzzer.Stats()
+	assert.Equal(t, 800, stats.MaxSignal)
+	assert.Equal(t, 100, stats.Signal)
+
+	plus, minus := fuzzer.Cover.GrabSignalDelta()
+	assert.Equal(t, 0, plus.Len())
+	assert.Equal(t, 200, minus.Len())
+
+	// Rotate the rest.
+	fuzzer.RotateMaxSignal(1000)
+	stats = fuzzer.Stats()
+	assert.Equal(t, 100, stats.MaxSignal)
+	assert.Equal(t, 100, stats.Signal)
+	plus, minus = fuzzer.Cover.GrabSignalDelta()
+	assert.Equal(t, 0, plus.Len())
+	assert.Equal(t, 700, minus.Len())
+}
+
 // Based on the example from Go documentation.
 var crc32q = crc32.MakeTable(0xD5828281)