pkg/fuzzer,pkg/corpus: detection and preservation of programs with probability coverage

4 files changed, 78 insertions, 40 deletions

diff --git a/pkg/corpus/corpus.go b/pkg/corpus/corpus.go
index 54c8d96cd..e6569dbc6 100644
--- a/pkg/corpus/corpus.go
+++ b/pkg/corpus/corpus.go
@@ -94,13 +94,14 @@ type ItemUpdate struct {
 // too hard to synchonize accesses to them across the whole project.
 // When Corpus updates one of its items, it saves a copy of it.
 type Item struct {
-	Sig     string
-	Call    int
-	Prog    *prog.Prog
-	HasAny  bool // whether the prog contains squashed arguments
-	Signal  signal.Signal
-	Cover   []uint64
-	Updates []ItemUpdate
+	Sig          string
+	Call         int
+	Prog         *prog.Prog
+	HasAny       bool // whether the prog contains squashed arguments
+	Signal       signal.Signal
+	StableSignal signal.Signal
+	Cover        []uint64
+	Updates      []ItemUpdate
 
 	areas map[*focusAreaState]struct{}
 }
@@ -110,16 +111,19 @@ func (item Item) StringCall() string {
 }
 
 type NewInput struct {
-	Prog     *prog.Prog
-	Call     int
-	Signal   signal.Signal
-	Cover    []uint64
-	RawCover []uint64
+	Prog         *prog.Prog
+	Call         int
+	Signal       signal.Signal
+	StableSignal signal.Signal
+	Cover        []uint64
+	RawCover     []uint64
+	ProbOnly     bool
 }
 
 type NewItemEvent struct {
 	Sig      string
 	Exists   bool
+	ProbOnly bool
 	ProgData []byte
 	NewCover []uint64
 }
@@ -141,18 +145,21 @@ func (corpus *Corpus) Save(inp NewInput) {
 		exists = true
 		newSignal := old.Signal.Copy()
 		newSignal.Merge(inp.Signal)
+		newStableSignal := old.StableSignal.Copy()
+		newStableSignal.Merge(inp.StableSignal)
 		var newCover cover.Cover
 		newCover.Merge(old.Cover)
 		newCover.Merge(inp.Cover)
 		newItem = &Item{
-			Sig:     sig,
-			Prog:    old.Prog,
-			Call:    old.Call,
-			HasAny:  old.HasAny,
-			Signal:  newSignal,
-			Cover:   newCover.Serialize(),
-			Updates: append([]ItemUpdate{}, old.Updates...),
-			areas:   maps.Clone(old.areas),
+			Sig:          sig,
+			Prog:         old.Prog,
+			Call:         old.Call,
+			HasAny:       old.HasAny,
+			Signal:       newSignal,
+			StableSignal: newStableSignal,
+			Cover:        newCover.Serialize(),
+			Updates:      append([]ItemUpdate{}, old.Updates...),
+			areas:        maps.Clone(old.areas),
 		}
 		const maxUpdates = 32
 		if len(newItem.Updates) < maxUpdates {
@@ -160,18 +167,20 @@ func (corpus *Corpus) Save(inp NewInput) {
 		}
 	} else {
 		newItem = &Item{
-			Sig:     sig,
-			Call:    inp.Call,
-			Prog:    inp.Prog,
-			HasAny:  inp.Prog.ContainsAny(),
-			Signal:  inp.Signal,
-			Cover:   inp.Cover,
-			Updates: []ItemUpdate{update},
+			Sig:          sig,
+			Call:         inp.Call,
+			Prog:         inp.Prog,
+			HasAny:       inp.Prog.ContainsAny(),
+			Signal:       inp.Signal,
+			StableSignal: inp.StableSignal,
+			Cover:        inp.Cover,
+			Updates:      []ItemUpdate{update},
 		}
 	}
+
 	corpus.progsMap[sig] = newItem
 	corpus.applyFocusAreas(newItem, newItem.Cover)
-	corpus.saveProgram(inp.Prog, newItem.Signal)
+	corpus.saveProgram(inp.Prog, newItem.StableSignal)
 
 	corpus.signal.Merge(inp.Signal)
 	newCover := corpus.cover.MergeDiff(inp.Cover)
@@ -181,6 +190,7 @@ func (corpus *Corpus) Save(inp NewInput) {
 		case corpus.updates <- NewItemEvent{
 			Sig:      sig,
 			Exists:   exists,
+			ProbOnly: inp.ProbOnly,
 			ProgData: progData,
 			NewCover: newCover,
 		}:
diff --git a/pkg/fuzzer/cover.go b/pkg/fuzzer/cover.go
index e2dca3d88..191ff1491 100644
--- a/pkg/fuzzer/cover.go
+++ b/pkg/fuzzer/cover.go
@@ -36,6 +36,14 @@ func (cover *Cover) addRawMaxSignal(signal []uint64, prio uint8) signal.Signal {
 	return diff
 }
 
+func (cover *Cover) addMaxSignal(signal signal.Signal) signal.Signal {
+	cover.mu.Lock()
+	defer cover.mu.Unlock()
+	diff := cover.maxSignal.MergeDiff(signal)
+	cover.newSignal.Merge(diff)
+	return diff
+}
+
 func (cover *Cover) CopyMaxSignal() signal.Signal {
 	cover.mu.RLock()
 	defer cover.mu.RUnlock()
diff --git a/pkg/fuzzer/fuzzer.go b/pkg/fuzzer/fuzzer.go
index bd55ca9c6..3241cb63a 100644
--- a/pkg/fuzzer/fuzzer.go
+++ b/pkg/fuzzer/fuzzer.go
@@ -24,8 +24,9 @@ import (
 
 type Fuzzer struct {
 	Stats
-	Config *Config
-	Cover  *Cover
+	Config    *Config
+	Cover     *Cover
+	ProbCover *Cover
 
 	ctx          context.Context
 	mu           sync.Mutex
@@ -50,9 +51,10 @@ func NewFuzzer(ctx context.Context, cfg *Config, rnd *rand.Rand,
 		}
 	}
 	f := &Fuzzer{
-		Stats:  newStats(target),
-		Config: cfg,
-		Cover:  newCover(),
+		Stats:     newStats(target),
+		Config:    cfg,
+		Cover:     newCover(),
+		ProbCover: new(Cover),
 
 		ctx:         ctx,
 		rnd:         rnd,
diff --git a/pkg/fuzzer/job.go b/pkg/fuzzer/job.go
index bbac544f6..1f450ff7e 100644
--- a/pkg/fuzzer/job.go
+++ b/pkg/fuzzer/job.go
@@ -93,7 +93,9 @@ type triageCall struct {
 
 	// Filled after deflake:
 	signals         [deflakeNeedRuns]signal.Signal
+	probSignal      signal.Signal
 	stableSignal    signal.Signal
+	newProbSignal   signal.Signal
 	newStableSignal signal.Signal
 	cover           cover.Cover
 	rawCover        []uint64
@@ -162,12 +164,16 @@ func (job *triageJob) run(fuzzer *Fuzzer) {
 }
 
 func (job *triageJob) handleCall(call int, info *triageCall) {
-	if info.newStableSignal.Empty() {
+	skip := true
+	skip = skip && info.newStableSignal.Empty()
+	skip = skip && (info.newProbSignal.Empty() || info.newProbSignal.Len() < 4 && info.newProbSignal.Metric() < (1<<2))
+
+	if skip {
 		return
 	}
 
 	p := job.p
-	if job.flags&ProgMinimized == 0 {
+	if job.flags&ProgMinimized == 0 && !info.newStableSignal.Empty() {
 		p, call = job.minimize(call, info)
 		if p == nil {
 			return
@@ -209,11 +215,13 @@ func (job *triageJob) handleCall(call int, info *triageCall) {
 	}
 	job.fuzzer.Logf(2, "added new input for %v to the corpus: %s", callName, p)
 	input := corpus.NewInput{
-		Prog:     p,
-		Call:     call,
-		Signal:   info.stableSignal,
-		Cover:    info.cover.Serialize(),
-		RawCover: info.rawCover,
+		Prog:         p,
+		Call:         call,
+		ProbOnly:     info.newStableSignal.Empty(),
+		Signal:       info.probSignal,
+		StableSignal: info.stableSignal,
+		Cover:        info.cover.Serialize(),
+		RawCover:     info.rawCover,
 	}
 	job.fuzzer.Config.Corpus.Save(input)
 }
@@ -291,6 +299,16 @@ func (job *triageJob) deflake(exec func(*queue.Request, ProgFlags) *queue.Result
 	}
 	job.info.Logf("deflake complete")
 	for call, info := range job.calls {
+		for i := range needRuns - 1 {
+			info.probSignal.Merge(info.signals[i].CopyWithPrio(uint8(i) << 2))
+		}
+		info.newProbSignal = job.fuzzer.ProbCover.addMaxSignal(info.probSignal)
+		job.info.Logf("call #%d [%s]: |probability signal|=%d, |new probability signal|=%d%s",
+			call, job.p.CallName(call), info.probSignal.Len(), info.newProbSignal.Len(),
+			signalPreview(info.newProbSignal))
+	}
+
+	for call, info := range job.calls {
 		info.stableSignal = info.signals[needRuns-1]
 		info.newStableSignal = info.newSignal.Intersection(info.stableSignal)
 		job.info.Logf("call #%d [%s]: |stable signal|=%d, |new stable signal|=%d%s",