Merge pull request #11 from vanhauser-thc/neverZero_counters

Never zero counters added

6 files changed, 98 insertions, 6 deletions

diff --git a/afl-as.h b/afl-as.h
index ebd57109..2c84f9f3 100644
--- a/afl-as.h
+++ b/afl-as.h
@@ -189,6 +189,7 @@ static const u8* main_payload_32 =
   "  orb  $1, (%edx, %edi, 1)\n"
 #else
   "  incb (%edx, %edi, 1)\n"
+  "  adcb $0, (%edx, %edi, 1)\n"
 #endif /* ^SKIP_COUNTS */
   "\n"
   "__afl_return:\n"
@@ -417,6 +418,7 @@ static const u8* main_payload_64 =
   "  orb  $1, (%rdx, %rcx, 1)\n"
 #else
   "  incb (%rdx, %rcx, 1)\n"
+  "  adcb $0, (%rdx, %rcx, 1)\n"
 #endif /* ^SKIP_COUNTS */
   "\n"
   "__afl_return:\n"
diff --git a/docs/ChangeLog b/docs/ChangeLog
index b758b211..b8d0d7ac 100644
--- a/docs/ChangeLog
+++ b/docs/ChangeLog
@@ -17,6 +17,8 @@ sending a mail to <afl-users+subscribe@googlegroups.com>.
 Version ++2.52d (tbd):
 -----------------------------
 
+  - added never zero counters for afl-gcc and optional (because of an
+    optimization issue in llvm < 9) for llvm_mode (AFL_LLVM_NEVER_ZERO=1)
   - more cpu power for afl-system-config
   - added forkserver patch to afl-tmin, makes it much faster (originally from
     github.com/nccgroup/TriforceAFL)
diff --git a/docs/env_variables.txt b/docs/env_variables.txt
index 2a824766..d854ea8d 100644
--- a/docs/env_variables.txt
+++ b/docs/env_variables.txt
@@ -106,6 +106,14 @@ Then there are a few specific features that are only available in llvm_mode:
 
     See llvm_mode/README.whitelist for more information.
 
+  OTHER
+  =====
+    - Setting export AFL_LLVM_NOT_ZERO=1 during compilation will use counters
+      that skip zero on overflow. This is the default for llvm >= 9,
+      however for llvm versions below that this will increase an unnecessary
+      slowdown due a performance issue that is only fixed in llvm 9+.
+      This feature increases path discovery by a little bit.
+
 Note that AFL_INST_RATIO will behave a bit differently than for afl-gcc,
 because functions are *not* instrumented unconditionally - so low values
 will have a more striking effect. For this tool, 0 is not a valid choice.
diff --git a/llvm_mode/Makefile b/llvm_mode/Makefile
index 3304e62d..b6ab0c61 100644
--- a/llvm_mode/Makefile
+++ b/llvm_mode/Makefile
@@ -25,11 +25,17 @@ VERSION     = $(shell grep '^\#define VERSION ' ../config.h | cut -d '"' -f2)
 LLVM_CONFIG ?= llvm-config
 #LLVM_OK = $(shell $(LLVM_CONFIG) --version | egrep -q '^[5-6]' && echo 0 || echo 1 )
 LLVM_UNSUPPORTED = $(shell $(LLVM_CONFIG) --version | egrep -q '^9|3.0' && echo 1 || echo 0 )
+LLVM_MAJOR = ($shell $(LLVM_CONFIG) --version | sed 's/\..*//')
 
 ifeq "$(LLVM_UNSUPPORTED)" "1"
   $(warn llvm_mode only supports versions 3.8.0 up to 8.x )
 endif
 
+# this is not visible yet:
+ifeq "$(LLVM_MAJOR)" "9"
+  $(info llvm_mode deteted llvm 9, enabling neverZero implementation)
+endif
+
 CFLAGS      ?= -O3 -funroll-loops
 CFLAGS      += -Wall -D_FORTIFY_SOURCE=2 -g -Wno-pointer-sign \
                -DAFL_PATH=\"$(HELPER_PATH)\" -DBIN_PATH=\"$(BIN_PATH)\" \
diff --git a/llvm_mode/README.neverzero b/llvm_mode/README.neverzero
new file mode 100644
index 00000000..ef873acb
--- /dev/null
+++ b/llvm_mode/README.neverzero
@@ -0,0 +1,22 @@
+Usage
+=====
+
+In larger, complex or reiterative programs the map that collects the edge pairs
+can easily fill up and wrap.
+This is not that much of an issue - unless by chance it wraps just to a 0
+when the program execution ends.
+In this case afl-fuzz is not able to see that the pair has been accessed and
+will ignore it.
+
+NeverZero prevents this behaviour. If a counter wraps, it jumps over the 0
+directly to a 1. This improves path discovery (by a very little amount)
+at a very little cost (one instruction per edge).
+
+This is implemented in afl-gcc, however for llvm_mode this is optional if
+the llvm version is below 9 - as there is a perfomance bug that is only fixed
+in version 9 and onwards.
+
+If you want to enable this for llvm < 9 then set
+
+export AFL_LLVM_NOT_ZERO=1
+
diff --git a/llvm_mode/afl-llvm-pass.so.cc b/llvm_mode/afl-llvm-pass.so.cc
index d46db7c0..cfeff968 100644
--- a/llvm_mode/afl-llvm-pass.so.cc
+++ b/llvm_mode/afl-llvm-pass.so.cc
@@ -118,6 +118,10 @@ bool AFLCoverage::runOnModule(Module &M) {
 
   }
 
