From f85e28d8a74848f34bdfb105079245c3d38ff9ae Mon Sep 17 00:00:00 2001 From: Aleksandr Nogikh Date: Wed, 20 Mar 2024 21:00:39 +0100 Subject: 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. --- pkg/fuzzer/cover.go | 32 +++++++++++++++++++----- pkg/fuzzer/fuzzer.go | 12 +++++++++ pkg/fuzzer/fuzzer_test.go | 63 +++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 101 insertions(+), 6 deletions(-) (limited to 'pkg/fuzzer') 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) -- cgit mrf-deployment