forked from google/syzkaller
/
prio.go
265 lines (248 loc) · 6.91 KB
/
prio.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
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
// Copyright 2015/2016 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 prog
import (
"fmt"
"math/rand"
"sort"
)
// Calulation of call-to-call priorities.
// For a given pair of calls X and Y, the priority is our guess as to whether
// additional of call Y into a program containing call X is likely to give
// new coverage or not.
// The current algorithm has two components: static and dynamic.
// The static component is based on analysis of argument types. For example,
// if call X and call Y both accept fd[sock], then they are more likely to give
// new coverage together.
// The dynamic component is based on frequency of occurrence of a particular
// pair of syscalls in a single program in corpus. For example, if socket and
// connect frequently occur in programs together, we give higher priority to
// this pair of syscalls.
// Note: the current implementation is very basic, there is no theory behind any
// constants.
func (target *Target) CalculatePriorities(corpus []*Prog) [][]float32 {
static := target.calcStaticPriorities()
dynamic := target.calcDynamicPrio(corpus)
for i, prios := range static {
for j, p := range prios {
dynamic[i][j] *= p
}
}
return dynamic
return static
}
func (target *Target) calcStaticPriorities() [][]float32 {
uses := make(map[string]map[int]float32)
for _, c := range target.Syscalls {
noteUsage := func(weight float32, str string, args ...interface{}) {
id := fmt.Sprintf(str, args...)
if uses[id] == nil {
uses[id] = make(map[int]float32)
}
old := uses[id][c.ID]
if weight > old {
uses[id][c.ID] = weight
}
}
ForeachType(c, func(t Type) {
switch a := t.(type) {
case *ResourceType:
if a.Desc.Name == "pid" || a.Desc.Name == "uid" || a.Desc.Name == "gid" {
// Pid/uid/gid usually play auxiliary role,
// but massively happen in some structs.
noteUsage(0.1, "res%v", a.Desc.Name)
} else {
str := "res"
for i, k := range a.Desc.Kind {
str += "-" + k
w := 1.0
if i < len(a.Desc.Kind)-1 {
w = 0.2
}
noteUsage(float32(w), str)
}
}
case *PtrType:
if _, ok := a.Type.(*StructType); ok {
noteUsage(1.0, "ptrto-%v", a.Type.Name())
}
if _, ok := a.Type.(*UnionType); ok {
noteUsage(1.0, "ptrto-%v", a.Type.Name())
}
if arr, ok := a.Type.(*ArrayType); ok {
noteUsage(1.0, "ptrto-%v", arr.Type.Name())
}
case *BufferType:
switch a.Kind {
case BufferBlobRand, BufferBlobRange, BufferText:
case BufferString:
if a.SubKind != "" {
noteUsage(0.2, fmt.Sprintf("str-%v", a.SubKind))
}
case BufferFilename:
noteUsage(1.0, "filename")
default:
panic("unknown buffer kind")
}
case *VmaType:
noteUsage(0.5, "vma")
case *IntType:
switch a.Kind {
case IntPlain, IntFileoff, IntRange:
default:
panic("unknown int kind")
}
}
})
}
prios := make([][]float32, len(target.Syscalls))
for i := range prios {
prios[i] = make([]float32, len(target.Syscalls))
}
for _, calls := range uses {
for c0, w0 := range calls {
for c1, w1 := range calls {
if c0 == c1 {
// Self-priority is assigned below.
continue
}
prios[c0][c1] += w0 * w1
}
}
}
// Self-priority (call wrt itself) is assigned to the maximum priority
// this call has wrt other calls. This way the priority is high, but not too high.
for c0, pp := range prios {
var max float32
for _, p := range pp {
if max < p {
max = p
}
}
pp[c0] = max
}
normalizePrio(prios)
return prios
}
func (target *Target) calcDynamicPrio(corpus []*Prog) [][]float32 {
prios := make([][]float32, len(target.Syscalls))
for i := range prios {
prios[i] = make([]float32, len(target.Syscalls))
}
for _, p := range corpus {
for _, c0 := range p.Calls {
for _, c1 := range p.Calls {
id0 := c0.Meta.ID
id1 := c1.Meta.ID
// There are too many mmap's anyway.
if id0 == id1 || c0.Meta == target.MmapSyscall ||
c1.Meta == target.MmapSyscall {
continue
}
prios[id0][id1] += 1.0
}
}
}
normalizePrio(prios)
return prios
}
// normalizePrio assigns some minimal priorities to calls with zero priority,
// and then normalizes priorities to 0.1..1 range.
func normalizePrio(prios [][]float32) {
for _, prio := range prios {
max := float32(0)
min := float32(1e10)
nzero := 0
for _, p := range prio {
if max < p {
max = p
}
if p != 0 && min > p {
min = p
}
if p == 0 {
nzero++
}
}
if nzero != 0 {
min /= 2 * float32(nzero)
}
for i, p := range prio {
if max == 0 {
prio[i] = 1
continue
}
if p == 0 {
p = min
}
p = (p-min)/(max-min)*0.9 + 0.1
if p > 1 {
p = 1
}
prio[i] = p
}
}
}
// ChooseTable allows to do a weighted choice of a syscall for a given syscall
// based on call-to-call priorities and a set of enabled syscalls.
type ChoiceTable struct {
target *Target
run [][]int
enabledCalls []*Syscall
enabled map[*Syscall]bool
}
func (target *Target) BuildChoiceTable(prios [][]float32, enabled map[*Syscall]bool) *ChoiceTable {
if enabled == nil {
enabled = make(map[*Syscall]bool)
for _, c := range target.Syscalls {
enabled[c] = true
}
}
var enabledCalls []*Syscall
for c := range enabled {
enabledCalls = append(enabledCalls, c)
}
run := make([][]int, len(target.Syscalls))
for i := range run {
if !enabled[target.Syscalls[i]] {
continue
}
run[i] = make([]int, len(target.Syscalls))
sum := 0
for j := range run[i] {
if enabled[target.Syscalls[j]] {
sum += int(prios[i][j] * 1000)
}
run[i][j] = sum
}
}
return &ChoiceTable{target, run, enabledCalls, enabled}
}
func (ct *ChoiceTable) Choose(r *rand.Rand, call int) int {
if call < 0 {
return ct.enabledCalls[r.Intn(len(ct.enabledCalls))].ID
}
run := ct.run[call] // get array of prios for that specific call
if run == nil { // return random call, no prio info to judge
return ct.enabledCalls[r.Intn(len(ct.enabledCalls))].ID
}
for {
// ct is built via accumulation, so run[1 ... n] is monotonically increasing
// run[i+1] = run[i] + prios[i][j] * 1000
// we choose x to be a random number between [0, ..., run[n]]
// and because run is monotonically increasing, we thus have higher chance
// to select a call with a larger probability slice
// if the width of the entire array is run[n], the width of a single syscall i
// is prio[i][j] * 1000. Hence it takes up said percentage of the width.
// Thus the probability of selecting a particular syscall is equal exactly
// to its normalized priority. i.e. prio[a] = 5, prio[b] = 10, prio[c] = 5
// then run=[aaaaa,bbbbbbbbbb,cccccc], and probability of adding each syscall
// is .25, .5, .25, respectively.
x := r.Intn(run[len(run)-1])
i := sort.SearchInts(run, x)
if !ct.enabled[ct.target.Syscalls[i]] {
continue
}
return i
}
}