add new seed selection algo and make it the default
MODIFY
docs/Changelog.md
docs/Changelog.md
@@ -17,6 +17,10 @@ sending a mail to <afl-users+subscribe@googlegroups.com>.
- memory limits are now disabled by default, set them with -m if required
- deterministic fuzzing is now disabled by default and can be enabled with
-D. It is still enabled by default for -M.
+ - a new seed selection was implemented that uses weighted randoms based on
+ a schedule performance score, which is much better that the previous
+ walk the whole queue approach. Select the old mode with -Z (auto enabled
+ with -M)
- statsd support by Edznux, thanks a lot!
- Marcel Boehme submitted a patch that improves all AFFast schedules :)
- reading testcases from -i now descends into subdirectories

MODIFY
include/afl-fuzz.h
include/afl-fuzz.h
@@ -151,7 +151,8 @@ struct queue_entry {
favored, /* Currently favored? */
fs_redundant, /* Marked as redundant in the fs? */
fully_colorized, /* Do not run redqueen stage again */
- is_ascii; /* Is the input just ascii text? */
+ is_ascii, /* Is the input just ascii text? */
+ disabled; /* Is disabled from fuzz selection */
u32 bitmap_size, /* Number of bits set in bitmap */
fuzz_level, /* Number of fuzzing iterations */
@@ -165,6 +166,8 @@ struct queue_entry {
u8 *trace_mini; /* Trace bytes, if kept */
u32 tc_ref; /* Trace bytes ref count */
+ double perf_score; /* performance score */
+
struct queue_entry *next; /* Next element, if any */
};
@@ -488,12 +491,17 @@ typedef struct afl_state {
disable_trim, /* Never trim in fuzz_one */
shmem_testcase_mode, /* If sharedmem testcases are used */
expand_havoc, /* perform expensive havoc after no find */
- cycle_schedules; /* cycle power schedules? */
+ cycle_schedules, /* cycle power schedules? */
+ old_seed_selection; /* use vanilla afl seed selection */
u8 *virgin_bits, /* Regions yet untouched by fuzzing */
*virgin_tmout, /* Bits we haven't seen in tmouts */
*virgin_crash; /* Bits we haven't seen in crashes */
+ double *alias_probability; /* alias weighted probabilities */
+ u32 * alias_table; /* alias weighted random lookup table */
+ u32 active_paths; /* enabled entries in the queue */
+
u8 *var_bytes; /* Bytes that appear to be variable */
#define N_FUZZ_SIZE (1 << 21)
@@ -1009,6 +1017,8 @@ void find_timeout(afl_state_t *);
double get_runnable_processes(void);
void nuke_resume_dir(afl_state_t *);
int check_main_node_exists(afl_state_t *);
+u32 select_next_queue_entry(afl_state_t *afl);
+void create_alias_table(afl_state_t *afl);
void setup_dirs_fds(afl_state_t *);
void setup_cmdline_file(afl_state_t *, char **);
void setup_stdio_file(afl_state_t *);

MODIFY
src/afl-fuzz-init.c
src/afl-fuzz-init.c
@@ -959,6 +959,8 @@ void perform_dry_run(afl_state_t *afl) {
/* Remove from fuzzing queue but keep for splicing */
struct queue_entry *p = afl->queue;
+ p->disabled = 1;
+ p->perf_score = 0;
while (p && p->next != q)
p = p->next;
@@ -968,6 +970,7 @@ void perform_dry_run(afl_state_t *afl) {
afl->queue = q->next;
--afl->pending_not_fuzzed;
+ --afl->active_paths;
afl->max_depth = 0;
p = afl->queue;
@@ -1054,6 +1057,7 @@ restart_outer_cull_loop:
duplicates = 1;
--afl->pending_not_fuzzed;
+ afl->active_paths--;
// We do not remove any of the memory allocated because for
// splicing the data might still be interesting.
@@ -1063,11 +1067,15 @@ restart_outer_cull_loop:
// we keep the shorter file
if (p->len >= q->len) {
+ p->disabled = 1;
+ p->perf_score = 0;
q->next = p->next;
goto restart_inner_cull_loop;
} else {
+ q->disabled = 1;
+ q->perf_score = 0;
if (prev)
prev->next = q = p;
else

MODIFY
src/afl-fuzz-one.c
src/afl-fuzz-one.c
@@ -554,6 +554,9 @@ u8 fuzz_one_original(afl_state_t *afl) {
* PERFORMANCE SCORE *
*********************/
+ if (likely(!afl->old_seed_selection))
+ orig_perf = perf_score = afl->queue_cur->perf_score;
+ else
orig_perf = perf_score = calculate_score(afl, afl->queue_cur);
if (unlikely(perf_score == 0)) { goto abandon_entry; }
@@ -2769,6 +2772,9 @@ static u8 mopt_common_fuzzing(afl_state_t *afl, MOpt_globals_t MOpt_globals) {
* PERFORMANCE SCORE *
*********************/
+ if (likely(!afl->old_seed_selection))
+ orig_perf = perf_score = afl->queue_cur->perf_score;
+ else
orig_perf = perf_score = calculate_score(afl, afl->queue_cur);
if (unlikely(afl->shm.cmplog_mode && !afl->queue_cur->fully_colorized)) {

MODIFY
src/afl-fuzz-queue.c
src/afl-fuzz-queue.c
#include <ctype.h>
#include <math.h>
+inline u32 select_next_queue_entry(afl_state_t *afl) {
+
+ u32 r = rand_below(afl, 0xffffffff);
+ u32 s = r % afl->queued_paths;
+ // fprintf(stderr, "select: r=%u s=%u ... r < prob[s]=%f ? s=%u :
+ // alias[%u]=%u\n", r, s, afl->alias_probability[s], s, s,
+ // afl->alias_table[s]);
+ return (r < afl->alias_probability[s] ? s : afl->alias_table[s]);
+
+}
+
+void create_alias_table(afl_state_t *afl) {
+
+ u32 n = afl->queued_paths, i = 0, a, g;
+
+ 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 = (u32 *)afl_realloc(AFL_BUF_PARAM(out_scratch), n * sizeof(u32));
+ int * L = (u32 *)afl_realloc(AFL_BUF_PARAM(in_scratch), n * sizeof(u32));
+
+ if (!P || !S || !L) FATAL("could not aquire memory for alias table");
+ memset((void *)afl->alias_table, 0, n * sizeof(u32));
+ memset((void *)afl->alias_probability, 0, n * sizeof(double));
+
+ double sum = 0;
+
+ for (i = 0; i < n; i++) {
+
+ struct queue_entry *q = afl->queue_buf[i];
+
+ if (!q->disabled) q->perf_score = calculate_score(afl, q);
+
+ sum += q->perf_score;
+ /*
+ if (afl->debug)
+ fprintf(stderr, "entry %u: score=%f %s (sum: %f)\n", i, q->perf_score,
+ q->disabled ? "disabled" : "", sum);
+ */
+
+ }
+
+ for (i = 0; i < n; i++) {
+
+ struct queue_entry *q = afl->queue_buf[i];
+
+ P[i] = q->perf_score * n / sum;
+
+ }
+
+ int nS = 0, nL = 0, s;
+ for (s = (s32)n - 1; s >= 0; --s) {
+
+ if (P[s] < 1)
+ S[nS++] = s;
+ else
+ L[nL++] = s;
+
+ }
+
+ while (nS && nL) {
+
+ 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)
+ S[nS++] = g;
+ else
+ L[nL++] = g;
+
+ }
+
+ while (nL)
+ afl->alias_probability[L[--nL]] = 1;
+
+ while (nS)
+ afl->alias_probability[S[--nS]] = 1;
+
+ /*
+ if (afl->debug) {
+
+ fprintf(stderr, " %-3s %-3s %-9s\n", "entry", "alias", "prob");
+ for (u32 i = 0; i < n; ++i)
+ fprintf(stderr, " %3i %3i %9.7f\n", i, afl->alias_table[i],
+ afl->alias_probability[i]);
+
+ }
+
+ int prob = 0;
+ fprintf(stderr, "Alias:");
+ for (i = 0; i < n; i++) {
+
+ fprintf(stderr, " [%u]=%u", i, afl->alias_table[i]);
+ if (afl->alias_table[i] >= n)
+ prob = i;
+
+ }
+
+ fprintf(stderr, "\n");
+
+ if (prob) {
+
+ fprintf(stderr, "PROBLEM! alias[%u] = %u\n", prob,
+ afl->alias_table[prob]);
+
+ for (i = 0; i < n; i++) {
+
+ struct queue_entry *q = afl->queue_buf[i];
+
+ fprintf(stderr, "%u: score=%f\n", i, q->perf_score);
+
+ }
+
+ }
+
+ */
+
+}
+
/* Mark deterministic checks as done for a particular queue entry. We use the
.state file to avoid repeating deterministic fuzzing when resuming aborted
scans. */
@@ -237,6 +360,7 @@ void add_to_queue(afl_state_t *afl, u8 *fname, u32 len, u8 passed_det) {
if (likely(q->len > 4)) afl->ready_for_splicing_count++;
++afl->queued_paths;
+ ++afl->active_paths;
++afl->pending_not_fuzzed;
afl->cycles_wo_finds = 0;

MODIFY
src/afl-fuzz.c
src/afl-fuzz.c
@@ -115,6 +115,8 @@ static void usage(u8 *argv0, int more_help) {
" if using QEMU, just use -c 0.\n\n"
"Fuzzing behavior settings:\n"
+ " -Z - sequential queue selection instead of weighted "
+ "random\n"
" -N - do not unlink the fuzzing input file (for devices "
"etc.)\n"
" -n - fuzz without instrumentation (non-instrumented mode)\n"
@@ -131,8 +133,7 @@ static void usage(u8 *argv0, int more_help) {
"Other stuff:\n"
" -M/-S id - distributed mode (see docs/parallel_fuzzing.md)\n"
- " use -D to force -S secondary to perform deterministic "
- "fuzzing\n"
+ " -M auto-sets -D and -Z (use -d to disable -D)\n"
" -F path - sync to a foreign fuzzer queue directory (requires "
"-M, can\n"
" be specified up to %u times)\n"
@@ -250,7 +251,7 @@ int main(int argc, char **argv_orig, char **envp) {
s32 opt, i;
u64 prev_queued = 0;
- u32 sync_interval_cnt = 0, seek_to, show_help = 0, map_size = MAP_SIZE;
+ u32 sync_interval_cnt = 0, seek_to = 0, show_help = 0, map_size = MAP_SIZE;
u8 *extras_dir[4];
u8 mem_limit_given = 0, exit_1 = 0, debug = 0,
extras_dir_cnt = 0 /*, have_p = 0*/;
@@ -287,10 +288,14 @@ int main(int argc, char **argv_orig, char **envp) {
while ((opt = getopt(
argc, argv,
- "+b:c:i:I:o:f:F:m:t:T:dDnCB:S:M:x:QNUWe:p:s:V:E:L:hRP:")) > 0) {
+ "+b:c:i:I:o:f:F:m:t:T:dDnCB:S:M:x:QNUWe:p:s:V:E:L:hRP:Z")) > 0) {
switch (opt) {
+ case 'Z':
+ afl->old_seed_selection = 1;
+ break;
+
case 'I':
afl->infoexec = optarg;
break;
@@ -355,14 +360,16 @@ int main(int argc, char **argv_orig, char **envp) {
afl->schedule = RARE;
- } else if (!stricmp(optarg, "explore") || !stricmp(optarg, "afl")) {
-
- afl->schedule = EXPLORE;
+ } else if (!stricmp(optarg, "explore") || !stricmp(optarg, "afl") ||
- } else if (!stricmp(optarg, "seek") || !stricmp(optarg, "default") ||
+ !stricmp(optarg, "default") ||
!stricmp(optarg, "normal")) {
+ afl->schedule = EXPLORE;
+
+ } else if (!stricmp(optarg, "seek")) {
+
afl->schedule = SEEK;
} else {
@@ -404,7 +411,8 @@ int main(int argc, char **argv_orig, char **envp) {
if (afl->sync_id) { FATAL("Multiple -S or -M options not supported"); }
afl->sync_id = ck_strdup(optarg);
- afl->skip_deterministic = 0;
+ afl->skip_deterministic = 0; // force determinsitic fuzzing
+ afl->old_seed_selection = 1; // force old queue walking seed selection
if ((c = strchr(afl->sync_id, ':'))) {
@@ -1131,8 +1139,10 @@ int main(int argc, char **argv_orig, char **envp) {
if (afl->is_secondary_node && check_main_node_exists(afl) == 0) {
- WARNF("no -M main node found. You need to run one main instance!");
- sleep(3);
+ WARNF(
+ "no -M main node found. It is recommended to run exactly one main "
+ "instance.");
+ sleep(1);
}
@@ -1302,7 +1312,7 @@ int main(int argc, char **argv_orig, char **envp) {
show_init_stats(afl);
- seek_to = find_start_position(afl);
+ if (unlikely(afl->old_seed_selection)) seek_to = find_start_position(afl);
write_stats_file(afl, 0, 0, 0);
maybe_update_plot_file(afl, 0, 0);
@@ -1324,20 +1334,29 @@ int main(int argc, char **argv_orig, char **envp) {
// real start time, we reset, so this works correctly with -V
afl->start_time = get_cur_time();
+ u32 runs_in_current_cycle = (u32)-1;
+ u32 prev_queued_paths = 0;
+
while (1) {
u8 skipped_fuzz;
cull_queue(afl);
- if (!afl->queue_cur) {
+ if (unlikely((!afl->old_seed_selection &&
+ runs_in_current_cycle > afl->queued_paths) ||
+ (afl->old_seed_selection && !afl->queue_cur))) {
++afl->queue_cycle;
- afl->current_entry = 0;
+ runs_in_current_cycle = 0;
afl->cur_skipped_paths = 0;
+
+ if (unlikely(afl->old_seed_selection)) {
+
+ afl->current_entry = 0;
afl->queue_cur = afl->queue;
- if (seek_to) {
+ if (unlikely(seek_to)) {
afl->current_entry = seek_to;
afl->queue_cur = afl->queue_buf[seek_to];
@@ -1345,7 +1364,7 @@ int main(int argc, char **argv_orig, char **envp) {
}
- // show_stats(afl);
+ }
if (unlikely(afl->not_on_tty)) {
@@ -1366,9 +1385,11 @@ int main(int argc, char **argv_orig, char **envp) {
switch (afl->expand_havoc) {
case 0:
+ // this adds extra splicing mutation options to havoc mode
afl->expand_havoc = 1;
break;
case 1:
+ // add MOpt mutator
if (afl->limit_time_sig == 0 && !afl->custom_only &&
!afl->python_only) {
@@ -1381,25 +1402,26 @@ int main(int argc, char **argv_orig, char **envp) {
break;
case 2:
// if (!have_p) afl->schedule = EXPLOIT;
+ // increase havoc mutations per fuzz attempt
afl->havoc_stack_pow2++;
afl->expand_havoc = 3;
break;
case 3:
+ // further increase havoc mutations per fuzz attempt
afl->havoc_stack_pow2++;
afl->expand_havoc = 4;
break;
case 4:
+ // if not in sync mode, enable deterministic mode?
+ // if (!afl->sync_dir) afl->skip_deterministic = 0;
+ afl->expand_havoc = 5;
+ break;
+ case 5:
// nothing else currently
break;
}
- if (afl->expand_havoc) {
-
- } else
-
- afl->expand_havoc = 1;
-
} else {
afl->use_splicing = 1;
@@ -1470,6 +1492,22 @@ int main(int argc, char **argv_orig, char **envp) {
}
+ if (likely(!afl->old_seed_selection)) {
+
+ ++runs_in_current_cycle;
+ if (unlikely(prev_queued_paths < afl->queued_paths)) {
+
+ // we have new queue entries since the last run, recreate alias table
+ prev_queued_paths = afl->queued_paths;
+ create_alias_table(afl);
+
+ }
+
+ afl->current_entry = select_next_queue_entry(afl);
+ afl->queue_cur = afl->queue_buf[afl->current_entry];
+
+ }
+
skipped_fuzz = fuzz_one(afl);
if (!skipped_fuzz && !afl->stop_soon && afl->sync_id) {
@@ -1490,11 +1528,15 @@ int main(int argc, char **argv_orig, char **envp) {
if (afl->stop_soon) { break; }
+ if (unlikely(afl->old_seed_selection)) {
+
afl->queue_cur = afl->queue_cur->next;
++afl->current_entry;
}
+ }
+
write_bitmap(afl);
maybe_update_plot_file(afl, 0, 0);
save_auto(afl);

add new seed selection algo and make it the default