new seed selection algorithm

2 files changed, 50 insertions, 15 deletions

diff --git a/docs/Changelog.md b/docs/Changelog.md
index 1f6a940e..633e7071 100644
--- a/docs/Changelog.md
+++ b/docs/Changelog.md
@@ -8,9 +8,12 @@
     - fixed a regression in afl-fuzz that resulted in a 5-10% performace loss
       do a switch from gettimeofday() to clock_gettime() which should be rather
       three times faster. The reason for this is unknown.
+    - new queue selection algorithm based on 2 core years of queue data
+      analysis. gives a noticable improvement on coverage although the results
+      seem counterintuitive :-)
     - added AFL_DISABLE_REDUNDANT for huge queues
-    - fix AFL_PERSISTENT_RECORD
     - added `AFL_NO_SYNC` environment variable that does what you think it does
+    - fix AFL_PERSISTENT_RECORD
     - run custom_post_process after standard trimming
     - prevent filenames in the queue that have spaces
     - minor fix for FAST schedules
@@ -33,6 +36,7 @@
   * afl-showmap
     - fix memory leak on shmem testcase usage (thanks to @ndrewh)
     - minor fix to collect coverage -C (thanks to @bet4it)
+  * Fixed a shmem mmap bug (that rarely came up on MacOS)
   * libtokencap: script generate_libtoken_dict.sh added by @a-shvedov 
   * enhanced the ASAN configuration
 
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;