From 36127fb1970746f53fec44f9394061f57a4e94c3 Mon Sep 17 00:00:00 2001 From: vanhauser-thc Date: Wed, 5 Apr 2023 12:59:20 +0200 Subject: add -z switch --- src/afl-fuzz-queue.c | 7 ++++++- 1 file changed, 6 insertions(+), 1 deletion(-) (limited to 'src/afl-fuzz-queue.c') diff --git a/src/afl-fuzz-queue.c b/src/afl-fuzz-queue.c index 40184645..1cdc8b54 100644 --- a/src/afl-fuzz-queue.c +++ b/src/afl-fuzz-queue.c @@ -74,9 +74,14 @@ 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 (unlikely(weight < 1.0)) { weight = 1.0; } + if (unlikely(weight < 0.1)) { weight = 0.1; } if (unlikely(q->favored)) { weight *= 5; } if (unlikely(!q->was_fuzzed)) { weight *= 2; } + if (unlikely(afl->prefer_new)) { + + weight *= (2.0 * (q->id / (afl->queued_items - 1))); + + } return weight; -- cgit 1.4.1 From dba93705a79fb859ce0ede606f79dd4ed203725b Mon Sep 17 00:00:00 2001 From: vanhauser-thc Date: Wed, 5 Apr 2023 13:07:22 +0200 Subject: better new weighting --- src/afl-fuzz-queue.c | 10 ++++++---- 1 file changed, 6 insertions(+), 4 deletions(-) (limited to 'src/afl-fuzz-queue.c') diff --git a/src/afl-fuzz-queue.c b/src/afl-fuzz-queue.c index 1cdc8b54..3335e869 100644 --- a/src/afl-fuzz-queue.c +++ b/src/afl-fuzz-queue.c @@ -74,15 +74,17 @@ 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 (unlikely(weight < 0.1)) { weight = 0.1; } - if (unlikely(q->favored)) { weight *= 5; } - if (unlikely(!q->was_fuzzed)) { weight *= 2; } + if (unlikely(afl->prefer_new)) { - weight *= (2.0 * (q->id / (afl->queued_items - 1))); + weight *= (2.0 * ((1 + q->id) / afl->queued_items)); } + if (unlikely(weight < 0.1)) { weight = 0.1; } + if (unlikely(q->favored)) { weight *= 5; } + if (unlikely(!q->was_fuzzed)) { weight *= 2; } + return weight; } -- cgit 1.4.1 From f9851dbfbbfbc013172f500099b5f4dc572c508b Mon Sep 17 00:00:00 2001 From: vanhauser-thc Date: Sat, 8 Apr 2023 13:00:57 +0200 Subject: hopefully better -z algorithm --- src/afl-fuzz-queue.c | 26 ++++++++++++++++++++------ 1 file changed, 20 insertions(+), 6 deletions(-) (limited to 'src/afl-fuzz-queue.c') diff --git a/src/afl-fuzz-queue.c b/src/afl-fuzz-queue.c index 3335e869..6fc3c743 100644 --- a/src/afl-fuzz-queue.c +++ b/src/afl-fuzz-queue.c @@ -75,12 +75,6 @@ double compute_weight(afl_state_t *afl, struct queue_entry *q, weight *= (log(q->bitmap_size) / avg_bitmap_size); weight *= (1 + (q->tc_ref / avg_top_size)); - if (unlikely(afl->prefer_new)) { - - weight *= (2.0 * ((1 + q->id) / afl->queued_items)); - - } - if (unlikely(weight < 0.1)) { weight = 0.1; } if (unlikely(q->favored)) { weight *= 5; } if (unlikely(!q->was_fuzzed)) { weight *= 2; } @@ -155,6 +149,26 @@ void create_alias_table(afl_state_t *afl) { } + if (unlikely(afl->prefer_new) && afl->queued_discovered) { + + double avg_weight = sum / active; + + for (i = n - afl->queued_discovered; i < n; i++) { + + struct queue_entry *q = afl->queue_buf[i]; + + if (likely(!q->disabled) && q->weight > avg_weight) { + + double prev_weight = q->weight; + q->weight *= (2.0 * (i / n)); + sum += (q->weight - prev_weight); + + } + + } + + } + for (i = 0; i < n; i++) { // weight is always 0 for disabled entries -- cgit 1.4.1 From 6cc8d607fb24e060591ece4b42d83fc06de68fc6 Mon Sep 17 00:00:00 2001 From: vanhauser-thc Date: Thu, 13 Apr 2023 11:44:39 +0200 Subject: remove -z option, use -p mmopt instead --- GNUmakefile | 2 +- docs/Changelog.md | 2 +- include/afl-fuzz.h | 3 +-- instrumentation/SanitizerCoverageLTO.so.cc | 2 +- instrumentation/SanitizerCoveragePCGUARD.so.cc | 2 +- src/afl-fuzz-queue.c | 14 ++++---------- src/afl-fuzz.c | 7 +------ 7 files changed, 10 insertions(+), 22 deletions(-) (limited to 'src/afl-fuzz-queue.c') diff --git a/GNUmakefile b/GNUmakefile index 208e965b..85f164f5 100644 --- a/GNUmakefile +++ b/GNUmakefile @@ -546,7 +546,7 @@ ifndef AFL_NO_X86 test_build: afl-cc afl-gcc afl-as afl-showmap @echo "[*] Testing the CC wrapper afl-cc and its instrumentation output..." @unset AFL_MAP_SIZE AFL_USE_UBSAN AFL_USE_CFISAN AFL_USE_LSAN AFL_USE_ASAN AFL_USE_MSAN; ASAN_OPTIONS=detect_leaks=0 AFL_INST_RATIO=100 AFL_PATH=. ./afl-cc test-instr.c $(LDFLAGS) -o test-instr 2>&1 || (echo "Oops, afl-cc failed"; exit 1 ) - - ASAN_OPTIONS=detect_leaks=0 ./afl-showmap -m none -o .test-instr0 ./test-instr < /dev/null + -ASAN_OPTIONS=detect_leaks=0 ./afl-showmap -q -m none -o .test-instr0 ./test-instr < /dev/null -echo 1 | ASAN_OPTIONS=detect_leaks=0 ./afl-showmap -m none -q -o .test-instr1 ./test-instr @rm -f test-instr @cmp -s .test-instr0 .test-instr1; DR="$$?"; rm -f .test-instr0 .test-instr1; if [ "$$DR" = "0" ]; then echo; echo "Oops, the instrumentation of afl-cc does not seem to be behaving correctly!"; echo; echo "Please post to https://github.com/AFLplusplus/AFLplusplus/issues to troubleshoot the issue."; echo; exit 1; fi diff --git a/docs/Changelog.md b/docs/Changelog.md index 736deb30..501300b1 100644 --- a/docs/Changelog.md +++ b/docs/Changelog.md @@ -12,7 +12,7 @@ - fixed a crash in pizza (1st april easter egg) mode. Sorry for everyone who was affected! - allow pizza mode to be disabled when AFL_PIZZA_MODE is set to -1 - - add -z switch to prefer new coverage findings in seed selection + - option `-p mmopt` now also selects new queue items more often - print name of custom mutator in UI - afl-cc: - add CFI sanitizer variant to gcc targets diff --git a/include/afl-fuzz.h b/include/afl-fuzz.h index 7ff3315b..5fd393dd 100644 --- a/include/afl-fuzz.h +++ b/include/afl-fuzz.h @@ -501,8 +501,7 @@ typedef struct afl_state { custom_splice_optout, /* Custom mutator no splice buffer */ is_main_node, /* if this is the main node */ is_secondary_node, /* if this is a secondary instance */ - pizza_is_served, /* pizza mode */ - prefer_new; /* prefer new queue entries */ + pizza_is_served; /* pizza mode */ u32 stats_update_freq; /* Stats update frequency (execs) */ diff --git a/instrumentation/SanitizerCoverageLTO.so.cc b/instrumentation/SanitizerCoverageLTO.so.cc index 5603c455..e41f19b6 100644 --- a/instrumentation/SanitizerCoverageLTO.so.cc +++ b/instrumentation/SanitizerCoverageLTO.so.cc @@ -18,7 +18,7 @@ #include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/SmallVector.h" #if LLVM_VERSION_MAJOR < 17 -#include "llvm/ADT/Triple.h" + #include "llvm/ADT/Triple.h" #endif #include "llvm/Analysis/EHPersonalities.h" #include "llvm/Analysis/PostDominators.h" diff --git a/instrumentation/SanitizerCoveragePCGUARD.so.cc b/instrumentation/SanitizerCoveragePCGUARD.so.cc index 5f23698b..85b1ddd5 100644 --- a/instrumentation/SanitizerCoveragePCGUARD.so.cc +++ b/instrumentation/SanitizerCoveragePCGUARD.so.cc @@ -14,7 +14,7 @@ #include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/SmallVector.h" #if LLVM_VERSION_MAJOR < 17 -#include "llvm/ADT/Triple.h" + #include "llvm/ADT/Triple.h" #endif #include "llvm/Analysis/EHPersonalities.h" #include "llvm/Analysis/PostDominators.h" diff --git a/src/afl-fuzz-queue.c b/src/afl-fuzz-queue.c index 6fc3c743..8ad7cd97 100644 --- a/src/afl-fuzz-queue.c +++ b/src/afl-fuzz-queue.c @@ -149,21 +149,15 @@ void create_alias_table(afl_state_t *afl) { } - if (unlikely(afl->prefer_new) && afl->queued_discovered) { + if (unlikely(afl->schedule == MMOPT) && afl->queued_discovered) { - double avg_weight = sum / active; + u32 cnt = afl->queued_discovered >= 5 ? 5 : afl->queued_discovered; - for (i = n - afl->queued_discovered; i < n; i++) { + for (i = n - cnt; i < n; i++) { struct queue_entry *q = afl->queue_buf[i]; - if (likely(!q->disabled) && q->weight > avg_weight) { - - double prev_weight = q->weight; - q->weight *= (2.0 * (i / n)); - sum += (q->weight - prev_weight); - - } + if (likely(!q->disabled)) { q->weight *= 2.0; } } diff --git a/src/afl-fuzz.c b/src/afl-fuzz.c index a0c322da..5ba54d0b 100644 --- a/src/afl-fuzz.c +++ b/src/afl-fuzz.c @@ -132,7 +132,6 @@ static void usage(u8 *argv0, int more_help) { " fast(default), explore, exploit, seek, rare, mmopt, " "coe, lin\n" " quad -- see docs/FAQ.md for more information\n" - " -z - prefer new coverage findings when fuzzing\n" " -f file - location read by the fuzzed program (default: stdin " "or @@)\n" " -t msec - timeout for each run (auto-scaled, default %u ms). " @@ -556,7 +555,7 @@ int main(int argc, char **argv_orig, char **envp) { while ( (opt = getopt( argc, argv, - "+Ab:B:c:CdDe:E:hi:I:f:F:g:G:l:L:m:M:nNOo:p:RQs:S:t:T:UV:WXx:YzZ")) > + "+Ab:B:c:CdDe:E:hi:I:f:F:g:G:l:L:m:M:nNOo:p:RQs:S:t:T:UV:WXx:YZ")) > 0) { switch (opt) { @@ -569,10 +568,6 @@ int main(int argc, char **argv_orig, char **envp) { afl->max_length = atoi(optarg); break; - case 'z': - afl->prefer_new = 1; - break; - case 'Z': afl->old_seed_selection = 1; break; -- cgit 1.4.1 From a2daef29f9c323c0a6a7a64013aadb79ffd3e534 Mon Sep 17 00:00:00 2001 From: van Hauser Date: Thu, 27 Apr 2023 17:57:22 +0200 Subject: slightly different weighting algo (#1719) * better seed selection * slightly different weighting calculation * remove unnecessary memset --- include/afl-fuzz.h | 4 +-- src/afl-fuzz-queue.c | 92 +++++++++++++++++++++++++++++++++++----------------- 2 files changed, 65 insertions(+), 31 deletions(-) (limited to 'src/afl-fuzz-queue.c') diff --git a/include/afl-fuzz.h b/include/afl-fuzz.h index 831a0dbc..8fb7ecb1 100644 --- a/include/afl-fuzz.h +++ b/include/afl-fuzz.h @@ -1223,7 +1223,7 @@ double rand_next_percent(afl_state_t *afl); static inline u32 rand_below(afl_state_t *afl, u32 limit) { - if (limit <= 1) return 0; + if (unlikely(limit <= 1)) return 0; /* The boundary not being necessarily a power of 2, we need to ensure the result uniformity. */ @@ -1256,7 +1256,7 @@ static inline u32 rand_below(afl_state_t *afl, u32 limit) { expand havoc mode */ static inline u32 rand_below_datalen(afl_state_t *afl, u32 limit) { - if (limit <= 1) return 0; + if (unlikely(limit <= 1)) return 0; switch (rand_below(afl, 3)) { diff --git a/src/afl-fuzz-queue.c b/src/afl-fuzz-queue.c index 8ad7cd97..b10bf749 100644 --- a/src/afl-fuzz-queue.c +++ b/src/afl-fuzz-queue.c @@ -49,11 +49,13 @@ inline u32 select_next_queue_entry(afl_state_t *afl) { u32 s = rand_below(afl, afl->queued_items); double p = rand_next_percent(afl); + /* fprintf(stderr, "select: p=%f s=%u ... p < prob[s]=%f ? s=%u : alias[%u]=%u" " ==> %u\n", p, s, afl->alias_probability[s], s, s, afl->alias_table[s], p < afl->alias_probability[s] ? s : afl->alias_table[s]); */ + return (p < afl->alias_probability[s] ? s : afl->alias_table[s]); } @@ -87,25 +89,28 @@ double compute_weight(afl_state_t *afl, struct queue_entry *q, void create_alias_table(afl_state_t *afl) { - u32 n = afl->queued_items, i = 0, a, g; + u32 n = afl->queued_items, i = 0, nSmall = 0, nLarge = n - 1; double sum = 0; + double *P = (double *)afl_realloc(AFL_BUF_PARAM(out), n * sizeof(double)); + u32 *Small = (int *)afl_realloc(AFL_BUF_PARAM(out_scratch), n * sizeof(u32)); + u32 *Large = (int *)afl_realloc(AFL_BUF_PARAM(in_scratch), n * sizeof(u32)); + afl->alias_table = (u32 *)afl_realloc((void **)&afl->alias_table, n * sizeof(u32)); afl->alias_probability = (double *)afl_realloc( (void **)&afl->alias_probability, n * sizeof(double)); - double *P = (double *)afl_realloc(AFL_BUF_PARAM(out), n * sizeof(double)); - int *S = (int *)afl_realloc(AFL_BUF_PARAM(out_scratch), n * sizeof(u32)); - int *L = (int *)afl_realloc(AFL_BUF_PARAM(in_scratch), n * sizeof(u32)); - if (!P || !S || !L || !afl->alias_table || !afl->alias_probability) { + if (!P || !Small || !Large || !afl->alias_table || !afl->alias_probability) { FATAL("could not acquire memory for alias table"); } - memset((void *)afl->alias_table, 0, n * sizeof(u32)); memset((void *)afl->alias_probability, 0, n * sizeof(double)); + memset((void *)afl->alias_table, 0, n * sizeof(u32)); + memset((void *)Small, 0, n * sizeof(u32)); + memset((void *)Large, 0, n * sizeof(u32)); if (likely(afl->schedule < RARE)) { @@ -166,7 +171,15 @@ void create_alias_table(afl_state_t *afl) { for (i = 0; i < n; i++) { // weight is always 0 for disabled entries - P[i] = (afl->queue_buf[i]->weight * n) / sum; + if (unlikely(afl->queue_buf[i]->disabled)) { + + P[i] = 0; + + } else { + + P[i] = (afl->queue_buf[i]->weight * n) / sum; + + } } @@ -176,60 +189,81 @@ void create_alias_table(afl_state_t *afl) { struct queue_entry *q = afl->queue_buf[i]; - if (likely(!q->disabled)) { q->perf_score = calculate_score(afl, q); } + if (likely(!q->disabled)) { + + q->perf_score = calculate_score(afl, q); + sum += q->perf_score; - sum += q->perf_score; + } } for (i = 0; i < n; i++) { // perf_score is always 0 for disabled entries - P[i] = (afl->queue_buf[i]->perf_score * n) / sum; + if (unlikely(afl->queue_buf[i]->disabled)) { + + P[i] = 0; + + } else { + + P[i] = (afl->queue_buf[i]->perf_score * n) / sum; + + } } } - int nS = 0, nL = 0, s; - for (s = (s32)n - 1; s >= 0; --s) { + // Done collecting weightings in P, now create the arrays. + + for (s32 j = (s32)(n - 1); j >= 0; j--) { - if (P[s] < 1) { + if (P[j] < 1) { - S[nS++] = s; + Small[nSmall++] = (u32)j; } else { - L[nL++] = s; + Large[nLarge--] = (u32)j; } } - while (nS && nL) { + while (nSmall && nLarge != n - 1) { + + u32 small = Small[--nSmall]; + u32 large = Large[++nLarge]; + + afl->alias_probability[small] = P[small]; + afl->alias_table[small] = large; - a = S[--nS]; - g = L[--nL]; - afl->alias_probability[a] = P[a]; - afl->alias_table[a] = g; - P[g] = P[g] + P[a] - 1; - if (P[g] < 1) { + P[large] = P[large] - (1 - P[small]); - S[nS++] = g; + if (P[large] < 1) { + + Small[nSmall++] = large; } else { - L[nL++] = g; + Large[nLarge--] = large; } } - while (nL) - afl->alias_probability[L[--nL]] = 1; + while (nSmall) { + + afl->alias_probability[Small[--nSmall]] = 1; + + } - while (nS) - afl->alias_probability[S[--nS]] = 1; + while (nLarge != n - 1) { + + afl->alias_probability[Large[++nLarge]] = 1; + + } afl->reinit_table = 0; @@ -264,7 +298,7 @@ void create_alias_table(afl_state_t *afl) { */ /* fprintf(stderr, " entry alias probability perf_score weight - filename\n"); for (u32 i = 0; i < n; ++i) fprintf(stderr, " %5u %5u %11u + filename\n"); for (i = 0; i < n; ++i) fprintf(stderr, " %5u %5u %11u %0.9f %0.9f %s\n", i, afl->alias_table[i], afl->alias_probability[i], afl->queue_buf[i]->perf_score, afl->queue_buf[i]->weight, afl->queue_buf[i]->fname); -- cgit 1.4.1