From 75d0c41e361583cf922b6082b1cb13eee2811e33 Mon Sep 17 00:00:00 2001 From: Cristian Cadar Date: Fri, 4 Aug 2017 23:15:29 +0100 Subject: Added checks for div/mod by zero and overshifts in constant expressions. Such div/mod by zero expressions would previously crash KLEE. Added two test cases, one for div/mod by zero, the other for overshift. This fixes the bug reported in #268. --- lib/Core/ExecutorUtil.cpp | 24 ++++++++++++++++++++++++ test/Feature/ConstExprWithDivZero.ll | 18 ++++++++++++++++++ test/Feature/ConstExprWithOvershift.ll | 16 ++++++++++++++++ 3 files changed, 58 insertions(+) create mode 100644 test/Feature/ConstExprWithDivZero.ll create mode 100644 test/Feature/ConstExprWithOvershift.ll diff --git a/lib/Core/ExecutorUtil.cpp b/lib/Core/ExecutorUtil.cpp index 0a8f08ed..bd8aa200 100644 --- a/lib/Core/ExecutorUtil.cpp +++ b/lib/Core/ExecutorUtil.cpp @@ -126,6 +126,30 @@ namespace klee { if (numOperands > 1) op2 = evalConstant(ce->getOperand(1), ki); if (numOperands > 2) op3 = evalConstant(ce->getOperand(2), ki); + /* Checking for possible errors during constant folding */ + switch (ce->getOpcode()) { + case Instruction::SDiv: + case Instruction::UDiv: + case Instruction::SRem: + case Instruction::URem: + if (op2->getLimitedValue() == 0) { + std::string msg("Division/modulo by zero during constant folding at location "); + llvm::raw_string_ostream os(msg); + os << (ki ? ki->printFileLine().c_str() : "[unknown]"); + klee_error("%s", os.str().c_str()); + } + break; + case Instruction::Shl: + case Instruction::LShr: + case Instruction::AShr: + if (op2->getLimitedValue() >= op1->getWidth()) { + std::string msg("Overshift during constant folding at location "); + llvm::raw_string_ostream os(msg); + os << (ki ? ki->printFileLine().c_str() : "[unknown]"); + klee_error("%s", os.str().c_str()); + } + } + std::string msg("Unknown ConstantExpr type"); llvm::raw_string_ostream os(msg); diff --git a/test/Feature/ConstExprWithDivZero.ll b/test/Feature/ConstExprWithDivZero.ll new file mode 100644 index 00000000..f430dad9 --- /dev/null +++ b/test/Feature/ConstExprWithDivZero.ll @@ -0,0 +1,18 @@ +; REQUIRES: llvm-3.4 +; RUN: llvm-as %s -f -o %t.bc +; RUN: rm -rf %t.klee-out +; RUN: not %klee --output-dir=%t.klee-out %t.bc 2> %t.log +; RUN: FileCheck --input-file %t.log %s + +; See https://github.com/klee/klee/issues/268 + +target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128" +target triple = "x86_64-pc-linux-gnu" + +@a = internal global i32 0, align 4 +@b = internal global [1 x i32] [i32 1], align 4 + +define i32 @main() { +; CHECK: Division/modulo by zero during constant folding + ret i32 trunc (i64 sdiv (i64 2036854775807, i64 sext (i32 select (i1 icmp eq (i32* getelementptr inbounds ([1 x i32]* @b, i64 0, i64 0), i32* @a), i32 1, i32 0) to i64)) to i32) +} diff --git a/test/Feature/ConstExprWithOvershift.ll b/test/Feature/ConstExprWithOvershift.ll new file mode 100644 index 00000000..7d4a1284 --- /dev/null +++ b/test/Feature/ConstExprWithOvershift.ll @@ -0,0 +1,16 @@ +; REQUIRES: llvm-3.4 +; RUN: llvm-as %s -f -o %t.bc +; RUN: rm -rf %t.klee-out +; RUN: not %klee --output-dir=%t.klee-out %t.bc 2> %t.log +; RUN: FileCheck --input-file %t.log %s + +target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128" +target triple = "x86_64-pc-linux-gnu" + +@a = internal global i32 0, align 4 +@b = internal global [1 x i32] [i32 1], align 4 + +define i32 @main() { +; CHECK: Overshift during constant folding + ret i32 ashr (i32 zext (i1 icmp ne (i32* getelementptr inbounds ([1 x i32]* @b, i64 0, i64 0), i32* @a) to i32), i32 trunc (i64 add (i64 zext (i1 icmp ne (i32* getelementptr inbounds ([1 x i32]* @b, i64 0, i64 0), i32* @a) to i64), i64 31) to i32)) +} -- cgit 1.4.1 From 966c8102a7b851f5199ea6ff4d83ea1472913a7f Mon Sep 17 00:00:00 2001 From: Cristian Cadar Date: Sat, 5 Aug 2017 21:13:21 +0100 Subject: Untabify this file, which was using a mix of spaces and tabs for alignment. --- lib/Core/ExecutorUtil.cpp | 128 +++++++++++++++++++++++----------------------- 1 file changed, 64 insertions(+), 64 deletions(-) diff --git a/lib/Core/ExecutorUtil.cpp b/lib/Core/ExecutorUtil.cpp index bd8aa200..53f4c5b8 100644 --- a/lib/Core/ExecutorUtil.cpp +++ b/lib/Core/ExecutorUtil.cpp @@ -36,87 +36,87 @@ using namespace llvm; namespace klee { ref Executor::evalConstant(const Constant *c, - const KInstruction *ki) { + const KInstruction *ki) { if (!ki) { KConstant* kc = kmodule->getKConstant(c); if (kc) - ki = kc->ki; + ki = kc->ki; } if (const llvm::ConstantExpr *ce = dyn_cast(c)) { return evalConstantExpr(ce, ki); } else { if (const ConstantInt *ci = dyn_cast(c)) { - return ConstantExpr::alloc(ci->getValue()); + return ConstantExpr::alloc(ci->getValue()); } else if (const ConstantFP *cf = dyn_cast(c)) { - return ConstantExpr::alloc(cf->getValueAPF().bitcastToAPInt()); + return ConstantExpr::alloc(cf->getValueAPF().bitcastToAPInt()); } else if (const GlobalValue *gv = dyn_cast(c)) { - return globalAddresses.find(gv)->second; + return globalAddresses.find(gv)->second; } else if (isa(c)) { - return Expr::createPointer(0); + return Expr::createPointer(0); } else if (isa(c) || isa(c)) { - return ConstantExpr::create(0, getWidthForLLVMType(c->getType())); + return ConstantExpr::create(0, getWidthForLLVMType(c->getType())); } else if (const ConstantDataSequential *cds = dyn_cast(c)) { - std::vector > kids; - for (unsigned i = 0, e = cds->getNumElements(); i != e; ++i) { - ref kid = evalConstant(cds->getElementAsConstant(i), ki); - kids.push_back(kid); - } - ref res = ConcatExpr::createN(kids.size(), kids.data()); - return cast(res); + std::vector > kids; + for (unsigned i = 0, e = cds->getNumElements(); i != e; ++i) { + ref kid = evalConstant(cds->getElementAsConstant(i), ki); + kids.push_back(kid); + } + ref res = ConcatExpr::createN(kids.size(), kids.data()); + return cast(res); } else if (const ConstantStruct *cs = dyn_cast(c)) { - const StructLayout *sl = kmodule->targetData->getStructLayout(cs->getType()); - llvm::SmallVector, 4> kids; - for (unsigned i = cs->getNumOperands(); i != 0; --i) { - unsigned op = i-1; - ref kid = evalConstant(cs->getOperand(op), ki); + const StructLayout *sl = kmodule->targetData->getStructLayout(cs->getType()); + llvm::SmallVector, 4> kids; + for (unsigned i = cs->getNumOperands(); i != 0; --i) { + unsigned op = i-1; + ref kid = evalConstant(cs->getOperand(op), ki); - uint64_t thisOffset = sl->getElementOffsetInBits(op), - nextOffset = (op == cs->getNumOperands() - 1) - ? sl->getSizeInBits() - : sl->getElementOffsetInBits(op+1); - if (nextOffset-thisOffset > kid->getWidth()) { - uint64_t paddingWidth = nextOffset-thisOffset-kid->getWidth(); - kids.push_back(ConstantExpr::create(0, paddingWidth)); - } + uint64_t thisOffset = sl->getElementOffsetInBits(op), + nextOffset = (op == cs->getNumOperands() - 1) + ? sl->getSizeInBits() + : sl->getElementOffsetInBits(op+1); + if (nextOffset-thisOffset > kid->getWidth()) { + uint64_t paddingWidth = nextOffset-thisOffset-kid->getWidth(); + kids.push_back(ConstantExpr::create(0, paddingWidth)); + } - kids.push_back(kid); - } - ref res = ConcatExpr::createN(kids.size(), kids.data()); - return cast(res); + kids.push_back(kid); + } + ref res = ConcatExpr::createN(kids.size(), kids.data()); + return cast(res); } else if (const ConstantArray *ca = dyn_cast(c)){ - llvm::SmallVector, 4> kids; - for (unsigned i = ca->getNumOperands(); i != 0; --i) { - unsigned op = i-1; - ref kid = evalConstant(ca->getOperand(op), ki); - kids.push_back(kid); - } - ref res = ConcatExpr::createN(kids.size(), kids.data()); - return cast(res); + llvm::SmallVector, 4> kids; + for (unsigned i = ca->getNumOperands(); i != 0; --i) { + unsigned op = i-1; + ref kid = evalConstant(ca->getOperand(op), ki); + kids.push_back(kid); + } + ref res = ConcatExpr::createN(kids.size(), kids.data()); + return cast(res); } else if (const ConstantVector *cv = dyn_cast(c)) { - llvm::SmallVector, 8> kids; - const size_t numOperands = cv->getNumOperands(); - kids.reserve(numOperands); - for (unsigned i = 0; i < numOperands; ++i) { - kids.push_back(evalConstant(cv->getOperand(i), ki)); - } - ref res = ConcatExpr::createN(numOperands, kids.data()); - assert(isa(res) && - "result of constant vector built is not a constant"); - return cast(res); + llvm::SmallVector, 8> kids; + const size_t numOperands = cv->getNumOperands(); + kids.reserve(numOperands); + for (unsigned i = 0; i < numOperands; ++i) { + kids.push_back(evalConstant(cv->getOperand(i), ki)); + } + ref res = ConcatExpr::createN(numOperands, kids.data()); + assert(isa(res) && + "result of constant vector built is not a constant"); + return cast(res); } else { - std::string msg("Cannot handle constant "); - llvm::raw_string_ostream os(msg); - os << "'" << *c << "' at location " - << (ki ? ki->printFileLine().c_str() : "[unknown]"); - klee_error("%s", os.str().c_str()); + std::string msg("Cannot handle constant "); + llvm::raw_string_ostream os(msg); + os << "'" << *c << "' at location " + << (ki ? ki->printFileLine().c_str() : "[unknown]"); + klee_error("%s", os.str().c_str()); } } } ref Executor::evalConstantExpr(const llvm::ConstantExpr *ce, - const KInstruction *ki) { + const KInstruction *ki) { llvm::Type *type = ce->getType(); ref op1(0), op2(0), op3(0); @@ -133,20 +133,20 @@ namespace klee { case Instruction::SRem: case Instruction::URem: if (op2->getLimitedValue() == 0) { - std::string msg("Division/modulo by zero during constant folding at location "); - llvm::raw_string_ostream os(msg); - os << (ki ? ki->printFileLine().c_str() : "[unknown]"); - klee_error("%s", os.str().c_str()); + std::string msg("Division/modulo by zero during constant folding at location "); + llvm::raw_string_ostream os(msg); + os << (ki ? ki->printFileLine().c_str() : "[unknown]"); + klee_error("%s", os.str().c_str()); } break; case Instruction::Shl: case Instruction::LShr: case Instruction::AShr: if (op2->getLimitedValue() >= op1->getWidth()) { - std::string msg("Overshift during constant folding at location "); - llvm::raw_string_ostream os(msg); - os << (ki ? ki->printFileLine().c_str() : "[unknown]"); - klee_error("%s", os.str().c_str()); + std::string msg("Overshift during constant folding at location "); + llvm::raw_string_ostream os(msg); + os << (ki ? ki->printFileLine().c_str() : "[unknown]"); + klee_error("%s", os.str().c_str()); } } @@ -156,7 +156,7 @@ namespace klee { switch (ce->getOpcode()) { default : os << "'" << *ce << "' at location " - << (ki ? ki->printFileLine().c_str() : "[unknown]"); + << (ki ? ki->printFileLine().c_str() : "[unknown]"); klee_error("%s", os.str().c_str()); case Instruction::Trunc: -- cgit 1.4.1