From f8301282120cc3cc58d641ddc99f92b14d894692 Mon Sep 17 00:00:00 2001 From: Dan Liew Date: Fri, 30 Aug 2013 16:43:30 +0100 Subject: Fixed bug where divide by zero bugs would only be detected once in a program even if there were many divide by zero bugs. The fix basically inlines all function calls to klee_div_zero_check() so that each call to klee_report_error() is a unique instruction for each instrumentation of a divide operation. It also seems that inlining the call "magically" fixed the debug information (file and line number) of the instruction so that the debug information on the inlined instructions matches that of the instrumented division instruction. Note that the command line option -emit-all-errors could be used to workaround the bug fixed in this commit. --- lib/Module/KModule.cpp | 61 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 61 insertions(+) (limited to 'lib/Module') diff --git a/lib/Module/KModule.cpp b/lib/Module/KModule.cpp index 1629bb79..a6047536 100644 --- a/lib/Module/KModule.cpp +++ b/lib/Module/KModule.cpp @@ -47,6 +47,10 @@ #endif #include "llvm/Transforms/Scalar.h" +#include +#include +#include + #include using namespace llvm; @@ -212,6 +216,52 @@ static void forceImport(Module *m, const char *name, LLVM_TYPE_Q Type *retType, } } +/// 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 klee_div_zero_check() +static void inlineChecks(Module *module, const char * functionName) { + std::vector 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(&*i) ) + { + if ( ci->getCalledFunction() == runtimeCheckCall) + checkCalls.push_back(ci); + } + } + } + + unsigned int successCount=0; + unsigned int failCount=0; + InlineFunctionInfo IFI(0,0); + for ( std::vector::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()) { @@ -312,6 +362,17 @@ void KModule::prepare(const Interpreter::ModuleOptions &opts, path.appendComponent("libkleeRuntimeIntrinsic.bca"); 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"); + + // Needs to happen after linking (since ctors/dtors can be modified) // and optimization (since global optimization can rewrite lists). injectStaticConstructorsAndDestructors(module); -- cgit 1.4.1 From 4b477f8108a2a92012ff138725f6c6f26ccb23e5 Mon Sep 17 00:00:00 2001 From: Dan Liew Date: Thu, 29 Aug 2013 17:30:33 +0100 Subject: 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. --- include/klee/Interpreter.h | 6 ++-- lib/Module/Checks.cpp | 59 ++++++++++++++++++++++++++++++++ lib/Module/KModule.cpp | 3 ++ lib/Module/Passes.h | 25 ++++++++++++++ runtime/Intrinsic/klee_overshift_check.c | 31 +++++++++++++++++ test/Feature/OvershiftCheck.c | 26 ++++++++++++++ tools/klee/main.cpp | 10 ++++-- 7 files changed, 156 insertions(+), 4 deletions(-) create mode 100644 runtime/Intrinsic/klee_overshift_check.c create mode 100644 test/Feature/OvershiftCheck.c (limited to 'lib/Module') 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 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(i)) { + // find all shift instructions + Instruction::BinaryOps opcode = binOp->getOpcode(); + + if (opcode == Instruction::Shl || + opcode == Instruction::LShr || + opcode == Instruction::AShr ) { + std::vector 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(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! 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 + +/* 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/tools/klee/main.cpp b/tools/klee/main.cpp index 92e4df67..7cd61788 100644 --- a/tools/klee/main.cpp +++ b/tools/klee/main.cpp @@ -148,7 +148,12 @@ namespace { CheckDivZero("check-div-zero", cl::desc("Inject checks for division-by-zero"), cl::init(true)); - + + cl::opt + CheckOvershift("check-overshift", + cl::desc("Inject checks for overshift"), + cl::init(true)); + cl::opt OutputDir("output-dir", cl::desc("Directory to write results in (defaults to klee-out-N)"), @@ -1241,7 +1246,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 */ -- cgit 1.4.1