Merge pull request #202 from vanhauser-thc/cmplog_routines

Cmplog routines for LLVM mode

9 files changed, 612 insertions, 465 deletions

diff --git a/include/afl-fuzz.h b/include/afl-fuzz.h
index c62fcc84..46bead3a 100644
--- a/include/afl-fuzz.h
+++ b/include/afl-fuzz.h
@@ -118,7 +118,8 @@ struct queue_entry {
       has_new_cov,                      /* Triggers new coverage?           */
       var_behavior,                     /* Variable behavior?               */
       favored,                          /* Currently favored?               */
-      fs_redundant;                     /* Marked as redundant in the fs?   */
+      fs_redundant,                     /* Marked as redundant in the fs?   */
+      fully_colorized;                  /* Do not run redqueen stage again  */
 
   u32 bitmap_size,                      /* Number of bits set in bitmap     */
       fuzz_level,                       /* Number of fuzzing iterations     */
diff --git a/include/cmplog.h b/include/cmplog.h
index c02650ee..18c6a7ef 100644
--- a/include/cmplog.h
+++ b/include/cmplog.h
@@ -31,6 +31,7 @@
 
 #define CMP_MAP_W 65536
 #define CMP_MAP_H 256
+#define CMP_MAP_RTN_H (CMP_MAP_H / 4)
 
 #define SHAPE_BYTES(x) (x + 1)
 
diff --git a/llvm_mode/Makefile b/llvm_mode/Makefile
index cdd89f27..5567f793 100644
--- a/llvm_mode/Makefile
+++ b/llvm_mode/Makefile
@@ -132,9 +132,9 @@ ifeq "$(TEST_MMAP)" "1"
 endif
 
 ifndef AFL_TRACE_PC
-  PROGS      = ../afl-clang-fast ../afl-llvm-cmplog-rt.o ../afl-llvm-cmplog-rt-32.o ../afl-llvm-cmplog-rt-64.o ../afl-llvm-pass.so ../libLLVMInsTrim.so ../afl-llvm-rt.o ../afl-llvm-rt-32.o ../afl-llvm-rt-64.o ../compare-transform-pass.so ../split-compares-pass.so ../split-switches-pass.so
+  PROGS      = ../afl-clang-fast ../afl-llvm-pass.so ../libLLVMInsTrim.so ../afl-llvm-rt.o ../afl-llvm-rt-32.o ../afl-llvm-rt-64.o ../compare-transform-pass.so ../split-compares-pass.so ../split-switches-pass.so ../cmplog-routines-pass.so
 else
-  PROGS      = ../afl-clang-fast ../afl-llvm-cmplog-rt.o ../afl-llvm-cmplog-rt-32.o ../afl-llvm-cmplog-rt-64.o ../afl-llvm-rt.o ../afl-llvm-rt-32.o ../afl-llvm-rt-64.o ../compare-transform-pass.so ../split-compares-pass.so ../split-switches-pass.so
+  PROGS      = ../afl-clang-fast ../afl-llvm-rt.o ../afl-llvm-rt-32.o ../afl-llvm-rt-64.o ../compare-transform-pass.so ../split-compares-pass.so ../split-switches-pass.so
 endif
 
 ifneq "$(CLANGVER)" "$(LLVMVER)"
@@ -219,6 +219,9 @@ afl-common.o: ../src/afl-common.c
 	$(CXX) $(CLANG_CFL) -shared $< -o $@ $(CLANG_LFL)
 # /laf
 
+../cmplog-routines-pass.so:	cmplog-routines-pass.cc | test_deps
+	$(CXX) $(CLANG_CFL) -shared $< -o $@ $(CLANG_LFL)
+
 ../afl-llvm-rt.o: afl-llvm-rt.o.c | test_deps
 	$(CC) $(CFLAGS) -fPIC -c $< -o $@
 
@@ -230,17 +233,6 @@ afl-common.o: ../src/afl-common.c
 	@printf "[*] Building 64-bit variant of the runtime (-m64)... "
 	@$(CC) $(CFLAGS) -m64 -fPIC -c $< -o $@ 2>/dev/null; if [ "$$?" = "0" ]; then echo "success!"; else echo "failed (that's fine)"; fi
 
-../afl-llvm-cmplog-rt.o: afl-llvm-cmplog-rt.o.c | test_deps
-	$(CC) $(CFLAGS) -fPIC -c $< -o $@
-
-../afl-llvm-cmplog-rt-32.o: afl-llvm-cmplog-rt.o.c | test_deps
-	@printf "[*] Building 32-bit variant of the CmpLog runtime (-m32)... "
-	@$(CC) $(CFLAGS) -m32 -fPIC -c $< -o $@ 2>/dev/null; if [ "$$?" = "0" ]; then echo "success!"; else echo "failed (that's fine)"; fi
-
-../afl-llvm-cmplog-rt-64.o: afl-llvm-cmplog-rt.o.c | test_deps
-	@printf "[*] Building 64-bit variant of the CmpLog runtime (-m64)... "
-	@$(CC) $(CFLAGS) -m64 -fPIC -c $< -o $@ 2>/dev/null; if [ "$$?" = "0" ]; then echo "success!"; else echo "failed (that's fine)"; fi
-
 test_build: $(PROGS)
 	@echo "[*] Testing the CC wrapper and instrumentation output..."
 	unset AFL_USE_ASAN AFL_USE_MSAN AFL_INST_RATIO; AFL_QUIET=1 AFL_PATH=. AFL_CC=$(CC) AFL_LLVM_LAF_SPLIT_SWITCHES=1 AFL_LLVM_LAF_TRANSFORM_COMPARES=1 AFL_LLVM_LAF_SPLIT_COMPARES=1 ../afl-clang-fast $(CFLAGS) ../test-instr.c -o test-instr $(LDFLAGS)
diff --git a/llvm_mode/afl-clang-fast.c b/llvm_mode/afl-clang-fast.c
index 5e152e86..683b6bee 100644
--- a/llvm_mode/afl-clang-fast.c
+++ b/llvm_mode/afl-clang-fast.c
@@ -202,6 +202,14 @@ static void edit_params(u32 argc, char** argv) {
   if (cmplog_mode) {
 
     cc_params[cc_par_cnt++] = "-fsanitize-coverage=trace-pc-guard,trace-cmp";
+    
+    cc_params[cc_par_cnt++] = "-Xclang";
+    cc_params[cc_par_cnt++] = "-load";
+    cc_params[cc_par_cnt++] = "-Xclang";
+    cc_params[cc_par_cnt++] =
+        alloc_printf("%s/cmplog-routines-pass.so", obj_path);
+    
+    cc_params[cc_par_cnt++] = "-fno-inline";
 
   } else {
 
@@ -411,20 +419,12 @@ static void edit_params(u32 argc, char** argv) {
     switch (bit_mode) {
 
       case 0:
-        if (cmplog_mode)
-          cc_params[cc_par_cnt++] =
-              alloc_printf("%s/afl-llvm-cmplog-rt.o", obj_path);
-        else
-          cc_params[cc_par_cnt++] = alloc_printf("%s/afl-llvm-rt.o", obj_path);
+        cc_params[cc_par_cnt++] = alloc_printf("%s/afl-llvm-rt.o", obj_path);
         break;
 
       case 32:
-        if (cmplog_mode)
-          cc_params[cc_par_cnt++] =
-              alloc_printf("%s/afl-llvm-cmplog-rt-32.o", obj_path);
-        else
-          cc_params[cc_par_cnt++] =
-              alloc_printf("%s/afl-llvm-rt-32.o", obj_path);
+        cc_params[cc_par_cnt++] =
+            alloc_printf("%s/afl-llvm-rt-32.o", obj_path);
 
         if (access(cc_params[cc_par_cnt - 1], R_OK))
           FATAL("-m32 is not supported by your compiler");
@@ -432,12 +432,8 @@ static void edit_params(u32 argc, char** argv) {
         break;
 
       case 64:
-        if (cmplog_mode)
-          cc_params[cc_par_cnt++] =
-              alloc_printf("%s/afl-llvm-cmplog-rt-64.o", obj_path);
-        else
-          cc_params[cc_par_cnt++] =
-              alloc_printf("%s/afl-llvm-rt-64.o", obj_path);
+        cc_params[cc_par_cnt++] =
+            alloc_printf("%s/afl-llvm-rt-64.o", obj_path);
 
         if (access(cc_params[cc_par_cnt - 1], R_OK))
           FATAL("-m64 is not supported by your compiler");
diff --git a/llvm_mode/afl-llvm-cmplog-rt.o.c b/llvm_mode/afl-llvm-cmplog-rt.o.c
deleted file mode 100644
index 7a513c0d..00000000
--- a/llvm_mode/afl-llvm-cmplog-rt.o.c
+++ /dev/null
@@ -1,412 +0,0 @@
-/*
-   american fuzzy lop++ - LLVM instrumentation bootstrap
-   ---------------------------------------------------
-
-   Written by Laszlo Szekeres <lszekeres@google.com> and
-              Michal Zalewski
-
-   LLVM integration design comes from Laszlo Szekeres.
-
-   Copyright 2015, 2016 Google Inc. All rights reserved.
-   Copyright 2019-2020 AFLplusplus Project. All rights reserved.
-
-   Licensed under the Apache License, Version 2.0 (the "License");
-   you may not use this file except in compliance with the License.
-   You may obtain a copy of the License at:
-
-     http://www.apache.org/licenses/LICENSE-2.0
-
-   This code is the rewrite of afl-as.h's main_payload.
-
-*/
-
-#ifdef __ANDROID__
-#include "android-ashmem.h"
-#endif
-#include "config.h"
-#include "types.h"
-#include "cmplog.h"
-
-#include <stdio.h>
-#include <stdlib.h>
-#include <signal.h>
-#include <unistd.h>
-#include <string.h>
-#include <assert.h>
-#include <stdint.h>
-
-#include <sys/mman.h>
-#include <sys/shm.h>
-#include <sys/wait.h>
-#include <sys/types.h>
-
-/* This is a somewhat ugly hack for the experimental 'trace-pc-guard' mode.
-   Basically, we need to make sure that the forkserver is initialized after
-   the LLVM-generated runtime initialization pass, not before. */
-
-#ifdef USE_TRACE_PC
-#define CONST_PRIO 5
-#else
-#define CONST_PRIO 0
-#endif                                                     /* ^USE_TRACE_PC */
-
-#include <sys/mman.h>
-#include <fcntl.h>
-
-/* Globals needed by the injected instrumentation. The __afl_area_initial region
-   is used for instrumentation output before __afl_map_shm() has a chance to
-   run. It will end up as .comm, so it shouldn't be too wasteful. */
-
-// In CmpLog, the only usage of __afl_area_ptr is to report errors
-u8* __afl_area_ptr;
-
-struct cmp_map* __afl_cmp_map;
-__thread u32    __afl_cmp_counter;
-
-/* Running in persistent mode? */
-
-static u8 is_persistent;
-
-/* SHM setup. */
-
-static void __afl_map_shm(void) {
-
-  u8* id_str = getenv(SHM_ENV_VAR);
-
-  /* If we're running under AFL, attach to the appropriate region, replacing the
-     early-stage __afl_area_initial region that is needed to allow some really
-     hacky .init code to work correctly in projects such as OpenSSL. */
-
-  if (id_str) {
-
-#ifdef USEMMAP
-    const char*    shm_file_path = id_str;
-    int            shm_fd = -1;
-    unsigned char* shm_base = NULL;
-
-    /* create the shared memory segment as if it was a file */
-    shm_fd = shm_open(shm_file_path, O_RDWR, 0600);
-    if (shm_fd == -1) {
-
-      printf("shm_open() failed\n");
-      exit(1);
-
-    }
-
-    /* map the shared memory segment to the address space of the process */
-    shm_base = mmap(0, MAP_SIZE, PROT_READ | PROT_WRITE, MAP_SHARED, shm_fd, 0);
-    if (shm_base == MAP_FAILED) {
-
-      close(shm_fd);
-      shm_fd = -1;
-
-      printf("mmap() failed\n");
-      exit(2);
-
-    }
-
-    __afl_area_ptr = shm_base;
-#else
-    u32 shm_id = atoi(id_str);
-
-    __afl_area_ptr = shmat(shm_id, NULL, 0);
-#endif
-
-    /* Whooooops. */
-
-    if (__afl_area_ptr == (void*)-1) _exit(1);
-
-    /* Write something into the bitmap so that even with low AFL_INST_RATIO,
-       our parent doesn't give up on us. */
-
-    __afl_area_ptr[0] = 1;
-
-  }
-
-  id_str = getenv(CMPLOG_SHM_ENV_VAR);
-
-  if (id_str) {
-
-    u32 shm_id = atoi(id_str);
-
-    __afl_cmp_map = shmat(shm_id, NULL, 0);
-
-    if (__afl_cmp_map == (void*)-1) _exit(1);
-
-  }
-
-}
-
-/* Fork server logic. */
-
-static void __afl_start_forkserver(void) {
-
-  static u8 tmp[4];
-  s32       child_pid;
-
-  u8 child_stopped = 0;
-
-  void (*old_sigchld_handler)(int) = 0;  // = signal(SIGCHLD, SIG_DFL);
-
-  /* Phone home and tell the parent that we're OK. If parent isn't there,
-     assume we're not running in forkserver mode and just execute program. */
-
-  if (write(FORKSRV_FD + 1, tmp, 4) != 4) return;
-
-  while (1) {
-
-    u32 was_killed;
-    int status;
-
-    /* Wait for parent by reading from the pipe. Abort if read fails. */
-
-    if (read(FORKSRV_FD, &was_killed, 4) != 4) _exit(1);
-
-    /* If we stopped the child in persistent mode, but there was a race
-       condition and afl-fuzz already issued SIGKILL, write off the old
-       process. */
-
-    if (child_stopped && was_killed) {
-
-      child_stopped = 0;
-      if (waitpid(child_pid, &status, 0) < 0) _exit(1);
-
-    }
-
-    if (!child_stopped) {
-
-      /* Once woken up, create a clone of our process. */
-
-      child_pid = fork();
-      if (child_pid < 0) _exit(1);
-
-      /* In child process: close fds, resume execution. */
-
-      if (!child_pid) {
-
-        signal(SIGCHLD, old_sigchld_handler);
-
-        close(FORKSRV_FD);
-        close(FORKSRV_FD + 1);
-        return;
-
-      }
-
-    } else {
-
-      /* Special handling for persistent mode: if the child is alive but
-         currently stopped, simply restart it with SIGCONT. */
-
-      kill(child_pid, SIGCONT);
-      child_stopped = 0;
-
-    }
-
-    /* In parent process: write PID to pipe, then wait for child. */
-
-    if (write(FORKSRV_FD + 1, &child_pid, 4) != 4) _exit(1);
-
-    if (waitpid(child_pid, &status, is_persistent ? WUNTRACED : 0) < 0)
-      _exit(1);
-
-    /* In persistent mode, the child stops itself with SIGSTOP to indicate
-       a successful run. In this case, we want to wake it up without forking
-       again. */
-
-    if (WIFSTOPPED(status)) child_stopped = 1;
-
-    /* Relay wait status to pipe, then loop back. */
-
-    if (write(FORKSRV_FD + 1, &status, 4) != 4) _exit(1);
-
-  }
-
-}
-
-/* A simplified persistent mode handler, used as explained in README.llvm. */
-
-int __afl_persistent_loop(unsigned int max_cnt) {
-
-  static u8  first_pass = 1;
-  static u32 cycle_cnt;
-
-  if (first_pass) {
-
-    /* Make sure that every iteration of __AFL_LOOP() starts with a clean slate.
-       On subsequent calls, the parent will take care of that, but on the first
-       iteration, it's our job to erase any trace of whatever happened
-       before the loop. */
-
-    if (is_persistent) {
-
-      // memset(__afl_area_ptr, 0, MAP_SIZE);
-      __afl_area_ptr[0] = 1;
-
-    }
-
-    cycle_cnt = max_cnt;
-    first_pass = 0;
-    return 1;
-
-  }
-
-  if (is_persistent) {
-
-    if (--cycle_cnt) {
-
-      raise(SIGSTOP);
-
-      __afl_area_ptr[0] = 1;
-
-      return 1;
-
-    } else {
-
-      /* When exiting __AFL_LOOP(), make sure that the subsequent code that
-         follows the loop is not traced. We do that by pivoting back to the
-         dummy output region. */
-
-      // __afl_area_ptr = __afl_area_initial;
-
-    }
-
-  }
-
-  return 0;
-
-}
-
-/* This one can be called from user code when deferred forkserver mode
-    is enabled. */
-
-void __afl_manual_init(void) {
-
-  static u8 init_done;
-
-  if (!init_done) {
-
-    __afl_map_shm();
-    __afl_start_forkserver();
-    init_done = 1;
-
-  }
-
-}
-
-/* Proper initialization routine. */
-
-__attribute__((constructor(CONST_PRIO))) void __afl_auto_init(void) {
-
-  is_persistent = !!getenv(PERSIST_ENV_VAR);
-
-  if (getenv(DEFER_ENV_VAR)) return;
-
-  __afl_manual_init();
-
-}
-
-///// CmpLog instrumentation
-
-void __sanitizer_cov_trace_cmp1(uint8_t Arg1, uint8_t Arg2) {
-
-  return;
-
-}
-
-void __sanitizer_cov_trace_cmp2(uint16_t Arg1, uint16_t Arg2) {
-
-  if (!__afl_cmp_map) return;
-
-  uintptr_t k = (uintptr_t)__builtin_return_address(0);
-  k = (k >> 4) ^ (k << 8);
-  k &= CMP_MAP_W - 1;
-
-  u32 hits = __afl_cmp_map->headers[k].hits;
-  __afl_cmp_map->headers[k].hits = hits + 1;
-  // if (!__afl_cmp_map->headers[k].cnt)
-  //  __afl_cmp_map->headers[k].cnt = __afl_cmp_counter++;
-
-  __afl_cmp_map->headers[k].shape = 1;
-  //__afl_cmp_map->headers[k].type = CMP_TYPE_INS;
-
-  hits &= CMP_MAP_H - 1;
-  __afl_cmp_map->log[k][hits].v0 = Arg1;
-  __afl_cmp_map->log[k][hits].v1 = Arg2;
-
-}
-
-void __sanitizer_cov_trace_cmp4(uint32_t Arg1, uint32_t Arg2) {
-
-  if (!__afl_cmp_map) return;
-
-  uintptr_t k = (uintptr_t)__builtin_return_address(0);
-  k = (k >> 4) ^ (k << 8);
-  k &= CMP_MAP_W - 1;
-
-  u32 hits = __afl_cmp_map->headers[k].hits;
-  __afl_cmp_map->headers[k].hits = hits + 1;
-
-  __afl_cmp_map->headers[k].shape = 3;
-
-  hits &= CMP_MAP_H - 1;
-  __afl_cmp_map->log[k][hits].v0 = Arg1;
-  __afl_cmp_map->log[k][hits].v1 = Arg2;
-
-}
-
-void __sanitizer_cov_trace_cmp8(uint64_t Arg1, uint64_t Arg2) {
-
-  if (!__afl_cmp_map) return;
-
-  uintptr_t k = (uintptr_t)__builtin_return_address(0);
-  k = (k >> 4) ^ (k << 8);
-  k &= CMP_MAP_W - 1;
-
-  u32 hits = __afl_cmp_map->headers[k].hits;
-  __afl_cmp_map->headers[k].hits = hits + 1;
-
-  __afl_cmp_map->headers[k].shape = 7;
-
-  hits &= CMP_MAP_H - 1;
-  __afl_cmp_map->log[k][hits].v0 = Arg1;
-  __afl_cmp_map->log[k][hits].v1 = Arg2;
-
-}
-
-#if defined(__APPLE__)
-#pragma weak __sanitizer_cov_trace_const_cmp1 = __sanitizer_cov_trace_cmp1
-#pragma weak __sanitizer_cov_trace_const_cmp2 = __sanitizer_cov_trace_cmp2
-#pragma weak __sanitizer_cov_trace_const_cmp4 = __sanitizer_cov_trace_cmp4
-#pragma weak __sanitizer_cov_trace_const_cmp8 = __sanitizer_cov_trace_cmp8
-#else
-void __sanitizer_cov_trace_const_cmp1(uint8_t Arg1, uint8_t Arg2)
-    __attribute__((alias("__sanitizer_cov_trace_cmp1")));
-void __sanitizer_cov_trace_const_cmp2(uint16_t Arg1, uint16_t Arg2)
-    __attribute__((alias("__sanitizer_cov_trace_cmp2")));
-void __sanitizer_cov_trace_const_cmp4(uint32_t Arg1, uint32_t Arg2)
-    __attribute__((alias("__sanitizer_cov_trace_cmp4")));
-void __sanitizer_cov_trace_const_cmp8(uint64_t Arg1, uint64_t Arg2)
-    __attribute__((alias("__sanitizer_cov_trace_cmp8")));
-#endif                                                /* defined(__APPLE__) */
-
-void __sanitizer_cov_trace_switch(uint64_t Val, uint64_t* Cases) {
-
-  for (uint64_t i = 0; i < Cases[0]; i++) {
-
-    uintptr_t k = (uintptr_t)__builtin_return_address(0) + i;
-    k = (k >> 4) ^ (k << 8);
-    k &= CMP_MAP_W - 1;
-
-    u32 hits = __afl_cmp_map->headers[k].hits;
-    __afl_cmp_map->headers[k].hits = hits + 1;
-
-    __afl_cmp_map->headers[k].shape = 7;
-
-    hits &= CMP_MAP_H - 1;
-    __afl_cmp_map->log[k][hits].v0 = Val;
-    __afl_cmp_map->log[k][hits].v1 = Cases[i + 2];
-
-  }
-
-}
-
diff --git a/llvm_mode/afl-llvm-rt.o.c b/llvm_mode/afl-llvm-rt.o.c
index 9632844f..d776462c 100644
--- a/llvm_mode/afl-llvm-rt.o.c
+++ b/llvm_mode/afl-llvm-rt.o.c
@@ -34,6 +34,7 @@
 #include <string.h>
 #include <assert.h>
 #include <stdint.h>
+#include <errno.h>
 
 #include <sys/mman.h>
 #include <sys/shm.h>
@@ -66,6 +67,9 @@ u32 __afl_prev_loc;
 __thread u32 __afl_prev_loc;
 #endif
 
+struct cmp_map* __afl_cmp_map;
+__thread u32    __afl_cmp_counter;
+
 /* Running in persistent mode? */
 
 static u8 is_persistent;
@@ -351,3 +355,152 @@ void __sanitizer_cov_trace_pc_guard_init(uint32_t* start, uint32_t* stop) {
 
 }
 
+///// CmpLog instrumentation
+
+void __sanitizer_cov_trace_cmp1(uint8_t Arg1, uint8_t Arg2) {
+
+  return;
+
+}
+
+void __sanitizer_cov_trace_cmp2(uint16_t Arg1, uint16_t Arg2) {
+
+  if (!__afl_cmp_map) return;
+
+  uintptr_t k = (uintptr_t)__builtin_return_address(0);
+  k = (k >> 4) ^ (k << 8);
+  k &= CMP_MAP_W - 1;
+  
+  __afl_cmp_map->headers[k].type = CMP_TYPE_INS;
+
+  u32 hits = __afl_cmp_map->headers[k].hits;
+  __afl_cmp_map->headers[k].hits = hits + 1;
+  // if (!__afl_cmp_map->headers[k].cnt)
+  //  __afl_cmp_map->headers[k].cnt = __afl_cmp_counter++;
+
+  __afl_cmp_map->headers[k].shape = 1;
+  //__afl_cmp_map->headers[k].type = CMP_TYPE_INS;
+
+  hits &= CMP_MAP_H - 1;
+  __afl_cmp_map->log[k][hits].v0 = Arg1;
+  __afl_cmp_map->log[k][hits].v1 = Arg2;
+
+}
+
+void __sanitizer_cov_trace_cmp4(uint32_t Arg1, uint32_t Arg2) {
+
+  if (!__afl_cmp_map) return;
+
+  uintptr_t k = (uintptr_t)__builtin_return_address(0);
+  k = (k >> 4) ^ (k << 8);
+  k &= CMP_MAP_W - 1;
+  
+  __afl_cmp_map->headers[k].type = CMP_TYPE_INS;
+
+  u32 hits = __afl_cmp_map->headers[k].hits;
+  __afl_cmp_map->headers[k].hits = hits + 1;
+
+  __afl_cmp_map->headers[k].shape = 3;
+
+  hits &= CMP_MAP_H - 1;
+  __afl_cmp_map->log[k][hits].v0 = Arg1;
+  __afl_cmp_map->log[k][hits].v1 = Arg2;
+
+}
+
+void __sanitizer_cov_trace_cmp8(uint64_t Arg1, uint64_t Arg2) {
+
+  if (!__afl_cmp_map) return;
+
+  uintptr_t k = (uintptr_t)__builtin_return_address(0);
+  k = (k >> 4) ^ (k << 8);
+  k &= CMP_MAP_W - 1;
+  
+  __afl_cmp_map->headers[k].type = CMP_TYPE_INS;
+
+  u32 hits = __afl_cmp_map->headers[k].hits;
+  __afl_cmp_map->headers[k].hits = hits + 1;
+
+  __afl_cmp_map->headers[k].shape = 7;
+
+  hits &= CMP_MAP_H - 1;
+  __afl_cmp_map->log[k][hits].v0 = Arg1;
+  __afl_cmp_map->log[k][hits].v1 = Arg2;
+
+}
+
+#if defined(__APPLE__)
+#pragma weak __sanitizer_cov_trace_const_cmp1 = __sanitizer_cov_trace_cmp1
+#pragma weak __sanitizer_cov_trace_const_cmp2 = __sanitizer_cov_trace_cmp2
+#pragma weak __sanitizer_cov_trace_const_cmp4 = __sanitizer_cov_trace_cmp4
+#pragma weak __sanitizer_cov_trace_const_cmp8 = __sanitizer_cov_trace_cmp8
+#else
+void __sanitizer_cov_trace_const_cmp1(uint8_t Arg1, uint8_t Arg2)
+    __attribute__((alias("__sanitizer_cov_trace_cmp1")));
+void __sanitizer_cov_trace_const_cmp2(uint16_t Arg1, uint16_t Arg2)
+    __attribute__((alias("__sanitizer_cov_trace_cmp2")));
+void __sanitizer_cov_trace_const_cmp4(uint32_t Arg1, uint32_t Arg2)
+    __attribute__((alias("__sanitizer_cov_trace_cmp4")));
+void __sanitizer_cov_trace_const_cmp8(uint64_t Arg1, uint64_t Arg2)
+    __attribute__((alias("__sanitizer_cov_trace_cmp8")));
+#endif                                                /* defined(__APPLE__) */
+
+void __sanitizer_cov_trace_switch(uint64_t Val, uint64_t* Cases) {
+
+  for (uint64_t i = 0; i < Cases[0]; i++) {
+
+    uintptr_t k = (uintptr_t)__builtin_return_address(0) + i;
+    k = (k >> 4) ^ (k << 8);
+    k &= CMP_MAP_W - 1;
+
+    __afl_cmp_map->headers[k].type = CMP_TYPE_INS;
+
+    u32 hits = __afl_cmp_map->headers[k].hits;
+    __afl_cmp_map->headers[k].hits = hits + 1;
+
+    __afl_cmp_map->headers[k].shape = 7;
+
+    hits &= CMP_MAP_H - 1;
+    __afl_cmp_map->log[k][hits].v0 = Val;
+    __afl_cmp_map->log[k][hits].v1 = Cases[i + 2];
+
+  }
+
+}
+
+// POSIX shenanigan to see if an area is mapped.
+// If it is mapped as X-only, we have a problem, so maybe we should add a check
+// to avoid to call it on .text addresses
+static int area_is_mapped(void* ptr, size_t len) {
+
+  char * p = ptr;
+  char * page = (char*)((uintptr_t)p & ~(sysconf(_SC_PAGE_SIZE) -1));
+
+  int r = msync(page, (p - page) + len, MS_ASYNC);
+  if (r < 0)
+    return errno != ENOMEM;
+  return 1;
+
+}
+
+void __cmplog_rtn_hook(void* ptr1, void* ptr2) {
+
+  if (!area_is_mapped(ptr1, 32) || !area_is_mapped(ptr2, 32))
+    return;
+  
+  uintptr_t k = (uintptr_t)__builtin_return_address(0);
+  k = (k >> 4) ^ (k << 8);
+  k &= CMP_MAP_W - 1;
+
+  __afl_cmp_map->headers[k].type = CMP_TYPE_RTN;
+
+  u32 hits = __afl_cmp_map->headers[k].hits;
+  __afl_cmp_map->headers[k].hits = hits + 1;
+
+  __afl_cmp_map->headers[k].shape = 31;
+
+  hits &= CMP_MAP_RTN_H - 1;
+  __builtin_memcpy(((struct cmpfn_operands*)__afl_cmp_map->log[k])[hits].v0, ptr1, 32);
+  __builtin_memcpy(((struct cmpfn_operands*)__afl_cmp_map->log[k])[hits].v1, ptr2, 32);
+
+}
diff --git a/llvm_mode/cmplog-routines-pass.cc b/llvm_mode/cmplog-routines-pass.cc
new file mode 100644
index 00000000..e7125f9f
--- /dev/null
+++ b/llvm_mode/cmplog-routines-pass.cc
@@ -0,0 +1,325 @@
+/*
+   american fuzzy lop++ - LLVM CmpLog instrumentation
+   --------------------------------------------------
+
+   Written by Andrea Fioraldi <andreafioraldi@gmail.com>
+
+   Copyright 2015, 2016 Google Inc. All rights reserved.
+   Copyright 2019-2020 AFLplusplus Project. All rights reserved.
+
+   Licensed under the Apache License, Version 2.0 (the "License");
+   you may not use this file except in compliance with the License.
+   You may obtain a copy of the License at:
+
+     http://www.apache.org/licenses/LICENSE-2.0
+
+*/
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <unistd.h>
+
+#include <list>
+#include <string>
+#include <fstream>
+#include <sys/time.h>
+#include "llvm/Config/llvm-config.h"
+
+#include "llvm/ADT/Statistic.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/LegacyPassManager.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Transforms/IPO/PassManagerBuilder.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Pass.h"
+#include "llvm/Analysis/ValueTracking.h"
+
+#if LLVM_VERSION_MAJOR > 3 || \
+    (LLVM_VERSION_MAJOR == 3 && LLVM_VERSION_MINOR > 4)
+#include "llvm/IR/Verifier.h"
+#include "llvm/IR/DebugInfo.h"
+#else
+#include "llvm/Analysis/Verifier.h"
+#include "llvm/DebugInfo.h"
+#define nullptr 0
+#endif
+
+#include <set>
+
+using namespace llvm;
+
+namespace {
+
+class CmpLogRoutines : public ModulePass {
+
+ public:
+  static char ID;
+  CmpLogRoutines() : ModulePass(ID) {
+
+    char *instWhiteListFilename = getenv("AFL_LLVM_WHITELIST");
+    if (instWhiteListFilename) {
+
+      std::string   line;
+      std::ifstream fileStream;
+      fileStream.open(instWhiteListFilename);
+      if (!fileStream) report_fatal_error("Unable to open AFL_LLVM_WHITELIST");
+      getline(fileStream, line);
+      while (fileStream) {
+
+        myWhitelist.push_back(line);
+        getline(fileStream, line);
+
+      }
+
+    }
+
+  }
+
+  bool runOnModule(Module &M) override;
+
+#if LLVM_VERSION_MAJOR < 4
+  const char *getPassName() const override {
+
+#else
+  StringRef getPassName() const override {
+
+#endif
+    return "cmplog routines";
+
+  }
+
+ protected:
+  std::list<std::string> myWhitelist;
+
+ private:
+  bool hookRtns(Module &M);
+
+};
+
+}  // namespace
+
+char CmpLogRoutines::ID = 0;
+
+bool CmpLogRoutines::hookRtns(Module &M) {
+
+  std::vector<CallInst *> calls;
+  LLVMContext &           C = M.getContext();
+
+  Type * VoidTy = Type::getVoidTy(C);
+  PointerType * VoidPtrTy = PointerType::get(VoidTy, 0);
+
+#if LLVM_VERSION_MAJOR < 9
+  Constant *
+#else
+  FunctionCallee
+#endif
+      c = M.getOrInsertFunction("__cmplog_rtn_hook", VoidTy, VoidPtrTy, VoidPtrTy
+#if LLVM_VERSION_MAJOR < 5
+                                ,
+                                NULL
+#endif
+      );
+#if LLVM_VERSION_MAJOR < 9
+  Function *cmplogHookFn = cast<Function>(c);
+#else
+  FunctionCallee cmplogHookFn = c;
+#endif
+
+  /* iterate over all functions, bbs and instruction and add suitable calls */
+  for (auto &F : M) {
+
+    for (auto &BB : F) {
+
+      if (!myWhitelist.empty()) {
+
+        BasicBlock::iterator IP = BB.getFirstInsertionPt();
+
+        bool instrumentBlock = false;
+
+        /* Get the current location using debug information.
+         * For now, just instrument the block if we are not able
+         * to determine our location. */
+        DebugLoc Loc = IP->getDebugLoc();
+#if LLVM_VERSION_MAJOR >= 4 || \
+    (LLVM_VERSION_MAJOR == 3 && LLVM_VERSION_MINOR >= 7)
+        if (Loc) {
+
+          DILocation *cDILoc = dyn_cast<DILocation>(Loc.getAsMDNode());
+
+          unsigned int instLine = cDILoc->getLine();
+          StringRef    instFilename = cDILoc->getFilename();
+
+          if (instFilename.str().empty()) {
+
+            /* If the original location is empty, try using the inlined location
+             */
+            DILocation *oDILoc = cDILoc->getInlinedAt();
+            if (oDILoc) {
+
+              instFilename = oDILoc->getFilename();
+              instLine = oDILoc->getLine();
+
+            }
+
+          }
+
+          (void)instLine;
+
+          /* Continue only if we know where we actually are */
+          if (!instFilename.str().empty()) {
+
+            for (std::list<std::string>::iterator it = myWhitelist.begin();
+                 it != myWhitelist.end(); ++it) {
+
+              /* We don't check for filename equality here because
+               * filenames might actually be full paths. Instead we
+               * check that the actual filename ends in the filename
+               * specified in the list. */
+              if (instFilename.str().length() >= it->length()) {
+
+                if (instFilename.str().compare(
+                        instFilename.str().length() - it->length(),
+                        it->length(), *it) == 0) {
+
+                  instrumentBlock = true;
+                  break;
+
+                }
+
+              }
+
+            }
+
+          }
+
+        }
+
+#else
+        if (!Loc.isUnknown()) {
+
+          DILocation cDILoc(Loc.getAsMDNode(C));
+
+          unsigned int instLine = cDILoc.getLineNumber();
+          StringRef    instFilename = cDILoc.getFilename();
+
+          (void)instLine;
+
+          /* Continue only if we know where we actually are */
+          if (!instFilename.str().empty()) {
+
+            for (std::list<std::string>::iterator it = myWhitelist.begin();
+                 it != myWhitelist.end(); ++it) {
+
+              /* We don't check for filename equality here because
+               * filenames might actually be full paths. Instead we
+               * check that the actual filename ends in the filename
+               * specified in the list. */
+              if (instFilename.str().length() >= it->length()) {
+
+                if (instFilename.str().compare(
+                        instFilename.str().length() - it->length(),
+                        it->length(), *it) == 0) {
+
+                  instrumentBlock = true;
+                  break;
+
+                }
+
+              }
+
+            }
+
+          }
+
+        }
+
+#endif
+
+        /* Either we couldn't figure out our location or the location is
+         * not whitelisted, so we skip instrumentation. */
+        if (!instrumentBlock) continue;
+
+      }
+
+      for (auto &IN : BB) {
+
+        CallInst *callInst = nullptr;
+
+        if ((callInst = dyn_cast<CallInst>(&IN))) {
+
+          Function *Callee = callInst->getCalledFunction();
+          if (!Callee) continue;
+          if (callInst->getCallingConv() != llvm::CallingConv::C) continue;
+
+          FunctionType *FT = Callee->getFunctionType();
+
+          bool isPtrRtn =
+              FT->getNumParams() >= 2 && !FT->getReturnType()->isVoidTy() &&
+              FT->getParamType(0) == FT->getParamType(1) &&
+              FT->getParamType(0)->isPointerTy();
+          
+          if (!isPtrRtn)
+            continue;
+          
+          calls.push_back(callInst);
+
+        }
+
+      }
+
+    }
+
+  }
+
+  if (!calls.size()) return false;
+  errs() << "Hooking " << calls.size() << " calls with pointers as arguments\n";
+
+  for (auto &callInst : calls) {
+
+    Value *v1P = callInst->getArgOperand(0),
+          *v2P = callInst->getArgOperand(1);
+    
+    IRBuilder<> IRB(callInst->getParent());
+    IRB.SetInsertPoint(callInst);
+    
+    std::vector<Value*> args;
+    args.push_back(v1P);
+    args.push_back(v2P);
+    
+    IRB.CreateCall(cmplogHookFn, args, "tmp");
+
+    // errs() << callInst->getCalledFunction()->getName() << "\n";
+
+  }
+
+  return true;
+
+}
+
+bool CmpLogRoutines::runOnModule(Module &M) {
+
+  if (getenv("AFL_QUIET") == NULL)
+    llvm::errs() << "Running cmplog-routines-pass by andreafioraldi@gmail.com\n";
+  hookRtns(M);
+  verifyModule(M);
+
+  return true;
+
+}
+
+static void registerCmpLogRoutinesPass(const PassManagerBuilder &,
+                                  legacy::PassManagerBase &PM) {
+
+  auto p = new CmpLogRoutines();
+  PM.add(p);
+
+}
+
+static RegisterStandardPasses RegisterCmpLogRoutinesPass(
+    PassManagerBuilder::EP_OptimizerLast, registerCmpLogRoutinesPass);
+
+static RegisterStandardPasses RegisterCmpLogRoutinesPass0(
+    PassManagerBuilder::EP_EnabledOnOptLevel0, registerCmpLogRoutinesPass);
+
diff --git a/src/afl-fuzz-one.c b/src/afl-fuzz-one.c
index c1f3f9ac..18376556 100644
--- a/src/afl-fuzz-one.c
+++ b/src/afl-fuzz-one.c
@@ -531,7 +531,7 @@ u8 fuzz_one_original(char** argv) {
 
   }
 
-  if (cmplog_mode) {
+  if (cmplog_mode && !queue_cur->fully_colorized) {
 
     if (input_to_state_stage(argv, in_buf, out_buf, len, queue_cur->exec_cksum))
       goto abandon_entry;
diff --git a/src/afl-fuzz-redqueen.c b/src/afl-fuzz-redqueen.c
index 4f5d69f7..b09a977f 100644
--- a/src/afl-fuzz-redqueen.c
+++ b/src/afl-fuzz-redqueen.c
@@ -145,6 +145,9 @@ u8 colorization(u8* buf, u32 len, u32 exec_cksum) {
     --stage_cur;
 
   }
+  
+  if (stage_cur)
+    queue_cur->fully_colorized = 1;
 
   new_hit_cnt = queued_paths + unique_crashes;
   stage_finds[STAGE_COLORIZATION] += new_hit_cnt - orig_hit_cnt;
@@ -204,7 +207,7 @@ checksum_fail:
 
 ///// Input to State replacement
 
-u8 its_fuzz(u32 idx, u32 size, u8* buf, u32 len, u8* status) {
+u8 its_fuzz(u8* buf, u32 len, u8* status) {
 
   u64 orig_hit_cnt, new_hit_cnt;
 
@@ -214,18 +217,11 @@ u8 its_fuzz(u32 idx, u32 size, u8* buf, u32 len, u8* status) {
 
   new_hit_cnt = queued_paths + unique_crashes;
 
-  if (unlikely(new_hit_cnt != orig_hit_cnt)) {
-
+  if (unlikely(new_hit_cnt != orig_hit_cnt))
     *status = 1;
-
-  } else {
-
-    if (size >= MIN_AUTO_EXTRA && size <= MAX_AUTO_EXTRA)
-      maybe_add_auto(&buf[idx], size);
+  else
     *status = 2;
 
-  }
-
   return 0;
 
 }
@@ -251,7 +247,7 @@ u8 cmp_extend_encoding(struct cmp_header* h, u64 pattern, u64 repl, u32 idx,
     if (its_len >= 8 && *buf_64 == pattern && *o_buf_64 == pattern) {
 
       *buf_64 = repl;
-      if (unlikely(its_fuzz(idx, 8, buf, len, status))) return 1;
+      if (unlikely(its_fuzz(buf, len, status))) return 1;
       *buf_64 = pattern;
 
     }
@@ -269,7 +265,7 @@ u8 cmp_extend_encoding(struct cmp_header* h, u64 pattern, u64 repl, u32 idx,
     if (its_len >= 4 && *buf_32 == (u32)pattern && *o_buf_32 == (u32)pattern) {
 
       *buf_32 = (u32)repl;
-      if (unlikely(its_fuzz(idx, 4, buf, len, status))) return 1;
+      if (unlikely(its_fuzz(buf, len, status))) return 1;
       *buf_32 = pattern;
 
     }
@@ -287,7 +283,7 @@ u8 cmp_extend_encoding(struct cmp_header* h, u64 pattern, u64 repl, u32 idx,
     if (its_len >= 2 && *buf_16 == (u16)pattern && *o_buf_16 == (u16)pattern) {
 
       *buf_16 = (u16)repl;
-      if (unlikely(its_fuzz(idx, 2, buf, len, status))) return 1;
+      if (unlikely(its_fuzz(buf, len, status))) return 1;
       *buf_16 = (u16)pattern;
 
     }
@@ -305,7 +301,7 @@ u8 cmp_extend_encoding(struct cmp_header* h, u64 pattern, u64 repl, u32 idx,
     if (its_len >= 2 && *buf_8 == (u8)pattern && *o_buf_8 == (u8)pattern) {
 
       *buf_8 = (u8)repl;
-      if (unlikely(its_fuzz(idx, 1, buf, len, status)))
+      if (unlikely(its_fuzz(buf, len, status)))
         return 1;
       *buf_16 = (u16)pattern;
 
@@ -417,12 +413,97 @@ u8 cmp_fuzz(u32 key, u8* orig_buf, u8* buf, u32 len) {
 
 }
 
+u8 rtn_extend_encoding(struct cmp_header* h, u8* pattern, u8* repl, u32 idx,
+                       u8* orig_buf, u8* buf, u32 len, u8* status) {
+
+  u32 i;
+  u32 its_len = MIN(32, len - idx);
+  
+  u8 save[32];
+  memcpy(save, &buf[idx], its_len);
+
+  *status = 0;
+
+  for (i = 0; i < its_len; ++i) {
+  
+    if (pattern[idx + i] != orig_buf[idx + i] || *status == 1)
+      break;
+    
+    buf[idx +i] = repl[idx + i];
+    if (unlikely(its_fuzz(buf, len, status))) return 1;
+  
+  }
+  
+  memcpy(&buf[idx], save, i);
+  return 0;
+
+}
+
+u8 rtn_fuzz(u32 key, u8* orig_buf, u8* buf, u32 len) {
+
+  struct cmp_header* h = &cmp_map->headers[key];
+  u32                i, j, idx;
+
+  u32 loggeds = h->hits;
+  if (h->hits > CMP_MAP_RTN_H) loggeds = CMP_MAP_RTN_H;
+
+  u8 status;
+  // opt not in the paper
+  u32 fails = 0;
+
+  for (i = 0; i < loggeds; ++i) {
+
+    struct cmpfn_operands* o = &((struct cmpfn_operands*)cmp_map->log[key])[i];
+
+    // opt not in the paper
+    for (j = 0; j < i; ++j)
+      if (!memcmp(&((struct cmpfn_operands*)cmp_map->log[key])[j], o, sizeof(struct cmpfn_operands)))
+        goto rtn_fuzz_next_iter;
+
+    for (idx = 0; idx < len && fails < 8; ++idx) {
+
+      if (unlikely(rtn_extend_encoding(h, o->v0, o->v1, idx, orig_buf, buf, len,
+                                       &status)))
+        return 1;
+      if (status == 2)
+        ++fails;
+      else if (status == 1)
+        break;
+
+      if (unlikely(rtn_extend_encoding(h, o->v1, o->v0, idx, orig_buf, buf, len,
+                                       &status)))
+        return 1;
+      if (status == 2)
+        ++fails;
+      else if (status == 1)
+        break;
+
+    }
+
+    // If failed, add to dictionary
+    if (fails == 8) {
+
+      maybe_add_auto(o->v0, SHAPE_BYTES(h->shape));
+      maybe_add_auto(o->v1, SHAPE_BYTES(h->shape));
+
+    }
+
+  rtn_fuzz_next_iter:
+    stage_cur++;
+
+  }
+
+  return 0;
+
+}
+
 ///// Input to State stage
 
 // queue_cur->exec_cksum
 u8 input_to_state_stage(char** argv, u8* orig_buf, u8* buf, u32 len,
                         u32 exec_cksum) {
 
+  u8 r = 1;
   its_argv = argv;
 
   if (unlikely(colorization(buf, len, exec_cksum))) return 1;
@@ -445,27 +526,37 @@ u8 input_to_state_stage(char** argv, u8* orig_buf, u8* buf, u32 len,
   for (k = 0; k < CMP_MAP_W; ++k) {
 
     if (!cmp_map->headers[k].hits) continue;
-    if (cmp_map->headers[k].hits > CMP_MAP_H)
-      stage_max += CMP_MAP_H;
+    if (cmp_map->headers[k].type == CMP_TYPE_INS)
+      stage_max += MIN(cmp_map->headers[k].hits, CMP_MAP_H);
     else
-      stage_max += cmp_map->headers[k].hits;
+      stage_max += MIN(cmp_map->headers[k].hits, CMP_MAP_RTN_H);
 
   }
-
+  
   for (k = 0; k < CMP_MAP_W; ++k) {
 
     if (!cmp_map->headers[k].hits) continue;
-    cmp_fuzz(k, orig_buf, buf, len);
+    
+    if (cmp_map->headers[k].type == CMP_TYPE_INS) {
+      if (unlikely(cmp_fuzz(k, orig_buf, buf, len)))
+        goto exit_its;
+    } else {
+      if (unlikely(rtn_fuzz(k, orig_buf, buf, len)))
+        goto exit_its;
+    }
 
   }
 
-  memcpy(orig_buf, buf, len);
+  r = 0;
 
+exit_its:
+  memcpy(orig_buf, buf, len);
+  
   new_hit_cnt = queued_paths + unique_crashes;
   stage_finds[STAGE_ITS] += new_hit_cnt - orig_hit_cnt;
   stage_cycles[STAGE_ITS] += total_execs - orig_execs;
 
-  return 0;
+  return r;
 
 }