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