AFLNET源码理解（四）

源码理解（四）"/>

AFLNET源码理解（四）

今天看看perform_dry_run()和fuzz_one()函数

perform_dry_run()

/* Perform dry run of all test cases to confirm that the app is working asexpected. This is done only for the initial inputs, and only once. */static void perform_dry_run(char** argv) {struct queue_entry* q = queue;u32 cal_failures = 0;u8* skip_crashes = getenv("AFL_SKIP_CRASHES");while (q) {u8* use_mem;u8  res;s32 fd;q->is_initial_seed = 1;u8* fn = strrchr(q->fname, '/') + 1;ACTF("Attempting dry run with '%s'...", fn);fd = open(q->fname, O_RDONLY);if (fd < 0) PFATAL("Unable to open '%s'", q->fname);use_mem = ck_alloc_nozero(q->len);if (read(fd, use_mem, q->len) != q->len)FATAL("Short read from '%s'", q->fname);close(fd);/* AFLNet construct the kl_messages linked list for this queue entry*/kl_messages = construct_kl_messages(q->fname, q->regions, q->region_count);res = calibrate_case(argv, q, use_mem, 0, 1);ck_free(use_mem);/* Update state-aware variables (e.g., state machine, regions and their annotations */if (state_aware_mode) update_state_aware_variables(q, 1);/* save the seed to file for replaying */u8 *fn_replay = alloc_printf("%s/replayable-queue/%s", out_dir, basename(q->fname));save_kl_messages_to_file(kl_messages, fn_replay, 1, messages_sent);ck_free(fn_replay);/* AFLNet delete the kl_messages */delete_kl_messages(kl_messages);if (stop_soon) return;if (res == crash_mode || res == FAULT_NOBITS)SAYF(cGRA "    len = %u, map size = %u, exec speed = %llu us\n" cRST,q->len, q->bitmap_size, q->exec_us);switch (res) {case FAULT_NONE:if (q == queue) check_map_coverage();if (crash_mode) FATAL("Test case '%s' does *NOT* crash", fn);break;case FAULT_TMOUT:if (timeout_given) {/* The -t nn+ syntax in the command line sets timeout_given to '2' andinstructs afl-fuzz to tolerate but skip queue entries that timeout. */if (timeout_given > 1) {WARNF("Test case results in a timeout (skipping)");q->cal_failed = CAL_CHANCES;cal_failures++;break;}SAYF("\n" cLRD "[-] " cRST"The program took more than %u ms to process one of the initial test cases.\n""    Usually, the right thing to do is to relax the -t option - or to delete it\n""    altogether and allow the fuzzer to auto-calibrate. That said, if you know\n""    what you are doing and want to simply skip the unruly test cases, append\n""    '+' at the end of the value passed to -t ('-t %u+').\n", exec_tmout,exec_tmout);FATAL("Test case '%s' results in a timeout", fn);} else {SAYF("\n" cLRD "[-] " cRST"The program took more than %u ms to process one of the initial test cases.\n""    This is bad news; raising the limit with the -t option is possible, but\n""    will probably make the fuzzing process extremely slow.\n\n""    If this test case is just a fluke, the other option is to just avoid it\n""    altogether, and find one that is less of a CPU hog.\n", exec_tmout);FATAL("Test case '%s' results in a timeout", fn);}case FAULT_CRASH:if (crash_mode) break;if (skip_crashes) {WARNF("Test case results in a crash (skipping)");q->cal_failed = CAL_CHANCES;cal_failures++;break;}if (mem_limit) {SAYF("\n" cLRD "[-] " cRST"Oops, the program crashed with one of the test cases provided. There are\n""    several possible explanations:\n\n""    - The test case causes known crashes under normal working conditions. If\n""      so, please remove it. The fuzzer should be seeded with interesting\n""      inputs - but not ones that cause an outright crash.\n\n""    - The current memory limit (%s) is too low for this program, causing\n""      it to die due to OOM when parsing valid files. To fix this, try\n""      bumping it up with the -m setting in the command line. If in doubt,\n""      try something along the lines of:\n\n"#ifdef RLIMIT_AS"      ( ulimit -Sv $[%llu << 10]; /path/to/binary [...] <testcase )\n\n"
#else"      ( ulimit -Sd $[%llu << 10]; /path/to/binary [...] <testcase )\n\n"
#endif /* ^RLIMIT_AS */"      Tip: you can use  to quickly\n""      estimate the required amount of virtual memory for the binary. Also,\n""      if you are using ASAN, see %s/notes_for_asan.txt.\n\n"#ifdef __APPLE__"    - On MacOS X, the semantics of fork() syscalls are non-standard and may\n""      break afl-fuzz performance optimizations when running platform-specific\n""      binaries. To fix this, set AFL_NO_FORKSRV=1 in the environment.\n\n"#endif /* __APPLE__ */"    - Least likely, there is a horrible bug in the fuzzer. If other options\n""      fail, poke <lcamtuf@coredump.cx> for troubleshooting tips.\n",DMS(mem_limit << 20), mem_limit - 1, doc_path);} else {SAYF("\n" cLRD "[-] " cRST"Oops, the program crashed with one of the test cases provided. There are\n""    several possible explanations:\n\n""    - The test case causes known crashes under normal working conditions. If\n""      so, please remove it. The fuzzer should be seeded with interesting\n""      inputs - but not ones that cause an outright crash.\n\n"#ifdef __APPLE__"    - On MacOS X, the semantics of fork() syscalls are non-standard and may\n""      break afl-fuzz performance optimizations when running platform-specific\n""      binaries. To fix this, set AFL_NO_FORKSRV=1 in the environment.\n\n"#endif /* __APPLE__ */"    - Least likely, there is a horrible bug in the fuzzer. If other options\n""      fail, poke <lcamtuf@coredump.cx> for troubleshooting tips.\n");}FATAL("Test case '%s' results in a crash", fn);case FAULT_ERROR:FATAL("Unable to execute target application ('%s')", argv[0]);case FAULT_NOINST:FATAL("No instrumentation detected");case FAULT_NOBITS:useless_at_start++;if (!in_bitmap && !shuffle_queue)WARNF("No new instrumentation output, test case may be useless.");break;}if (q->var_behavior) WARNF("Instrumentation output varies across runs.");q = q->next;}if (cal_failures) {if (cal_failures == queued_paths)FATAL("All test cases time out%s, giving up!",skip_crashes ? " or crash" : "");WARNF("Skipped %u test cases (%0.02f%%) due to timeouts%s.", cal_failures,((double)cal_failures) * 100 / queued_paths,skip_crashes ? " or crashes" : "");if (cal_failures * 5 > queued_paths)WARNF(cLRD "High percentage of rejected test cases, check settings!");}OKF("All test cases processed.");}

perform_dry_run()函数是用于测试所有测试用例以确认程序按照预期运行，只在初始输入时执行且只执行一次。
对于输入的测试用例数组queue_entry* q进行遍历，对于每一个queue_entry 首先构造消息序列链表

 /* AFLNet construct the kl_messages linked list for this queue entry*/kl_messages = construct_kl_messages(q->fname, q->regions, q->region_count);res = calibrate_case(argv, q, use_mem, 0, 1);ck_free(use_mem);

之后在dry_run状态下更新状态机，之后保存生成的消息序列列表到文件中用于重新发送。
其中perform_dry_run()调用了calibrate_case()函数，这个函数实际对测试用例进行了一次测试以检测测试用例是否有问题需要校准。

static u8 calibrate_case(char** argv, struct queue_entry* q, u8* use_mem,u32 handicap, u8 from_queue)

static u8 calibrate_case(char** argv, struct queue_entry* q, u8* use_mem,u32 handicap, u8 from_queue) {static u8 first_trace[MAP_SIZE];u8  fault = 0, new_bits = 0, var_detected = 0,first_run = (q->exec_cksum == 0);u64 start_us, stop_us;s32 old_sc = stage_cur, old_sm = stage_max;u32 use_tmout = exec_tmout;u8* old_sn = stage_name;/* Be a bit more generous about timeouts when resuming sessions, or whentrying to calibrate already-added finds. This helps avoid trouble dueto intermittent latency. */if (!from_queue || resuming_fuzz)use_tmout = MAX(exec_tmout + CAL_TMOUT_ADD,exec_tmout * CAL_TMOUT_PERC / 100);q->cal_failed++;stage_name = "calibration";stage_max  = fast_cal ? 3 : CAL_CYCLES;/* Make sure the forkserver is up before we do anything, and let's notcount its spin-up time toward binary calibration. */if (dumb_mode != 1 && !no_forkserver && !forksrv_pid)init_forkserver(argv);if (q->exec_cksum) memcpy(first_trace, trace_bits, MAP_SIZE);start_us = get_cur_time_us();for (stage_cur = 0; stage_cur < stage_max; stage_cur++) {u32 cksum;if (!first_run && !(stage_cur % stats_update_freq)) show_stats();write_to_testcase(use_mem, q->len);fault = run_target(argv, use_tmout);/* stop_soon is set by the handler for Ctrl+C. When it's pressed,we want to bail out quickly. */if (stop_soon || fault != crash_mode) goto abort_calibration;if (!dumb_mode && !stage_cur && !count_bytes(trace_bits)) {fault = FAULT_NOINST;goto abort_calibration;}cksum = hash32(trace_bits, MAP_SIZE, HASH_CONST);if (q->exec_cksum != cksum) {u8 hnb = has_new_bits(virgin_bits);if (hnb > new_bits) new_bits = hnb;if (q->exec_cksum) {u32 i;for (i = 0; i < MAP_SIZE; i++) {if (!var_bytes[i] && first_trace[i] != trace_bits[i]) {var_bytes[i] = 1;stage_max    = CAL_CYCLES_LONG;}}var_detected = 1;} else {q->exec_cksum = cksum;memcpy(first_trace, trace_bits, MAP_SIZE);}}}stop_us = get_cur_time_us();total_cal_us     += stop_us - start_us;total_cal_cycles += stage_max;/* OK, let's collect some stats about the performance of this test case.This is used for fuzzing air time calculations in calculate_score(). */q->exec_us     = (stop_us - start_us) / stage_max;q->bitmap_size = count_bytes(trace_bits);q->handicap    = handicap;q->cal_failed  = 0;total_bitmap_size += q->bitmap_size;total_bitmap_entries++;update_bitmap_score(q);/* If this case didn't result in new output from the instrumentation, tellparent. This is a non-critical problem, but something to warn the userabout. */if (!dumb_mode && first_run && !fault && !new_bits) fault = FAULT_NOBITS;abort_calibration:if (new_bits == 2 && !q->has_new_cov) {q->has_new_cov = 1;queued_with_cov++;}/* Mark variable paths. */if (var_detected) {var_byte_count = count_bytes(var_bytes);if (!q->var_behavior) {mark_as_variable(q);queued_variable++;}}stage_name = old_sn;stage_cur  = old_sc;stage_max  = old_sm;if (!first_run) show_stats();return fault;}

这部分跟AFL对比了一下，只删改了一小部分关于hub变量的代码，应该影响不是很大。

fuzz_one()

先来看看fuzz_one()的辅助函数

EXP_ST u8 common_fuzz_stuff(char** argv, u8* out_buf, u32 len)

/* Write a modified test case, run program, process results. Handleerror conditions, returning 1 if it's time to bail out. This isa helper function for fuzz_one(). */EXP_ST u8 common_fuzz_stuff(char** argv, u8* out_buf, u32 len) {u8 fault;if (post_handler) {out_buf = post_handler(out_buf, &len);if (!out_buf || !len) return 0;}write_to_testcase(out_buf, len);/* AFLNet update kl_messages linked list */// parse the out_buf into messagesu32 region_count;region_t *regions = (*extract_requests)(out_buf, len, &region_count);if (!region_count) PFATAL("AFLNet Region count cannot be Zero");// update kl_messages linked listu32 i;kliter_t(lms) *prev_last_message, *cur_last_message;prev_last_message = get_last_message(kl_messages);// limit the #messages based on max_seed_region_count to reduce overheadfor (i = 0; i < region_count; i++) {u32 len;//Identify region sizeif (i == max_seed_region_count) {len = regions[region_count - 1].end_byte - regions[i].start_byte + 1;} else {len = regions[i].end_byte - regions[i].start_byte + 1;}//Create a new messagemessage_t *m = (message_t *) ck_alloc(sizeof(message_t));m->mdata = (char *) ck_alloc(len);m->msize = len;if (m->mdata == NULL) PFATAL("Unable to allocate memory region to store new message");memcpy(m->mdata, &out_buf[regions[i].start_byte], len);//Insert the message to the linked list*kl_pushp(lms, kl_messages) = m;//Update M2_next in case it points to the tail (M3 is empty)//because the tail in klist is updated once a new entry is pushed into it//in fact, the old tail storage is used to store the newly added entry and a new tail is createdif (M2_next->next == kl_end(kl_messages)) {M2_next = kl_end(kl_messages);}if (i == max_seed_region_count) break;}ck_free(regions);cur_last_message = get_last_message(kl_messages);// update the linked list with the new M2 & free the previous M2//detach the head of previous M2 from the listkliter_t(lms) *old_M2_start;if (M2_prev == NULL) {old_M2_start = kl_begin(kl_messages);kl_begin(kl_messages) = kl_next(prev_last_message);kl_next(cur_last_message) = M2_next;kl_next(prev_last_message) = kl_end(kl_messages);} else {old_M2_start = kl_next(M2_prev);kl_next(M2_prev) = kl_next(prev_last_message);kl_next(cur_last_message) = M2_next;kl_next(prev_last_message) = kl_end(kl_messages);}// free the previous M2kliter_t(lms) *cur_it, *next_it;cur_it = old_M2_start;next_it = kl_next(cur_it);do {ck_free(kl_val(cur_it)->mdata);ck_free(kl_val(cur_it));kmp_free(lms, kl_messages->mp, cur_it);--kl_messages->size;cur_it = next_it;next_it = kl_next(next_it);} while(cur_it != M2_next);/* End of AFLNet code */fault = run_target(argv, exec_tmout);//Update fuzz count, no matter whether the generated test is interesting or notif (state_aware_mode) update_fuzzs();if (stop_soon) return 1;if (fault == FAULT_TMOUT) {if (subseq_tmouts++ > TMOUT_LIMIT) {cur_skipped_paths++;return 1;}} else subseq_tmouts = 0;/* Users can hit us with SIGUSR1 to request the current inputto be abandoned. */if (skip_requested) {skip_requested = 0;cur_skipped_paths++;return 1;}/* This handles FAULT_ERROR for us: */queued_discovered += save_if_interesting(argv, out_buf, len, fault);if (!(stage_cur % stats_update_freq) || stage_cur + 1 == stage_max)show_stats();return 0;}

其中这部分是AFLNET的代码

/* AFLNet update kl_messages linked list */// parse the out_buf into messagesu32 region_count;region_t *regions = (*extract_requests)(out_buf, len, &region_count);if (!region_count) PFATAL("AFLNet Region count cannot be Zero");// update kl_messages linked listu32 i;kliter_t(lms) *prev_last_message, *cur_last_message;prev_last_message = get_last_message(kl_messages);// limit the #messages based on max_seed_region_count to reduce overheadfor (i = 0; i < region_count; i++) {u32 len;//Identify region sizeif (i == max_seed_region_count) {len = regions[region_count - 1].end_byte - regions[i].start_byte + 1;} else {len = regions[i].end_byte - regions[i].start_byte + 1;}//Create a new messagemessage_t *m = (message_t *) ck_alloc(sizeof(message_t));m->mdata = (char *) ck_alloc(len);m->msize = len;if (m->mdata == NULL) PFATAL("Unable to allocate memory region to store new message");memcpy(m->mdata, &out_buf[regions[i].start_byte], len);//Insert the message to the linked list*kl_pushp(lms, kl_messages) = m;//Update M2_next in case it points to the tail (M3 is empty)//because the tail in klist is updated once a new entry is pushed into it//in fact, the old tail storage is used to store the newly added entry and a new tail is createdif (M2_next->next == kl_end(kl_messages)) {M2_next = kl_end(kl_messages);}if (i == max_seed_region_count) break;}ck_free(regions);cur_last_message = get_last_message(kl_messages);// update the linked list with the new M2 & free the previous M2//detach the head of previous M2 from the listkliter_t(lms) *old_M2_start;if (M2_prev == NULL) {old_M2_start = kl_begin(kl_messages);kl_begin(kl_messages) = kl_next(prev_last_message);kl_next(cur_last_message) = M2_next;kl_next(prev_last_message) = kl_end(kl_messages);} else {old_M2_start = kl_next(M2_prev);kl_next(M2_prev) = kl_next(prev_last_message);kl_next(cur_last_message) = M2_next;kl_next(prev_last_message) = kl_end(kl_messages);}// free the previous M2kliter_t(lms) *cur_it, *next_it;cur_it = old_M2_start;next_it = kl_next(cur_it);do {ck_free(kl_val(cur_it)->mdata);ck_free(kl_val(cur_it));kmp_free(lms, kl_messages->mp, cur_it);--kl_messages->size;cur_it = next_it;next_it = kl_next(next_it);} while(cur_it != M2_next);/* End of AFLNet code */

AFLNET增加的代码主要是解析out_buf中的数据并用于构造条新消息插入到原来的测试消息序列中。之后更新M2消息序列。

static u8 fuzz_one(char** argv)

这个函数非常长，有1千多行代码，我们只关注AFLNET状态机模式下的部分。

/* Take the current entry from the queue, fuzz it for a while. Thisfunction is a tad too long... returns 0 if fuzzed successfully, 1 ifskipped or bailed out. */static u8 fuzz_one(char** argv) {s32 len, fd, temp_len, i, j;u8  *in_buf = NULL, *out_buf, *orig_in, *ex_tmp, *eff_map = 0;u64 havoc_queued,  orig_hit_cnt, new_hit_cnt;u32 splice_cycle = 0, perf_score = 100, orig_perf, prev_cksum, eff_cnt = 1, M2_len;u8  ret_val = 1, doing_det = 0;u8  a_collect[MAX_AUTO_EXTRA];u32 a_len = 0;#ifdef IGNORE_FINDS/* In IGNORE_FINDS mode, skip any entries that weren't in theinitial data set. */if (queue_cur->depth > 1) return 1;#else//Skip some steps if in state_aware_mode because in this mode//the seed is selected based on state-aware algorithmsif (state_aware_mode) goto AFLNET_REGIONS_SELECTION;if (pending_favored) {/* If we have any favored, non-fuzzed new arrivals in the queue,possibly skip to them at the expense of already-fuzzed or non-favoredcases. */if ((queue_cur->was_fuzzed || !queue_cur->favored) &&UR(100) < SKIP_TO_NEW_PROB) return 1;} else if (!dumb_mode && !queue_cur->favored && queued_paths > 10) {/* Otherwise, still possibly skip non-favored cases, albeit less often.The odds of skipping stuff are higher for already-fuzzed inputs andlower for never-fuzzed entries. */if (queue_cycle > 1 && !queue_cur->was_fuzzed) {if (UR(100) < SKIP_NFAV_NEW_PROB) return 1;} else {if (UR(100) < SKIP_NFAV_OLD_PROB) return 1;}}#endif /* ^IGNORE_FINDS */if (not_on_tty) {ACTF("Fuzzing test case #%u (%u total, %llu uniq crashes found)...",current_entry, queued_paths, unique_crashes);fflush(stdout);}AFLNET_REGIONS_SELECTION:;subseq_tmouts = 0;cur_depth = queue_cur->depth;u32 M2_start_region_ID = 0, M2_region_count = 0;/* Identify the prefix M1, the candidate subsequence M2, and the suffix M3. See AFLNet paper *//* In this implementation, we only need to indentify M2_start_region_ID which is the first region of M2and M2_region_count which is the total number of regions in M2. How the information is identified isstate aware dependent. However, once the information is clear, the code for fuzzing preparation is the same */if (state_aware_mode) {/* In state aware mode, select M2 based on the targeted state ID */u32 total_region = queue_cur->region_count;if (total_region == 0) PFATAL("0 region found for %s", queue_cur->fname);if (target_state_id == 0) {//No prefix subsequence (M1 is empty)M2_start_region_ID = 0;M2_region_count = 0;//To compute M2_region_count, we identify the first region which has a different annotation//Now we quickly compare the state count, we could make it more fine grained by comparing the exact response codesfor(i = 0; i < queue_cur->region_count ; i++) {if (queue_cur->regions[i].state_count != queue_cur->regions[0].state_count) break;M2_region_count++;}} else {//M1 is unlikely to be emptyM2_start_region_ID = 0;//Identify M2_start_region_ID first based on the target_state_idfor(i = 0; i < queue_cur->region_count; i++) {u32 regionalStateCount = queue_cur->regions[i].state_count;if (regionalStateCount > 0) {//reachableStateID is the last ID in the state_sequenceu32 reachableStateID = queue_cur->regions[i].state_sequence[regionalStateCount - 1];M2_start_region_ID++;if (reachableStateID == target_state_id) break;} else {//No annotation for this regionreturn 1;}}//Then identify M2_region_countfor(i = M2_start_region_ID; i < queue_cur->region_count ; i++) {if (queue_cur->regions[i].state_count != queue_cur->regions[M2_start_region_ID].state_count) break;M2_region_count++;}//Handle corner case(s) and skip the current queue entryif (M2_start_region_ID >= queue_cur->region_count) return 1;}} else {/* Select M2 randomly */u32 total_region = queue_cur->region_count;if (total_region == 0) PFATAL("0 region found for %s", queue_cur->fname);M2_start_region_ID = UR(total_region);M2_region_count = UR(total_region - M2_start_region_ID);if (M2_region_count == 0) M2_region_count++; //Mutate one region at least}/* Construct the kl_messages linked list and identify boundary pointers (M2_prev and M2_next) */kl_messages = construct_kl_messages(queue_cur->fname, queue_cur->regions, queue_cur->region_count);kliter_t(lms) *it;M2_prev = NULL;M2_next = kl_end(kl_messages);u32 count = 0;for (it = kl_begin(kl_messages); it != kl_end(kl_messages); it = kl_next(it)) {if (count == M2_start_region_ID - 1) {M2_prev = it;}if (count == M2_start_region_ID + M2_region_count) {M2_next = it;}count++;}/* Construct the buffer to be mutated and update out_buf */if (M2_prev == NULL) {it = kl_begin(kl_messages);} else {it = kl_next(M2_prev);}u32 in_buf_size = 0;while (it != M2_next) {in_buf = (u8 *) ck_realloc (in_buf, in_buf_size + kl_val(it)->msize);if (!in_buf) PFATAL("AFLNet cannot allocate memory for in_buf");//Retrieve data from kl_messages to populate the in_bufmemcpy(&in_buf[in_buf_size], kl_val(it)->mdata, kl_val(it)->msize);in_buf_size += kl_val(it)->msize;it = kl_next(it);}orig_in = in_buf;out_buf = ck_alloc_nozero(in_buf_size);memcpy(out_buf, in_buf, in_buf_size);//Update len to keep the correct size of the buffer being mutatedlen = in_buf_size;//Save the len for later useM2_len = len;/********************** PERFORMANCE SCORE **********************/orig_perf = perf_score = calculate_score(queue_cur);/* Skip right away if -d is given, if we have done deterministic fuzzing onthis entry ourselves (was_fuzzed), or if it has gone through deterministictesting in earlier, resumed runs (passed_det). */if (skip_deterministic || queue_cur->was_fuzzed || queue_cur->passed_det)goto havoc_stage;/* Skip deterministic fuzzing if exec path checksum puts this out of scopefor this master instance. */if (master_max && (queue_cur->exec_cksum % master_max) != master_id - 1)goto havoc_stage;doing_det = 1;/********************************************** SIMPLE BITFLIP (+dictionary construction) **********************************************/#define FLIP_BIT(_ar, _b) do { \u8* _arf = (u8*)(_ar); \u32 _bf = (_b); \_arf[(_bf) >> 3] ^= (128 >> ((_bf) & 7)); \} while (0)/* Single walking bit. */stage_short = "flip1";stage_max   = len << 3;stage_name  = "bitflip 1/1";stage_val_type = STAGE_VAL_NONE;orig_hit_cnt = queued_paths + unique_crashes;prev_cksum = queue_cur->exec_cksum;for (stage_cur = 0; stage_cur < stage_max; stage_cur++) {stage_cur_byte = stage_cur >> 3;FLIP_BIT(out_buf, stage_cur);if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;FLIP_BIT(out_buf, stage_cur);/* While flipping the least significant bit in every byte, pull of an extratrick to detect possible syntax tokens. In essence, the idea is that ifyou have a binary blob like this:xxxxxxxxIHDRxxxxxxxx...and changing the leading and trailing bytes causes variable or nochanges in program flow, but touching any character in the "IHDR" stringalways produces the same, distinctive path, it's highly likely that"IHDR" is an atomically-checked magic value of special significance tothe fuzzed format.We do this here, rather than as a separate stage, because it's a niceway to keep the operation approximately "free" (i.e., no extra execs).Empirically, performing the check when flipping the least significant bitis advantageous, compared to doing it at the time of more disruptivechanges, where the program flow may be affected in more violent ways.The caveat is that we won't generate dictionaries in the -d mode or -Smode - but that's probably a fair trade-off.This won't work particularly well with paths that exhibit variablebehavior, but fails gracefully, so we'll carry out the checks anyway.*/if (!dumb_mode && (stage_cur & 7) == 7) {u32 cksum = hash32(trace_bits, MAP_SIZE, HASH_CONST);if (stage_cur == stage_max - 1 && cksum == prev_cksum) {/* If at end of file and we are still collecting a string, grab thefinal character and force output. */if (a_len < MAX_AUTO_EXTRA) a_collect[a_len] = out_buf[stage_cur >> 3];a_len++;if (a_len >= MIN_AUTO_EXTRA && a_len <= MAX_AUTO_EXTRA)maybe_add_auto(a_collect, a_len);} else if (cksum != prev_cksum) {/* Otherwise, if the checksum has changed, see if we have somethingworthwhile queued up, and collect that if the answer is yes. */if (a_len >= MIN_AUTO_EXTRA && a_len <= MAX_AUTO_EXTRA)maybe_add_auto(a_collect, a_len);a_len = 0;prev_cksum = cksum;}/* Continue collecting string, but only if the bit flip actually madeany difference - we don't want no-op tokens. */if (cksum != queue_cur->exec_cksum) {if (a_len < MAX_AUTO_EXTRA) a_collect[a_len] = out_buf[stage_cur >> 3];a_len++;}}}new_hit_cnt = queued_paths + unique_crashes;stage_finds[STAGE_FLIP1]  += new_hit_cnt - orig_hit_cnt;stage_cycles[STAGE_FLIP1] += stage_max;/* Two walking bits. */stage_name  = "bitflip 2/1";stage_short = "flip2";stage_max   = (len << 3) - 1;orig_hit_cnt = new_hit_cnt;for (stage_cur = 0; stage_cur < stage_max; stage_cur++) {stage_cur_byte = stage_cur >> 3;FLIP_BIT(out_buf, stage_cur);FLIP_BIT(out_buf, stage_cur + 1);if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;FLIP_BIT(out_buf, stage_cur);FLIP_BIT(out_buf, stage_cur + 1);}new_hit_cnt = queued_paths + unique_crashes;stage_finds[STAGE_FLIP2]  += new_hit_cnt - orig_hit_cnt;stage_cycles[STAGE_FLIP2] += stage_max;/* Four walking bits. */stage_name  = "bitflip 4/1";stage_short = "flip4";stage_max   = (len << 3) - 3;orig_hit_cnt = new_hit_cnt;for (stage_cur = 0; stage_cur < stage_max; stage_cur++) {stage_cur_byte = stage_cur >> 3;FLIP_BIT(out_buf, stage_cur);FLIP_BIT(out_buf, stage_cur + 1);FLIP_BIT(out_buf, stage_cur + 2);FLIP_BIT(out_buf, stage_cur + 3);if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;FLIP_BIT(out_buf, stage_cur);FLIP_BIT(out_buf, stage_cur + 1);FLIP_BIT(out_buf, stage_cur + 2);FLIP_BIT(out_buf, stage_cur + 3);}new_hit_cnt = queued_paths + unique_crashes;stage_finds[STAGE_FLIP4]  += new_hit_cnt - orig_hit_cnt;stage_cycles[STAGE_FLIP4] += stage_max;/* Effector map setup. These macros calculate:EFF_APOS      - position of a particular file offset in the map.EFF_ALEN      - length of a map with a particular number of bytes.EFF_SPAN_ALEN - map span for a sequence of bytes.*/#define EFF_APOS(_p)          ((_p) >> EFF_MAP_SCALE2)
#define EFF_REM(_x)           ((_x) & ((1 << EFF_MAP_SCALE2) - 1))
#define EFF_ALEN(_l)          (EFF_APOS(_l) + !!EFF_REM(_l))
#define EFF_SPAN_ALEN(_p, _l) (EFF_APOS((_p) + (_l) - 1) - EFF_APOS(_p) + 1)/* Initialize effector map for the next step (see comments below). Alwaysflag first and last byte as doing something. */eff_map    = ck_alloc(EFF_ALEN(len));eff_map[0] = 1;if (EFF_APOS(len - 1) != 0) {eff_map[EFF_APOS(len - 1)] = 1;eff_cnt++;}/* Walking byte. */stage_name  = "bitflip 8/8";stage_short = "flip8";stage_max   = len;orig_hit_cnt = new_hit_cnt;for (stage_cur = 0; stage_cur < stage_max; stage_cur++) {stage_cur_byte = stage_cur;out_buf[stage_cur] ^= 0xFF;if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;/* We also use this stage to pull off a simple trick: we identifybytes that seem to have no effect on the current execution patheven when fully flipped - and we skip them during more expensivedeterministic stages, such as arithmetics or known ints. */if (!eff_map[EFF_APOS(stage_cur)]) {u32 cksum;/* If in dumb mode or if the file is very short, just flag everythingwithout wasting time on checksums. */if (!dumb_mode && len >= EFF_MIN_LEN)cksum = hash32(trace_bits, MAP_SIZE, HASH_CONST);elsecksum = ~queue_cur->exec_cksum;if (cksum != queue_cur->exec_cksum) {eff_map[EFF_APOS(stage_cur)] = 1;eff_cnt++;}}out_buf[stage_cur] ^= 0xFF;}/* If the effector map is more than EFF_MAX_PERC dense, just flag thewhole thing as worth fuzzing, since we wouldn't be saving much timeanyway. */if (eff_cnt != EFF_ALEN(len) &&eff_cnt * 100 / EFF_ALEN(len) > EFF_MAX_PERC) {memset(eff_map, 1, EFF_ALEN(len));blocks_eff_select += EFF_ALEN(len);} else {blocks_eff_select += eff_cnt;}blocks_eff_total += EFF_ALEN(len);new_hit_cnt = queued_paths + unique_crashes;stage_finds[STAGE_FLIP8]  += new_hit_cnt - orig_hit_cnt;stage_cycles[STAGE_FLIP8] += stage_max;/* Two walking bytes. */if (len < 2) goto skip_bitflip;stage_name  = "bitflip 16/8";stage_short = "flip16";stage_cur   = 0;stage_max   = len - 1;orig_hit_cnt = new_hit_cnt;for (i = 0; i < len - 1; i++) {/* Let's consult the effector map... */if (!eff_map[EFF_APOS(i)] && !eff_map[EFF_APOS(i + 1)]) {stage_max--;continue;}stage_cur_byte = i;*(u16*)(out_buf + i) ^= 0xFFFF;if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;stage_cur++;*(u16*)(out_buf + i) ^= 0xFFFF;}new_hit_cnt = queued_paths + unique_crashes;stage_finds[STAGE_FLIP16]  += new_hit_cnt - orig_hit_cnt;stage_cycles[STAGE_FLIP16] += stage_max;if (len < 4) goto skip_bitflip;/* Four walking bytes. */stage_name  = "bitflip 32/8";stage_short = "flip32";stage_cur   = 0;stage_max   = len - 3;orig_hit_cnt = new_hit_cnt;for (i = 0; i < len - 3; i++) {/* Let's consult the effector map... */if (!eff_map[EFF_APOS(i)] && !eff_map[EFF_APOS(i + 1)] &&!eff_map[EFF_APOS(i + 2)] && !eff_map[EFF_APOS(i + 3)]) {stage_max--;continue;}stage_cur_byte = i;*(u32*)(out_buf + i) ^= 0xFFFFFFFF;if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;stage_cur++;*(u32*)(out_buf + i) ^= 0xFFFFFFFF;}new_hit_cnt = queued_paths + unique_crashes;stage_finds[STAGE_FLIP32]  += new_hit_cnt - orig_hit_cnt;stage_cycles[STAGE_FLIP32] += stage_max;skip_bitflip:if (no_arith) goto skip_arith;/*********************** ARITHMETIC INC/DEC ***********************//* 8-bit arithmetics. */stage_name  = "arith 8/8";stage_short = "arith8";stage_cur   = 0;stage_max   = 2 * len * ARITH_MAX;stage_val_type = STAGE_VAL_LE;orig_hit_cnt = new_hit_cnt;for (i = 0; i < len; i++) {u8 orig = out_buf[i];/* Let's consult the effector map... */if (!eff_map[EFF_APOS(i)]) {stage_max -= 2 * ARITH_MAX;continue;}stage_cur_byte = i;for (j = 1; j <= ARITH_MAX; j++) {u8 r = orig ^ (orig + j);/* Do arithmetic operations only if the result couldn't be a productof a bitflip. */if (!could_be_bitflip(r)) {stage_cur_val = j;out_buf[i] = orig + j;if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;stage_cur++;} else stage_max--;r =  orig ^ (orig - j);if (!could_be_bitflip(r)) {stage_cur_val = -j;out_buf[i] = orig - j;if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;stage_cur++;} else stage_max--;out_buf[i] = orig;}}new_hit_cnt = queued_paths + unique_crashes;stage_finds[STAGE_ARITH8]  += new_hit_cnt - orig_hit_cnt;stage_cycles[STAGE_ARITH8] += stage_max;/* 16-bit arithmetics, both endians. */if (len < 2) goto skip_arith;stage_name  = "arith 16/8";stage_short = "arith16";stage_cur   = 0;stage_max   = 4 * (len - 1) * ARITH_MAX;orig_hit_cnt = new_hit_cnt;for (i = 0; i < len - 1; i++) {u16 orig = *(u16*)(out_buf + i);/* Let's consult the effector map... */if (!eff_map[EFF_APOS(i)] && !eff_map[EFF_APOS(i + 1)]) {stage_max -= 4 * ARITH_MAX;continue;}stage_cur_byte = i;for (j = 1; j <= ARITH_MAX; j++) {u16 r1 = orig ^ (orig + j),r2 = orig ^ (orig - j),r3 = orig ^ SWAP16(SWAP16(orig) + j),r4 = orig ^ SWAP16(SWAP16(orig) - j);/* Try little endian addition and subtraction first. Do it onlyif the operation would affect more than one byte (hence the& 0xff overflow checks) and if it couldn't be a product ofa bitflip. */stage_val_type = STAGE_VAL_LE;if ((orig & 0xff) + j > 0xff && !could_be_bitflip(r1)) {stage_cur_val = j;*(u16*)(out_buf + i) = orig + j;if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;stage_cur++;} else stage_max--;if ((orig & 0xff) < j && !could_be_bitflip(r2)) {stage_cur_val = -j;*(u16*)(out_buf + i) = orig - j;if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;stage_cur++;} else stage_max--;/* Big endian comes next. Same deal. */stage_val_type = STAGE_VAL_BE;if ((orig >> 8) + j > 0xff && !could_be_bitflip(r3)) {stage_cur_val = j;*(u16*)(out_buf + i) = SWAP16(SWAP16(orig) + j);if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;stage_cur++;} else stage_max--;if ((orig >> 8) < j && !could_be_bitflip(r4)) {stage_cur_val = -j;*(u16*)(out_buf + i) = SWAP16(SWAP16(orig) - j);if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;stage_cur++;} else stage_max--;*(u16*)(out_buf + i) = orig;}}new_hit_cnt = queued_paths + unique_crashes;stage_finds[STAGE_ARITH16]  += new_hit_cnt - orig_hit_cnt;stage_cycles[STAGE_ARITH16] += stage_max;/* 32-bit arithmetics, both endians. */if (len < 4) goto skip_arith;stage_name  = "arith 32/8";stage_short = "arith32";stage_cur   = 0;stage_max   = 4 * (len - 3) * ARITH_MAX;orig_hit_cnt = new_hit_cnt;for (i = 0; i < len - 3; i++) {u32 orig = *(u32*)(out_buf + i);/* Let's consult the effector map... */if (!eff_map[EFF_APOS(i)] && !eff_map[EFF_APOS(i + 1)] &&!eff_map[EFF_APOS(i + 2)] && !eff_map[EFF_APOS(i + 3)]) {stage_max -= 4 * ARITH_MAX;continue;}stage_cur_byte = i;for (j = 1; j <= ARITH_MAX; j++) {u32 r1 = orig ^ (orig + j),r2 = orig ^ (orig - j),r3 = orig ^ SWAP32(SWAP32(orig) + j),r4 = orig ^ SWAP32(SWAP32(orig) - j);/* Little endian first. Same deal as with 16-bit: we only want totry if the operation would have effect on more than two bytes. */stage_val_type = STAGE_VAL_LE;if ((orig & 0xffff) + j > 0xffff && !could_be_bitflip(r1)) {stage_cur_val = j;*(u32*)(out_buf + i) = orig + j;if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;stage_cur++;} else stage_max--;if ((orig & 0xffff) < j && !could_be_bitflip(r2)) {stage_cur_val = -j;*(u32*)(out_buf + i) = orig - j;if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;stage_cur++;} else stage_max--;/* Big endian next. */stage_val_type = STAGE_VAL_BE;if ((SWAP32(orig) & 0xffff) + j > 0xffff && !could_be_bitflip(r3)) {stage_cur_val = j;*(u32*)(out_buf + i) = SWAP32(SWAP32(orig) + j);if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;stage_cur++;} else stage_max--;if ((SWAP32(orig) & 0xffff) < j && !could_be_bitflip(r4)) {stage_cur_val = -j;*(u32*)(out_buf + i) = SWAP32(SWAP32(orig) - j);if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;stage_cur++;} else stage_max--;*(u32*)(out_buf + i) = orig;}}new_hit_cnt = queued_paths + unique_crashes;stage_finds[STAGE_ARITH32]  += new_hit_cnt - orig_hit_cnt;stage_cycles[STAGE_ARITH32] += stage_max;skip_arith:/*********************** INTERESTING VALUES ***********************/stage_name  = "interest 8/8";stage_short = "int8";stage_cur   = 0;stage_max   = len * sizeof(interesting_8);stage_val_type = STAGE_VAL_LE;orig_hit_cnt = new_hit_cnt;/* Setting 8-bit integers. */for (i = 0; i < len; i++) {u8 orig = out_buf[i];/* Let's consult the effector map... */if (!eff_map[EFF_APOS(i)]) {stage_max -= sizeof(interesting_8);continue;}stage_cur_byte = i;for (j = 0; j < sizeof(interesting_8); j++) {/* Skip if the value could be a product of bitflips or arithmetics. */if (could_be_bitflip(orig ^ (u8)interesting_8[j]) ||could_be_arith(orig, (u8)interesting_8[j], 1)) {stage_max--;continue;}stage_cur_val = interesting_8[j];out_buf[i] = interesting_8[j];if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;out_buf[i] = orig;stage_cur++;}}new_hit_cnt = queued_paths + unique_crashes;stage_finds[STAGE_INTEREST8]  += new_hit_cnt - orig_hit_cnt;stage_cycles[STAGE_INTEREST8] += stage_max;/* Setting 16-bit integers, both endians. */if (no_arith || len < 2) goto skip_interest;stage_name  = "interest 16/8";stage_short = "int16";stage_cur   = 0;stage_max   = 2 * (len - 1) * (sizeof(interesting_16) >> 1);orig_hit_cnt = new_hit_cnt;for (i = 0; i < len - 1; i++) {u16 orig = *(u16*)(out_buf + i);/* Let's consult the effector map... */if (!eff_map[EFF_APOS(i)] && !eff_map[EFF_APOS(i + 1)]) {stage_max -= sizeof(interesting_16);continue;}stage_cur_byte = i;for (j = 0; j < sizeof(interesting_16) / 2; j++) {stage_cur_val = interesting_16[j];/* Skip if this could be a product of a bitflip, arithmetics,or single-byte interesting value insertion. */if (!could_be_bitflip(orig ^ (u16)interesting_16[j]) &&!could_be_arith(orig, (u16)interesting_16[j], 2) &&!could_be_interest(orig, (u16)interesting_16[j], 2, 0)) {stage_val_type = STAGE_VAL_LE;*(u16*)(out_buf + i) = interesting_16[j];if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;stage_cur++;} else stage_max--;if ((u16)interesting_16[j] != SWAP16(interesting_16[j]) &&!could_be_bitflip(orig ^ SWAP16(interesting_16[j])) &&!could_be_arith(orig, SWAP16(interesting_16[j]), 2) &&!could_be_interest(orig, SWAP16(interesting_16[j]), 2, 1)) {stage_val_type = STAGE_VAL_BE;*(u16*)(out_buf + i) = SWAP16(interesting_16[j]);if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;stage_cur++;} else stage_max--;}*(u16*)(out_buf + i) = orig;}new_hit_cnt = queued_paths + unique_crashes;stage_finds[STAGE_INTEREST16]  += new_hit_cnt - orig_hit_cnt;stage_cycles[STAGE_INTEREST16] += stage_max;if (len < 4) goto skip_interest;/* Setting 32-bit integers, both endians. */stage_name  = "interest 32/8";stage_short = "int32";stage_cur   = 0;stage_max   = 2 * (len - 3) * (sizeof(interesting_32) >> 2);orig_hit_cnt = new_hit_cnt;for (i = 0; i < len - 3; i++) {u32 orig = *(u32*)(out_buf + i);/* Let's consult the effector map... */if (!eff_map[EFF_APOS(i)] && !eff_map[EFF_APOS(i + 1)] &&!eff_map[EFF_APOS(i + 2)] && !eff_map[EFF_APOS(i + 3)]) {stage_max -= sizeof(interesting_32) >> 1;continue;}stage_cur_byte = i;for (j = 0; j < sizeof(interesting_32) / 4; j++) {stage_cur_val = interesting_32[j];/* Skip if this could be a product of a bitflip, arithmetics,or word interesting value insertion. */if (!could_be_bitflip(orig ^ (u32)interesting_32[j]) &&!could_be_arith(orig, interesting_32[j], 4) &&!could_be_interest(orig, interesting_32[j], 4, 0)) {stage_val_type = STAGE_VAL_LE;*(u32*)(out_buf + i) = interesting_32[j];if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;stage_cur++;} else stage_max--;if ((u32)interesting_32[j] != SWAP32(interesting_32[j]) &&!could_be_bitflip(orig ^ SWAP32(interesting_32[j])) &&!could_be_arith(orig, SWAP32(interesting_32[j]), 4) &&!could_be_interest(orig, SWAP32(interesting_32[j]), 4, 1)) {stage_val_type = STAGE_VAL_BE;*(u32*)(out_buf + i) = SWAP32(interesting_32[j]);if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;stage_cur++;} else stage_max--;}*(u32*)(out_buf + i) = orig;}new_hit_cnt = queued_paths + unique_crashes;stage_finds[STAGE_INTEREST32]  += new_hit_cnt - orig_hit_cnt;stage_cycles[STAGE_INTEREST32] += stage_max;skip_interest:/********************* DICTIONARY STUFF *********************/if (!extras_cnt) goto skip_user_extras;/* Overwrite with user-supplied extras. */stage_name  = "user extras (over)";stage_short = "ext_UO";stage_cur   = 0;stage_max   = extras_cnt * len;stage_val_type = STAGE_VAL_NONE;orig_hit_cnt = new_hit_cnt;for (i = 0; i < len; i++) {u32 last_len = 0;stage_cur_byte = i;/* Extras are sorted by size, from smallest to largest. This meansthat we don't have to worry about restoring the buffer inbetween writes at a particular offset determined by the outerloop. */for (j = 0; j < extras_cnt; j++) {/* Skip extras probabilistically if extras_cnt > MAX_DET_EXTRAS. Alsoskip them if there's no room to insert the payload, if the tokenis redundant, or if its entire span has no bytes set in the effectormap. */if ((extras_cnt > MAX_DET_EXTRAS && UR(extras_cnt) >= MAX_DET_EXTRAS) ||extras[j].len > len - i ||!memcmp(extras[j].data, out_buf + i, extras[j].len) ||!memchr(eff_map + EFF_APOS(i), 1, EFF_SPAN_ALEN(i, extras[j].len))) {stage_max--;continue;}last_len = extras[j].len;memcpy(out_buf + i, extras[j].data, last_len);if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;stage_cur++;}/* Restore all the clobbered memory. */memcpy(out_buf + i, in_buf + i, last_len);}new_hit_cnt = queued_paths + unique_crashes;stage_finds[STAGE_EXTRAS_UO]  += new_hit_cnt - orig_hit_cnt;stage_cycles[STAGE_EXTRAS_UO] += stage_max;/* Insertion of user-supplied extras. */stage_name  = "user extras (insert)";stage_short = "ext_UI";stage_cur   = 0;stage_max   = extras_cnt * len;orig_hit_cnt = new_hit_cnt;ex_tmp = ck_alloc(len + MAX_DICT_FILE);for (i = 0; i <= len; i++) {stage_cur_byte = i;for (j = 0; j < extras_cnt; j++) {if (len + extras[j].len > MAX_FILE) {stage_max--;continue;}/* Insert token */memcpy(ex_tmp + i, extras[j].data, extras[j].len);/* Copy tail */memcpy(ex_tmp + i + extras[j].len, out_buf + i, len - i);if (common_fuzz_stuff(argv, ex_tmp, len + extras[j].len)) {ck_free(ex_tmp);goto abandon_entry;}stage_cur++;}/* Copy head */ex_tmp[i] = out_buf[i];}ck_free(ex_tmp);new_hit_cnt = queued_paths + unique_crashes;stage_finds[STAGE_EXTRAS_UI]  += new_hit_cnt - orig_hit_cnt;stage_cycles[STAGE_EXTRAS_UI] += stage_max;skip_user_extras:if (!a_extras_cnt) goto skip_extras;stage_name  = "auto extras (over)";stage_short = "ext_AO";stage_cur   = 0;stage_max   = MIN(a_extras_cnt, USE_AUTO_EXTRAS) * len;stage_val_type = STAGE_VAL_NONE;orig_hit_cnt = new_hit_cnt;for (i = 0; i < len; i++) {u32 last_len = 0;stage_cur_byte = i;for (j = 0; j < MIN(a_extras_cnt, USE_AUTO_EXTRAS); j++) {/* See the comment in the earlier code; extras are sorted by size. */if (a_extras[j].len > len - i ||!memcmp(a_extras[j].data, out_buf + i, a_extras[j].len) ||!memchr(eff_map + EFF_APOS(i), 1, EFF_SPAN_ALEN(i, a_extras[j].len))) {stage_max--;continue;}last_len = a_extras[j].len;memcpy(out_buf + i, a_extras[j].data, last_len);if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;stage_cur++;}/* Restore all the clobbered memory. */memcpy(out_buf + i, in_buf + i, last_len);}new_hit_cnt = queued_paths + unique_crashes;stage_finds[STAGE_EXTRAS_AO]  += new_hit_cnt - orig_hit_cnt;stage_cycles[STAGE_EXTRAS_AO] += stage_max;skip_extras:/* If we made this to here without jumping to havoc_stage or abandon_entry,we're properly done with deterministic steps and can mark it as suchin the .state/ directory. */if (!queue_cur->passed_det) mark_as_det_done(queue_cur);/***************** RANDOM HAVOC *****************/havoc_stage:stage_cur_byte = -1;/* The havoc stage mutation code is also invoked when splicing files; if thesplice_cycle variable is set, generate different descriptions and such. */if (!splice_cycle) {stage_name  = "havoc";stage_short = "havoc";stage_max   = (doing_det ? HAVOC_CYCLES_INIT : HAVOC_CYCLES) *perf_score / havoc_div / 100;} else {static u8 tmp[32];perf_score = orig_perf;sprintf(tmp, "splice %u", splice_cycle);stage_name  = tmp;stage_short = "splice";stage_max   = SPLICE_HAVOC * perf_score / havoc_div / 100;}if (stage_max < HAVOC_MIN) stage_max = HAVOC_MIN;temp_len = len;orig_hit_cnt = queued_paths + unique_crashes;havoc_queued = queued_paths;/* We essentially just do several thousand runs (depending on perf_score)where we take the input file and make random stacked tweaks. */for (stage_cur = 0; stage_cur < stage_max; stage_cur++) {u32 use_stacking = 1 << (1 + UR(HAVOC_STACK_POW2));stage_cur_val = use_stacking;for (i = 0; i < use_stacking; i++) {switch (UR(15 + 2 + (region_level_mutation ? 4 : 0))) {case 0:/* Flip a single bit somewhere. Spooky! */FLIP_BIT(out_buf, UR(temp_len << 3));break;case 1:/* Set byte to interesting value. */out_buf[UR(temp_len)] = interesting_8[UR(sizeof(interesting_8))];break;case 2:/* Set word to interesting value, randomly choosing endian. */if (temp_len < 2) break;if (UR(2)) {*(u16*)(out_buf + UR(temp_len - 1)) =interesting_16[UR(sizeof(interesting_16) >> 1)];} else {*(u16*)(out_buf + UR(temp_len - 1)) = SWAP16(interesting_16[UR(sizeof(interesting_16) >> 1)]);}break;case 3:/* Set dword to interesting value, randomly choosing endian. */if (temp_len < 4) break;if (UR(2)) {*(u32*)(out_buf + UR(temp_len - 3)) =interesting_32[UR(sizeof(interesting_32) >> 2)];} else {*(u32*)(out_buf + UR(temp_len - 3)) = SWAP32(interesting_32[UR(sizeof(interesting_32) >> 2)]);}break;case 4:/* Randomly subtract from byte. */out_buf[UR(temp_len)] -= 1 + UR(ARITH_MAX);break;case 5:/* Randomly add to byte. */out_buf[UR(temp_len)] += 1 + UR(ARITH_MAX);break;case 6:/* Randomly subtract from word, random endian. */if (temp_len < 2) break;if (UR(2)) {u32 pos = UR(temp_len - 1);*(u16*)(out_buf + pos) -= 1 + UR(ARITH_MAX);} else {u32 pos = UR(temp_len - 1);u16 num = 1 + UR(ARITH_MAX);*(u16*)(out_buf + pos) =SWAP16(SWAP16(*(u16*)(out_buf + pos)) - num);}break;case 7:/* Randomly add to word, random endian. */if (temp_len < 2) break;if (UR(2)) {u32 pos = UR(temp_len - 1);*(u16*)(out_buf + pos) += 1 + UR(ARITH_MAX);} else {u32 pos = UR(temp_len - 1);u16 num = 1 + UR(ARITH_MAX);*(u16*)(out_buf + pos) =SWAP16(SWAP16(*(u16*)(out_buf + pos)) + num);}break;case 8:/* Randomly subtract from dword, random endian. */if (temp_len < 4) break;if (UR(2)) {u32 pos = UR(temp_len - 3);*(u32*)(out_buf + pos) -= 1 + UR(ARITH_MAX);} else {u32 pos = UR(temp_len - 3);u32 num = 1 + UR(ARITH_MAX);*(u32*)(out_buf + pos) =SWAP32(SWAP32(*(u32*)(out_buf + pos)) - num);}break;case 9:/* Randomly add to dword, random endian. */if (temp_len < 4) break;if (UR(2)) {u32 pos = UR(temp_len - 3);*(u32*)(out_buf + pos) += 1 + UR(ARITH_MAX);} else {u32 pos = UR(temp_len - 3);u32 num = 1 + UR(ARITH_MAX);*(u32*)(out_buf + pos) =SWAP32(SWAP32(*(u32*)(out_buf + pos)) + num);}break;case 10:/* Just set a random byte to a random value. Because,why not. We use XOR with 1-255 to eliminate thepossibility of a no-op. */out_buf[UR(temp_len)] ^= 1 + UR(255);break;case 11 ... 12: {/* Delete bytes. We're making this a bit more likelythan insertion (the next option) in hopes of keepingfiles reasonably small. */u32 del_from, del_len;if (temp_len < 2) break;/* Don't delete too much. */del_len = choose_block_len(temp_len - 1);del_from = UR(temp_len - del_len + 1);memmove(out_buf + del_from, out_buf + del_from + del_len,temp_len - del_from - del_len);temp_len -= del_len;break;}case 13:if (temp_len + HAVOC_BLK_XL < MAX_FILE) {/* Clone bytes (75%) or insert a block of constant bytes (25%). */u8  actually_clone = UR(4);u32 clone_from, clone_to, clone_len;u8* new_buf;if (actually_clone) {clone_len  = choose_block_len(temp_len);clone_from = UR(temp_len - clone_len + 1);} else {clone_len = choose_block_len(HAVOC_BLK_XL);clone_from = 0;}clone_to   = UR(temp_len);new_buf = ck_alloc_nozero(temp_len + clone_len);/* Head */memcpy(new_buf, out_buf, clone_to);/* Inserted part */if (actually_clone)memcpy(new_buf + clone_to, out_buf + clone_from, clone_len);elsememset(new_buf + clone_to,UR(2) ? UR(256) : out_buf[UR(temp_len)], clone_len);/* Tail */memcpy(new_buf + clone_to + clone_len, out_buf + clone_to,temp_len - clone_to);ck_free(out_buf);out_buf = new_buf;temp_len += clone_len;}break;case 14: {/* Overwrite bytes with a randomly selected chunk (75%) or fixedbytes (25%). */u32 copy_from, copy_to, copy_len;if (temp_len < 2) break;copy_len  = choose_block_len(temp_len - 1);copy_from = UR(temp_len - copy_len + 1);copy_to   = UR(temp_len - copy_len + 1);if (UR(4)) {if (copy_from != copy_to)memmove(out_buf + copy_to, out_buf + copy_from, copy_len);} else memset(out_buf + copy_to,UR(2) ? UR(256) : out_buf[UR(temp_len)], copy_len);break;}/* Values 15 and 16 can be selected only if there are any extraspresent in the dictionaries. */case 15: {if (extras_cnt + a_extras_cnt == 0) break;/* Overwrite bytes with an extra. */if (!extras_cnt || (a_extras_cnt && UR(2))) {/* No user-specified extras or odds in our favor. Let's use anauto-detected one. */u32 use_extra = UR(a_extras_cnt);u32 extra_len = a_extras[use_extra].len;u32 insert_at;if (extra_len > temp_len) break;insert_at = UR(temp_len - extra_len + 1);memcpy(out_buf + insert_at, a_extras[use_extra].data, extra_len);} else {/* No auto extras or odds in our favor. Use the dictionary. */u32 use_extra = UR(extras_cnt);u32 extra_len = extras[use_extra].len;u32 insert_at;if (extra_len > temp_len) break;insert_at = UR(temp_len - extra_len + 1);memcpy(out_buf + insert_at, extras[use_extra].data, extra_len);}break;}case 16: {if (extras_cnt + a_extras_cnt == 0) break;u32 use_extra, extra_len, insert_at = UR(temp_len + 1);u8* new_buf;/* Insert an extra. Do the same dice-rolling stuff as for theprevious case. */if (!extras_cnt || (a_extras_cnt && UR(2))) {use_extra = UR(a_extras_cnt);extra_len = a_extras[use_extra].len;if (temp_len + extra_len >= MAX_FILE) break;new_buf = ck_alloc_nozero(temp_len + extra_len);/* Head */memcpy(new_buf, out_buf, insert_at);/* Inserted part */memcpy(new_buf + insert_at, a_extras[use_extra].data, extra_len);} else {use_extra = UR(extras_cnt);extra_len = extras[use_extra].len;if (temp_len + extra_len >= MAX_FILE) break;new_buf = ck_alloc_nozero(temp_len + extra_len);/* Head */memcpy(new_buf, out_buf, insert_at);/* Inserted part */memcpy(new_buf + insert_at, extras[use_extra].data, extra_len);}/* Tail */memcpy(new_buf + insert_at + extra_len, out_buf + insert_at,temp_len - insert_at);ck_free(out_buf);out_buf   = new_buf;temp_len += extra_len;break;}/* Values 17 to 20 can be selected only if region-level mutations are enabled *//* Replace the current region with a random region from a random seed */case 17: {u32 src_region_len = 0;u8* new_buf = choose_source_region(&src_region_len);if (new_buf == NULL) break;//replace the current regionck_free(out_buf);out_buf = new_buf;temp_len = src_region_len;break;}/* Insert a random region from a random seed to the beginning of the current region */case 18: {u32 src_region_len = 0;u8* src_region = choose_source_region(&src_region_len);if (src_region == NULL) break;if (temp_len + src_region_len >= MAX_FILE) {ck_free(src_region);break;}u8* new_buf = ck_alloc_nozero(temp_len + src_region_len);memcpy(new_buf, src_region, src_region_len);memcpy(&new_buf[src_region_len], out_buf, temp_len);ck_free(out_buf);ck_free(src_region);out_buf = new_buf;temp_len += src_region_len;break;}/* Insert a random region from a random seed to the end of the current region */case 19: {u32 src_region_len = 0;u8* src_region = choose_source_region(&src_region_len);if (src_region == NULL) break;if (temp_len + src_region_len >= MAX_FILE) {ck_free(src_region);break;}u8* new_buf = ck_alloc_nozero(temp_len + src_region_len);memcpy(new_buf, out_buf, temp_len);memcpy(&new_buf[temp_len], src_region, src_region_len);ck_free(out_buf);ck_free(src_region);out_buf = new_buf;temp_len += src_region_len;break;}/* Duplicate the current region */case 20: {if (temp_len * 2 >= MAX_FILE) break;u8* new_buf = ck_alloc_nozero(temp_len * 2);memcpy(new_buf, out_buf, temp_len);memcpy(&new_buf[temp_len], out_buf, temp_len);ck_free(out_buf);out_buf = new_buf;temp_len += temp_len;break;}}}if (common_fuzz_stuff(argv, out_buf, temp_len))goto abandon_entry;/* out_buf might have been mangled a bit, so let's restore it to itsoriginal size and shape. */if (temp_len < len) out_buf = ck_realloc(out_buf, len);temp_len = len;memcpy(out_buf, in_buf, len);/* If we're finding new stuff, let's run for a bit longer, limitspermitting. */if (queued_paths != havoc_queued) {if (perf_score <= HAVOC_MAX_MULT * 100) {stage_max  *= 2;perf_score *= 2;}havoc_queued = queued_paths;}}new_hit_cnt = queued_paths + unique_crashes;if (!splice_cycle) {stage_finds[STAGE_HAVOC]  += new_hit_cnt - orig_hit_cnt;stage_cycles[STAGE_HAVOC] += stage_max;} else {stage_finds[STAGE_SPLICE]  += new_hit_cnt - orig_hit_cnt;stage_cycles[STAGE_SPLICE] += stage_max;}#ifndef IGNORE_FINDS/************* SPLICING *************//* This is a last-resort strategy triggered by a full round with no findings.It takes the current input file, randomly selects another input, andsplices them together at some offset, then relies on the havoccode to mutate that blob. */retry_splicing:if (use_splicing && splice_cycle++ < SPLICE_CYCLES &&queued_paths > 1 && M2_len > 1) {struct queue_entry* target;u32 tid, split_at;u8* new_buf;s32 f_diff, l_diff;/* First of all, if we've modified in_buf for havoc, let's clean thatup... */if (in_buf != orig_in) {ck_free(in_buf);in_buf = orig_in;len = M2_len;}/* Pick a random queue entry and seek to it. Don't splice with yourself. */do { tid = UR(queued_paths); } while (tid == current_entry);splicing_with = tid;target = queue;while (tid >= 100) { target = target->next_100; tid -= 100; }while (tid--) target = target->next;/* Make sure that the target has a reasonable length. */while (target && (target->len < 2 || target == queue_cur)) {target = target->next;splicing_with++;}if (!target) goto retry_splicing;/* Read the testcase into a new buffer. */fd = open(target->fname, O_RDONLY);if (fd < 0) PFATAL("Unable to open '%s'", target->fname);new_buf = ck_alloc_nozero(target->len);ck_read(fd, new_buf, target->len, target->fname);close(fd);/* Find a suitable splicing location, somewhere between the first andthe last differing byte. Bail out if the difference is just a singlebyte or so. */locate_diffs(in_buf, new_buf, MIN(len, target->len), &f_diff, &l_diff);if (f_diff < 0 || l_diff < 2 || f_diff == l_diff) {ck_free(new_buf);goto retry_splicing;}/* Split somewhere between the first and last differing byte. */split_at = f_diff + UR(l_diff - f_diff);/* Do the thing. */len = target->len;memcpy(new_buf, in_buf, split_at);in_buf = new_buf;ck_free(out_buf);out_buf = ck_alloc_nozero(len);memcpy(out_buf, in_buf, len);goto havoc_stage;}#endif /* !IGNORE_FINDS */ret_val = 0;abandon_entry:splicing_with = -1;/* Update pending_not_fuzzed count if we made it through the calibrationcycle and have not seen this entry before. */if (!stop_soon && !queue_cur->cal_failed && !queue_cur->was_fuzzed) {queue_cur->was_fuzzed = 1;was_fuzzed_map[get_state_index(target_state_id)][queue_cur->index] = 1;pending_not_fuzzed--;if (queue_cur->favored) pending_favored--;}//munmap(orig_in, queue_cur->len);ck_free(orig_in);if (in_buf != orig_in) ck_free(in_buf);ck_free(out_buf);ck_free(eff_map);delete_kl_messages(kl_messages);return ret_val;#undef FLIP_BIT}

控制流从这里开始

//Skip some steps if in state_aware_mode because in this mode//the seed is selected based on state-aware algorithmsif (state_aware_mode) goto AFLNET_REGIONS_SELECTION;

之后跳到AFLNET_REGIONS_SELECTION
这里首先设置两个变量u32 M2_start_region_ID = 0, M2_region_count = 0;用于记录M2消息序列的区域。
在状态感知模式下通过target state ID来划分M2序列。
划分完成后构造消息序列kl_messages。
通过划分好的M2起始区域所在位置数和长度对消息序列划分

/* Construct the kl_messages linked list and identify boundary pointers (M2_prev and M2_next) */kl_messages = construct_kl_messages(queue_cur->fname, queue_cur->regions, queue_cur->region_count);kliter_t(lms) *it;M2_prev = NULL;M2_next = kl_end(kl_messages);u32 count = 0;for (it = kl_begin(kl_messages); it != kl_end(kl_messages); it = kl_next(it)) {if (count == M2_start_region_ID - 1) {M2_prev = it;}if (count == M2_start_region_ID + M2_region_count) {M2_next = it;}count++;}

找到对应M2的子消息序列的起始和结束位置。

/* Construct the buffer to be mutated and update out_buf */if (M2_prev == NULL) {it = kl_begin(kl_messages);} else {it = kl_next(M2_prev);}u32 in_buf_size = 0;while (it != M2_next) {in_buf = (u8 *) ck_realloc (in_buf, in_buf_size + kl_val(it)->msize);if (!in_buf) PFATAL("AFLNet cannot allocate memory for in_buf");//Retrieve data from kl_messages to populate the in_bufmemcpy(&in_buf[in_buf_size], kl_val(it)->mdata, kl_val(it)->msize);in_buf_size += kl_val(it)->msize;it = kl_next(it);}orig_in = in_buf;out_buf = ck_alloc_nozero(in_buf_size);memcpy(out_buf, in_buf, in_buf_size);//Update len to keep the correct size of the buffer being mutatedlen = in_buf_size;//Save the len for later useM2_len = len;

后面是一些变异策略，每种策略中均调用了common_fuzz_stuff()函数

 if (common_fuzz_stuff(argv, out_buf, len)) goto abandon_entry;