forked from DynamoRIO/drmemory
-
Notifications
You must be signed in to change notification settings - Fork 0
/
drfuzz.dox
268 lines (213 loc) · 12.6 KB
/
drfuzz.dox
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 (c) 2014-2016 Google, Inc. All rights reserved.
* **********************************************************/
/*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
* * Redistributions of source code must retain the above copyright notice,
* this list of conditions and the following disclaimer.
*
* * Redistributions in binary form must reproduce the above copyright notice,
* this list of conditions and the following disclaimer in the documentation
* and/or other materials provided with the distribution.
*
* * Neither the name of Google, Inc. nor the names of its contributors may be
* used to endorse or promote products derived from this software without
* specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL GOOGLE, INC. OR CONTRIBUTORS BE LIABLE
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
* SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
* CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
* DAMAGE.
*/
/**
***************************************************************************
***************************************************************************
\page page_drfuzz Dr. Fuzz: Dynamic Fuzz Testing Extension
The Dr. Fuzz DynamoRIO Extension provides fuzz testing features.
Dr. Fuzz is part of the Dr. Memory Framework.
Dr. Fuzz is used to implement the
\if TOOL_DR_MEMORY Dr. Memory \ref page_fuzzer \else fuzz testing mode \endif.
- \ref sec_drfuzz_setup
- \ref sec_drfuzz_API
- \ref sec_drfuzz_mutators Mutators
\section sec_drfuzz_setup Setup
To use \p Dr. Fuzz with your client, first locate the Dr. Memory
Framework. Then use the standard method of using an Extension with the
name \p drfuzz. The two steps will look like this in your client's
\p CMakeLists.txt file:
\code
find_package(DrMemoryFramework)
use_DynamoRIO_extension(clientname drfuzz)
\endcode
To point CMake at the framework, set the DrMemoryFramework_DIR variable to
point at the \p drmf subdirectory of the Dr. Memory package that you are
using. For example:
\code
cmake -G"Ninja" -DDynamoRIO_DIR=c:/path/to/DynamoRIO-Windows-4.1.0-8/cmake -DDrMemoryFramework_DIR=c:/path/to/DrMemory-Windows-1.6.0-2/drmf ../mysrcs/
\endcode
That will automatically set up the include path and library dependence.
Your client must call \p drfuzz_init() prior to accessing any API
routines in \p drfuzz, and should call \p drfuzz_exit() at process exit
time.
\section sec_drfuzz_API Dr. Fuzz API
\p Dr. Fuzz provides the following key features:
-# Repeat execution of the test target function with fuzzed arguments.
-# Mutate argument values using bit flipping, random number algorithms,
or custom user-provided mutators.
-# Schedule fuzz iterations for a target function and set of arguments.
-# Report state information on a crash caused by fuzz inputs.
The client can use the provided Dr. Fuzz APIs to fuzz test the target application. The
most flexible approach is to use Dr. Fuzz directly to control the
fuzzing cycle using registered callbacks. This approach also requires the most effort, so
users who wish to get going quickly may prefer to use Dr. Memory's fuzzing
features, which leverage Dr. Fuzz.
\section sec_drfuzz_mutators Dr. Fuzz Mutators
To support custom mutators, mutation is performed by a libary separate from
the main \p Dr. Fuzz control library. \p Dr. Fuzz provides a default
mutator library which contains several different mutator implementations.
\subsection sec_drfuzz_mut_ops Default Mutator Options
The default mutator built-in to \p Dr. Fuzz supports several mutation
variations, controlled by the following options (which are passed to
drfuzz_mutator_start()):
- -alg <algorithm_name><br>
Specifies the algorithm for generating a new value. The choices are:
- "random": Randomly search the domain of possible permutations.
This is the default for -unit token.
- "ordered": Exhaustively search all possible permutations in an ordered
manner. This is the default for -unit bits and -unit num.
- -unit <unit_name><br>
Specifies the unit of transformation for applying the mutation algorithm.
The choices are:
- "bits": Bitwise application of the mutation algorithm. This is the default.
- "num": Numeric application of the mutation algorithm.
- "token": Insertion of tokens from a dictionary. The dictionary must
be specified via -dictionary.
- -flags <int><br>
Flags for the mutator. Some flags are specific to a particular algorithm and/or
mutation unit. The choices are:
- 0x1: Reset the buffer contents to the input_seed after every bit-flip
mutation. Not valid for -unit num. On by default.
- 0x2: Seed the mutator's random number generator with the current clock time.
- -sparsity <int><br>
The degree of sparseness in the random coverage of the "random" algorithm
with unit "bits" (invalid for other configurations). Sparsity of n will yield on
average 1/n total values relative to the "ordered" algorithm in the same configuration.
If the sparsity is set to 0, the default value of 1 will be used instead.
- -max_value <uint64><br>
For buffers of size 8 bytes or smaller, specifies the maximum mutation value. Use
value 0 to disable the maximum value (i.e., limit only by the buffer capacity).
- -random_seed <uint64><br>
Set the randomization seed for algorithm "random".
The default random seed is 0x5a8390e9a31dc65fULL, which was selected to
have an equal number of 0 and 1 bits.
- -dictionary <path><br>
Specifies a dictionary file containing tokens for -unit token.
The file format is compatible with AFL (http://lcamtuf.coredump.cx/afl/).
It is a text file with one token, in double quotes, per line, with an
optional preceding name followed by an equals sign.
Non-printable characters must use \\x hex escapes, and double quotes and
backslashes must be escaped by a preceding backslash.
Comment lines starting with '#' can be included.
An example:
\code
"token42"
"different_token"
unprint="\xCD\xEF"
mytokA="internal\"quotes\""
\endcode
The default options are for ordered, seed-centric bit-flipping.
The algorithms are further described below.
\subsection sec_mutator_alg_and_unit Mutator Algorithms and Units
The default mutator provides two algorithms for mutating the fuzzed argument, ordered
and random, and each algorithm can operate in terms of bit-flips or integers.
The latter option is referred to as the "unit" of mutation. The behavior of
these two mutator options can be easily seen in the following example, where
the app's original argument value is all zero (at left), and each successive
value reflects one mutation:
Ordered bit-flip: 0x00000000 => 0x00000001 => 0x00000100 => 0x00010000 => 0x01000000
Random bit-flip: 0x00000000 => 0x00200000 => 0x00008000 => 0x00000004 => 0x00002000
Ordered numeric: 0x00000000 => 0x00000001 => 0x00000002 => 0x00000003 => 0x00000004
Random numeric: 0x00000000 => 0x7abcbb5e => 0xc6f15f41 => 0xaebd59a2 => 0xc375f0ae
Notice that the bit-flip unit does not flip bits in a lexical sequence, even
when the ordered algorithm is selected. Instead, it distributes the flips across
the bytes first, and secondarily across the bits of each byte. The goal is to
improve mutator coverage for very large input buffers, especially when the sparsity
option is used (see below). The following sequence illustrates how ordered bit-flip
distributes all permutations of a single flip across a 2-byte buffer:
0x0000 => 0x0001 => 0x0100 => 0x0002 => 0x0200 => 0x0004 => 0x0400 => 0x0008 => 0x0800
=> 0x0010 => 0x1000 => 0x0020 => 0x0200 => 0x0040 => 0x4000 => 0x0080 => 0x8000
After completing all flips of a single bit, the mutator will proceed to flip two bits:
0x0000 => 0x0101 => 0x0003 => 0x0201 => 0x0005 => 0x0401 => 0x0009 => 0x0801 => 0x0011
=> 0x1001 => 0x0021 => 0x2001 => 0x0041 => 0x4001 => 0x0081 => 0x8001 => 0x0006
\subsection sec_mutator_rand_gen Mutator Random Number Generator
The mutator uses a stateless xorshift algorithm for all of its randomized
decisions (see xorshift64star on https://en.wikipedia.org/wiki/Xorshift).
For randomized bit-flip, the mutator selects which bits to flip using the
Fisher-Yates shuffle (https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle).
To repeat a fuzz test using the exact same sequence of values for the fuzz
target function, specify the same random seed as the original fuzz test
using the mutator descriptor's optional last field; for example:
-fuzz_mutator "r|b|r|1|0x17a3cd8648a6ab1f"
To avoid repeating the exact same fuzz test when using the random algorithm,
and pass flag \p 't' in the mutator descriptor (field 3 in option
\p -fuzz_mutator) to seed the random algorithm with the system clock time. The
seed will be reported in the log and in the console output (when enabled) for
future reference, e.g., to repeat that fuzz test.
\subsection sec_mutator_proximity Mutator "Proximity" via Reset Option
Although the fuzzer executes the target function as rapidly as possible on
the given hardware (by redirecting execution directly from the function
return back into the function entry point), the number of possible values
for the fuzzed argument usually makes it impossible to try all permutations.
In many scenarios, the most interesting app functionality can be reached
using argument values that are very similar to a "correct" or "typical"
input value. For this reason, the fuzzer takes the original argument value
passed by the application as a starting point for mutation. To explore input
values that are most similar to the app's original input value, use flag
\p 'r' in the mutator descriptor (field 3 in option \p -fuzz_mutator) to
reset the argument to the app's original value before each mutation. Omitting
this flag will cause the successive mutations to accumulate. For example, a
bit-flipping mutator using the reset option might generate the following
sequence on a 4-byte buffer, where the first value is the app's original
argument value, and each successive value reflects one mutation (marked
with overstrike):
__ __ __ __
0x01020304 => 0x01020305 => 0x01020204 => 0x01030304 => 0x00020304
But the same mutator without the reset option would generate this sequence:
__ ____ ______ ________
0x01020304 => 0x01020305 => 0x01020205 => 0x01030205 => 0x00030205
As you can see, the mutated value remains very similar to the original input
when using the reset option, but quickly diverges without it.
\subsection sec_mutator_sparsity Mutator Sparsity
For many target functions, the reset option generates inputs that are too
similar, causing the majority of inputs to be redundant--yet completely
random input may also be ineffective. To generate a moderately diverse
range of input values, the sparsity can be specified in the mutator
descriptor (field 4 in option \p -fuzz_mutator). The term "sparsity" refers
to the coverage of the space of possible input values, where a sparsity of
1 indicates to first cover all values reachable by a single bit-flip of the
app's original argument value, then cover all values reachable by 2 bit-flips,
and so on. By increasing the sparsity, the mutator will reduce the number
of permutations it generates at each degree of bit flipping. The following
table provides an example of sparsity one, given a 4-byte input buffer:
Bit-Flip Degree Total Mutator Values
1 32
2 992
3 29760
By increasing the sparsity to just 4, the number of mutator values at each
degree of bit flipping is greatly reduced:
Bit-Flip Degree Total Mutator Values
1 8
2 248
3 7440
This second approach balances the diversity of input values with the
proximity of each generated input to the app's original argument value.
*/