From e46c106b890404fbeb2d0e6120510ddf83113da6 Mon Sep 17 00:00:00 2001 From: vanhauser-thc Date: Thu, 6 Jun 2024 10:25:19 +0200 Subject: new seed selection algorithm --- src/afl-fuzz-queue.c | 59 +++++++++++++++++++++++++++++++++++++++------------- 1 file changed, 45 insertions(+), 14 deletions(-) (limited to 'src/afl-fuzz-queue.c') diff --git a/src/afl-fuzz-queue.c b/src/afl-fuzz-queue.c index 784b377a..d19dd51a 100644 --- a/src/afl-fuzz-queue.c +++ b/src/afl-fuzz-queue.c @@ -60,9 +60,9 @@ inline u32 select_next_queue_entry(afl_state_t *afl) { } -double compute_weight(afl_state_t *afl, struct queue_entry *q, - double avg_exec_us, double avg_bitmap_size, - double avg_top_size) { +inline double compute_weight(afl_state_t *afl, struct queue_entry *q, + double avg_exec_us, double avg_bitmap_size, + double avg_len) { double weight = 1.0; @@ -73,14 +73,45 @@ double compute_weight(afl_state_t *afl, struct queue_entry *q, } - if (likely(afl->schedule < RARE)) { weight *= (avg_exec_us / q->exec_us); } - weight *= (log(q->bitmap_size) / avg_bitmap_size); - weight *= (1 + (q->tc_ref / avg_top_size)); + if (likely(afl->schedule < RARE)) { + + double t = q->exec_us / avg_exec_us; + if (likely(t < 0.1)) { + + // nothing + + } else if (likely(t <= 0.25)) + + weight *= 0.9; + else if (likely(t <= 0.5)) { + + // nothing + + } else if (likely(t < 1.0)) + + weight *= 1.15; + else if (unlikely(t > 2.5 && t < 5.0)) + weight *= 1.1; + // else nothing + + } + + double l = q->len / avg_len; + if (likely(l < 0.1)) + weight *= 0.75; + else if (likely(l < 0.25)) + weight *= 1.1; + else if (unlikely(l >= 10)) + weight *= 1.1; + + double bms = q->bitmap_size / avg_bitmap_size; + if (likely(bms < 0.5)) + weight *= (1.0 + ((bms - 0.5) / 2)); + else if (unlikely(bms > 1.33)) + weight *= 1.1; - if (unlikely(weight < 0.1)) { weight = 0.1; } - if (unlikely(q->favored)) { weight *= 5; } - if (unlikely(!q->was_fuzzed)) { weight *= 2; } - if (unlikely(q->fs_redundant)) { weight *= 0.8; } + if (unlikely(!q->was_fuzzed)) { weight *= 2.5; } + if (unlikely(q->fs_redundant)) { weight *= 0.75; } return weight; @@ -117,7 +148,7 @@ void create_alias_table(afl_state_t *afl) { double avg_exec_us = 0.0; double avg_bitmap_size = 0.0; - double avg_top_size = 0.0; + double avg_len = 0.0; u32 active = 0; for (i = 0; i < n; i++) { @@ -129,7 +160,7 @@ void create_alias_table(afl_state_t *afl) { avg_exec_us += q->exec_us; avg_bitmap_size += log(q->bitmap_size); - avg_top_size += q->tc_ref; + avg_len += q->len; ++active; } @@ -138,7 +169,7 @@ void create_alias_table(afl_state_t *afl) { avg_exec_us /= active; avg_bitmap_size /= active; - avg_top_size /= active; + avg_len /= active; for (i = 0; i < n; i++) { @@ -147,7 +178,7 @@ void create_alias_table(afl_state_t *afl) { if (likely(!q->disabled)) { q->weight = - compute_weight(afl, q, avg_exec_us, avg_bitmap_size, avg_top_size); + compute_weight(afl, q, avg_exec_us, avg_bitmap_size, avg_len); q->perf_score = calculate_score(afl, q); sum += q->weight; -- cgit 1.4.1 From 477063e9ee88da5feb73b38b27a1241e8b77e002 Mon Sep 17 00:00:00 2001 From: vanhauser-thc Date: Thu, 6 Jun 2024 17:52:21 +0200 Subject: memory adjustments --- TODO.md | 1 + docs/Changelog.md | 1 + src/afl-fuzz-queue.c | 112 +++++++++++++++++++++++------------------------- src/afl-fuzz-redqueen.c | 34 ++++++++------- src/afl-fuzz-skipdet.c | 9 ++-- 5 files changed, 78 insertions(+), 79 deletions(-) (limited to 'src/afl-fuzz-queue.c') diff --git a/TODO.md b/TODO.md index ace07434..000c78dd 100644 --- a/TODO.md +++ b/TODO.md @@ -2,6 +2,7 @@ ## Must + - review: queue_testcase_store_mem and queue_testcase_get - hardened_usercopy=0 page_alloc.shuffle=0 - add value_profile but only enable after 15 minutes without finds - cmplog max items env? diff --git a/docs/Changelog.md b/docs/Changelog.md index 633e7071..cf5d2500 100644 --- a/docs/Changelog.md +++ b/docs/Changelog.md @@ -23,6 +23,7 @@ - -V timing is now accurately the fuzz time (without syncing), before long calibration times and syncing could result in now fuzzing being made when the time was already run out until then, thanks to @eqv! + - make afl-fuzz use less memory with cmplog and fix a memleak * afl-cc: - re-enable i386 support that was accidently disabled - fixes for LTO and outdated afl-gcc mode for i386 diff --git a/src/afl-fuzz-queue.c b/src/afl-fuzz-queue.c index d19dd51a..cbdfd5b0 100644 --- a/src/afl-fuzz-queue.c +++ b/src/afl-fuzz-queue.c @@ -60,63 +60,6 @@ inline u32 select_next_queue_entry(afl_state_t *afl) { } -inline double compute_weight(afl_state_t *afl, struct queue_entry *q, - double avg_exec_us, double avg_bitmap_size, - double avg_len) { - - double weight = 1.0; - - if (likely(afl->schedule >= FAST && afl->schedule <= RARE)) { - - u32 hits = afl->n_fuzz[q->n_fuzz_entry]; - if (likely(hits)) { weight /= (log10(hits) + 1); } - - } - - if (likely(afl->schedule < RARE)) { - - double t = q->exec_us / avg_exec_us; - if (likely(t < 0.1)) { - - // nothing - - } else if (likely(t <= 0.25)) - - weight *= 0.9; - else if (likely(t <= 0.5)) { - - // nothing - - } else if (likely(t < 1.0)) - - weight *= 1.15; - else if (unlikely(t > 2.5 && t < 5.0)) - weight *= 1.1; - // else nothing - - } - - double l = q->len / avg_len; - if (likely(l < 0.1)) - weight *= 0.75; - else if (likely(l < 0.25)) - weight *= 1.1; - else if (unlikely(l >= 10)) - weight *= 1.1; - - double bms = q->bitmap_size / avg_bitmap_size; - if (likely(bms < 0.5)) - weight *= (1.0 + ((bms - 0.5) / 2)); - else if (unlikely(bms > 1.33)) - weight *= 1.1; - - if (unlikely(!q->was_fuzzed)) { weight *= 2.5; } - if (unlikely(q->fs_redundant)) { weight *= 0.75; } - - return weight; - -} - /* create the alias table that allows weighted random selection - expensive */ void create_alias_table(afl_state_t *afl) { @@ -177,8 +120,59 @@ void create_alias_table(afl_state_t *afl) { if (likely(!q->disabled)) { - q->weight = - compute_weight(afl, q, avg_exec_us, avg_bitmap_size, avg_len); + double weight = 1.0; + { // inline does result in a compile error with LTO, weird + + if (likely(afl->schedule >= FAST && afl->schedule <= RARE)) { + + u32 hits = afl->n_fuzz[q->n_fuzz_entry]; + if (likely(hits)) { weight /= (log10(hits) + 1); } + + } + + if (likely(afl->schedule < RARE)) { + + double t = q->exec_us / avg_exec_us; + if (likely(t < 0.1)) { + + // nothing + + } else if (likely(t <= 0.25)) + + weight *= 0.9; + else if (likely(t <= 0.5)) { + + // nothing + + } else if (likely(t < 1.0)) + + weight *= 1.15; + else if (unlikely(t > 2.5 && t < 5.0)) + weight *= 1.1; + // else nothing + + } + + double l = q->len / avg_len; + if (likely(l < 0.1)) + weight *= 0.75; + else if (likely(l < 0.25)) + weight *= 1.1; + else if (unlikely(l >= 10)) + weight *= 1.1; + + double bms = q->bitmap_size / avg_bitmap_size; + if (likely(bms < 0.5)) + weight *= (1.0 + ((bms - 0.5) / 2)); + else if (unlikely(bms > 1.33)) + weight *= 1.1; + + if (unlikely(!q->was_fuzzed)) { weight *= 2.5; } + if (unlikely(q->fs_redundant)) { weight *= 0.75; } + + } + + q->weight = weight; q->perf_score = calculate_score(afl, q); sum += q->weight; diff --git a/src/afl-fuzz-redqueen.c b/src/afl-fuzz-redqueen.c index 9316da71..6c3582f2 100644 --- a/src/afl-fuzz-redqueen.c +++ b/src/afl-fuzz-redqueen.c @@ -322,7 +322,7 @@ static u8 colorization(afl_state_t *afl, u8 *buf, u32 len, memcpy(backup, buf, len); memcpy(changed, buf, len); - if (afl->cmplog_random_colorization) { + if (likely(afl->cmplog_random_colorization)) { random_replace(afl, changed, len); @@ -402,6 +402,7 @@ static u8 colorization(afl_state_t *afl, u8 *buf, u32 len, u32 i = 1; u32 positions = 0; + while (i) { restart: @@ -2996,15 +2997,16 @@ u8 input_to_state_stage(afl_state_t *afl, u8 *orig_buf, u8 *buf, u32 len) { struct tainted *t = taint; +#ifdef _DEBUG while (t) { -#ifdef _DEBUG fprintf(stderr, "T: idx=%u len=%u\n", t->pos, t->len); -#endif t = t->next; } +#endif + #if defined(_DEBUG) || defined(CMPLOG_INTROSPECTION) u64 start_time = get_cur_time(); u32 cmp_locations = 0; @@ -3148,27 +3150,27 @@ u8 input_to_state_stage(afl_state_t *afl, u8 *orig_buf, u8 *buf, u32 len) { exit_its: - if (afl->cmplog_lvl == CMPLOG_LVL_MAX) { + // if (afl->cmplog_lvl == CMPLOG_LVL_MAX) { - afl->queue_cur->colorized = CMPLOG_LVL_MAX; + afl->queue_cur->colorized = CMPLOG_LVL_MAX; - if (afl->queue_cur->cmplog_colorinput) { + if (afl->queue_cur->cmplog_colorinput) { - ck_free(afl->queue_cur->cmplog_colorinput); + ck_free(afl->queue_cur->cmplog_colorinput); - } + } - while (taint) { + while (taint) { - t = taint->next; - ck_free(taint); - taint = t; + t = taint->next; + ck_free(taint); + taint = t; - } + } - afl->queue_cur->taint = NULL; + afl->queue_cur->taint = NULL; - } else { + /*} else { afl->queue_cur->colorized = LVL2; @@ -3182,7 +3184,7 @@ exit_its: } - } + }*/ #ifdef CMPLOG_COMBINE if (afl->queued_items + afl->saved_crashes > orig_hit_cnt + 1) { diff --git a/src/afl-fuzz-skipdet.c b/src/afl-fuzz-skipdet.c index e52d59a3..8a927292 100644 --- a/src/afl-fuzz-skipdet.c +++ b/src/afl-fuzz-skipdet.c @@ -33,15 +33,15 @@ u8 is_det_timeout(u64 cur_ms, u8 is_flip) { u8 should_det_fuzz(afl_state_t *afl, struct queue_entry *q) { - if (!afl->skipdet_g->virgin_det_bits) { + if (unlikely(!afl->skipdet_g->virgin_det_bits)) { afl->skipdet_g->virgin_det_bits = (u8 *)ck_alloc(sizeof(u8) * afl->fsrv.map_size); } - if (!q->favored || q->passed_det) return 0; - if (!q->trace_mini) return 0; + if (likely(!q->favored || q->passed_det)) return 0; + if (unlikely(!q->trace_mini)) return 0; if (!afl->skipdet_g->last_cov_undet) afl->skipdet_g->last_cov_undet = get_cur_time(); @@ -122,7 +122,8 @@ u8 skip_deterministic_stage(afl_state_t *afl, u8 *orig_buf, u8 *out_buf, afl->stage_cur = 0; orig_hit_cnt = afl->queued_items + afl->saved_crashes; - u8 *inf_eff_map = (u8 *)ck_alloc(sizeof(u8) * len); + static u8 *inf_eff_map; + inf_eff_map = (u8 *)ck_realloc(inf_eff_map, sizeof(u8) * len); memset(inf_eff_map, 1, sizeof(u8) * len); if (common_fuzz_stuff(afl, orig_buf, len)) { return 0; } -- cgit 1.4.1 From fe36ceaa552569be66447aba11885259ca700d85 Mon Sep 17 00:00:00 2001 From: vanhauser-thc Date: Fri, 7 Jun 2024 11:16:42 +0200 Subject: minor testcache optimizations --- TODO.md | 1 - src/afl-fuzz-queue.c | 197 ++++++++++++++++++++++++++------------------------- 2 files changed, 102 insertions(+), 96 deletions(-) (limited to 'src/afl-fuzz-queue.c') diff --git a/TODO.md b/TODO.md index 000c78dd..ace07434 100644 --- a/TODO.md +++ b/TODO.md @@ -2,7 +2,6 @@ ## Must - - review: queue_testcase_store_mem and queue_testcase_get - hardened_usercopy=0 page_alloc.shuffle=0 - add value_profile but only enable after 15 minutes without finds - cmplog max items env? diff --git a/src/afl-fuzz-queue.c b/src/afl-fuzz-queue.c index cbdfd5b0..f4cb930d 100644 --- a/src/afl-fuzz-queue.c +++ b/src/afl-fuzz-queue.c @@ -621,6 +621,8 @@ void add_to_queue(afl_state_t *afl, u8 *fname, u32 len, u8 passed_det) { q->trace_mini = NULL; q->testcase_buf = NULL; q->mother = afl->queue_cur; + q->weight = 1.0; + q->perf_score = 100; #ifdef INTROSPECTION q->bitsmap_size = afl->bitsmap_size; @@ -1226,9 +1228,11 @@ inline void queue_testcase_retake(afl_state_t *afl, struct queue_entry *q, u32 len = q->len; - if (len != old_len) { + // only realloc if necessary or useful + // (a custom trim can make the testcase larger) + if (unlikely(len > old_len || len < old_len + 1024)) { - afl->q_testcase_cache_size = afl->q_testcase_cache_size + len - old_len; + afl->q_testcase_cache_size += len - old_len; q->testcase_buf = (u8 *)realloc(q->testcase_buf, len); if (unlikely(!q->testcase_buf)) { @@ -1257,41 +1261,48 @@ inline void queue_testcase_retake_mem(afl_state_t *afl, struct queue_entry *q, if (likely(q->testcase_buf)) { - u32 is_same = in == q->testcase_buf; + if (likely(in != q->testcase_buf)) { - if (likely(len != old_len)) { + // only realloc if we save memory + if (unlikely(len < old_len + 1024)) { - u8 *ptr = (u8 *)realloc(q->testcase_buf, len); + u8 *ptr = (u8 *)realloc(q->testcase_buf, len); - if (likely(ptr)) { + if (likely(ptr)) { - q->testcase_buf = ptr; - afl->q_testcase_cache_size = afl->q_testcase_cache_size + len - old_len; + q->testcase_buf = ptr; + afl->q_testcase_cache_size += len - old_len; + + } } - } + memcpy(q->testcase_buf, in, len); - if (unlikely(!is_same)) { memcpy(q->testcase_buf, in, len); } + } } } /* Returns the testcase buf from the file behind this queue entry. - Increases the refcount. */ + Increases the refcount. */ inline u8 *queue_testcase_get(afl_state_t *afl, struct queue_entry *q) { - u32 len = q->len; + if (likely(q->testcase_buf)) { return q->testcase_buf; } + + u32 len = q->len; + double weight = q->weight; - /* first handle if no testcase cache is configured */ + // first handle if no testcase cache is configured, or if the + // weighting of the testcase is below average. - if (unlikely(!afl->q_testcase_max_cache_size)) { + if (unlikely(weight < 1.0 || !afl->q_testcase_max_cache_size)) { u8 *buf; - if (unlikely(q == afl->queue_cur)) { + if (likely(q == afl->queue_cur)) { buf = (u8 *)afl_realloc((void **)&afl->testcase_buf, len); @@ -1317,118 +1328,113 @@ inline u8 *queue_testcase_get(afl_state_t *afl, struct queue_entry *q) { } - /* now handle the testcase cache */ + /* now handle the testcase cache and we know it is an interesting one */ - if (unlikely(!q->testcase_buf)) { - - /* Buf not cached, let's load it */ - u32 tid = afl->q_testcase_max_cache_count; - static u32 do_once = 0; // because even threaded we would want this. WIP - - while (unlikely( - (afl->q_testcase_cache_size + len >= afl->q_testcase_max_cache_size && - afl->q_testcase_cache_count > 1) || - afl->q_testcase_cache_count >= afl->q_testcase_max_cache_entries - 1)) { + /* Buf not cached, let's load it */ + u32 tid = afl->q_testcase_max_cache_count; + static u32 do_once = 0; // because even threaded we would want this. WIP - /* We want a max number of entries to the cache that we learn. - Very simple: once the cache is filled by size - that is the max. */ + while (unlikely( + (afl->q_testcase_cache_size + len >= afl->q_testcase_max_cache_size && + afl->q_testcase_cache_count > 1) || + afl->q_testcase_cache_count >= afl->q_testcase_max_cache_entries - 1)) { - if (unlikely(afl->q_testcase_cache_size + len >= - afl->q_testcase_max_cache_size && - (afl->q_testcase_cache_count < - afl->q_testcase_max_cache_entries && - afl->q_testcase_max_cache_count < - afl->q_testcase_max_cache_entries) && - !do_once)) { + /* We want a max number of entries to the cache that we learn. + Very simple: once the cache is filled by size - that is the max. */ - if (afl->q_testcase_max_cache_count > afl->q_testcase_cache_count) { + if (unlikely( + afl->q_testcase_cache_size + len >= + afl->q_testcase_max_cache_size && + (afl->q_testcase_cache_count < afl->q_testcase_max_cache_entries && + afl->q_testcase_max_cache_count < + afl->q_testcase_max_cache_entries) && + !do_once)) { - afl->q_testcase_max_cache_entries = - afl->q_testcase_max_cache_count + 1; - - } else { + if (afl->q_testcase_max_cache_count > afl->q_testcase_cache_count) { - afl->q_testcase_max_cache_entries = afl->q_testcase_cache_count + 1; + afl->q_testcase_max_cache_entries = afl->q_testcase_max_cache_count + 1; - } + } else { - do_once = 1; - // release unneeded memory - afl->q_testcase_cache = (struct queue_entry **)ck_realloc( - afl->q_testcase_cache, - (afl->q_testcase_max_cache_entries + 1) * sizeof(size_t)); + afl->q_testcase_max_cache_entries = afl->q_testcase_cache_count + 1; } - /* Cache full. We neet to evict one or more to map one. - Get a random one which is not in use */ + do_once = 1; + // release unneeded memory + afl->q_testcase_cache = (struct queue_entry **)ck_realloc( + afl->q_testcase_cache, + (afl->q_testcase_max_cache_entries + 1) * sizeof(size_t)); - do { + } - // if the cache (MB) is not enough for the queue then this gets - // undesirable because q_testcase_max_cache_count grows sometimes - // although the number of items in the cache will not change hence - // more and more loops - tid = rand_below(afl, afl->q_testcase_max_cache_count); + /* Cache full. We neet to evict one or more to map one. + Get a random one which is not in use */ - } while (afl->q_testcase_cache[tid] == NULL || + do { - afl->q_testcase_cache[tid] == afl->queue_cur); + // if the cache (MB) is not enough for the queue then this gets + // undesirable because q_testcase_max_cache_count grows sometimes + // although the number of items in the cache will not change hence + // more and more loops + tid = rand_below(afl, afl->q_testcase_max_cache_count); - struct queue_entry *old_cached = afl->q_testcase_cache[tid]; - free(old_cached->testcase_buf); - old_cached->testcase_buf = NULL; - afl->q_testcase_cache_size -= old_cached->len; - afl->q_testcase_cache[tid] = NULL; - --afl->q_testcase_cache_count; - ++afl->q_testcase_evictions; - if (tid < afl->q_testcase_smallest_free) - afl->q_testcase_smallest_free = tid; + } while (afl->q_testcase_cache[tid] == NULL || - } + afl->q_testcase_cache[tid] == afl->queue_cur); - if (unlikely(tid >= afl->q_testcase_max_cache_entries)) { + struct queue_entry *old_cached = afl->q_testcase_cache[tid]; + free(old_cached->testcase_buf); + old_cached->testcase_buf = NULL; + afl->q_testcase_cache_size -= old_cached->len; + afl->q_testcase_cache[tid] = NULL; + --afl->q_testcase_cache_count; + ++afl->q_testcase_evictions; + if (tid < afl->q_testcase_smallest_free) + afl->q_testcase_smallest_free = tid; - // uh we were full, so now we have to search from start - tid = afl->q_testcase_smallest_free; + } - } + if (unlikely(tid >= afl->q_testcase_max_cache_entries)) { - // we need this while loop in case there were ever previous evictions but - // not in this call. - while (unlikely(afl->q_testcase_cache[tid] != NULL)) - ++tid; + // uh we were full, so now we have to search from start + tid = afl->q_testcase_smallest_free; - /* Map the test case into memory. */ + } - int fd = open((char *)q->fname, O_RDONLY); + // we need this while loop in case there were ever previous evictions but + // not in this call. + while (unlikely(afl->q_testcase_cache[tid] != NULL)) + ++tid; - if (unlikely(fd < 0)) { PFATAL("Unable to open '%s'", (char *)q->fname); } + /* Map the test case into memory. */ - q->testcase_buf = (u8 *)malloc(len); + int fd = open((char *)q->fname, O_RDONLY); - if (unlikely(!q->testcase_buf)) { + if (unlikely(fd < 0)) { PFATAL("Unable to open '%s'", (char *)q->fname); } - PFATAL("Unable to malloc '%s' with len %u", (char *)q->fname, len); + q->testcase_buf = (u8 *)malloc(len); - } + if (unlikely(!q->testcase_buf)) { - ck_read(fd, q->testcase_buf, len, q->fname); - close(fd); + PFATAL("Unable to malloc '%s' with len %u", (char *)q->fname, len); + + } - /* Register testcase as cached */ - afl->q_testcase_cache[tid] = q; - afl->q_testcase_cache_size += len; - ++afl->q_testcase_cache_count; - if (likely(tid >= afl->q_testcase_max_cache_count)) { + ck_read(fd, q->testcase_buf, len, q->fname); + close(fd); - afl->q_testcase_max_cache_count = tid + 1; + /* Register testcase as cached */ + afl->q_testcase_cache[tid] = q; + afl->q_testcase_cache_size += len; + ++afl->q_testcase_cache_count; + if (likely(tid >= afl->q_testcase_max_cache_count)) { - } else if (unlikely(tid == afl->q_testcase_smallest_free)) { + afl->q_testcase_max_cache_count = tid + 1; - afl->q_testcase_smallest_free = tid + 1; + } else if (unlikely(tid == afl->q_testcase_smallest_free)) { - } + afl->q_testcase_smallest_free = tid + 1; } @@ -1443,12 +1449,13 @@ inline void queue_testcase_store_mem(afl_state_t *afl, struct queue_entry *q, u32 len = q->len; - if (unlikely(afl->q_testcase_cache_size + len >= + if (unlikely(q->weight < 1.0 || + afl->q_testcase_cache_size + len >= afl->q_testcase_max_cache_size || afl->q_testcase_cache_count >= afl->q_testcase_max_cache_entries - 1)) { - // no space? will be loaded regularly later. + // no space or uninteresting? will be loaded regularly later. return; } -- cgit 1.4.1