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.

2 files changed, 64 insertions, 0 deletions

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())
+}