1294332Sdes/* $OpenBSD: fuzz.c,v 1.8 2015/03/03 20:42:49 djm 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> 23294332Sdes#include <sys/uio.h> 24276707Sdes 25276707Sdes#include <assert.h> 26276707Sdes#include <ctype.h> 27276707Sdes#include <stdio.h> 28276707Sdes#ifdef HAVE_STDINT_H 29276707Sdes# include <stdint.h> 30276707Sdes#endif 31276707Sdes#include <stdlib.h> 32276707Sdes#include <string.h> 33294332Sdes#include <signal.h> 34294332Sdes#include <unistd.h> 35276707Sdes 36276707Sdes#include "test_helper.h" 37294332Sdes#include "atomicio.h" 38276707Sdes 39276707Sdes/* #define FUZZ_DEBUG */ 40276707Sdes 41276707Sdes#ifdef FUZZ_DEBUG 42276707Sdes# define FUZZ_DBG(x) do { \ 43276707Sdes printf("%s:%d %s: ", __FILE__, __LINE__, __func__); \ 44276707Sdes printf x; \ 45276707Sdes printf("\n"); \ 46276707Sdes fflush(stdout); \ 47276707Sdes } while (0) 48276707Sdes#else 49276707Sdes# define FUZZ_DBG(x) 50276707Sdes#endif 51276707Sdes 52276707Sdes/* For brevity later */ 53276707Sdestypedef unsigned long long fuzz_ullong; 54276707Sdes 55276707Sdes/* For base-64 fuzzing */ 56276707Sdesstatic const char fuzz_b64chars[] = 57276707Sdes "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"; 58276707Sdes 59276707Sdesstruct fuzz { 60276707Sdes /* Fuzz method currently in use */ 61276707Sdes int strategy; 62276707Sdes 63276707Sdes /* Fuzz methods remaining */ 64276707Sdes int strategies; 65276707Sdes 66276707Sdes /* Original seed data blob */ 67276707Sdes void *seed; 68276707Sdes size_t slen; 69276707Sdes 70276707Sdes /* Current working copy of seed with fuzz mutations applied */ 71276707Sdes u_char *fuzzed; 72276707Sdes 73276707Sdes /* Used by fuzz methods */ 74276707Sdes size_t o1, o2; 75276707Sdes}; 76276707Sdes 77276707Sdesstatic const char * 78276707Sdesfuzz_ntop(u_int n) 79276707Sdes{ 80276707Sdes switch (n) { 81276707Sdes case 0: 82276707Sdes return "NONE"; 83276707Sdes case FUZZ_1_BIT_FLIP: 84276707Sdes return "FUZZ_1_BIT_FLIP"; 85276707Sdes case FUZZ_2_BIT_FLIP: 86276707Sdes return "FUZZ_2_BIT_FLIP"; 87276707Sdes case FUZZ_1_BYTE_FLIP: 88276707Sdes return "FUZZ_1_BYTE_FLIP"; 89276707Sdes case FUZZ_2_BYTE_FLIP: 90276707Sdes return "FUZZ_2_BYTE_FLIP"; 91276707Sdes case FUZZ_TRUNCATE_START: 92276707Sdes return "FUZZ_TRUNCATE_START"; 93276707Sdes case FUZZ_TRUNCATE_END: 94276707Sdes return "FUZZ_TRUNCATE_END"; 95276707Sdes case FUZZ_BASE64: 96276707Sdes return "FUZZ_BASE64"; 97276707Sdes default: 98276707Sdes abort(); 99276707Sdes } 100276707Sdes} 101276707Sdes 102294332Sdesstatic int 103294332Sdesfuzz_fmt(struct fuzz *fuzz, char *s, size_t n) 104276707Sdes{ 105294332Sdes if (fuzz == NULL) 106294332Sdes return -1; 107276707Sdes 108276707Sdes switch (fuzz->strategy) { 109276707Sdes case FUZZ_1_BIT_FLIP: 110294332Sdes snprintf(s, n, "%s case %zu of %zu (bit: %zu)\n", 111276707Sdes fuzz_ntop(fuzz->strategy), 112276707Sdes fuzz->o1, fuzz->slen * 8, fuzz->o1); 113294332Sdes return 0; 114276707Sdes case FUZZ_2_BIT_FLIP: 115294332Sdes snprintf(s, n, "%s case %llu of %llu (bits: %zu, %zu)\n", 116276707Sdes fuzz_ntop(fuzz->strategy), 117276707Sdes (((fuzz_ullong)fuzz->o2) * fuzz->slen * 8) + fuzz->o1, 118276707Sdes ((fuzz_ullong)fuzz->slen * 8) * fuzz->slen * 8, 119276707Sdes fuzz->o1, fuzz->o2); 120294332Sdes return 0; 121276707Sdes case FUZZ_1_BYTE_FLIP: 122294332Sdes snprintf(s, n, "%s case %zu of %zu (byte: %zu)\n", 123276707Sdes fuzz_ntop(fuzz->strategy), 124276707Sdes fuzz->o1, fuzz->slen, fuzz->o1); 125294332Sdes return 0; 126276707Sdes case FUZZ_2_BYTE_FLIP: 127294332Sdes snprintf(s, n, "%s case %llu of %llu (bytes: %zu, %zu)\n", 128276707Sdes fuzz_ntop(fuzz->strategy), 129276707Sdes (((fuzz_ullong)fuzz->o2) * fuzz->slen) + fuzz->o1, 130276707Sdes ((fuzz_ullong)fuzz->slen) * fuzz->slen, 131276707Sdes fuzz->o1, fuzz->o2); 132294332Sdes return 0; 133276707Sdes case FUZZ_TRUNCATE_START: 134294332Sdes snprintf(s, n, "%s case %zu of %zu (offset: %zu)\n", 135276707Sdes fuzz_ntop(fuzz->strategy), 136276707Sdes fuzz->o1, fuzz->slen, fuzz->o1); 137294332Sdes return 0; 138276707Sdes case FUZZ_TRUNCATE_END: 139294332Sdes snprintf(s, n, "%s case %zu of %zu (offset: %zu)\n", 140276707Sdes fuzz_ntop(fuzz->strategy), 141276707Sdes fuzz->o1, fuzz->slen, fuzz->o1); 142294332Sdes return 0; 143276707Sdes case FUZZ_BASE64: 144276707Sdes assert(fuzz->o2 < sizeof(fuzz_b64chars) - 1); 145294332Sdes snprintf(s, n, "%s case %llu of %llu (offset: %zu char: %c)\n", 146276707Sdes fuzz_ntop(fuzz->strategy), 147276707Sdes (fuzz->o1 * (fuzz_ullong)64) + fuzz->o2, 148276707Sdes fuzz->slen * (fuzz_ullong)64, fuzz->o1, 149276707Sdes fuzz_b64chars[fuzz->o2]); 150294332Sdes return 0; 151276707Sdes default: 152294332Sdes return -1; 153276707Sdes abort(); 154276707Sdes } 155294332Sdes} 156276707Sdes 157294332Sdesstatic void 158294332Sdesdump(u_char *p, size_t len) 159294332Sdes{ 160294332Sdes size_t i, j; 161294332Sdes 162276707Sdes for (i = 0; i < len; i += 16) { 163276707Sdes fprintf(stderr, "%.4zd: ", i); 164276707Sdes for (j = i; j < i + 16; j++) { 165276707Sdes if (j < len) 166276707Sdes fprintf(stderr, "%02x ", p[j]); 167276707Sdes else 168276707Sdes fprintf(stderr, " "); 169276707Sdes } 170276707Sdes fprintf(stderr, " "); 171276707Sdes for (j = i; j < i + 16; j++) { 172276707Sdes if (j < len) { 173276707Sdes if (isascii(p[j]) && isprint(p[j])) 174276707Sdes fprintf(stderr, "%c", p[j]); 175276707Sdes else 176276707Sdes fprintf(stderr, "."); 177276707Sdes } 178276707Sdes } 179276707Sdes fprintf(stderr, "\n"); 180276707Sdes } 181276707Sdes} 182276707Sdes 183294332Sdesvoid 184294332Sdesfuzz_dump(struct fuzz *fuzz) 185294332Sdes{ 186294332Sdes char buf[256]; 187294332Sdes 188294332Sdes if (fuzz_fmt(fuzz, buf, sizeof(buf)) != 0) { 189294332Sdes fprintf(stderr, "%s: fuzz invalid\n", __func__); 190294332Sdes abort(); 191294332Sdes } 192294332Sdes fputs(buf, stderr); 193294332Sdes fprintf(stderr, "fuzz original %p len = %zu\n", fuzz->seed, fuzz->slen); 194294332Sdes dump(fuzz->seed, fuzz->slen); 195294332Sdes fprintf(stderr, "fuzz context %p len = %zu\n", fuzz, fuzz_len(fuzz)); 196294332Sdes dump(fuzz_ptr(fuzz), fuzz_len(fuzz)); 197294332Sdes} 198294332Sdes 199294332Sdes#ifdef SIGINFO 200294332Sdesstatic struct fuzz *last_fuzz; 201294332Sdes 202294332Sdesstatic void 203294332Sdessiginfo(int unused __attribute__((__unused__))) 204294332Sdes{ 205294332Sdes char buf[256]; 206294332Sdes 207294332Sdes test_info(buf, sizeof(buf)); 208294332Sdes atomicio(vwrite, STDERR_FILENO, buf, strlen(buf)); 209294332Sdes if (last_fuzz != NULL) { 210294332Sdes fuzz_fmt(last_fuzz, buf, sizeof(buf)); 211294332Sdes atomicio(vwrite, STDERR_FILENO, buf, strlen(buf)); 212294332Sdes } 213294332Sdes} 214294332Sdes#endif 215294332Sdes 216276707Sdesstruct fuzz * 217276707Sdesfuzz_begin(u_int strategies, const void *p, size_t l) 218276707Sdes{ 219276707Sdes struct fuzz *ret = calloc(sizeof(*ret), 1); 220276707Sdes 221276707Sdes assert(p != NULL); 222276707Sdes assert(ret != NULL); 223276707Sdes ret->seed = malloc(l); 224276707Sdes assert(ret->seed != NULL); 225276707Sdes memcpy(ret->seed, p, l); 226276707Sdes ret->slen = l; 227276707Sdes ret->strategies = strategies; 228276707Sdes 229276707Sdes assert(ret->slen < SIZE_MAX / 8); 230276707Sdes assert(ret->strategies <= (FUZZ_MAX|(FUZZ_MAX-1))); 231276707Sdes 232276707Sdes FUZZ_DBG(("begin, ret = %p", ret)); 233276707Sdes 234276707Sdes fuzz_next(ret); 235294332Sdes 236294332Sdes#ifdef SIGINFO 237294332Sdes last_fuzz = ret; 238294332Sdes signal(SIGINFO, siginfo); 239294332Sdes#endif 240294332Sdes 241276707Sdes return ret; 242276707Sdes} 243276707Sdes 244276707Sdesvoid 245276707Sdesfuzz_cleanup(struct fuzz *fuzz) 246276707Sdes{ 247276707Sdes FUZZ_DBG(("cleanup, fuzz = %p", fuzz)); 248294332Sdes#ifdef SIGINFO 249294332Sdes last_fuzz = NULL; 250294332Sdes signal(SIGINFO, SIG_DFL); 251294332Sdes#endif 252276707Sdes assert(fuzz != NULL); 253276707Sdes assert(fuzz->seed != NULL); 254276707Sdes assert(fuzz->fuzzed != NULL); 255276707Sdes free(fuzz->seed); 256276707Sdes free(fuzz->fuzzed); 257276707Sdes free(fuzz); 258276707Sdes} 259276707Sdes 260276707Sdesstatic int 261276707Sdesfuzz_strategy_done(struct fuzz *fuzz) 262276707Sdes{ 263276707Sdes FUZZ_DBG(("fuzz = %p, strategy = %s, o1 = %zu, o2 = %zu, slen = %zu", 264276707Sdes fuzz, fuzz_ntop(fuzz->strategy), fuzz->o1, fuzz->o2, fuzz->slen)); 265276707Sdes 266276707Sdes switch (fuzz->strategy) { 267276707Sdes case FUZZ_1_BIT_FLIP: 268276707Sdes return fuzz->o1 >= fuzz->slen * 8; 269276707Sdes case FUZZ_2_BIT_FLIP: 270276707Sdes return fuzz->o2 >= fuzz->slen * 8; 271276707Sdes case FUZZ_2_BYTE_FLIP: 272276707Sdes return fuzz->o2 >= fuzz->slen; 273276707Sdes case FUZZ_1_BYTE_FLIP: 274276707Sdes case FUZZ_TRUNCATE_START: 275276707Sdes case FUZZ_TRUNCATE_END: 276276707Sdes case FUZZ_BASE64: 277276707Sdes return fuzz->o1 >= fuzz->slen; 278276707Sdes default: 279276707Sdes abort(); 280276707Sdes } 281276707Sdes} 282276707Sdes 283276707Sdesvoid 284276707Sdesfuzz_next(struct fuzz *fuzz) 285276707Sdes{ 286276707Sdes u_int i; 287276707Sdes 288276707Sdes FUZZ_DBG(("start, fuzz = %p, strategy = %s, strategies = 0x%lx, " 289276707Sdes "o1 = %zu, o2 = %zu, slen = %zu", fuzz, fuzz_ntop(fuzz->strategy), 290276707Sdes (u_long)fuzz->strategies, fuzz->o1, fuzz->o2, fuzz->slen)); 291276707Sdes 292276707Sdes if (fuzz->strategy == 0 || fuzz_strategy_done(fuzz)) { 293276707Sdes /* If we are just starting out, we need to allocate too */ 294276707Sdes if (fuzz->fuzzed == NULL) { 295276707Sdes FUZZ_DBG(("alloc")); 296276707Sdes fuzz->fuzzed = calloc(fuzz->slen, 1); 297276707Sdes } 298276707Sdes /* Pick next strategy */ 299276707Sdes FUZZ_DBG(("advance")); 300276707Sdes for (i = 1; i <= FUZZ_MAX; i <<= 1) { 301276707Sdes if ((fuzz->strategies & i) != 0) { 302276707Sdes fuzz->strategy = i; 303276707Sdes break; 304276707Sdes } 305276707Sdes } 306276707Sdes FUZZ_DBG(("selected = %u", fuzz->strategy)); 307276707Sdes if (fuzz->strategy == 0) { 308276707Sdes FUZZ_DBG(("done, no more strategies")); 309276707Sdes return; 310276707Sdes } 311276707Sdes fuzz->strategies &= ~(fuzz->strategy); 312276707Sdes fuzz->o1 = fuzz->o2 = 0; 313276707Sdes } 314276707Sdes 315276707Sdes assert(fuzz->fuzzed != NULL); 316276707Sdes 317276707Sdes switch (fuzz->strategy) { 318276707Sdes case FUZZ_1_BIT_FLIP: 319276707Sdes assert(fuzz->o1 / 8 < fuzz->slen); 320276707Sdes memcpy(fuzz->fuzzed, fuzz->seed, fuzz->slen); 321276707Sdes fuzz->fuzzed[fuzz->o1 / 8] ^= 1 << (fuzz->o1 % 8); 322276707Sdes fuzz->o1++; 323276707Sdes break; 324276707Sdes case FUZZ_2_BIT_FLIP: 325276707Sdes assert(fuzz->o1 / 8 < fuzz->slen); 326276707Sdes assert(fuzz->o2 / 8 < fuzz->slen); 327276707Sdes memcpy(fuzz->fuzzed, fuzz->seed, fuzz->slen); 328276707Sdes fuzz->fuzzed[fuzz->o1 / 8] ^= 1 << (fuzz->o1 % 8); 329276707Sdes fuzz->fuzzed[fuzz->o2 / 8] ^= 1 << (fuzz->o2 % 8); 330276707Sdes fuzz->o1++; 331276707Sdes if (fuzz->o1 >= fuzz->slen * 8) { 332276707Sdes fuzz->o1 = 0; 333276707Sdes fuzz->o2++; 334276707Sdes } 335276707Sdes break; 336276707Sdes case FUZZ_1_BYTE_FLIP: 337276707Sdes assert(fuzz->o1 < fuzz->slen); 338276707Sdes memcpy(fuzz->fuzzed, fuzz->seed, fuzz->slen); 339276707Sdes fuzz->fuzzed[fuzz->o1] ^= 0xff; 340276707Sdes fuzz->o1++; 341276707Sdes break; 342276707Sdes case FUZZ_2_BYTE_FLIP: 343276707Sdes assert(fuzz->o1 < fuzz->slen); 344276707Sdes assert(fuzz->o2 < fuzz->slen); 345276707Sdes memcpy(fuzz->fuzzed, fuzz->seed, fuzz->slen); 346276707Sdes fuzz->fuzzed[fuzz->o1] ^= 0xff; 347276707Sdes fuzz->fuzzed[fuzz->o2] ^= 0xff; 348276707Sdes fuzz->o1++; 349276707Sdes if (fuzz->o1 >= fuzz->slen) { 350276707Sdes fuzz->o1 = 0; 351276707Sdes fuzz->o2++; 352276707Sdes } 353276707Sdes break; 354276707Sdes case FUZZ_TRUNCATE_START: 355276707Sdes case FUZZ_TRUNCATE_END: 356276707Sdes assert(fuzz->o1 < fuzz->slen); 357276707Sdes memcpy(fuzz->fuzzed, fuzz->seed, fuzz->slen); 358276707Sdes fuzz->o1++; 359276707Sdes break; 360276707Sdes case FUZZ_BASE64: 361276707Sdes assert(fuzz->o1 < fuzz->slen); 362276707Sdes assert(fuzz->o2 < sizeof(fuzz_b64chars) - 1); 363276707Sdes memcpy(fuzz->fuzzed, fuzz->seed, fuzz->slen); 364276707Sdes fuzz->fuzzed[fuzz->o1] = fuzz_b64chars[fuzz->o2]; 365276707Sdes fuzz->o2++; 366276707Sdes if (fuzz->o2 >= sizeof(fuzz_b64chars) - 1) { 367276707Sdes fuzz->o2 = 0; 368276707Sdes fuzz->o1++; 369276707Sdes } 370276707Sdes break; 371276707Sdes default: 372276707Sdes abort(); 373276707Sdes } 374276707Sdes 375276707Sdes FUZZ_DBG(("done, fuzz = %p, strategy = %s, strategies = 0x%lx, " 376276707Sdes "o1 = %zu, o2 = %zu, slen = %zu", fuzz, fuzz_ntop(fuzz->strategy), 377276707Sdes (u_long)fuzz->strategies, fuzz->o1, fuzz->o2, fuzz->slen)); 378276707Sdes} 379276707Sdes 380276707Sdesint 381294332Sdesfuzz_matches_original(struct fuzz *fuzz) 382294332Sdes{ 383294332Sdes if (fuzz_len(fuzz) != fuzz->slen) 384294332Sdes return 0; 385294332Sdes return memcmp(fuzz_ptr(fuzz), fuzz->seed, fuzz->slen) == 0; 386294332Sdes} 387294332Sdes 388294332Sdesint 389276707Sdesfuzz_done(struct fuzz *fuzz) 390276707Sdes{ 391276707Sdes FUZZ_DBG(("fuzz = %p, strategies = 0x%lx", fuzz, 392276707Sdes (u_long)fuzz->strategies)); 393276707Sdes 394276707Sdes return fuzz_strategy_done(fuzz) && fuzz->strategies == 0; 395276707Sdes} 396276707Sdes 397276707Sdessize_t 398276707Sdesfuzz_len(struct fuzz *fuzz) 399276707Sdes{ 400276707Sdes assert(fuzz->fuzzed != NULL); 401276707Sdes switch (fuzz->strategy) { 402276707Sdes case FUZZ_1_BIT_FLIP: 403276707Sdes case FUZZ_2_BIT_FLIP: 404276707Sdes case FUZZ_1_BYTE_FLIP: 405276707Sdes case FUZZ_2_BYTE_FLIP: 406276707Sdes case FUZZ_BASE64: 407276707Sdes return fuzz->slen; 408276707Sdes case FUZZ_TRUNCATE_START: 409276707Sdes case FUZZ_TRUNCATE_END: 410276707Sdes assert(fuzz->o1 <= fuzz->slen); 411276707Sdes return fuzz->slen - fuzz->o1; 412276707Sdes default: 413276707Sdes abort(); 414276707Sdes } 415276707Sdes} 416276707Sdes 417276707Sdesu_char * 418276707Sdesfuzz_ptr(struct fuzz *fuzz) 419276707Sdes{ 420276707Sdes assert(fuzz->fuzzed != NULL); 421276707Sdes switch (fuzz->strategy) { 422276707Sdes case FUZZ_1_BIT_FLIP: 423276707Sdes case FUZZ_2_BIT_FLIP: 424276707Sdes case FUZZ_1_BYTE_FLIP: 425276707Sdes case FUZZ_2_BYTE_FLIP: 426276707Sdes case FUZZ_BASE64: 427276707Sdes return fuzz->fuzzed; 428276707Sdes case FUZZ_TRUNCATE_START: 429276707Sdes assert(fuzz->o1 <= fuzz->slen); 430276707Sdes return fuzz->fuzzed + fuzz->o1; 431276707Sdes case FUZZ_TRUNCATE_END: 432276707Sdes assert(fuzz->o1 <= fuzz->slen); 433276707Sdes return fuzz->fuzzed; 434276707Sdes default: 435276707Sdes abort(); 436276707Sdes } 437276707Sdes} 438276707Sdes 439