diff options
| -rw-r--r-- | include/klee/Interpreter.h | 6 | ||||
| -rw-r--r-- | lib/Module/Checks.cpp | 59 | ||||
| -rw-r--r-- | lib/Module/KModule.cpp | 64 | ||||
| -rw-r--r-- | lib/Module/Passes.h | 25 | ||||
| -rw-r--r-- | runtime/Intrinsic/klee_overshift_check.c | 31 | ||||
| -rw-r--r-- | test/Feature/OvershiftCheck.c | 26 | ||||
| -rw-r--r-- | test/Feature/consecutive_divide_by_zero.c | 30 | ||||
| -rw-r--r-- | tools/klee/main.cpp | 10 |
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 */ |