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.

10 files changed, 220 insertions, 29 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())
+}
diff --git a/syz-fuzzer/fuzzer.go b/syz-fuzzer/fuzzer.go
index 17382bd03..d652a45bf 100644
--- a/syz-fuzzer/fuzzer.go
+++ b/syz-fuzzer/fuzzer.go
@@ -348,7 +348,7 @@ func (tool *FuzzerTool) exchangeDataCall(needProgs int, results []executionResul
 	if err := tool.manager.Call("Manager.ExchangeInfo", a, r); err != nil {
 		log.SyzFatalf("Manager.ExchangeInfo call failed: %v", err)
 	}
-	tool.addMaxSignal(r.NewMaxSignal)
+	tool.updateMaxSignal(r.NewMaxSignal, r.DropMaxSignal)
 	for _, req := range r.Requests {
 		p := tool.deserializeInput(req.ProgData)
 		if p == nil {
@@ -442,10 +442,11 @@ func (tool *FuzzerTool) diffMaxSignal(info *ipc.ProgInfo) {
 	diffProgInfo(info, tool.maxSignal)
 }
 
-func (tool *FuzzerTool) addMaxSignal(diff []uint32) {
+func (tool *FuzzerTool) updateMaxSignal(add, drop []uint32) {
 	tool.signalMu.Lock()
 	defer tool.signalMu.Unlock()
-	tool.maxSignal.Merge(signal.FromRaw(diff, 0))
+	tool.maxSignal.Subtract(signal.FromRaw(drop, 0))
+	tool.maxSignal.Merge(signal.FromRaw(add, 0))
 }
 
 func setupPprofHandler(port int) {
diff --git a/syz-manager/manager.go b/syz-manager/manager.go
index 673deadc9..1d5d26fce 100644
--- a/syz-manager/manager.go
+++ b/syz-manager/manager.go
@@ -1415,6 +1415,7 @@ func (mgr *Manager) machineChecked(a *rpctype.CheckArgs, enabledSyscalls map[*pr
 
 	mgr.loadCorpus()
 	go mgr.fuzzerLoop()
+	go mgr.fuzzerSignalRotation()
 }
 
 func (mgr *Manager) getFuzzer() *fuzzer.Fuzzer {
@@ -1423,14 +1424,46 @@ func (mgr *Manager) getFuzzer() *fuzzer.Fuzzer {
 	return mgr.fuzzer
 }
 
+func (mgr *Manager) fuzzerSignalRotation() {
+	const (
+		rotateSignals      = 1000
+		timeBetweenRotates = 15 * time.Minute
+		// Every X dropped signals may in the worst case lead up to 3 * X
+		// additional triage executions, which is in this case constitutes
+		// 3000/60000 = 5%.
+		execsBetweenRotates = 60000
+	)
+	var lastExecTotal uint64
+	lastRotation := time.Now()
+	for {
+		time.Sleep(time.Minute * 5)
+		mgr.mu.Lock()
+		phase := mgr.phase
+		mgr.mu.Unlock()
+		if phase < phaseTriagedCorpus {
+			continue
+		}
+		if mgr.stats.execTotal.get()-lastExecTotal < execsBetweenRotates {
+			continue
+		}
+		if time.Since(lastRotation) < timeBetweenRotates {
+			continue
+		}
+		mgr.fuzzer.RotateMaxSignal(rotateSignals)
+		lastRotation = time.Now()
+		lastExecTotal = mgr.stats.execTotal.get()
+	}
+}
+
 func (mgr *Manager) fuzzerLoop() {
 	for {
 		time.Sleep(time.Second / 2)
 
 		// Distribute new max signal over all instances.
-		newSignal := mgr.fuzzer.Cover.GrabNewSignal()
-		log.Logf(2, "distributing %d new signal", len(newSignal))
-		mgr.serv.distributeMaxSignal(newSignal)
+		newSignal, dropSignal := mgr.fuzzer.Cover.GrabSignalDelta()
+		log.Logf(2, "distributing %d new signal, %d dropped signal",
+			len(newSignal), len(dropSignal))
+		mgr.serv.distributeSignalDelta(newSignal, dropSignal)
 
 		// Collect statistics.
 		fuzzerStats := mgr.fuzzer.Stats()
diff --git a/syz-manager/rpc.go b/syz-manager/rpc.go
index 472c406d2..ed4d3fc91 100644
--- a/syz-manager/rpc.go
+++ b/syz-manager/rpc.go
@@ -43,9 +43,10 @@ type Runner struct {
 	machineInfo []byte
 	instModules *cover.CanonicalizerInstance
 
-	// The mutex protects newMaxSignal and requests.
+	// The mutex protects newMaxSignal, dropMaxSignal, and requests.
 	mu            sync.Mutex
 	newMaxSignal  signal.Signal
+	dropMaxSignal signal.Signal
 	nextRequestID atomic.Int64
 	requests      map[int64]*fuzzer.Request
 }
@@ -203,15 +204,17 @@ func (serv *RPCServer) ExchangeInfo(a *rpctype.ExchangeInfoRequest, r *rpctype.E
 
 	runner.mu.Lock()
 	// Let's transfer new max signal in portions.
+
 	const transferMaxSignal = 500000
-	maxSignalDiff := runner.newMaxSignal.Split(transferMaxSignal)
+	newSignal := runner.newMaxSignal.Split(transferMaxSignal)
+	dropSignal := runner.dropMaxSignal.Split(transferMaxSignal)
 	runner.mu.Unlock()
 
-	r.NewMaxSignal = runner.instModules.Decanonicalize(maxSignalDiff.ToRaw())
-
-	log.Logf(2, "exchange with %s: %d done, %d new requests, %d new max signal",
-		a.Name, len(a.Results), len(r.Requests), len(r.NewMaxSignal))
+	r.NewMaxSignal = runner.instModules.Decanonicalize(newSignal.ToRaw())
+	r.DropMaxSignal = runner.instModules.Decanonicalize(dropSignal.ToRaw())
 
+	log.Logf(2, "exchange with %s: %d done, %d new requests, %d new max signal, %d drop signal",
+		a.Name, len(a.Results), len(r.Requests), len(r.NewMaxSignal), len(r.DropMaxSignal))
 	return nil
 }
 
@@ -261,12 +264,13 @@ func (serv *RPCServer) shutdownInstance(name string) []byte {
 	return runner.machineInfo
 }
 
-func (serv *RPCServer) distributeMaxSignal(delta signal.Signal) {
+func (serv *RPCServer) distributeSignalDelta(plus, minus signal.Signal) {
 	serv.runners.Range(func(key, value any) bool {
 		runner := value.(*Runner)
 		runner.mu.Lock()
 		defer runner.mu.Unlock()
-		runner.newMaxSignal.Merge(delta)
+		runner.newMaxSignal.Merge(plus)
+		runner.dropMaxSignal.Merge(minus)
 		return true
 	})
 }