adjust cmplog header

5 files changed, 194 insertions, 13 deletions

diff --git a/.github/workflows/ci.yml b/.github/workflows/ci.yml
index ed382fbb..dd0d13e9 100644
--- a/.github/workflows/ci.yml
+++ b/.github/workflows/ci.yml
@@ -5,6 +5,7 @@ on:
     branches:
       - stable
       - dev
+      - 420
   pull_request:
     branches:
       - dev # No need for stable-pull-request, as that equals dev-push
diff --git a/GNUmakefile b/GNUmakefile
index 283c57c2..d3cf2674 100644
--- a/GNUmakefile
+++ b/GNUmakefile
@@ -464,8 +464,8 @@ src/afl-forkserver.o : $(COMM_HDR) src/afl-forkserver.c include/forkserver.h
 src/afl-sharedmem.o : $(COMM_HDR) src/afl-sharedmem.c include/sharedmem.h
 	$(CC) $(CFLAGS) $(CFLAGS_FLTO) -c src/afl-sharedmem.c -o src/afl-sharedmem.o
 
-afl-fuzz: $(COMM_HDR) include/afl-fuzz.h $(AFL_FUZZ_FILES) src/afl-common.o src/afl-sharedmem.o src/afl-forkserver.o src/afl-performance.o | test_x86
-	$(CC) $(CFLAGS) $(COMPILE_STATIC) $(CFLAGS_FLTO) $(AFL_FUZZ_FILES) src/afl-common.o src/afl-sharedmem.o src/afl-forkserver.o src/afl-performance.o -o $@ $(PYFLAGS) $(LDFLAGS) -lm
+afl-fuzz: $(COMM_HDR) include/afl-fuzz.h $(AFL_FUZZ_FILES) src/afl-common.o src/afl-sharedmem.o src/afl-forkserver.o src/afl-performance.o src/hashmap.c | test_x86
+	$(CC) $(CFLAGS) $(COMPILE_STATIC) $(CFLAGS_FLTO) -Wno-shift-count-overflow $(AFL_FUZZ_FILES) src/afl-common.o src/afl-sharedmem.o src/afl-forkserver.o src/afl-performance.o src/hashmap.c -o $@ $(PYFLAGS) $(LDFLAGS) -lm
 
 afl-showmap: src/afl-showmap.c src/afl-common.o src/afl-sharedmem.o src/afl-forkserver.o src/afl-performance.o $(COMM_HDR) | test_x86
 	$(CC) $(CFLAGS) $(COMPILE_STATIC) $(CFLAGS_FLTO) src/$@.c src/afl-fuzz-mutators.c src/afl-fuzz-python.c src/afl-common.o src/afl-sharedmem.o src/afl-forkserver.o src/afl-performance.o -o $@ $(PYFLAGS) $(LDFLAGS)
diff --git a/include/cmplog.h b/include/cmplog.h
index 91c2a665..589570fe 100644
--- a/include/cmplog.h
+++ b/include/cmplog.h
@@ -38,16 +38,16 @@
 
 #define SHAPE_BYTES(x) (x + 1)
 
-#define CMP_TYPE_INS 1
-#define CMP_TYPE_RTN 2
+#define CMP_TYPE_INS 0
+#define CMP_TYPE_RTN 1
 
 struct cmp_header {
 
   unsigned hits : 6;       // up to 63 entries, we have CMP_MAP_H = 32
-  unsigned shape : 6;      // 63 bytes, we support 32 max
-  unsigned type : 2;       // 4, we use 3: none, rtn, cmp
+  unsigned shape : 5;      // 31+1 bytes
+  unsigned type : 1;       // 4, we use 3: none, rtn, cmp
   unsigned attribute : 4;  // 16 for arithmetic comparison types
-  unsigned reserved : 6;
+  //unsigned reserved : 6;
 
 } __attribute__((packed));
 
diff --git a/src/afl-fuzz-redqueen.c b/src/afl-fuzz-redqueen.c
index eb96de68..bc83c9ed 100644
--- a/src/afl-fuzz-redqueen.c
+++ b/src/afl-fuzz-redqueen.c
@@ -87,6 +87,11 @@ static u32 hshape;
 static u64 screen_update;
 static u64 last_update;
 
