1 /* $OpenBSD: fuzz.c,v 1.8 2015/03/03 20:42:49 djm Exp $ */
2 /*
3 * Copyright (c) 2011 Damien Miller <djm@mindrot.org>
4 *
5 * Permission to use, copy, modify, and distribute this software for any
6 * purpose with or without fee is hereby granted, provided that the above
7 * copyright notice and this permission notice appear in all copies.
8 *
9 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
10 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
11 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
12 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
13 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
14 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
15 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
16 */
17
18 /* Utility functions/framework for fuzz tests */
19
20 #include <sys/types.h>
21 #include <sys/uio.h>
22
23 #include <assert.h>
24 #include <ctype.h>
25 #include <stdio.h>
26 #include <stdint.h>
27 #include <stdlib.h>
28 #include <string.h>
29 #include <signal.h>
30 #include <unistd.h>
31
32 #include "test_helper.h"
33 #include "atomicio.h"
34
35 /* #define FUZZ_DEBUG */
36
37 #ifdef FUZZ_DEBUG
38 # define FUZZ_DBG(x) do { \
39 printf("%s:%d %s: ", __FILE__, __LINE__, __func__); \
40 printf x; \
41 printf("\n"); \
42 fflush(stdout); \
43 } while (0)
44 #else
45 # define FUZZ_DBG(x)
46 #endif
47
48 /* For brevity later */
49 typedef unsigned long long fuzz_ullong;
50
51 /* For base-64 fuzzing */
52 static const char fuzz_b64chars[] =
53 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
54
55 struct fuzz {
56 /* Fuzz method currently in use */
57 int strategy;
58
59 /* Fuzz methods remaining */
60 int strategies;
61
62 /* Original seed data blob */
63 void *seed;
64 size_t slen;
65
66 /* Current working copy of seed with fuzz mutations applied */
67 u_char *fuzzed;
68
69 /* Used by fuzz methods */
70 size_t o1, o2;
71 };
72
73 static const char *
fuzz_ntop(u_int n)74 fuzz_ntop(u_int n)
75 {
76 switch (n) {
77 case 0:
78 return "NONE";
79 case FUZZ_1_BIT_FLIP:
80 return "FUZZ_1_BIT_FLIP";
81 case FUZZ_2_BIT_FLIP:
82 return "FUZZ_2_BIT_FLIP";
83 case FUZZ_1_BYTE_FLIP:
84 return "FUZZ_1_BYTE_FLIP";
85 case FUZZ_2_BYTE_FLIP:
86 return "FUZZ_2_BYTE_FLIP";
87 case FUZZ_TRUNCATE_START:
88 return "FUZZ_TRUNCATE_START";
89 case FUZZ_TRUNCATE_END:
90 return "FUZZ_TRUNCATE_END";
91 case FUZZ_BASE64:
92 return "FUZZ_BASE64";
93 default:
94 abort();
95 }
96 }
97
98 static int
fuzz_fmt(struct fuzz * fuzz,char * s,size_t n)99 fuzz_fmt(struct fuzz *fuzz, char *s, size_t n)
100 {
101 if (fuzz == NULL)
102 return -1;
103
104 switch (fuzz->strategy) {
105 case FUZZ_1_BIT_FLIP:
106 snprintf(s, n, "%s case %zu of %zu (bit: %zu)\n",
107 fuzz_ntop(fuzz->strategy),
108 fuzz->o1, fuzz->slen * 8, fuzz->o1);
109 return 0;
110 case FUZZ_2_BIT_FLIP:
111 snprintf(s, n, "%s case %llu of %llu (bits: %zu, %zu)\n",
112 fuzz_ntop(fuzz->strategy),
113 (((fuzz_ullong)fuzz->o2) * fuzz->slen * 8) + fuzz->o1,
114 ((fuzz_ullong)fuzz->slen * 8) * fuzz->slen * 8,
115 fuzz->o1, fuzz->o2);
116 return 0;
117 case FUZZ_1_BYTE_FLIP:
118 snprintf(s, n, "%s case %zu of %zu (byte: %zu)\n",
119 fuzz_ntop(fuzz->strategy),
120 fuzz->o1, fuzz->slen, fuzz->o1);
121 return 0;
122 case FUZZ_2_BYTE_FLIP:
123 snprintf(s, n, "%s case %llu of %llu (bytes: %zu, %zu)\n",
124 fuzz_ntop(fuzz->strategy),
125 (((fuzz_ullong)fuzz->o2) * fuzz->slen) + fuzz->o1,
126 ((fuzz_ullong)fuzz->slen) * fuzz->slen,
127 fuzz->o1, fuzz->o2);
128 return 0;
129 case FUZZ_TRUNCATE_START:
130 snprintf(s, n, "%s case %zu of %zu (offset: %zu)\n",
131 fuzz_ntop(fuzz->strategy),
132 fuzz->o1, fuzz->slen, fuzz->o1);
133 return 0;
134 case FUZZ_TRUNCATE_END:
135 snprintf(s, n, "%s case %zu of %zu (offset: %zu)\n",
136 fuzz_ntop(fuzz->strategy),
137 fuzz->o1, fuzz->slen, fuzz->o1);
138 return 0;
139 case FUZZ_BASE64:
140 assert(fuzz->o2 < sizeof(fuzz_b64chars) - 1);
141 snprintf(s, n, "%s case %llu of %llu (offset: %zu char: %c)\n",
142 fuzz_ntop(fuzz->strategy),
143 (fuzz->o1 * (fuzz_ullong)64) + fuzz->o2,
144 fuzz->slen * (fuzz_ullong)64, fuzz->o1,
145 fuzz_b64chars[fuzz->o2]);
146 return 0;
147 default:
148 return -1;
149 abort();
150 }
151 }
152
153 static void
dump(u_char * p,size_t len)154 dump(u_char *p, size_t len)
155 {
156 size_t i, j;
157
158 for (i = 0; i < len; i += 16) {
159 fprintf(stderr, "%.4zd: ", i);
160 for (j = i; j < i + 16; j++) {
161 if (j < len)
162 fprintf(stderr, "%02x ", p[j]);
163 else
164 fprintf(stderr, " ");
165 }
166 fprintf(stderr, " ");
167 for (j = i; j < i + 16; j++) {
168 if (j < len) {
169 if (isascii(p[j]) && isprint(p[j]))
170 fprintf(stderr, "%c", p[j]);
171 else
172 fprintf(stderr, ".");
173 }
174 }
175 fprintf(stderr, "\n");
176 }
177 }
178
179 void
fuzz_dump(struct fuzz * fuzz)180 fuzz_dump(struct fuzz *fuzz)
181 {
182 char buf[256];
183
184 if (fuzz_fmt(fuzz, buf, sizeof(buf)) != 0) {
185 fprintf(stderr, "%s: fuzz invalid\n", __func__);
186 abort();
187 }
188 fputs(buf, stderr);
189 fprintf(stderr, "fuzz original %p len = %zu\n", fuzz->seed, fuzz->slen);
190 dump(fuzz->seed, fuzz->slen);
191 fprintf(stderr, "fuzz context %p len = %zu\n", fuzz, fuzz_len(fuzz));
192 dump(fuzz_ptr(fuzz), fuzz_len(fuzz));
193 }
194
195 #ifdef SIGINFO
196 static struct fuzz *last_fuzz;
197
198 static void
siginfo(int unused)199 siginfo(int unused __attribute__((__unused__)))
200 {
201 char buf[256];
202
203 test_info(buf, sizeof(buf));
204 atomicio(vwrite, STDERR_FILENO, buf, strlen(buf));
205 if (last_fuzz != NULL) {
206 fuzz_fmt(last_fuzz, buf, sizeof(buf));
207 atomicio(vwrite, STDERR_FILENO, buf, strlen(buf));
208 }
209 }
210 #endif
211
212 struct fuzz *
fuzz_begin(u_int strategies,const void * p,size_t l)213 fuzz_begin(u_int strategies, const void *p, size_t l)
214 {
215 struct fuzz *ret = calloc(sizeof(*ret), 1);
216
217 assert(p != NULL);
218 assert(ret != NULL);
219 ret->seed = malloc(l);
220 assert(ret->seed != NULL);
221 memcpy(ret->seed, p, l);
222 ret->slen = l;
223 ret->strategies = strategies;
224
225 assert(ret->slen < SIZE_MAX / 8);
226 assert(ret->strategies <= (FUZZ_MAX|(FUZZ_MAX-1)));
227
228 FUZZ_DBG(("begin, ret = %p", ret));
229
230 fuzz_next(ret);
231
232 #ifdef SIGINFO
233 last_fuzz = ret;
234 signal(SIGINFO, siginfo);
235 #endif
236
237 return ret;
238 }
239
240 void
fuzz_cleanup(struct fuzz * fuzz)241 fuzz_cleanup(struct fuzz *fuzz)
242 {
243 FUZZ_DBG(("cleanup, fuzz = %p", fuzz));
244 #ifdef SIGINFO
245 last_fuzz = NULL;
246 signal(SIGINFO, SIG_DFL);
247 #endif
248 assert(fuzz != NULL);
249 assert(fuzz->seed != NULL);
250 assert(fuzz->fuzzed != NULL);
251 free(fuzz->seed);
252 free(fuzz->fuzzed);
253 free(fuzz);
254 }
255
256 static int
fuzz_strategy_done(struct fuzz * fuzz)257 fuzz_strategy_done(struct fuzz *fuzz)
258 {
259 FUZZ_DBG(("fuzz = %p, strategy = %s, o1 = %zu, o2 = %zu, slen = %zu",
260 fuzz, fuzz_ntop(fuzz->strategy), fuzz->o1, fuzz->o2, fuzz->slen));
261
262 switch (fuzz->strategy) {
263 case FUZZ_1_BIT_FLIP:
264 return fuzz->o1 >= fuzz->slen * 8;
265 case FUZZ_2_BIT_FLIP:
266 return fuzz->o2 >= fuzz->slen * 8;
267 case FUZZ_2_BYTE_FLIP:
268 return fuzz->o2 >= fuzz->slen;
269 case FUZZ_1_BYTE_FLIP:
270 case FUZZ_TRUNCATE_START:
271 case FUZZ_TRUNCATE_END:
272 case FUZZ_BASE64:
273 return fuzz->o1 >= fuzz->slen;
274 default:
275 abort();
276 }
277 }
278
279 void
fuzz_next(struct fuzz * fuzz)280 fuzz_next(struct fuzz *fuzz)
281 {
282 u_int i;
283
284 FUZZ_DBG(("start, fuzz = %p, strategy = %s, strategies = 0x%lx, "
285 "o1 = %zu, o2 = %zu, slen = %zu", fuzz, fuzz_ntop(fuzz->strategy),
286 (u_long)fuzz->strategies, fuzz->o1, fuzz->o2, fuzz->slen));
287
288 if (fuzz->strategy == 0 || fuzz_strategy_done(fuzz)) {
289 /* If we are just starting out, we need to allocate too */
290 if (fuzz->fuzzed == NULL) {
291 FUZZ_DBG(("alloc"));
292 fuzz->fuzzed = calloc(fuzz->slen, 1);
293 }
294 /* Pick next strategy */
295 FUZZ_DBG(("advance"));
296 for (i = 1; i <= FUZZ_MAX; i <<= 1) {
297 if ((fuzz->strategies & i) != 0) {
298 fuzz->strategy = i;
299 break;
300 }
301 }
302 FUZZ_DBG(("selected = %u", fuzz->strategy));
303 if (fuzz->strategy == 0) {
304 FUZZ_DBG(("done, no more strategies"));
305 return;
306 }
307 fuzz->strategies &= ~(fuzz->strategy);
308 fuzz->o1 = fuzz->o2 = 0;
309 }
310
311 assert(fuzz->fuzzed != NULL);
312
313 switch (fuzz->strategy) {
314 case FUZZ_1_BIT_FLIP:
315 assert(fuzz->o1 / 8 < fuzz->slen);
316 memcpy(fuzz->fuzzed, fuzz->seed, fuzz->slen);
317 fuzz->fuzzed[fuzz->o1 / 8] ^= 1 << (fuzz->o1 % 8);
318 fuzz->o1++;
319 break;
320 case FUZZ_2_BIT_FLIP:
321 assert(fuzz->o1 / 8 < fuzz->slen);
322 assert(fuzz->o2 / 8 < fuzz->slen);
323 memcpy(fuzz->fuzzed, fuzz->seed, fuzz->slen);
324 fuzz->fuzzed[fuzz->o1 / 8] ^= 1 << (fuzz->o1 % 8);
325 fuzz->fuzzed[fuzz->o2 / 8] ^= 1 << (fuzz->o2 % 8);
326 fuzz->o1++;
327 if (fuzz->o1 >= fuzz->slen * 8) {
328 fuzz->o1 = 0;
329 fuzz->o2++;
330 }
331 break;
332 case FUZZ_1_BYTE_FLIP:
333 assert(fuzz->o1 < fuzz->slen);
334 memcpy(fuzz->fuzzed, fuzz->seed, fuzz->slen);
335 fuzz->fuzzed[fuzz->o1] ^= 0xff;
336 fuzz->o1++;
337 break;
338 case FUZZ_2_BYTE_FLIP:
339 assert(fuzz->o1 < fuzz->slen);
340 assert(fuzz->o2 < fuzz->slen);
341 memcpy(fuzz->fuzzed, fuzz->seed, fuzz->slen);
342 fuzz->fuzzed[fuzz->o1] ^= 0xff;
343 fuzz->fuzzed[fuzz->o2] ^= 0xff;
344 fuzz->o1++;
345 if (fuzz->o1 >= fuzz->slen) {
346 fuzz->o1 = 0;
347 fuzz->o2++;
348 }
349 break;
350 case FUZZ_TRUNCATE_START:
351 case FUZZ_TRUNCATE_END:
352 assert(fuzz->o1 < fuzz->slen);
353 memcpy(fuzz->fuzzed, fuzz->seed, fuzz->slen);
354 fuzz->o1++;
355 break;
356 case FUZZ_BASE64:
357 assert(fuzz->o1 < fuzz->slen);
358 assert(fuzz->o2 < sizeof(fuzz_b64chars) - 1);
359 memcpy(fuzz->fuzzed, fuzz->seed, fuzz->slen);
360 fuzz->fuzzed[fuzz->o1] = fuzz_b64chars[fuzz->o2];
361 fuzz->o2++;
362 if (fuzz->o2 >= sizeof(fuzz_b64chars) - 1) {
363 fuzz->o2 = 0;
364 fuzz->o1++;
365 }
366 break;
367 default:
368 abort();
369 }
370
371 FUZZ_DBG(("done, fuzz = %p, strategy = %s, strategies = 0x%lx, "
372 "o1 = %zu, o2 = %zu, slen = %zu", fuzz, fuzz_ntop(fuzz->strategy),
373 (u_long)fuzz->strategies, fuzz->o1, fuzz->o2, fuzz->slen));
374 }
375
376 int
fuzz_matches_original(struct fuzz * fuzz)377 fuzz_matches_original(struct fuzz *fuzz)
378 {
379 if (fuzz_len(fuzz) != fuzz->slen)
380 return 0;
381 return memcmp(fuzz_ptr(fuzz), fuzz->seed, fuzz->slen) == 0;
382 }
383
384 int
fuzz_done(struct fuzz * fuzz)385 fuzz_done(struct fuzz *fuzz)
386 {
387 FUZZ_DBG(("fuzz = %p, strategies = 0x%lx", fuzz,
388 (u_long)fuzz->strategies));
389
390 return fuzz_strategy_done(fuzz) && fuzz->strategies == 0;
391 }
392
393 size_t
fuzz_len(struct fuzz * fuzz)394 fuzz_len(struct fuzz *fuzz)
395 {
396 assert(fuzz->fuzzed != NULL);
397 switch (fuzz->strategy) {
398 case FUZZ_1_BIT_FLIP:
399 case FUZZ_2_BIT_FLIP:
400 case FUZZ_1_BYTE_FLIP:
401 case FUZZ_2_BYTE_FLIP:
402 case FUZZ_BASE64:
403 return fuzz->slen;
404 case FUZZ_TRUNCATE_START:
405 case FUZZ_TRUNCATE_END:
406 assert(fuzz->o1 <= fuzz->slen);
407 return fuzz->slen - fuzz->o1;
408 default:
409 abort();
410 }
411 }
412
413 u_char *
fuzz_ptr(struct fuzz * fuzz)414 fuzz_ptr(struct fuzz *fuzz)
415 {
416 assert(fuzz->fuzzed != NULL);
417 switch (fuzz->strategy) {
418 case FUZZ_1_BIT_FLIP:
419 case FUZZ_2_BIT_FLIP:
420 case FUZZ_1_BYTE_FLIP:
421 case FUZZ_2_BYTE_FLIP:
422 case FUZZ_BASE64:
423 return fuzz->fuzzed;
424 case FUZZ_TRUNCATE_START:
425 assert(fuzz->o1 <= fuzz->slen);
426 return fuzz->fuzzed + fuzz->o1;
427 case FUZZ_TRUNCATE_END:
428 assert(fuzz->o1 <= fuzz->slen);
429 return fuzz->fuzzed;
430 default:
431 abort();
432 }
433 }
434
435