Sampling next seed by weight (hit_count, bitmap_size, exec_us)

3 files changed, 38 insertions, 10 deletions

diff --git a/include/afl-fuzz.h b/include/afl-fuzz.h
index bdf44def..6ce032df 100644
--- a/include/afl-fuzz.h
+++ b/include/afl-fuzz.h
@@ -168,7 +168,8 @@ struct queue_entry {
   u8 *trace_mini;                       /* Trace bytes, if kept             */
   u32 tc_ref;                           /* Trace bytes ref count            */
 
-  double perf_score;                    /* performance score                */
+  double perf_score,                    /* performance score                */
+         weight;
 
   u8 *testcase_buf;                     /* The testcase buffer, if loaded.  */
 
diff --git a/src/afl-fuzz-one.c b/src/afl-fuzz-one.c
index ca48f72a..a48afffb 100644
--- a/src/afl-fuzz-one.c
+++ b/src/afl-fuzz-one.c
@@ -445,8 +445,10 @@ u8 fuzz_one_original(afl_state_t *afl) {
 
   if (unlikely(afl->not_on_tty)) {
 
-    ACTF("Fuzzing test case #%u (%u total, %llu uniq crashes found)...",
-         afl->current_entry, afl->queued_paths, afl->unique_crashes);
+    ACTF("Fuzzing test case #%u (%u total, %llu uniq crashes found, perf_score=%0.0f, exec_us=%llu, hits=%u, map=%u)...",
+         afl->current_entry, afl->queued_paths, afl->unique_crashes,
+         afl->queue_cur->perf_score, afl->queue_cur->exec_us,
+         afl->n_fuzz[afl->queue_cur->n_fuzz_entry], afl->queue_cur->bitmap_size);
     fflush(stdout);
 
   }
diff --git a/src/afl-fuzz-queue.c b/src/afl-fuzz-queue.c
index f35b4f57..1e997c55 100644
--- a/src/afl-fuzz-queue.c
+++ b/src/afl-fuzz-queue.c
@@ -42,6 +42,21 @@ 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) {
+
+  u32 hits = afl->n_fuzz[q->n_fuzz_entry];
+  if (hits == 0) hits = 1;
+
+  double weight = 1.0;
+  weight *= avg_exec_us / q->exec_us;
+  weight *= log(q->bitmap_size) / avg_bitmap_size;
+  weight /= log10(hits) + 1;
+
+  if (q->favored) weight *= 5;
+
+  return weight;
+}
+
 /* create the alias table that allows weighted random selection - expensive */
 
 void create_alias_table(afl_state_t *afl) {
@@ -65,25 +80,35 @@ void create_alias_table(afl_state_t *afl) {
   memset((void *)afl->alias_table, 0, n * sizeof(u32));
   memset((void *)afl->alias_probability, 0, n * sizeof(double));
 
-  double sum = 0;
-
+  double avg_exec_us = 0.0;
+  double avg_bitmap_size = 0.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;
+    avg_exec_us += q->exec_us;
+    avg_bitmap_size += log(q->bitmap_size);
 
   }
+  avg_exec_us /= afl->queued_paths;
+  avg_bitmap_size /= afl->queued_paths;
 
+  double sum = 0;
   for (i = 0; i < n; i++) {
 
     struct queue_entry *q = afl->queue_buf[i];
-    P[i] = (q->perf_score * n) / sum;
+
+    if (!q->disabled) {
+      q->weight = compute_weight(afl, q, avg_exec_us, avg_bitmap_size);
+      q->perf_score = calculate_score(afl, q);
+    }
+
+    sum += q->weight;
 
   }
 
+  for (i = 0; i < n; i++)
+    P[i] = (afl->queue_buf[i]->weight * n) / sum;
+
   int nS = 0, nL = 0, s;
   for (s = (s32)n - 1; s >= 0; --s) {