+#if LLVM_VERSION_MAJOR < 9
+  char* neverZero_counters_str = getenv("AFL_LLVM_NOT_ZERO");
+#endif
+
   /* Get globals for the SHM region and the previous location. Note that
      __afl_prev_loc is thread-local. */
 
@@ -227,21 +231,69 @@ bool AFLCoverage::runOnModule(Module &M) {
 
       LoadInst *MapPtr = IRB.CreateLoad(AFLMapPtr);
       MapPtr->setMetadata(M.getMDKindID("nosanitize"), MDNode::get(C, None));
-      Value *MapPtrIdx =
-          IRB.CreateGEP(MapPtr, IRB.CreateXor(PrevLocCasted, CurLoc));
+      Value *MapPtrIdx = IRB.CreateGEP(MapPtr, IRB.CreateXor(PrevLocCasted, CurLoc));
 
       /* Update bitmap */
 
       LoadInst *Counter = IRB.CreateLoad(MapPtrIdx);
       Counter->setMetadata(M.getMDKindID("nosanitize"), MDNode::get(C, None));
+
       Value *Incr = IRB.CreateAdd(Counter, ConstantInt::get(Int8Ty, 1));
-      IRB.CreateStore(Incr, MapPtrIdx)
-          ->setMetadata(M.getMDKindID("nosanitize"), MDNode::get(C, None));
+
+#if LLVM_VERSION_MAJOR < 9
+      if (neverZero_counters_str != NULL) { // with llvm 9 we make this the default as the bug in llvm is then fixed
+#endif
+        /* hexcoder: Realize a counter that skips zero during overflow.
+         * Once this counter reaches its maximum value, it next increments to 1
+         *
+         * Instead of
+         * Counter + 1 -> Counter
+         * we inject now this
+         * Counter + 1 -> {Counter, OverflowFlag}
+         * Counter + OverflowFlag -> Counter
+         */
+/*       // we keep the old solutions just in case
+         // Solution #1
+         if (neverZero_counters_str[0] == '1') {
+           CallInst *AddOv = IRB.CreateBinaryIntrinsic(Intrinsic::uadd_with_overflow, Counter, ConstantInt::get(Int8Ty, 1));
+           AddOv->setMetadata(M.getMDKindID("nosanitize"), MDNode::get(C, None));
+           Value *SumWithOverflowBit = AddOv;
+           Incr = IRB.CreateAdd(IRB.CreateExtractValue(SumWithOverflowBit, 0),  // sum 
+                                IRB.CreateZExt( // convert from one bit type to 8 bits type 
+                                               IRB.CreateExtractValue(SumWithOverflowBit, 1), // overflow
+                                               Int8Ty));
+          // Solution #2
+          } else if (neverZero_counters_str[0] == '2') {
+             auto cf = IRB.CreateICmpEQ(Counter, ConstantInt::get(Int8Ty, 255));
+             Value *HowMuch = IRB.CreateAdd(ConstantInt::get(Int8Ty, 1), cf);
+             Incr = IRB.CreateAdd(Counter, HowMuch);
+          // Solution #3
+          } else if (neverZero_counters_str[0] == '3') {
+*/
+          // this is the solution we choose because llvm9 should do the right thing here
+            auto cf = IRB.CreateICmpEQ(Incr, ConstantInt::get(Int8Ty, 0));
+            auto carry = IRB.CreateZExt(cf, Int8Ty);
+            Incr = IRB.CreateAdd(Incr, carry);
+/*
+         // Solution #4
+         } else if (neverZero_counters_str[0] == '4') {
+            auto cf = IRB.CreateICmpULT(Incr, ConstantInt::get(Int8Ty, 1));
+            auto carry = IRB.CreateZExt(cf, Int8Ty);
+            Incr = IRB.CreateAdd(Incr, carry);
+         } else {
+            fprintf(stderr, "Error: unknown value for AFL_NZERO_COUNTS: %s (valid is 1-4)\n", neverZero_counters_str);
+            exit(-1);
+         }
+*/
+#if LLVM_VERSION_MAJOR < 9
+      }
+#endif
+
+      IRB.CreateStore(Incr, MapPtrIdx)->setMetadata(M.getMDKindID("nosanitize"), MDNode::get(C, None));
 
       /* Set prev_loc to cur_loc >> 1 */
 
-      StoreInst *Store =
-          IRB.CreateStore(ConstantInt::get(Int32Ty, cur_loc >> 1), AFLPrevLoc);
+      StoreInst *Store = IRB.CreateStore(ConstantInt::get(Int32Ty, cur_loc >> 1), AFLPrevLoc);
       Store->setMetadata(M.getMDKindID("nosanitize"), MDNode::get(C, None));
 
       inst_blocks++;