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.

7 files changed, 168 insertions, 15 deletions

diff --git a/pkg/corpus/corpus.go b/pkg/corpus/corpus.go
index 8eed1fc63..568da832b 100644
--- a/pkg/corpus/corpus.go
+++ b/pkg/corpus/corpus.go
@@ -149,13 +149,6 @@ func (corpus *Corpus) Save(inp NewInput) {
 		}
 	}
 }
-
-func (corpus *Corpus) DiffSignal(s signal.Signal) signal.Signal {
-	corpus.mu.RLock()
-	defer corpus.mu.RUnlock()
-	return corpus.signal.Diff(s)
-}
-
 func (corpus *Corpus) Signal() signal.Signal {
 	corpus.mu.RLock()
 	defer corpus.mu.RUnlock()
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)
 
diff --git a/pkg/rpctype/rpctype.go b/pkg/rpctype/rpctype.go
index 9f0b6846e..cb50ecfa6 100644
--- a/pkg/rpctype/rpctype.go
+++ b/pkg/rpctype/rpctype.go
@@ -49,8 +49,9 @@ type ExchangeInfoRequest struct {
 
 // ExchangeInfoReply is a reply to ExchangeInfoRequest.
 type ExchangeInfoReply struct {
-	Requests     []ExecutionRequest
-	NewMaxSignal []uint32
+	Requests      []ExecutionRequest
+	NewMaxSignal  []uint32
+	DropMaxSignal []uint32
 }
 
 // TODO: merge ExecutionRequest and ExecTask.
diff --git a/pkg/signal/signal.go b/pkg/signal/signal.go
index 2860be95e..f7f7899b2 100644
--- a/pkg/signal/signal.go
+++ b/pkg/signal/signal.go
@@ -4,6 +4,8 @@
 // Package signal provides types for working with feedback signal.
 package signal
 
+import "math/rand"
+
 type (
 	elemType uint32
 	prioType int8
@@ -119,6 +121,35 @@ func (s *Signal) Merge(s1 Signal) {
 	}
 }
 
+func (s *Signal) Subtract(s1 Signal) {
+	s0 := *s
+	if s0 == nil {
+		return
+	}
+	for e, p1 := range s1 {
+		if p, ok := s0[e]; ok && p == p1 {
+			delete(s0, e)
+		}
+	}
+}
+
+func (s Signal) RandomSubset(r *rand.Rand, size int) Signal {
+	if size > len(s) {
+		size = len(s)
+	}
+	keys := make([]elemType, 0, len(s))
+	for e := range s {
+		keys = append(keys, e)
+	}
+	r.Shuffle(len(keys), func(i, j int) { keys[i], keys[j] = keys[j], keys[i] })
+
+	ret := make(Signal, size)
+	for _, e := range keys[:size] {
+		ret[e] = s[e]
+	}
+	return ret
+}
+
 // FilterRaw returns a subset of original raw elements that coincides with the one in Signal.
 func (s Signal) FilterRaw(raw []uint32) []uint32 {
 	var ret []uint32
diff --git a/pkg/signal/signal_test.go b/pkg/signal/signal_test.go
new file mode 100644
index 000000000..f5582698f
--- /dev/null
+++ b/pkg/signal/signal_test.go
@@ -0,0 +1,33 @@
+// 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 signal
+
+import (
+	"math/rand"
+	"testing"
+
+	"github.com/google/syzkaller/pkg/testutil"
+	"github.com/stretchr/testify/assert"
+)
+
+func TestRandomSubset(t *testing.T) {
+	r := rand.New(testutil.RandSource(t))
+	base := FromRaw([]uint32{0, 1, 2, 3, 4}, 0)
+	var s Signal
+	for i := 0; i < 1000 && s.Len() < base.Len(); i++ {
+		delta := base.RandomSubset(r, 1)
+		assert.Equal(t, 1, delta.Len())
+		s.Merge(delta)
+	}
+	assert.Equal(t, base.Len(), s.Len())
+}
+
+func TestSubtract(t *testing.T) {
+	base := FromRaw([]uint32{0, 1, 2, 3, 4}, 0)
+	assert.Equal(t, 5, base.Len())
+	base.Subtract(FromRaw([]uint32{0}, 0))
+	assert.Equal(t, 4, base.Len())
+	base.Subtract(FromRaw([]uint32{1}, 0))
+	assert.Equal(t, 3, base.Len())
+}