syz-fuzzer: prioritize signal from successful syscalls

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

4 files changed, 190 insertions, 407 deletions

diff --git a/pkg/cover/cover.go b/pkg/cover/cover.go
index 4913d1e2f..367f68d4d 100644
--- a/pkg/cover/cover.go
+++ b/pkg/cover/cover.go
@@ -1,182 +1,30 @@
 // Copyright 2015 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 cover implements set operations on slices (arrays of coverage PCs). */
+// Package cover provides types for working with coverage information (arrays of covered PCs).
 package cover
 
-import (
-	"sort"
-)
+type Cover map[uint32]struct{}
 
-type Cover []uint32
-
-func (a Cover) Len() int           { return len(a) }
-func (a Cover) Less(i, j int) bool { return a[i] < a[j] }
-func (a Cover) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
-
-const sent = ^uint32(0)
-
-func Copy(cov Cover) Cover {
-	return append(Cover{}, cov...)
-}
-
-func RestorePC(pc uint32, base uint32) uint64 {
-	return uint64(base)<<32 + uint64(pc)
-}
-
-// Canonicalize sorts and removes duplicates.
-func Canonicalize(cov []uint32) Cover {
-	sort.Sort(Cover(cov))
-	i := 0
-	last := sent
-	for _, pc := range cov {
-		if pc != last {
-			last = pc
-			cov[i] = pc
-			i++
-		}
-	}
-	return Cover(cov[:i])
-}
-
-func Difference(cov0, cov1 Cover) Cover {
-	return foreach(cov0, cov1, func(v0, v1 uint32) uint32 {
-		if v0 < v1 {
-			return v0
-		}
-		return sent
-	})
-}
-
-func SymmetricDifference(cov0, cov1 Cover) Cover {
-	return foreach(cov0, cov1, func(v0, v1 uint32) uint32 {
-		if v0 < v1 {
-			return v0
-		}
-		if v1 < v0 {
-			return v1
-		}
-		return sent
-	})
-}
-
-func Union(cov0, cov1 Cover) Cover {
-	return foreach(cov0, cov1, func(v0, v1 uint32) uint32 {
-		if v0 <= v1 {
-			return v0
-		}
-		return v1
-	})
-}
-
-func Intersection(cov0, cov1 Cover) Cover {
-	return foreach(cov0, cov1, func(v0, v1 uint32) uint32 {
-		if v0 == v1 {
-			return v0
-		}
-		return sent
-	})
-}
-
-func foreach(cov0, cov1 Cover, f func(uint32, uint32) uint32) Cover {
-	var res []uint32
-	for i0, i1 := 0, 0; i0 < len(cov0) || i1 < len(cov1); {
-		v0, v1 := sent, sent
-		if i0 < len(cov0) {
-			v0 = cov0[i0]
-		}
-		if i1 < len(cov1) {
-			v1 = cov1[i1]
-		}
-		if v0 <= v1 {
-			i0++
-		}
-		if v1 <= v0 {
-			i1++
-		}
-		if v := f(v0, v1); v != sent {
-			res = append(res, v)
-		}
+func (covp *Cover) Merge(raw []uint32) {
+	cov := *covp
+	if cov == nil {
+		cov = make(Cover)
+		*covp = cov
 	}
-	return res
-}
-
-// HasDifference returns true if cov0 has some coverage that is not present in cov1.
-// This is called on fuzzer hot path.
-func HasDifference(cov0, cov1 Cover) bool {
-	i1 := 0
-	for _, v0 := range cov0 {
-		for ; i1 < len(cov1) && cov1[i1] < v0; i1++ {
-		}
-		if i1 == len(cov1) || cov1[i1] > v0 {
-			return true
-		}
-		i1++
+	for _, pc := range raw {
+		cov[pc] = struct{}{}
 	}
-	return false
 }
 
-// Minimize returns a minimal set of inputs that give the same coverage as the full corpus.
-func Minimize(corpus []Cover) []int {
-	inputs := make([]*minInput, len(corpus))
-	for i, cov := range corpus {
-		inputs[i] = &minInput{
-			idx: i,
-			cov: cov,
-		}
-	}
-	sort.Sort(minInputArray(inputs))
-	var min []int
-	covered := make(map[uint32]struct{})
-	for _, inp := range inputs {
-		hit := false
-		for _, pc := range inp.cov {
-			if !hit {
-				if _, ok := covered[pc]; !ok {
-					hit = true
-					min = append(min, inp.idx)
-				}
-			}
-			if hit {
-				covered[pc] = struct{}{}
-			}
-		}
+func (cov Cover) Serialize() []uint32 {
+	res := make([]uint32, 0, len(cov))
+	for pc := range cov {
+		res = append(res, pc)
 	}
-	return min
-}
-
-type minInput struct {
-	idx int
-	cov Cover
-}
-
-type minInputArray []*minInput
-
-// Inputs with larger coverage come first.
-func (a minInputArray) Len() int           { return len(a) }
-func (a minInputArray) Less(i, j int) bool { return len(a[i].cov) > len(a[j].cov) }
-func (a minInputArray) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
-
-func SignalNew(base map[uint32]struct{}, signal []uint32) bool {
-	for _, s := range signal {
-		if _, ok := base[s]; !ok {
-			return true
-		}
-	}
-	return false
-}
-
-func SignalDiff(base map[uint32]struct{}, signal []uint32) (diff []uint32) {
-	for _, s := range signal {
-		if _, ok := base[s]; !ok {
-			diff = append(diff, s)
-		}
-	}
-	return
+	return res
 }
 
-func SignalAdd(base map[uint32]struct{}, signal []uint32) {
-	for _, s := range signal {
-		base[s] = struct{}{}
-	}
+func RestorePC(pc uint32, base uint32) uint64 {
+	return uint64(base)<<32 + uint64(pc)
 }
diff --git a/pkg/cover/cover_test.go b/pkg/cover/cover_test.go
deleted file mode 100644
index 5297de66d..000000000
--- a/pkg/cover/cover_test.go
+++ /dev/null
@@ -1,235 +0,0 @@
-// Copyright 2015 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 cover
-
-import (
-	"math/rand"
-	"reflect"
-	"sort"
-	"testing"
-	"time"
-)
-
-func initTest(t *testing.T) (*rand.Rand, int) {
-	iters := 100000
-	if testing.Short() {
-		iters = 1000
-	}
-	seed := int64(time.Now().UnixNano())
-	rs := rand.NewSource(seed)
-	t.Logf("seed=%v", seed)
-	return rand.New(rs), iters
-}
-
-type Test struct {
-	V0 Cover
-	V1 Cover
-	R  Cover
-}
-
-func runTest(t *testing.T, f func(Cover, Cover) Cover, sorted, symmetric bool, tests []Test) {
-	if symmetric {
-		for _, test := range tests {
-			tests = append(tests, Test{test.V1, test.V0, test.R})
-		}
-	}
-	tests = append(tests, Test{Cover{}, Cover{}, Cover{}})
-	for _, test := range tests {
-		if sorted {
-			if !sort.IsSorted(test.V0) {
-				t.Fatalf("input is not sorted: %+v", test.V0)
-			}
-			if !sort.IsSorted(test.V1) {
-				t.Fatalf("input is not sorted: %+v", test.V1)
-			}
-		}
-		if !sort.IsSorted(test.R) {
-			t.Fatalf("golden is not sorted: %+v", test.R)
-		}
-		res := f(test.V0, test.V1)
-		if !sort.IsSorted(res) {
-			t.Fatalf("output is not sorted: %+v", res)
-		}
-		if (len(res) != 0 || len(test.R) != 0) && !reflect.DeepEqual(res, test.R) {
-			t.Fatalf("f(%+v, %+v) = %+v (expect: %+v)", test.V0, test.V1, res, test.R)
-		}
-	}
-}
-
-func TestCanonicalize(t *testing.T) {
-	runTest(t, func(c0, c1 Cover) Cover { return Canonicalize([]uint32(c0)) }, false, false, []Test{
-		{Cover{1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 6}, Cover{}, Cover{1, 2, 3, 4, 5, 6}},
-		{Cover{6, 2, 3, 4, 5, 1}, Cover{}, Cover{1, 2, 3, 4, 5, 6}},
-		{Cover{6, 1, 2, 6, 3, 3, 4, 5, 1}, Cover{}, Cover{1, 2, 3, 4, 5, 6}},
-	})
-}
-
-func TestDifference(t *testing.T) {
-	runTest(t, Difference, true, false, []Test{
-		{Cover{1, 2, 3, 4, 5, 6}, Cover{}, Cover{1, 2, 3, 4, 5, 6}},
-		{Cover{1, 2, 3, 4, 5, 6}, Cover{3}, Cover{1, 2, 4, 5, 6}},
-		{Cover{1, 2, 3, 4, 5, 6}, Cover{1, 6}, Cover{2, 3, 4, 5}},
-		{Cover{1, 2, 3, 4, 5, 6}, Cover{0, 10}, Cover{1, 2, 3, 4, 5, 6}},
-		{Cover{1, 2, 3, 4, 5, 6}, Cover{0, 3, 6}, Cover{1, 2, 4, 5}},
-	})
-}
-
-func TestSymmetricDifference(t *testing.T) {
-	runTest(t, SymmetricDifference, true, true, []Test{
-		{Cover{1, 2, 3, 4, 5, 6}, Cover{}, Cover{1, 2, 3, 4, 5, 6}},
-		{Cover{1, 2, 3, 4, 5, 6}, Cover{1, 2, 3, 4, 5, 6}, Cover{}},
-		{Cover{1, 2, 3, 4, 5, 6}, Cover{2, 4, 6}, Cover{1, 3, 5}},
-		{Cover{2, 4, 6}, Cover{1, 3, 5}, Cover{1, 2, 3, 4, 5, 6}},
-	})
-}
-
-func TestUnion(t *testing.T) {
-	runTest(t, Union, true, true, []Test{
-		{Cover{1, 2, 3, 4, 5, 6}, Cover{}, Cover{1, 2, 3, 4, 5, 6}},
-		{Cover{1, 2, 3, 4, 5, 6}, Cover{1, 2, 3, 4, 5, 6}, Cover{1, 2, 3, 4, 5, 6}},
-		{Cover{1, 3, 5}, Cover{2, 4, 6}, Cover{1, 2, 3, 4, 5, 6}},
-		{Cover{1, 2, 3, 5}, Cover{2, 4, 5, 6}, Cover{1, 2, 3, 4, 5, 6}},
-	})
-}
-
-func TestIntersection(t *testing.T) {
-	runTest(t, Intersection, true, true, []Test{
-		{Cover{1, 2, 3, 4, 5, 6}, Cover{}, Cover{}},
-		{Cover{1, 2, 3}, Cover{4, 5, 6}, Cover{}},
-		{Cover{1, 2, 3}, Cover{2, 3, 5}, Cover{2, 3}},
-	})
-}
-
-func TestMinimize(t *testing.T) {
-	tests := []struct {
-		inp []Cover
-		out []int
-	}{
-		// Take all.
-		{
-			[]Cover{
-				{1, 2, 3},
-				{4, 5, 6},
-				{7, 8, 9},
-			},
-			[]int{0, 1, 2},
-		},
-		// Take one.
-		{
-			[]Cover{
-				{1, 2, 3, 4, 5, 6, 7, 8, 9},
-				{1},
-				{2, 3, 4, 5},
-				{6, 7, 8},
-			},
-			[]int{0},
-		},
-		// Take two.
-		{
-			[]Cover{
-				{1, 2, 3, 4, 5, 6, 7, 8, 9},
-				{1},
-				{2, 3, 4, 5},
-				{10},
-			},
-			[]int{0, 3},
-		},
-		// Take another two.
-		{
-			[]Cover{
-				{1, 2, 3, 4},
-				{1, 2},
-				{3, 4, 5, 6, 7},
-				{3, 7},
-			},
-			[]int{2, 0},
-		},
-		// Take the largest one.
-		{
-			[]Cover{
-				{1, 2},
-				{1, 2, 3, 4, 5},
-				{3, 4, 5},
-			},
-			[]int{1},
-		},
-	}
-	for _, test := range tests {
-		res := Minimize(test.inp)
-		if !reflect.DeepEqual(res, test.out) {
-			t.Logf("corpus:")
-			for _, in := range test.inp {
-				t.Logf("  %+v", in)
-			}
-			t.Fatalf("expect: %+v, got: %+v", test.out, res)
-		}
-	}
-}
-
-func randCover(rnd *rand.Rand, maxLen int) Cover {
-	tmp := make(Cover, rnd.Intn(maxLen))
-	for j := range tmp {
-		tmp[j] = uint32(rnd.Intn(100))
-	}
-	return Canonicalize(tmp)
-}
-
-func TestMinimizeRandom(t *testing.T) {
-	rnd, iters := initTest(t)
-	for i := 0; i < iters; i++ {
-		n := rnd.Intn(20)
-		cov := make([]Cover, n)
-		for i := range cov {
-			cov[i] = randCover(rnd, 10)
-		}
-		var total Cover
-		for _, c := range cov {
-			total = Union(total, c)
-		}
-		mini := Minimize(cov)
-		var minimized Cover
-		for _, idx := range mini {
-			minimized = Union(minimized, cov[idx])
-		}
-		if !reflect.DeepEqual(total, minimized) {
-			t.Logf("minimized %v -> %v", len(cov), len(mini))
-			t.Logf("corpus:")
-			for _, in := range cov {
-				t.Logf("  %+v", in)
-			}
-			t.Logf("minimized:")
-			for _, in := range cov {
-				t.Logf("  %+v", in)
-			}
-			t.Fatalf("better luck next time")
-		}
-	}
-}
-
-func TestHasDifference(t *testing.T) {
-	rnd, iters := initTest(t)
-	for i := 0; i < iters; i++ {
-		cov1 := randCover(rnd, 20)
-		cov2 := randCover(rnd, 20)
-		diff := Difference(cov1, cov2)
-		hasDiff := HasDifference(cov1, cov2)
-		if len(diff) != 0 != hasDiff {
-			t.Fatalf("cov1=%+v cov2=%+v diff=%+v hasDiff=%v", cov1, cov2, diff, hasDiff)
-		}
-	}
-}
-
-func BenchmarkHasDifference(b *testing.B) {
-	rnd := rand.New(rand.NewSource(0))
-	cov0 := make(Cover, 70000)
-	for i := range cov0 {
-		cov0[i] = uint32(rnd.Intn(1 << 30))
-	}
-	cov1 := Canonicalize(append(Cover{}, cov0[:500]...))
-	cov0 = Canonicalize(cov0)
-	b.ResetTimer()
-	for i := 0; i < b.N; i++ {
-		_ = HasDifference(cov1, cov0)
-	}
-}
diff --git a/pkg/rpctype/rpctype.go b/pkg/rpctype/rpctype.go
index e4d62e2f0..d7fee32da 100644
--- a/pkg/rpctype/rpctype.go
+++ b/pkg/rpctype/rpctype.go
@@ -5,10 +5,14 @@
 // between various parts of the system.
 package rpctype
 
+import (
+	"github.com/google/syzkaller/pkg/signal"
+)
+
 type RpcInput struct {
 	Call   string
 	Prog   []byte
-	Signal []uint32
+	Signal signal.Serial
 	Cover  []uint32
 }
 
@@ -25,7 +29,7 @@ type ConnectArgs struct {
 type ConnectRes struct {
 	Prios        [][]float32
 	Inputs       []RpcInput
-	MaxSignal    []uint32
+	MaxSignal    signal.Serial
 	Candidates   []RpcCandidate
 	EnabledCalls string
 	NeedCheck    bool
@@ -54,14 +58,14 @@ type NewInputArgs struct {
 type PollArgs struct {
 	Name           string
 	NeedCandidates bool
-	MaxSignal      []uint32
+	MaxSignal      signal.Serial
 	Stats          map[string]uint64
 }
 
 type PollRes struct {
 	Candidates []RpcCandidate
 	NewInputs  []RpcInput
-	MaxSignal  []uint32
+	MaxSignal  signal.Serial
 }
 
 type HubConnectArgs struct {
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
+}