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