fuzz.c revision 323134 
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 */
53typedef unsigned long long fuzz_ullong;
54
55/* For base-64 fuzzing */
56static const char fuzz_b64chars[] =
57    "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
58
59struct 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
77static const char *
78fuzz_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
102static int
103fuzz_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
157static void
158dump(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
183void
184fuzz_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
200static struct fuzz *last_fuzz;
201
202static void
203siginfo(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
216struct fuzz *
217fuzz_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
244void
245fuzz_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
260static int
261fuzz_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
283void
284fuzz_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
380int
381fuzz_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
388int
389fuzz_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
397size_t
398fuzz_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
417u_char *
418fuzz_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