+// hashmap functions
+void hashmap_reset();
+bool hashmap_search_and_add(uint8_t type, uint64_t key);
+bool hashmap_search_and_add_ptr(uint8_t type, u8 *key);
+
 static struct range *add_range(struct range *ranges, u32 start, u32 end) {
 
   struct range *r = ck_alloc_nozero(sizeof(struct range));
@@ -795,7 +800,7 @@ static u8 cmp_extend_encoding(afl_state_t *afl, struct cmp_header *h,
   u64 *o_buf_64 = (u64 *)&orig_buf[idx];
   u32 *o_buf_32 = (u32 *)&orig_buf[idx];
   u16 *o_buf_16 = (u16 *)&orig_buf[idx];
-  u8  *o_buf_8 = &orig_buf[idx];
+  // u8  *o_buf_8 = &orig_buf[idx];
 
   u32 its_len = MIN(len - idx, taint_len);
 
@@ -836,6 +841,7 @@ static u8 cmp_extend_encoding(afl_state_t *afl, struct cmp_header *h,
 
   // necessary for preventing heap access overflow
   bytes = MIN(bytes, len - idx);
+  if (unlikely(bytes <= 1)) { return 0; }
 
   //  reverse atoi()/strnu?toll() is expensive, so we only to it in lvl 3
   if (afl->cmplog_enable_transform && (lvl & LVL3)) {
@@ -1266,6 +1272,7 @@ static u8 cmp_extend_encoding(afl_state_t *afl, struct cmp_header *h,
 
     }
 
+    /*
     if (*status != 1) {  // u8
 
       // if (its_len >= 1)
@@ -1290,6 +1297,8 @@ static u8 cmp_extend_encoding(afl_state_t *afl, struct cmp_header *h,
 
     }
 
+    */
+
   }
 
   // If 'S' is set for cmplog mode then we try a scale encoding of the value.
@@ -1881,6 +1890,8 @@ static u8 cmp_fuzz(afl_state_t *afl, u32 key, u8 *orig_buf, u8 *buf, u8 *cbuf,
 
   hshape = SHAPE_BYTES(h->shape);
 
+  if (hshape < 2) { return 0; }
+
   if (h->hits > CMP_MAP_H) {
 
     loggeds = CMP_MAP_H;
@@ -1906,8 +1917,6 @@ static u8 cmp_fuzz(afl_state_t *afl, u32 key, u8 *orig_buf, u8 *buf, u8 *cbuf,
 
 #endif
 
-  if (hshape < 2) { return 0; }
-
   for (i = 0; i < loggeds; ++i) {
 
     struct cmp_operands *o = &afl->shm.cmp_map->log[key][i];
@@ -1945,6 +1954,16 @@ static u8 cmp_fuzz(afl_state_t *afl, u32 key, u8 *orig_buf, u8 *buf, u8 *cbuf,
 
     }
 
+    // TODO: add attribute? not sure
+    if (hshape <= 8 && !hashmap_search_and_add(hshape - 1, o->v0) &&
+        !hashmap_search_and_add(hshape - 1, orig_o->v0) &&
+        !hashmap_search_and_add(hshape - 1, o->v1) &&
+        !hashmap_search_and_add(hshape - 1, orig_o->v1)) {
+
+      continue;
+
+    }
+
 #ifdef _DEBUG
     fprintf(stderr, "Handling: %llx->%llx vs %llx->%llx attr=%u shape=%u\n",
             orig_o->v0, o->v0, orig_o->v1, o->v1, h->attribute, hshape);
@@ -2615,12 +2634,13 @@ static u8 rtn_extend_encoding(afl_state_t *afl, u8 entry,
 
           }
 
-          memcpy(buf + idx, tmp, hlen + 1 + off);
+          u32 tmp_l = hlen + 1 + off;
+          memcpy(buf + idx, tmp, tmp_l);
           if (unlikely(its_fuzz(afl, buf, len, status))) { return 1; }
-          tmp[hlen + 1 + off] = 0;
+          tmp[tmp_l] = 0;
           // fprintf(stderr, "RTN ATTEMPT idx=%u len=%u fromhex %u %s %s result
           // %u\n", idx, len, fromhex, tmp, repl, *status);
-          memcpy(buf + idx, save, hlen + 1 + off);
+          memcpy(buf + idx, save, tmp_l);
 
         }
 
@@ -2755,6 +2775,15 @@ static u8 rtn_fuzz(afl_state_t *afl, u32 key, u8 *orig_buf, u8 *buf, u8 *cbuf,
     fprintf(stderr, "\n");
 #endif
 
+    if (hshape <= 8 && !hashmap_search_and_add_ptr(hshape - 1, o->v0) &&
+        !hashmap_search_and_add_ptr(hshape - 1, orig_o->v0) &&
+        !hashmap_search_and_add_ptr(hshape - 1, o->v1) &&
+        !hashmap_search_and_add_ptr(hshape - 1, orig_o->v1)) {
+
+      continue;
+
+    }
+
     t = taint;
     while (t->next) {
 
@@ -3021,6 +3050,8 @@ u8 input_to_state_stage(afl_state_t *afl, u8 *orig_buf, u8 *buf, u32 len) {
 
   // Start insertion loop
 
+  hashmap_reset();
+
   u64 orig_hit_cnt, new_hit_cnt;
   u64 orig_execs = afl->fsrv.total_execs;
   orig_hit_cnt = afl->queued_items + afl->saved_crashes;
diff --git a/src/hashmap.c b/src/hashmap.c
new file mode 100644
index 00000000..a0a9283c
--- /dev/null
+++ b/src/hashmap.c
@@ -0,0 +1,149 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <stdbool.h>
+#include "types.h"
+#define TABLE_SIZE 10007  // Use a prime number for better distribution
+
+typedef struct HashNode {
+
+  uint64_t         key;
+  struct HashNode *next;
+
+} HashNode;
+
+typedef struct HashMap {
+
+  HashNode **table;
+
+} HashMap;
+
+static HashMap *_hashmap;
+
+void hashmap_reset() {
+
+  if (unlikely(!_hashmap)) {
+
+    _hashmap = (HashMap *)malloc(sizeof(HashMap));
+    _hashmap->table = (HashNode **)malloc(sizeof(HashNode *) * TABLE_SIZE);
+    memset((char *)_hashmap->table, 0, sizeof(HashNode *) * TABLE_SIZE);
+
+  } else {
+
+    for (int i = 0; i < TABLE_SIZE; i++) {
+
+      HashNode *node = _hashmap->table[i];
+      while (node) {
+
+        HashNode *temp = node;
+        node = node->next;
+        free(temp);
+
+      }
+
+    }
+
+    memset((char *)_hashmap->table, 0, sizeof(HashNode *) * TABLE_SIZE);
+
+  }
+
+}
+
+static inline unsigned int hash(uint64_t key) {
+
+  return key % TABLE_SIZE;
+
+}
+
+// type must be below 8
+bool hashmap_search_and_add(uint8_t type, uint64_t key) {
+
+  if (unlikely(type >= 8)) return false;
+  uint64_t     val = (key & 0xf8ffffffffffffff) + (type << 56);
+  unsigned int index = hash(val);
+  HashNode    *node = _hashmap->table[index];
+  while (node) {
+
+    if (node->key == val) return true;
+    node = node->next;
+
+  }
+
+  // not found so add it
+  node = (HashNode *)malloc(sizeof(HashNode));
+  node->key = val;
+  node->next = _hashmap->table[index];
+  _hashmap->table[index] = node;
+
+  return false;
+
+}
+
+// type must be below 8
+bool hashmap_search_and_add_ptr(uint8_t type, u8 *key) {
+
+  if (unlikely(type >= 8)) return false;
+  uint64_t key_t = 0;
+  memcpy(((char *)key_t) + (7 - type), key, type + 1);
+  return hashmap_search_and_add(type, key_t);
+
+}
+
+/* below is not used */
+
+void hashmap_insert(uint64_t key) {
+
+  unsigned int index = hash(key);
+  HashNode    *node = (HashNode *)malloc(sizeof(HashNode));
+  node->key = key;
+  node->next = _hashmap->table[index];
+  _hashmap->table[index] = node;
+
+}
+
+bool hashmap_search(uint64_t key) {
+
+  unsigned int index = hash(key);
+  HashNode    *node = _hashmap->table[index];
+  while (node) {
+
+    if (node->key == key) return true;
+    node = node->next;
+
+  }
+
+  return false;
+
+}
+
+void delete(uint64_t key) {
+
+  unsigned int index = hash(key);
+  HashNode    *prev = NULL, *node = _hashmap->table[index];
+  while (node) {
+
+    if (node->key == key) {
+
+      if (prev)
+        prev->next = node->next;
+      else
+        _hashmap->table[index] = node->next;
+      free(node);
+      return;
+
+    }
+
+    prev = node;
+    node = node->next;
+
+  }
+
+}
+
+void freeHashMap(HashMap *map) {
+
+  free(_hashmap->table);
+  free(map);
+
+}
+