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