Merge pull request #26 from delcypher/fix_divide_by_zero

Fixed bug where divide by zero bugs would only be detected once in a program

8 files changed, 247 insertions, 4 deletions

diff --git a/include/klee/Interpreter.h b/include/klee/Interpreter.h
index e29db411..e93284d6 100644
--- a/include/klee/Interpreter.h
+++ b/include/klee/Interpreter.h
@@ -51,11 +51,13 @@ public:
     std::string LibraryDir;
     bool Optimize;
     bool CheckDivZero;
+    bool CheckOvershift;
 
     ModuleOptions(const std::string& _LibraryDir, 
-                  bool _Optimize, bool _CheckDivZero)
+                  bool _Optimize, bool _CheckDivZero,
+                  bool _CheckOvershift)
       : LibraryDir(_LibraryDir), Optimize(_Optimize), 
-        CheckDivZero(_CheckDivZero) {}
+        CheckDivZero(_CheckDivZero), CheckOvershift(_CheckOvershift) {}
   };
 
   enum LogType
diff --git a/lib/Module/Checks.cpp b/lib/Module/Checks.cpp
index 5cf57069..c6fc9d3a 100644
--- a/lib/Module/Checks.cpp
+++ b/lib/Module/Checks.cpp
@@ -94,3 +94,62 @@ bool DivCheckPass::runOnModule(Module &M) {
   }
   return moduleChanged;
 }
+
+char OvershiftCheckPass::ID;
+
+bool OvershiftCheckPass::runOnModule(Module &M) {
+  Function *overshiftCheckFunction = 0;
+
+  bool moduleChanged = false;
+
+  for (Module::iterator f = M.begin(), fe = M.end(); f != fe; ++f) {
+    for (Function::iterator b = f->begin(), be = f->end(); b != be; ++b) {
+      for (BasicBlock::iterator i = b->begin(), ie = b->end(); i != ie; ++i) {
+          if (BinaryOperator* binOp = dyn_cast<BinaryOperator>(i)) {
+          // find all shift instructions
+          Instruction::BinaryOps opcode = binOp->getOpcode();
+
+          if (opcode == Instruction::Shl ||
+              opcode == Instruction::LShr ||
+              opcode == Instruction::AShr ) {
+            std::vector<llvm::Value*> args;
+
+            // Determine bit width of first operand
+            uint64_t bitWidth=i->getOperand(0)->getType()->getScalarSizeInBits();
+
+            ConstantInt *bitWidthC = ConstantInt::get(Type::getInt64Ty(getGlobalContext()),bitWidth,false);
+            args.push_back(bitWidthC);
+
+            CastInst *shift =
+              CastInst::CreateIntegerCast(i->getOperand(1),
+                                          Type::getInt64Ty(getGlobalContext()),
+                                          false,  /* sign doesn't matter */
+                                          "int_cast_to_i64",
+                                          i);
+            args.push_back(shift);
+
+
+            // Lazily bind the function to avoid always importing it.
+            if (!overshiftCheckFunction) {
+              Constant *fc = M.getOrInsertFunction("klee_overshift_check",
+                                                   Type::getVoidTy(getGlobalContext()),
+                                                   Type::getInt64Ty(getGlobalContext()),
+                                                   Type::getInt64Ty(getGlobalContext()),
+                                                   NULL);
+              overshiftCheckFunction = cast<Function>(fc);
+            }
+
+            // Inject CallInstr to check if overshifting possible
+#if LLVM_VERSION_CODE >= LLVM_VERSION(3, 0)
+            CallInst::Create(overshiftCheckFunction, args, "", &*i);
+#else
+            CallInst::Create(overshiftCheckFunction, args.begin(), args.end(), "", &*i);
+#endif
+            moduleChanged = true;
+          }
+        }
+      }
+    }
+  }
+  return moduleChanged;
+}
diff --git a/lib/Module/KModule.cpp b/lib/Module/KModule.cpp
index 0d0244dd..ff13efda 100644
--- a/lib/Module/KModule.cpp
+++ b/lib/Module/KModule.cpp
@@ -57,6 +57,10 @@
 #endif
 #include "llvm/Transforms/Scalar.h"
 
+#include <llvm/Transforms/Utils/Cloning.h>
+#include <llvm/Support/InstIterator.h>
+#include <llvm/Support/Debug.h>
+
 #include <sstream>
 
 using namespace llvm;
@@ -224,6 +228,52 @@ static void forceImport(Module *m, const char *name, LLVM_TYPE_Q Type *retType,
 }
 #endif
 
