[libFuzzer] trace switch statements and apply mutations based on the expected case...
authorKostya Serebryany <kcc@google.com>
Fri, 31 Jul 2015 01:33:06 +0000 (01:33 +0000)
committerKostya Serebryany <kcc@google.com>
Fri, 31 Jul 2015 01:33:06 +0000 (01:33 +0000)
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@243726 91177308-0d34-0410-b5e6-96231b3b80d8

lib/Fuzzer/FuzzerTraceState.cpp
lib/Fuzzer/test/CMakeLists.txt
lib/Fuzzer/test/SwitchTest.cpp [new file with mode: 0644]
lib/Fuzzer/test/fuzzer.test
lib/Transforms/Instrumentation/SanitizerCoverage.cpp
test/Instrumentation/SanitizerCoverage/switch-tracing.ll [new file with mode: 0644]

index 637030c..e87fe6a 100644 (file)
@@ -216,6 +216,9 @@ class TraceState {
                         dfsan_label L2);
   void TraceCmpCallback(uintptr_t PC, size_t CmpSize, size_t CmpType, uint64_t Arg1,
                         uint64_t Arg2);
+
+  void TraceSwitchCallback(uintptr_t PC, size_t ValSizeInBits, uint64_t Val,
+                           size_t NumCases, uint64_t *Cases);
   int TryToAddDesiredData(uint64_t PresentData, uint64_t DesiredData,
                            size_t DataSize);
 
@@ -305,6 +308,7 @@ int TraceState::TryToAddDesiredData(uint64_t PresentData, uint64_t DesiredData,
       break;
     size_t Pos = Cur - Beg;
     assert(Pos < CurrentUnit.size());
+    if (Mutations.size() > 100000U) return Res;  // Just in case.
     Mutations.push_back({Pos, DataSize, DesiredData});
     Mutations.push_back({Pos, DataSize, DesiredData + 1});
     Mutations.push_back({Pos, DataSize, DesiredData - 1});
@@ -335,6 +339,13 @@ void TraceState::TraceCmpCallback(uintptr_t PC, size_t CmpSize, size_t CmpType,
   }
 }
 
+void TraceState::TraceSwitchCallback(uintptr_t PC, size_t ValSizeInBits,
+                                     uint64_t Val, size_t NumCases,
+                                     uint64_t *Cases) {
+  for (size_t i = 0; i < NumCases; i++)
+    TryToAddDesiredData(Val, Cases[i], ValSizeInBits / 8);
+}
+
 static TraceState *TS;
 
 void Fuzzer::StartTraceRecording() {
@@ -451,4 +462,10 @@ void __sanitizer_cov_trace_cmp(uint64_t SizeAndType, uint64_t Arg1,
   TS->TraceCmpCallback(PC, CmpSize, Type, Arg1, Arg2);
 }
 
+void __sanitizer_cov_trace_switch(uint64_t Val, uint64_t *Cases) {
+  if (!TS) return;
+  uintptr_t PC = reinterpret_cast<uintptr_t>(__builtin_return_address(0));
+  TS->TraceSwitchCallback(PC, Cases[1], Val, Cases[0], Cases + 2);
+}
+
 }  // extern "C"
index 4cff70c..ac21b46 100644 (file)
@@ -21,6 +21,7 @@ set(Tests
   SimpleCmpTest
   SimpleTest
   StrncmpTest
+  SwitchTest
   TimeoutTest
   )
 
diff --git a/lib/Fuzzer/test/SwitchTest.cpp b/lib/Fuzzer/test/SwitchTest.cpp
new file mode 100644 (file)
index 0000000..6e300aa
--- /dev/null
@@ -0,0 +1,35 @@
+// Simple test for a fuzzer. The fuzzer must find the interesting switch value.
+#include <cstdint>
+#include <cstdlib>
+#include <cstring>
+#include <cstddef>
+#include <iostream>
+
+static volatile int Sink;
+
+template<class T>
+bool Switch(const uint8_t *Data, size_t Size) {
+  T X;
+  if (Size < sizeof(X)) return false;
+  memcpy(&X, Data, sizeof(X));
+  switch (X) {
+    case 1: Sink = __LINE__; break;
+    case 101: Sink = __LINE__; break;
+    case 1001: Sink = __LINE__; break;
+    case 10001: Sink = __LINE__; break;
+    case 100001: Sink = __LINE__; break;
+    case 1000001: Sink = __LINE__; break;
+    case 10000001: Sink = __LINE__; break;
+    case 100000001: return true;
+  }
+  return false;
+}
+
+extern "C" void LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size) {
+  if (Switch<int>(Data, Size) && Size >= 12 &&
+      Switch<uint64_t>(Data + 4, Size - 4)) {
+    std::cout << "BINGO; Found the target, exiting\n";
+    exit(1);
+  }
+}
+
index d6dd3ff..63cb957 100644 (file)
@@ -31,3 +31,6 @@ Done1000000: Done 1000000 runs in
 
 RUN: not LLVMFuzzer-StrncmpTest -use_traces=1 -seed=1 -runs=10000    2>&1 | FileCheck %s
 RUN:     LLVMFuzzer-StrncmpTest               -seed=1 -runs=1000000  2>&1 | FileCheck %s --check-prefix=Done1000000
