add new seed selection algo and make it the default

6 files changed, 227 insertions, 33 deletions

diff --git a/docs/Changelog.md b/docs/Changelog.md
index 9eb47e18..f15f1d93 100644
--- a/docs/Changelog.md
+++ b/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
diff --git a/include/afl-fuzz.h b/include/afl-fuzz.h
index e9d148e9..45de197d 100644
--- a/include/afl-fuzz.h
+++ b/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 *);
diff --git a/src/afl-fuzz-init.c b/src/afl-fuzz-init.c
index 65478a78..881bf10f 100644
--- a/src/afl-fuzz-init.c
+++ b/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
diff --git a/src/afl-fuzz-one.c b/src/afl-fuzz-one.c
index c04b492b..6ef728e0 100644
--- a/src/afl-fuzz-one.c
+++ b/src/afl-fuzz-one.c
@@ -554,7 +554,10 @@ u8 fuzz_one_original(afl_state_t *afl) {
    * PERFORMANCE SCORE *
    *********************/
 
-  orig_perf = perf_score = calculate_score(afl, afl->queue_cur);
+  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,7 +2772,10 @@ static u8 mopt_common_fuzzing(afl_state_t *afl, MOpt_globals_t MOpt_globals) {
    * PERFORMANCE SCORE *
    *********************/
 
-  orig_perf = perf_score = calculate_score(afl, afl->queue_cur);
+  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)) {
 
diff --git a/src/afl-fuzz-queue.c b/src/afl-fuzz-queue.c
index 0d7d0314..d608e890 100644
--- a/src/afl-fuzz-queue.c
+++ b/src/afl-fuzz-queue.c
@@ -27,6 +27,129 @@
 #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;
diff --git a/src/afl-fuzz.c b/src/afl-fuzz.c
index 24df2997..004adffe 100644
--- a/src/afl-fuzz.c
+++ b/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,28 +1334,37 @@ 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;
-      afl->queue_cur = afl->queue;
 
-      if (seek_to) {
+      if (unlikely(afl->old_seed_selection)) {
 
-        afl->current_entry = seek_to;
-        afl->queue_cur = afl->queue_buf[seek_to];
-        seek_to = 0;
+        afl->current_entry = 0;
+        afl->queue_cur = afl->queue;
 
-      }
+        if (unlikely(seek_to)) {
 
-      // show_stats(afl);
+          afl->current_entry = seek_to;
+          afl->queue_cur = afl->queue_buf[seek_to];
+          seek_to = 0;
+
+        }
+
+      }
 
       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,8 +1528,12 @@ int main(int argc, char **argv_orig, char **envp) {
 
     if (afl->stop_soon) { break; }
 
-    afl->queue_cur = afl->queue_cur->next;
-    ++afl->current_entry;
+    if (unlikely(afl->old_seed_selection)) {
+
+      afl->queue_cur = afl->queue_cur->next;
+      ++afl->current_entry;
+
+    }
 
   }