+/// This function will take try to inline all calls to \p functionName
+/// in the module \p module .
+///
+/// It is intended that this function be used for inling calls to
+/// check functions like <tt>klee_div_zero_check()</tt>
+static void inlineChecks(Module *module, const char * functionName) {
+  std::vector<CallInst*> checkCalls;
+    Function* runtimeCheckCall = module->getFunction(functionName);
+    if (runtimeCheckCall == 0)
+    {
+      DEBUG( klee_warning("Failed to inline %s because no calls were made to it in module", functionName) );
+      return;
+    }
+
+    // Iterate through instructions in module and collect all
+    // call instructions to "functionName" that we care about.
+    for (Module::iterator f = module->begin(), fe = module->end(); f != fe; ++f) {
+      for (inst_iterator i=inst_begin(f), ie = inst_end(f); i != ie; ++i) {
+        if ( CallInst* ci = dyn_cast<CallInst>(&*i) )
+        {
+          if ( ci->getCalledFunction() == runtimeCheckCall)
+            checkCalls.push_back(ci);
+        }
+      }
+    }
+
+    unsigned int successCount=0;
+    unsigned int failCount=0;
+    InlineFunctionInfo IFI(0,0);
+    for ( std::vector<CallInst*>::iterator ci = checkCalls.begin(),
+          cie = checkCalls.end();
+          ci != cie; ++ci)
+    {
+      // Try to inline the function
+      if (InlineFunction(*ci,IFI))
+        ++successCount;
+      else
+      {
+        ++failCount;
+        klee_warning("Failed to inline function %s", functionName);
+      }
+    }
+
+    DEBUG( klee_message("Tried to inline calls to %s. %u successes, %u failures",functionName, successCount, failCount) );
+}
+
 void KModule::prepare(const Interpreter::ModuleOptions &opts,
                       InterpreterHandler *ih) {
   if (!MergeAtExit.empty()) {
@@ -284,6 +334,7 @@ void KModule::prepare(const Interpreter::ModuleOptions &opts,
   PassManager pm;
   pm.add(new RaiseAsmPass());
   if (opts.CheckDivZero) pm.add(new DivCheckPass());
+  if (opts.CheckOvershift) pm.add(new OvershiftCheckPass());
   // FIXME: This false here is to work around a bug in
   // IntrinsicLowering which caches values which may eventually be
   // deleted (via RAUW). This can be removed once LLVM fixes this
@@ -328,6 +379,19 @@ void KModule::prepare(const Interpreter::ModuleOptions &opts,
 #endif
   module = linkWithLibrary(module, path.c_str());
 
+  /* In order for KLEE to report ALL errors at instrumented
+   * locations the instrumentation call (e.g. "klee_div_zero_check")
+   * must be inlined. Otherwise one of the instructions in the
+   * instrumentation function will be used as the the location of
+   * the error which means that the error cannot be recorded again
+   * ( unless -emit-all-errors is used).
+   */
+  if (opts.CheckDivZero)
+    inlineChecks(module, "klee_div_zero_check");
+  if (opts.CheckOvershift)
+    inlineChecks(module, "klee_overshift_check");
+
+
   // Needs to happen after linking (since ctors/dtors can be modified)
   // and optimization (since global optimization can rewrite lists).
   injectStaticConstructorsAndDestructors(module);
diff --git a/lib/Module/Passes.h b/lib/Module/Passes.h
index d83e57ec..0c294daa 100644
--- a/lib/Module/Passes.h
+++ b/lib/Module/Passes.h
@@ -143,6 +143,31 @@ public:
   virtual bool runOnModule(llvm::Module &M);
 };
 
+/// This pass injects checks to check for overshifting.
+///
+/// Overshifting is where a Shl, LShr or AShr is performed
+/// where the shift amount is greater than width of the bitvector
+/// being shifted.
+/// In LLVM (and in C/C++) this undefined behaviour!
+///
+/// Example:
+/// \code
+///     unsigned char x=15;
+///     x << 4 ; // Defined behaviour
+///     x << 8 ; // Undefined behaviour
+///     x << 255 ; // Undefined behaviour
+/// \endcode
+class OvershiftCheckPass : public llvm::ModulePass {
+  static char ID;
+public:
+#if LLVM_VERSION_CODE < LLVM_VERSION(2, 8)
+  OvershiftCheckPass(): ModulePass((intptr_t) &ID) {}
+#else
+  OvershiftCheckPass(): ModulePass(ID) {}
+#endif
+  virtual bool runOnModule(llvm::Module &M);
+};
+
 /// LowerSwitchPass - Replace all SwitchInst instructions with chained branch
 /// instructions.  Note that this cannot be a BasicBlock pass because it
 /// modifies the CFG!
diff --git a/runtime/Intrinsic/klee_overshift_check.c b/runtime/Intrinsic/klee_overshift_check.c
new file mode 100644
index 00000000..c0cb6102
--- /dev/null
+++ b/runtime/Intrinsic/klee_overshift_check.c
@@ -0,0 +1,31 @@
+//===-- klee_overshift_check.c ---------------------------------------------===//
+//
+//                     The KLEE Symbolic Virtual Machine
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include <klee/klee.h>
+
+/* This instrumentation call is used to check for overshifting.
+ * If we do try to do x << y or x >> y
+ * where
+ *   bitWidth = sizeof(x)*8
+ *   shift = y
+ *
+ * then we can detect overshifting (which has undefined behaviour).
+ */
+void klee_overshift_check(unsigned long long bitWidth, unsigned long long shift) {
+  if (shift >= bitWidth) {
+    /* Maybe we shouldn't throw an error because
+     * overshifting can be non-fatal? Perhaps
+     * we should generate a test case but carry
+     * on executing the state with a warning?
+     */
+    klee_report_error("IGNORED", 0 /*Ignored */, "overshift error", "overshift.err");
+  }
+}
+
+
diff --git a/test/Feature/OvershiftCheck.c b/test/Feature/OvershiftCheck.c
new file mode 100644
index 00000000..bb967166
--- /dev/null
+++ b/test/Feature/OvershiftCheck.c
@@ -0,0 +1,26 @@
+// RUN: %llvmgcc %s -emit-llvm -g -O0 -c -o %t.bc
+// RUN: %klee -check-overshift %t.bc 2> %t.log
+// RUN: grep -c "overshift error" %t.log
+// RUN: grep -c "OvershiftCheck.c:19: overshift error" %t.log
+// RUN: grep -c "OvershiftCheck.c:23: overshift error" %t.log
+
+/* This test checks that two consecutive potential overshifts
+ * are reported as errors.
+ */
+int main()
+{
+  unsigned int x=15;
+  unsigned int y;
+  unsigned int z;
+  volatile unsigned int result;
+
+  /* Overshift if y>= sizeof(x) */
+  klee_make_symbolic(&y,sizeof(y),"shift_amount1");
+  result = x << y;
+
+  /* Overshift is z>= sizeof(x) */
+  klee_make_symbolic(&z,sizeof(z),"shift_amount2");
+  result = x >> z;
+
+  return 0;
+}
diff --git a/test/Feature/consecutive_divide_by_zero.c b/test/Feature/consecutive_divide_by_zero.c
new file mode 100644
index 00000000..c1185870
--- /dev/null
+++ b/test/Feature/consecutive_divide_by_zero.c
@@ -0,0 +1,30 @@
+// RUN: %llvmgcc -emit-llvm -c -g -O0 %s -o %t.bc
+// RUN: %klee -check-div-zero -emit-all-errors=0 %t.bc 2> %t.log
+// RUN: grep "completed paths = 3" %t.log
+// RUN: grep "generated tests = 3" %t.log
+// RUN: grep "consecutive_divide_by_zero.c:24: divide by zero" %t.log
+// RUN: grep "consecutive_divide_by_zero.c:27: divide by zero" %t.log
+
+/* This test case captures a bug where two distinct division
+*  by zero errors are treated as the same error and so
+*  only one test case is generated EVEN IF THERE ARE MULTIPLE 
+*  DISTINCT ERRORS!
+*/
+int main()
+{
+  unsigned int a=15;
+  unsigned int b=15;
+  volatile unsigned int d1;
+  volatile unsigned int d2;
+
+  klee_make_symbolic(&d1, sizeof(d1),"divisor1");
+  klee_make_symbolic(&d2, sizeof(d2),"divisor2");
+
+  // deliberate division by zero possible
+  unsigned int result1 = a / d1;
+
+  // another deliberate division by zero possible
+  unsigned int result2 = b / d2;
+
+  return 0;
+}
diff --git a/tools/klee/main.cpp b/tools/klee/main.cpp
index 5dbc8fb0..0e576415 100644
--- a/tools/klee/main.cpp
+++ b/tools/klee/main.cpp
@@ -158,7 +158,12 @@ namespace {
   CheckDivZero("check-div-zero", 
                cl::desc("Inject checks for division-by-zero"),
                cl::init(true));
-    
+
+  cl::opt<bool>
+  CheckOvershift("check-overshift",
+               cl::desc("Inject checks for overshift"),
+               cl::init(true));
+
   cl::opt<std::string>
   OutputDir("output-dir", 
             cl::desc("Directory to write results in (defaults to klee-out-N)"),
@@ -1251,7 +1256,8 @@ int main(int argc, char **argv, char **envp) {
 #endif
   Interpreter::ModuleOptions Opts(LibraryDir.c_str(),
                                   /*Optimize=*/OptimizeModule, 
-                                  /*CheckDivZero=*/CheckDivZero);
+                                  /*CheckDivZero=*/CheckDivZero,
+                                  /*CheckOvershift=*/CheckOvershift);
   
   switch (Libc) {
   case NoLibc: /* silence compiler warning */