+
+RUN: not LLVMFuzzer-SwitchTest -use_traces=1 -seed=1 -runs=100000    2>&1 | FileCheck %s
+RUN:     LLVMFuzzer-SwitchTest               -seed=1 -runs=1000000  2>&1 | FileCheck %s --check-prefix=Done1000000
index 7a5b4cb..c91b89d 100644 (file)
@@ -59,6 +59,7 @@ static const char *const kSanCovIndirCallName = "__sanitizer_cov_indir_call16";
 static const char *const kSanCovTraceEnter = "__sanitizer_cov_trace_func_enter";
 static const char *const kSanCovTraceBB = "__sanitizer_cov_trace_basic_block";
 static const char *const kSanCovTraceCmp = "__sanitizer_cov_trace_cmp";
+static const char *const kSanCovTraceSwitch = "__sanitizer_cov_trace_switch";
 static const char *const kSanCovModuleCtorName = "sancov.module_ctor";
 static const uint64_t    kSanCtorAndDtorPriority = 2;
 
@@ -148,6 +149,8 @@ class SanitizerCoverageModule : public ModulePass {
   void InjectCoverageForIndirectCalls(Function &F,
                                       ArrayRef<Instruction *> IndirCalls);
   void InjectTraceForCmp(Function &F, ArrayRef<Instruction *> CmpTraceTargets);
+  void InjectTraceForSwitch(Function &F,
+                            ArrayRef<Instruction *> SwitchTraceTargets);
   bool InjectCoverage(Function &F, ArrayRef<BasicBlock *> AllBlocks);
   void SetNoSanitizeMetadata(Instruction *I);
   void InjectCoverageAtBlock(Function &F, BasicBlock &BB, bool UseCalls);
@@ -159,8 +162,10 @@ class SanitizerCoverageModule : public ModulePass {
   Function *SanCovIndirCallFunction;
   Function *SanCovTraceEnter, *SanCovTraceBB;
   Function *SanCovTraceCmpFunction;
+  Function *SanCovTraceSwitchFunction;
   InlineAsm *EmptyAsm;
-  Type *IntptrTy, *Int64Ty;
+  Type *IntptrTy, *Int64Ty, *Int64PtrTy;
+  Module *CurModule;
   LLVMContext *C;
   const DataLayout *DL;
 
@@ -177,11 +182,13 @@ bool SanitizerCoverageModule::runOnModule(Module &M) {
     return false;
   C = &(M.getContext());
   DL = &M.getDataLayout();
+  CurModule = &M;
   IntptrTy = Type::getIntNTy(*C, DL->getPointerSizeInBits());
   Type *VoidTy = Type::getVoidTy(*C);
   IRBuilder<> IRB(*C);
   Type *Int8PtrTy = PointerType::getUnqual(IRB.getInt8Ty());
   Type *Int32PtrTy = PointerType::getUnqual(IRB.getInt32Ty());
+  Int64PtrTy = PointerType::getUnqual(IRB.getInt64Ty());
   Int64Ty = IRB.getInt64Ty();
 
   SanCovFunction = checkSanitizerInterfaceFunction(
@@ -194,6 +201,9 @@ bool SanitizerCoverageModule::runOnModule(Module &M) {
   SanCovTraceCmpFunction =
       checkSanitizerInterfaceFunction(M.getOrInsertFunction(
           kSanCovTraceCmp, VoidTy, Int64Ty, Int64Ty, Int64Ty, nullptr));
+  SanCovTraceSwitchFunction =
+      checkSanitizerInterfaceFunction(M.getOrInsertFunction(
+          kSanCovTraceSwitch, VoidTy, Int64Ty, Int64PtrTy, nullptr));
 
   // We insert an empty inline asm after cov callbacks to avoid callback merge.
   EmptyAsm = InlineAsm::get(FunctionType::get(IRB.getVoidTy(), false),
@@ -285,6 +295,7 @@ bool SanitizerCoverageModule::runOnFunction(Function &F) {
   SmallVector<Instruction*, 8> IndirCalls;
   SmallVector<BasicBlock*, 16> AllBlocks;
   SmallVector<Instruction*, 8> CmpTraceTargets;
+  SmallVector<Instruction*, 8> SwitchTraceTargets;
   for (auto &BB : F) {
     AllBlocks.push_back(&BB);
     for (auto &Inst : BB) {
@@ -293,13 +304,18 @@ bool SanitizerCoverageModule::runOnFunction(Function &F) {
         if (CS && !CS.getCalledFunction())
           IndirCalls.push_back(&Inst);
       }
-      if (Options.TraceCmp && isa<ICmpInst>(&Inst))
-        CmpTraceTargets.push_back(&Inst);
+      if (Options.TraceCmp) {
+        if (isa<ICmpInst>(&Inst))
+          CmpTraceTargets.push_back(&Inst);
+        if (isa<SwitchInst>(&Inst))
+          SwitchTraceTargets.push_back(&Inst);
+      }
     }
   }
   InjectCoverage(F, AllBlocks);
   InjectCoverageForIndirectCalls(F, IndirCalls);
   InjectTraceForCmp(F, CmpTraceTargets);
+  InjectTraceForSwitch(F, SwitchTraceTargets);
   return true;
 }
 
@@ -348,6 +364,42 @@ void SanitizerCoverageModule::InjectCoverageForIndirectCalls(
   }
 }
 
+// For every switch statement we insert a call:
+// __sanitizer_cov_trace_switch(CondValue,
+//      {NumCases, ValueSizeInBits, Case0Value, Case1Value, Case2Value, ... })
+
+void SanitizerCoverageModule::InjectTraceForSwitch(
+    Function &F, ArrayRef<Instruction *> SwitchTraceTargets) {
+  for (auto I : SwitchTraceTargets) {
+    if (SwitchInst *SI = dyn_cast<SwitchInst>(I)) {
+      IRBuilder<> IRB(I);
+      SmallVector<Constant *, 16> Initializers;
+      Value *Cond = SI->getCondition();
+      Initializers.push_back(ConstantInt::get(Int64Ty, SI->getNumCases()));
+      Initializers.push_back(
+          ConstantInt::get(Int64Ty, Cond->getType()->getScalarSizeInBits()));
+      if (Cond->getType()->getScalarSizeInBits() <
+          Int64Ty->getScalarSizeInBits())
+        Cond = IRB.CreateIntCast(Cond, Int64Ty, false);
+      for (auto It: SI->cases()) {
+        Constant *C = It.getCaseValue();
+        if (C->getType()->getScalarSizeInBits() <
+            Int64Ty->getScalarSizeInBits())
+          C = ConstantExpr::getCast(CastInst::ZExt, It.getCaseValue(), Int64Ty);
+        Initializers.push_back(C);
+      }
+      ArrayType *ArrayOfInt64Ty = ArrayType::get(Int64Ty, Initializers.size());
+      GlobalVariable *GV = new GlobalVariable(
+          *CurModule, ArrayOfInt64Ty, false, GlobalVariable::InternalLinkage,
+          ConstantArray::get(ArrayOfInt64Ty, Initializers),
+          "__sancov_gen_cov_switch_values");
+      IRB.CreateCall(SanCovTraceSwitchFunction,
+                     {Cond, IRB.CreatePointerCast(GV, Int64PtrTy)});
+    }
+  }
+}
+
+
 void SanitizerCoverageModule::InjectTraceForCmp(
     Function &F, ArrayRef<Instruction *> CmpTraceTargets) {
   for (auto I : CmpTraceTargets) {
@@ -403,7 +455,6 @@ void SanitizerCoverageModule::InjectCoverageAtBlock(Function &F, BasicBlock &BB,
 
   IRBuilder<> IRB(IP);
   IRB.SetCurrentDebugLocation(EntryLoc);
-  SmallVector<Value *, 1> Indices;
   Value *GuardP = IRB.CreateAdd(
       IRB.CreatePointerCast(GuardArray, IntptrTy),
       ConstantInt::get(IntptrTy, (1 + NumberOfInstrumentedBlocks()) * 4));
diff --git a/test/Instrumentation/SanitizerCoverage/switch-tracing.ll b/test/Instrumentation/SanitizerCoverage/switch-tracing.ll
new file mode 100644 (file)
index 0000000..9ad1c7a
--- /dev/null
@@ -0,0 +1,32 @@
+; Test -sanitizer-coverage-experimental-trace-compares=1 (instrumenting a switch)
+; RUN: opt < %s -sancov -sanitizer-coverage-level=1 -sanitizer-coverage-experimental-trace-compares=1  -S | FileCheck %s --check-prefix=CHECK
+
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"
+target triple = "x86_64-unknown-linux-gnu"
+declare void @_Z3bari(i32)
+define void @foo(i32 %x) {
+entry:
+; CHECK: __sancov_gen_cov_switch_values = internal global [5 x i64] [i64 3, i64 32, i64 1, i64 101, i64 1001]
+; CHECK: [[TMP:%[0-9]*]] = zext i32 %x to i64
+; CHECK-NEXT: call void @__sanitizer_cov_trace_switch(i64 [[TMP]], i64* getelementptr inbounds ([5 x i64], [5 x i64]* @__sancov_gen_cov_switch_values, i32 0, i32 0))
+  switch i32 %x, label %sw.epilog [
+    i32 1, label %sw.bb
+    i32 101, label %sw.bb.1
+    i32 1001, label %sw.bb.2
+  ]
+
+sw.bb:                                            ; preds = %entry
+  tail call void @_Z3bari(i32 4)
+  br label %sw.epilog
+
+sw.bb.1:                                          ; preds = %entry
+  tail call void @_Z3bari(i32 5)
+  br label %sw.epilog
+
+sw.bb.2:                                          ; preds = %entry
+  tail call void @_Z3bari(i32 6)
+  br label %sw.epilog
+
+sw.epilog:                                        ; preds = %entry, %sw.bb.2, %sw.bb.1, %sw.bb
+  ret void
+}