forked from google/syzkaller
-
Notifications
You must be signed in to change notification settings - Fork 1
/
cover.go
184 lines (163 loc) · 3.7 KB
/
cover.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
// 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
import (
"sort"
)
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)
}
}
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++
}
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
// loop accumulates all Covers that touch at least 1 new PC
for _, pc := range inp.cov {
if !hit {
if _, ok := covered[pc]; !ok {
hit = true
min = append(min, inp.idx)
}
}
if hit {
covered[pc] = struct{}{}
}
}
}
// min is the list of indices of covers that hit new PCs
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
}
func SignalAdd(base map[uint32]struct{}, signal []uint32) {
for _, s := range signal {
base[s] = struct{}{}
}
}