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. --- test/Feature/consecutive_divide_by_zero.c | 30 ++++++++++++++++++++++++++++++ 1 file changed, 30 insertions(+) create mode 100644 test/Feature/consecutive_divide_by_zero.c (limited to 'test') 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; +} -- 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 'test') 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