-
Notifications
You must be signed in to change notification settings - Fork 1
/
hints.go
268 lines (251 loc) · 7.8 KB
/
hints.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
266
267
268
// Copyright 2017 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
// A hint is basically a tuple consisting of a pointer to an argument
// in one of the syscalls of a program and a value, which should be
// assigned to that argument (we call it a replacer).
// A simplified version of hints workflow looks like this:
// 1. Fuzzer launches a program (we call it a hint seed) and collects all
// the comparisons' data for every syscall in the program.
// 2. Next it tries to match the obtained comparison operands' values
// vs. the input arguments' values.
// 3. For every such match the fuzzer mutates the program by
// replacing the pointed argument with the saved value.
// 4. If a valid program is obtained, then fuzzer launches it and
// checks if new coverage is obtained.
// For more insights on particular mutations please see prog/hints_test.go.
import (
"bytes"
"encoding/binary"
"fmt"
"sort"
)
// Example: for comparisons {(op1, op2), (op1, op3), (op1, op4), (op2, op1)}
// this map will store the following:
// m = {
// op1: {map[op2]: true, map[op3]: true, map[op4]: true},
// op2: {map[op1]: true}
// }.
type CompMap map[uint64]map[uint64]bool
const (
maxDataLength = 100
)
var specialIntsSet map[uint64]bool
func (m CompMap) AddComp(arg1, arg2 uint64) {
if _, ok := m[arg1]; !ok {
m[arg1] = make(map[uint64]bool)
}
m[arg1][arg2] = true
}
func (m CompMap) String() string {
buf := new(bytes.Buffer)
for v, comps := range m {
if len(buf.Bytes()) != 0 {
fmt.Fprintf(buf, ", ")
}
fmt.Fprintf(buf, "0x%x:", v)
for c := range comps {
fmt.Fprintf(buf, " 0x%x", c)
}
}
return buf.String()
}
// Mutates the program using the comparison operands stored in compMaps.
// For each of the mutants executes the exec callback.
func (p *Prog) MutateWithHints(callIndex int, comps CompMap, exec func(p *Prog)) {
p = p.Clone()
c := p.Calls[callIndex]
execValidate := func() {
p.Target.SanitizeCall(c)
p.debugValidate()
exec(p)
}
ForeachArg(c, func(arg Arg, _ *ArgCtx) {
generateHints(comps, arg, execValidate)
})
}
func generateHints(compMap CompMap, arg Arg, exec func()) {
typ := arg.Type()
if typ == nil || typ.Dir() == DirOut {
return
}
switch t := typ.(type) {
case *ProcType:
// Random proc will not pass validation.
// We can mutate it, but only if the resulting value is within the legal range.
return
case *ConstType:
if IsPad(typ) {
return
}
case *CsumType:
// Csum will not pass validation and is always computed.
return
case *BufferType:
switch t.Kind {
case BufferFilename:
// This can generate escaping paths and is probably not too useful anyway.
return
case BufferString:
if len(t.Values) != 0 {
// These are frequently file names or complete enumerations.
// Mutating these may be useful iff we intercept strcmp
// (and filter out file names).
return
}
}
}
switch a := arg.(type) {
case *ConstArg:
checkConstArg(a, compMap, exec)
case *DataArg:
checkDataArg(a, compMap, exec)
}
}
func checkConstArg(arg *ConstArg, compMap CompMap, exec func()) {
original := arg.Val
// Note: because shrinkExpand returns a map, order of programs is non-deterministic.
// This can affect test coverage reports.
for _, replacer := range shrinkExpand(original, compMap, arg.Type().TypeBitSize()) {
arg.Val = replacer
exec()
}
arg.Val = original
}
func checkDataArg(arg *DataArg, compMap CompMap, exec func()) {
bytes := make([]byte, 8)
data := arg.Data()
size := len(data)
if size > maxDataLength {
size = maxDataLength
}
for i := 0; i < size; i++ {
original := make([]byte, 8)
copy(original, data[i:])
val := binary.LittleEndian.Uint64(original)
for _, replacer := range shrinkExpand(val, compMap, 64) {
binary.LittleEndian.PutUint64(bytes, replacer)
copy(data[i:], bytes)
exec()
}
copy(data[i:], original)
}
}
// Shrink and expand mutations model the cases when the syscall arguments
// are casted to narrower (and wider) integer types.
// ======================================================================
// Motivation for shrink:
// void f(u16 x) {
// u8 y = (u8)x;
// if (y == 0xab) {...}
// }
// If we call f(0x1234), then we'll see a comparison 0x34 vs 0xab and we'll
// be unable to match the argument 0x1234 with any of the comparison operands.
// Thus we shrink 0x1234 to 0x34 and try to match 0x34.
// If there's a match for the shrank value, then we replace the corresponding
// bytes of the input (in the given example we'll get 0x12ab).
// Sometimes the other comparison operand will be wider than the shrank value
// (in the example above consider comparison if (y == 0xdeadbeef) {...}).
// In this case we ignore such comparison because we couldn't come up with
// any valid code example that does similar things. To avoid such comparisons
// we check the sizes with leastSize().
// ======================================================================
// Motivation for expand:
// void f(i8 x) {
// i16 y = (i16)x;
// if (y == -2) {...}
// }
// Suppose we call f(-1), then we'll see a comparison 0xffff vs 0xfffe and be
// unable to match input vs any operands. Thus we sign extend the input and
// check the extension.
// As with shrink we ignore cases when the other operand is wider.
// Note that executor sign extends all the comparison operands to int64.
// ======================================================================
func shrinkExpand(v uint64, compMap CompMap, bitsize uint64) []uint64 {
v = truncateToBitSize(v, bitsize)
limit := uint64(1<<bitsize - 1)
var replacers map[uint64]bool
for _, iwidth := range []int{8, 4, 2, 1, -4, -2, -1} {
var width int
var size, mutant uint64
if iwidth > 0 {
width = iwidth
size = uint64(width) * 8
mutant = v & ((1 << size) - 1)
} else {
width = -iwidth
size = uint64(width) * 8
if size > bitsize {
size = bitsize
}
if v&(1<<(size-1)) == 0 {
continue
}
mutant = v | ^((1 << size) - 1)
}
// Use big-endian match/replace for both blobs and ints.
// Sometimes we have unmarked blobs (no little/big-endian info);
// for ANYBLOBs we intentionally lose all marking;
// but even for marked ints we may need this too.
// Consider that kernel code does not convert the data
// (i.e. not ntohs(pkt->proto) == ETH_P_BATMAN),
// but instead converts the constant (i.e. pkt->proto == htons(ETH_P_BATMAN)).
// In such case we will see dynamic operand that does not match what we have in the program.
for _, bigendian := range []bool{false, true} {
if bigendian {
if width == 1 {
continue
}
mutant = swapInt(mutant, width)
}
for newV := range compMap[mutant] {
// Check the limit for negative numbers
if newV > limit && ((^(limit >> 1) & newV) != ^(limit >> 1)) {
continue
}
mask := uint64(1<<size - 1)
newHi := newV & ^mask
newV = newV & mask
if newHi != 0 && newHi^^mask != 0 {
continue
}
if bigendian {
newV = swapInt(newV, width)
}
if specialIntsSet[newV] {
continue
}
// Replace size least significant bits of v with
// corresponding bits of newV. Leave the rest of v as it was.
replacer := (v &^ mask) | newV
if replacer == v {
continue
}
replacer = truncateToBitSize(replacer, bitsize)
// TODO(dvyukov): should we try replacing with arg+/-1?
// This could trigger some off-by-ones.
if replacers == nil {
replacers = make(map[uint64]bool)
}
replacers[replacer] = true
}
}
}
if replacers == nil {
return nil
}
res := make([]uint64, 0, len(replacers))
for v := range replacers {
res = append(res, v)
}
sort.Slice(res, func(i, j int) bool {
return res[i] < res[j]
})
return res
}
func init() {
specialIntsSet = make(map[uint64]bool)
for _, v := range specialInts {
specialIntsSet[v] = true
}
}