syz-fuzzer: prioritize signal from successful syscalls

Signal on successful syscalls is more valuable than
signal on unsuccessful syscalls.y

1 files changed, 166 insertions, 0 deletions

diff --git a/pkg/signal/signal.go b/pkg/signal/signal.go
new file mode 100644
index 000000000..366407d04
--- /dev/null
+++ b/pkg/signal/signal.go
@@ -0,0 +1,166 @@
+// Copyright 2018 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 provides types for working with feedback signal.
+package signal
+
+import (
+	"sort"
+)
+
+type (
+	elemType uint32
+	prioType int8
+)
+
+type Signal map[elemType]prioType
+
+type Serial struct {
+	Elems []elemType
+	Prios []prioType
+}
+
+func (s Signal) Len() int {
+	return len(s)
+}
+
+func (s Signal) Empty() bool {
+	return len(s) == 0
+}
+
+func FromRaw(raw []uint32, prio uint8) Signal {
+	if len(raw) == 0 {
+		return nil
+	}
+	s := make(Signal, len(raw))
+	for _, e := range raw {
+		s[elemType(e)] = prioType(prio)
+	}
+	return s
+}
+
+func (s Signal) Serialize() Serial {
+	if s.Empty() {
+		return Serial{}
+	}
+	res := Serial{
+		Elems: make([]elemType, len(s)),
+		Prios: make([]prioType, len(s)),
+	}
+	i := 0
+	for e, p := range s {
+		res.Elems[i] = e
+		res.Prios[i] = p
+		i++
+	}
+	return res
+}
+
+func (ser Serial) Deserialize() Signal {
+	if len(ser.Elems) != len(ser.Prios) {
+		panic("corrupted Serial")
+	}
+	if len(ser.Elems) == 0 {
+		return nil
+	}
+	s := make(Signal, len(ser.Elems))
+	for i, e := range ser.Elems {
+		s[e] = ser.Prios[i]
+	}
+	return s
+}
+
+func (s Signal) Diff(s1 Signal) Signal {
+	if s1.Empty() {
+		return nil
+	}
+	var res Signal
+	for e, p1 := range s1 {
+		if p, ok := s[e]; ok && p >= p1 {
+			continue
+		}
+		if res == nil {
+			res = make(Signal)
+		}
+		res[e] = p1
+	}
+	return res
+}
+
+func (s Signal) DiffRaw(raw []uint32, prio uint8) Signal {
+	var res Signal
+	for _, e := range raw {
+		if p, ok := s[elemType(e)]; ok && p >= prioType(prio) {
+			continue
+		}
+		if res == nil {
+			res = make(Signal)
+		}
+		res[elemType(e)] = prioType(prio)
+	}
+	return res
+}
+
+func (s Signal) Intersection(s1 Signal) Signal {
+	if s1.Empty() {
+		return nil
+	}
+	res := make(Signal, len(s))
+	for e, p := range s {
+		if p1, ok := s1[e]; ok && p1 >= p {
+			res[e] = p
+		}
+	}
+	return res
+}
+
+func (sp *Signal) Merge(s1 Signal) {
+	if s1.Empty() {
+		return
+	}
+	s := *sp
+	if s == nil {
+		s = make(Signal, len(s1))
+		*sp = s
+	}
+	for e, p1 := range s1 {
+		if p, ok := s[e]; !ok || p < p1 {
+			s[e] = p1
+		}
+	}
+}
+
+type SignalContext struct {
+	Signal  Signal
+	Context interface{}
+}
+
+func Minimize(corpus []SignalContext) []interface{} {
+	sort.Slice(corpus, func(i, j int) bool {
+		return corpus[i].Signal.Len() > corpus[j].Signal.Len()
+	})
+	type ContextPrio struct {
+		prio prioType
+		idx  int
+	}
+	covered := make(map[elemType]ContextPrio)
+	for i, inp := range corpus {
+		for e, p := range inp.Signal {
+			if prev, ok := covered[e]; !ok || p > prev.prio {
+				covered[e] = ContextPrio{
+					prio: p,
+					idx:  i,
+				}
+			}
+		}
+	}
+	indices := make(map[int]struct{}, len(corpus))
+	for _, cp := range covered {
+		indices[cp.idx] = struct{}{}
+	}
+	result := make([]interface{}, 0, len(indices))
+	for idx := range indices {
+		result = append(result, corpus[idx].Context)
+	}
+	return result
+}