Implemented runtime check for overshift (controllable with --check-overshift

command line argument).

Overshift is where a Shl, AShr or LShr has a shift width greater
than the bit width of the first operand. This is undefined behaviour
in LLVM so we report this as an error.

3 files changed, 87 insertions, 0 deletions

diff --git a/lib/Module/Checks.cpp b/lib/Module/Checks.cpp
index 18ef398a..67ed9aa7 100644
--- a/lib/Module/Checks.cpp
+++ b/lib/Module/Checks.cpp
@@ -76,3 +76,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 a6047536..b646ca6e 100644
--- a/lib/Module/KModule.cpp
+++ b/lib/Module/KModule.cpp
@@ -322,6 +322,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
@@ -371,6 +372,8 @@ void KModule::prepare(const Interpreter::ModuleOptions &opts,
    */
   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)
diff --git a/lib/Module/Passes.h b/lib/Module/Passes.h
index b3c46124..b0d4c363 100644
--- a/lib/Module/Passes.h
+++ b/lib/Module/Passes.h
@@ -137,6 +137,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!