fuzz.c revision 276707
1276707Sdes/* $OpenBSD: fuzz.c,v 1.3 2014/05/02 09:41:32 andre Exp $ */ 2276707Sdes/* 3276707Sdes * Copyright (c) 2011 Damien Miller <djm@mindrot.org> 4276707Sdes * 5276707Sdes * Permission to use, copy, modify, and distribute this software for any 6276707Sdes * purpose with or without fee is hereby granted, provided that the above 7276707Sdes * copyright notice and this permission notice appear in all copies. 8276707Sdes * 9276707Sdes * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 10276707Sdes * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 11276707Sdes * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 12276707Sdes * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 13276707Sdes * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 14276707Sdes * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 15276707Sdes * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 16276707Sdes */ 17276707Sdes 18276707Sdes/* Utility functions/framework for fuzz tests */ 19276707Sdes 20276707Sdes#include "includes.h" 21276707Sdes 22276707Sdes#include <sys/types.h> 23276707Sdes 24276707Sdes#include <assert.h> 25276707Sdes#include <ctype.h> 26276707Sdes#include <stdio.h> 27276707Sdes#ifdef HAVE_STDINT_H 28276707Sdes# include <stdint.h> 29276707Sdes#endif 30276707Sdes#include <stdlib.h> 31276707Sdes#include <string.h> 32276707Sdes#include <assert.h> 33276707Sdes 34276707Sdes#include "test_helper.h" 35276707Sdes 36276707Sdes/* #define FUZZ_DEBUG */ 37276707Sdes 38276707Sdes#ifdef FUZZ_DEBUG 39276707Sdes# define FUZZ_DBG(x) do { \ 40276707Sdes printf("%s:%d %s: ", __FILE__, __LINE__, __func__); \ 41276707Sdes printf x; \ 42276707Sdes printf("\n"); \ 43276707Sdes fflush(stdout); \ 44276707Sdes } while (0) 45276707Sdes#else 46276707Sdes# define FUZZ_DBG(x) 47276707Sdes#endif 48276707Sdes 49276707Sdes/* For brevity later */ 50276707Sdestypedef unsigned long long fuzz_ullong; 51276707Sdes 52276707Sdes/* For base-64 fuzzing */ 53276707Sdesstatic const char fuzz_b64chars[] = 54276707Sdes "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"; 55276707Sdes 56276707Sdesstruct fuzz { 57276707Sdes /* Fuzz method currently in use */ 58276707Sdes int strategy; 59276707Sdes 60276707Sdes /* Fuzz methods remaining */ 61276707Sdes int strategies; 62276707Sdes 63276707Sdes /* Original seed data blob */ 64276707Sdes void *seed; 65276707Sdes size_t slen; 66276707Sdes 67276707Sdes /* Current working copy of seed with fuzz mutations applied */ 68276707Sdes u_char *fuzzed; 69276707Sdes 70276707Sdes /* Used by fuzz methods */ 71276707Sdes size_t o1, o2; 72276707Sdes}; 73276707Sdes 74276707Sdesstatic const char * 75276707Sdesfuzz_ntop(u_int n) 76276707Sdes{ 77276707Sdes switch (n) { 78276707Sdes case 0: 79276707Sdes return "NONE"; 80276707Sdes case FUZZ_1_BIT_FLIP: 81276707Sdes return "FUZZ_1_BIT_FLIP"; 82276707Sdes case FUZZ_2_BIT_FLIP: 83276707Sdes return "FUZZ_2_BIT_FLIP"; 84276707Sdes case FUZZ_1_BYTE_FLIP: 85276707Sdes return "FUZZ_1_BYTE_FLIP"; 86276707Sdes case FUZZ_2_BYTE_FLIP: 87276707Sdes return "FUZZ_2_BYTE_FLIP"; 88276707Sdes case FUZZ_TRUNCATE_START: 89276707Sdes return "FUZZ_TRUNCATE_START"; 90276707Sdes case FUZZ_TRUNCATE_END: 91276707Sdes return "FUZZ_TRUNCATE_END"; 92276707Sdes case FUZZ_BASE64: 93276707Sdes return "FUZZ_BASE64"; 94276707Sdes default: 95276707Sdes abort(); 96276707Sdes } 97276707Sdes} 98276707Sdes 99276707Sdesvoid 100276707Sdesfuzz_dump(struct fuzz *fuzz) 101276707Sdes{ 102276707Sdes u_char *p = fuzz_ptr(fuzz); 103276707Sdes size_t i, j, len = fuzz_len(fuzz); 104276707Sdes 105276707Sdes switch (fuzz->strategy) { 106276707Sdes case FUZZ_1_BIT_FLIP: 107276707Sdes fprintf(stderr, "%s case %zu of %zu (bit: %zu)\n", 108276707Sdes fuzz_ntop(fuzz->strategy), 109276707Sdes fuzz->o1, fuzz->slen * 8, fuzz->o1); 110276707Sdes break; 111276707Sdes case FUZZ_2_BIT_FLIP: 112276707Sdes fprintf(stderr, "%s case %llu of %llu (bits: %zu, %zu)\n", 113276707Sdes fuzz_ntop(fuzz->strategy), 114276707Sdes (((fuzz_ullong)fuzz->o2) * fuzz->slen * 8) + fuzz->o1, 115276707Sdes ((fuzz_ullong)fuzz->slen * 8) * fuzz->slen * 8, 116276707Sdes fuzz->o1, fuzz->o2); 117276707Sdes break; 118276707Sdes case FUZZ_1_BYTE_FLIP: 119276707Sdes fprintf(stderr, "%s case %zu of %zu (byte: %zu)\n", 120276707Sdes fuzz_ntop(fuzz->strategy), 121276707Sdes fuzz->o1, fuzz->slen, fuzz->o1); 122276707Sdes break; 123276707Sdes case FUZZ_2_BYTE_FLIP: 124276707Sdes fprintf(stderr, "%s case %llu of %llu (bytes: %zu, %zu)\n", 125276707Sdes fuzz_ntop(fuzz->strategy), 126276707Sdes (((fuzz_ullong)fuzz->o2) * fuzz->slen) + fuzz->o1, 127276707Sdes ((fuzz_ullong)fuzz->slen) * fuzz->slen, 128276707Sdes fuzz->o1, fuzz->o2); 129276707Sdes break; 130276707Sdes case FUZZ_TRUNCATE_START: 131276707Sdes fprintf(stderr, "%s case %zu of %zu (offset: %zu)\n", 132276707Sdes fuzz_ntop(fuzz->strategy), 133276707Sdes fuzz->o1, fuzz->slen, fuzz->o1); 134276707Sdes break; 135276707Sdes case FUZZ_TRUNCATE_END: 136276707Sdes fprintf(stderr, "%s case %zu of %zu (offset: %zu)\n", 137276707Sdes fuzz_ntop(fuzz->strategy), 138276707Sdes fuzz->o1, fuzz->slen, fuzz->o1); 139276707Sdes break; 140276707Sdes case FUZZ_BASE64: 141276707Sdes assert(fuzz->o2 < sizeof(fuzz_b64chars) - 1); 142276707Sdes fprintf(stderr, "%s case %llu of %llu (offset: %zu char: %c)\n", 143276707Sdes fuzz_ntop(fuzz->strategy), 144276707Sdes (fuzz->o1 * (fuzz_ullong)64) + fuzz->o2, 145276707Sdes fuzz->slen * (fuzz_ullong)64, fuzz->o1, 146276707Sdes fuzz_b64chars[fuzz->o2]); 147276707Sdes break; 148276707Sdes default: 149276707Sdes abort(); 150276707Sdes } 151276707Sdes 152276707Sdes fprintf(stderr, "fuzz context %p len = %zu\n", fuzz, len); 153276707Sdes for (i = 0; i < len; i += 16) { 154276707Sdes fprintf(stderr, "%.4zd: ", i); 155276707Sdes for (j = i; j < i + 16; j++) { 156276707Sdes if (j < len) 157276707Sdes fprintf(stderr, "%02x ", p[j]); 158276707Sdes else 159276707Sdes fprintf(stderr, " "); 160276707Sdes } 161276707Sdes fprintf(stderr, " "); 162276707Sdes for (j = i; j < i + 16; j++) { 163276707Sdes if (j < len) { 164276707Sdes if (isascii(p[j]) && isprint(p[j])) 165276707Sdes fprintf(stderr, "%c", p[j]); 166276707Sdes else 167276707Sdes fprintf(stderr, "."); 168276707Sdes } 169276707Sdes } 170276707Sdes fprintf(stderr, "\n"); 171276707Sdes } 172276707Sdes} 173276707Sdes 174276707Sdesstruct fuzz * 175276707Sdesfuzz_begin(u_int strategies, const void *p, size_t l) 176276707Sdes{ 177276707Sdes struct fuzz *ret = calloc(sizeof(*ret), 1); 178276707Sdes 179276707Sdes assert(p != NULL); 180276707Sdes assert(ret != NULL); 181276707Sdes ret->seed = malloc(l); 182276707Sdes assert(ret->seed != NULL); 183276707Sdes memcpy(ret->seed, p, l); 184276707Sdes ret->slen = l; 185276707Sdes ret->strategies = strategies; 186276707Sdes 187276707Sdes assert(ret->slen < SIZE_MAX / 8); 188276707Sdes assert(ret->strategies <= (FUZZ_MAX|(FUZZ_MAX-1))); 189276707Sdes 190276707Sdes FUZZ_DBG(("begin, ret = %p", ret)); 191276707Sdes 192276707Sdes fuzz_next(ret); 193276707Sdes return ret; 194276707Sdes} 195276707Sdes 196276707Sdesvoid 197276707Sdesfuzz_cleanup(struct fuzz *fuzz) 198276707Sdes{ 199276707Sdes FUZZ_DBG(("cleanup, fuzz = %p", fuzz)); 200276707Sdes assert(fuzz != NULL); 201276707Sdes assert(fuzz->seed != NULL); 202276707Sdes assert(fuzz->fuzzed != NULL); 203276707Sdes free(fuzz->seed); 204276707Sdes free(fuzz->fuzzed); 205276707Sdes free(fuzz); 206276707Sdes} 207276707Sdes 208276707Sdesstatic int 209276707Sdesfuzz_strategy_done(struct fuzz *fuzz) 210276707Sdes{ 211276707Sdes FUZZ_DBG(("fuzz = %p, strategy = %s, o1 = %zu, o2 = %zu, slen = %zu", 212276707Sdes fuzz, fuzz_ntop(fuzz->strategy), fuzz->o1, fuzz->o2, fuzz->slen)); 213276707Sdes 214276707Sdes switch (fuzz->strategy) { 215276707Sdes case FUZZ_1_BIT_FLIP: 216276707Sdes return fuzz->o1 >= fuzz->slen * 8; 217276707Sdes case FUZZ_2_BIT_FLIP: 218276707Sdes return fuzz->o2 >= fuzz->slen * 8; 219276707Sdes case FUZZ_2_BYTE_FLIP: 220276707Sdes return fuzz->o2 >= fuzz->slen; 221276707Sdes case FUZZ_1_BYTE_FLIP: 222276707Sdes case FUZZ_TRUNCATE_START: 223276707Sdes case FUZZ_TRUNCATE_END: 224276707Sdes case FUZZ_BASE64: 225276707Sdes return fuzz->o1 >= fuzz->slen; 226276707Sdes default: 227276707Sdes abort(); 228276707Sdes } 229276707Sdes} 230276707Sdes 231276707Sdesvoid 232276707Sdesfuzz_next(struct fuzz *fuzz) 233276707Sdes{ 234276707Sdes u_int i; 235276707Sdes 236276707Sdes FUZZ_DBG(("start, fuzz = %p, strategy = %s, strategies = 0x%lx, " 237276707Sdes "o1 = %zu, o2 = %zu, slen = %zu", fuzz, fuzz_ntop(fuzz->strategy), 238276707Sdes (u_long)fuzz->strategies, fuzz->o1, fuzz->o2, fuzz->slen)); 239276707Sdes 240276707Sdes if (fuzz->strategy == 0 || fuzz_strategy_done(fuzz)) { 241276707Sdes /* If we are just starting out, we need to allocate too */ 242276707Sdes if (fuzz->fuzzed == NULL) { 243276707Sdes FUZZ_DBG(("alloc")); 244276707Sdes fuzz->fuzzed = calloc(fuzz->slen, 1); 245276707Sdes } 246276707Sdes /* Pick next strategy */ 247276707Sdes FUZZ_DBG(("advance")); 248276707Sdes for (i = 1; i <= FUZZ_MAX; i <<= 1) { 249276707Sdes if ((fuzz->strategies & i) != 0) { 250276707Sdes fuzz->strategy = i; 251276707Sdes break; 252276707Sdes } 253276707Sdes } 254276707Sdes FUZZ_DBG(("selected = %u", fuzz->strategy)); 255276707Sdes if (fuzz->strategy == 0) { 256276707Sdes FUZZ_DBG(("done, no more strategies")); 257276707Sdes return; 258276707Sdes } 259276707Sdes fuzz->strategies &= ~(fuzz->strategy); 260276707Sdes fuzz->o1 = fuzz->o2 = 0; 261276707Sdes } 262276707Sdes 263276707Sdes assert(fuzz->fuzzed != NULL); 264276707Sdes 265276707Sdes switch (fuzz->strategy) { 266276707Sdes case FUZZ_1_BIT_FLIP: 267276707Sdes assert(fuzz->o1 / 8 < fuzz->slen); 268276707Sdes memcpy(fuzz->fuzzed, fuzz->seed, fuzz->slen); 269276707Sdes fuzz->fuzzed[fuzz->o1 / 8] ^= 1 << (fuzz->o1 % 8); 270276707Sdes fuzz->o1++; 271276707Sdes break; 272276707Sdes case FUZZ_2_BIT_FLIP: 273276707Sdes assert(fuzz->o1 / 8 < fuzz->slen); 274276707Sdes assert(fuzz->o2 / 8 < fuzz->slen); 275276707Sdes memcpy(fuzz->fuzzed, fuzz->seed, fuzz->slen); 276276707Sdes fuzz->fuzzed[fuzz->o1 / 8] ^= 1 << (fuzz->o1 % 8); 277276707Sdes fuzz->fuzzed[fuzz->o2 / 8] ^= 1 << (fuzz->o2 % 8); 278276707Sdes fuzz->o1++; 279276707Sdes if (fuzz->o1 >= fuzz->slen * 8) { 280276707Sdes fuzz->o1 = 0; 281276707Sdes fuzz->o2++; 282276707Sdes } 283276707Sdes break; 284276707Sdes case FUZZ_1_BYTE_FLIP: 285276707Sdes assert(fuzz->o1 < fuzz->slen); 286276707Sdes memcpy(fuzz->fuzzed, fuzz->seed, fuzz->slen); 287276707Sdes fuzz->fuzzed[fuzz->o1] ^= 0xff; 288276707Sdes fuzz->o1++; 289276707Sdes break; 290276707Sdes case FUZZ_2_BYTE_FLIP: 291276707Sdes assert(fuzz->o1 < fuzz->slen); 292276707Sdes assert(fuzz->o2 < fuzz->slen); 293276707Sdes memcpy(fuzz->fuzzed, fuzz->seed, fuzz->slen); 294276707Sdes fuzz->fuzzed[fuzz->o1] ^= 0xff; 295276707Sdes fuzz->fuzzed[fuzz->o2] ^= 0xff; 296276707Sdes fuzz->o1++; 297276707Sdes if (fuzz->o1 >= fuzz->slen) { 298276707Sdes fuzz->o1 = 0; 299276707Sdes fuzz->o2++; 300276707Sdes } 301276707Sdes break; 302276707Sdes case FUZZ_TRUNCATE_START: 303276707Sdes case FUZZ_TRUNCATE_END: 304276707Sdes assert(fuzz->o1 < fuzz->slen); 305276707Sdes memcpy(fuzz->fuzzed, fuzz->seed, fuzz->slen); 306276707Sdes fuzz->o1++; 307276707Sdes break; 308276707Sdes case FUZZ_BASE64: 309276707Sdes assert(fuzz->o1 < fuzz->slen); 310276707Sdes assert(fuzz->o2 < sizeof(fuzz_b64chars) - 1); 311276707Sdes memcpy(fuzz->fuzzed, fuzz->seed, fuzz->slen); 312276707Sdes fuzz->fuzzed[fuzz->o1] = fuzz_b64chars[fuzz->o2]; 313276707Sdes fuzz->o2++; 314276707Sdes if (fuzz->o2 >= sizeof(fuzz_b64chars) - 1) { 315276707Sdes fuzz->o2 = 0; 316276707Sdes fuzz->o1++; 317276707Sdes } 318276707Sdes break; 319276707Sdes default: 320276707Sdes abort(); 321276707Sdes } 322276707Sdes 323276707Sdes FUZZ_DBG(("done, fuzz = %p, strategy = %s, strategies = 0x%lx, " 324276707Sdes "o1 = %zu, o2 = %zu, slen = %zu", fuzz, fuzz_ntop(fuzz->strategy), 325276707Sdes (u_long)fuzz->strategies, fuzz->o1, fuzz->o2, fuzz->slen)); 326276707Sdes} 327276707Sdes 328276707Sdesint 329276707Sdesfuzz_done(struct fuzz *fuzz) 330276707Sdes{ 331276707Sdes FUZZ_DBG(("fuzz = %p, strategies = 0x%lx", fuzz, 332276707Sdes (u_long)fuzz->strategies)); 333276707Sdes 334276707Sdes return fuzz_strategy_done(fuzz) && fuzz->strategies == 0; 335276707Sdes} 336276707Sdes 337276707Sdessize_t 338276707Sdesfuzz_len(struct fuzz *fuzz) 339276707Sdes{ 340276707Sdes assert(fuzz->fuzzed != NULL); 341276707Sdes switch (fuzz->strategy) { 342276707Sdes case FUZZ_1_BIT_FLIP: 343276707Sdes case FUZZ_2_BIT_FLIP: 344276707Sdes case FUZZ_1_BYTE_FLIP: 345276707Sdes case FUZZ_2_BYTE_FLIP: 346276707Sdes case FUZZ_BASE64: 347276707Sdes return fuzz->slen; 348276707Sdes case FUZZ_TRUNCATE_START: 349276707Sdes case FUZZ_TRUNCATE_END: 350276707Sdes assert(fuzz->o1 <= fuzz->slen); 351276707Sdes return fuzz->slen - fuzz->o1; 352276707Sdes default: 353276707Sdes abort(); 354276707Sdes } 355276707Sdes} 356276707Sdes 357276707Sdesu_char * 358276707Sdesfuzz_ptr(struct fuzz *fuzz) 359276707Sdes{ 360276707Sdes assert(fuzz->fuzzed != NULL); 361276707Sdes switch (fuzz->strategy) { 362276707Sdes case FUZZ_1_BIT_FLIP: 363276707Sdes case FUZZ_2_BIT_FLIP: 364276707Sdes case FUZZ_1_BYTE_FLIP: 365276707Sdes case FUZZ_2_BYTE_FLIP: 366276707Sdes case FUZZ_BASE64: 367276707Sdes return fuzz->fuzzed; 368276707Sdes case FUZZ_TRUNCATE_START: 369276707Sdes assert(fuzz->o1 <= fuzz->slen); 370276707Sdes return fuzz->fuzzed + fuzz->o1; 371276707Sdes case FUZZ_TRUNCATE_END: 372276707Sdes assert(fuzz->o1 <= fuzz->slen); 373276707Sdes return fuzz->fuzzed; 374276707Sdes default: 375276707Sdes abort(); 376276707Sdes } 377276707Sdes} 378276707Sdes 379