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 *
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
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
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
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
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 *
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
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
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
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
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
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
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 *
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