Index: include/clang/StaticAnalyzer/Checkers/Checkers.td =================================================================== --- include/clang/StaticAnalyzer/Checkers/Checkers.td +++ include/clang/StaticAnalyzer/Checkers/Checkers.td @@ -248,6 +248,10 @@ HelpText<"Check for assigning uninitialized values">, DescFile<"UndefinedAssignmentChecker.cpp">; +def UnsequencedModificationChecker : Checker<"UB">, + HelpText<"Check for unsequenced modifications">, + DescFile<"UnsequencedModificationChecker.cpp">; + def UndefBranchChecker : Checker<"Branch">, HelpText<"Check for uninitialized values used as branch conditions">, DescFile<"UndefBranchChecker.cpp">; Index: lib/StaticAnalyzer/Checkers/CMakeLists.txt =================================================================== --- lib/StaticAnalyzer/Checkers/CMakeLists.txt +++ lib/StaticAnalyzer/Checkers/CMakeLists.txt @@ -87,6 +87,7 @@ UndefResultChecker.cpp UndefinedArraySubscriptChecker.cpp UndefinedAssignmentChecker.cpp + UnsequencedModificationChecker.cpp UnixAPIChecker.cpp UnreachableCodeChecker.cpp VforkChecker.cpp Index: lib/StaticAnalyzer/Checkers/UnsequencedModificationChecker.cpp =================================================================== --- lib/StaticAnalyzer/Checkers/UnsequencedModificationChecker.cpp +++ lib/StaticAnalyzer/Checkers/UnsequencedModificationChecker.cpp @@ -0,0 +1,450 @@ +//=== UnsequencedModificationChecker.cpp -------------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This defines UnsequencedModificationChecker, a builtin check in ExprEngine +// that performs checks for unsequenced modifications. +// +//===----------------------------------------------------------------------===// + +#include "ClangSACheckers.h" +#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" +#include "clang/StaticAnalyzer/Core/Checker.h" +#include "clang/StaticAnalyzer/Core/CheckerManager.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" +#include "llvm/ADT/SmallString.h" +#include "llvm/Support/raw_ostream.h" +#include +#include +#include +#include +#include + +using namespace clang; +using namespace ento; + +namespace { + + enum UBType + { + UB_VAR, + UB_ARRAY, + UB_POINTER, + UB_POINTERINDEX + }; + + class UBDecl + { + public: + UBDecl(const VarDecl *vd) + { + this->idx = SVal(); + this->type = UB_VAR; + this->vd = vd; + }; + UBDecl(const VarDecl *vd, enum UBType t) + : vd(vd), type(t) + { + this->idx = SVal(); + } + UBDecl(const VarDecl *vd, SVal index) + { + this->type = UB_ARRAY; + this->vd = vd; + this->idx = index; + }; + void changeType(enum UBType t) + { + this->type = t; + }; + bool operator==(const UBDecl& ub) + { + if (this->type != ub.type) + return false; + switch(this->type) + { + case UB_VAR: + case UB_POINTER: + return this->vd == ub.vd; + case UB_ARRAY: + case UB_POINTERINDEX: + return this->vd == ub.vd && this->idx == ub.idx; + }; + return false; + }; + const VarDecl *vd; + SVal idx; + enum UBType type; + private: + }; + + enum UBAction + { + UBUSED = 1, + UBMODIFIED = 2, + UBMULTIPLE = 4, + }; + + class UBListElement + { + public: + UBListElement(std::shared_ptr& ub, enum UBAction action) + :ub(ub), action(action) + { }; + UBListElement(std::shared_ptr& ub, uint32_t action) + :ub(ub), action(action) + { }; + bool operator==(const UBDecl& elt) + { + return *ub == elt; + }; + std::shared_ptr ub; + uint32_t action; + }; + + class UBList + { + public: + UBList() = default; + void push(std::shared_ptr ub, enum UBAction action) + { + auto it = std::find(list.begin(), list.end(), *ub); + if (it != list.end()) + { + if (it->action == action && action == UBMODIFIED) + it->action = UBMULTIPLE; + else + it->action |= action; + } + else + list.push_back(UBListElement(ub, action)); + }; + void pushCallExpr(std::shared_ptr ub, uint32_t action) + { + auto it = std::find(list.begin(), list.end(), *ub); + if (it != list.end()) + { + if (action != it->action) + it->action = UBMODIFIED; + } + else + list.push_back(UBListElement(ub, action)); + } + void push(std::shared_ptr ub, uint32_t action) + { + auto it = std::find(list.begin(), list.end(), *ub); + if (it != list.end()) + { + if (it->action == action && action == UBMODIFIED) + it->action = UBMULTIPLE; + else + it->action |= action; + } + else + list.push_back(UBListElement(ub, action)); + }; + size_t size() + { + return list.size(); + }; + std::shared_ptr find_UB() + { + for (auto &elt : list) + { + if (elt.action == UBMULTIPLE || elt.action == (UBMODIFIED|UBUSED)) + return elt.ub; + } + return nullptr; + }; + std::list list; + }; + + class UnsequencedModificationChecker + : public Checker< check::PreStmt > { + + mutable std::unique_ptr BT; + + public: + void checkPreStmt(const Stmt *, CheckerContext &) const; + + private: + void BinOpUnsequencedChecker(const BinaryOperator *, CheckerContext&, UBList&) const; + void CallExprChecker(const CallExpr *, CheckerContext&, UBList&) const; + std::shared_ptr DetermineType(const Stmt*, UBList&, CheckerContext&) const; + std::shared_ptr DetermineTypeExpr(const Expr*, UBList&, CheckerContext&) const; + std::shared_ptr UnaryOperatorChecker(const UnaryOperator*, UBList&, CheckerContext&) const; + std::shared_ptr DeclarationChecker(const DeclRefExpr*, UBList&, CheckerContext&) const; + std::shared_ptr ArraySubChecker(const ArraySubscriptExpr*, UBList&, CheckerContext&) const; + const Expr* CleanExpr(const Expr*) const; + std::shared_ptr DeclStmtChecker(const DeclStmt*, UBList&, CheckerContext&) const; + void ReturnStmtChecker(const ReturnStmt* , UBList&, CheckerContext&) const; + }; + +} // end anonymous namespace + +const Expr* UnsequencedModificationChecker::CleanExpr(const Expr *E) const +{ + const Expr *tmp; + do { + tmp = E; + E = E->IgnoreParens()->IgnoreCasts(); + } while (E != tmp); + return E; +} + +std::shared_ptr +UnsequencedModificationChecker::DetermineType(const Stmt* S, UBList& Set, + CheckerContext& C) const +{ + if (!S) + return nullptr; + if (const Expr *E = dyn_cast(S)) + return this->DetermineTypeExpr(E, Set, C); + else if (const DeclStmt *DS = dyn_cast(S)) + return this->DeclStmtChecker(DS, Set, C); + else if (const ReturnStmt *RS = dyn_cast(S)) + this->ReturnStmtChecker(RS, Set, C); + return nullptr; +} + +std::shared_ptr +UnsequencedModificationChecker::DetermineTypeExpr(const Expr* E, UBList& Set, + CheckerContext& C) const +{ + if (!E) + return nullptr; + E = this->CleanExpr(E); + if (const BinaryOperator* BO = dyn_cast(E)) + this->BinOpUnsequencedChecker(BO, C, Set); + else if (const UnaryOperator* UO = dyn_cast(E)) + return this->UnaryOperatorChecker(UO, Set, C); + else if (const DeclRefExpr* DR = dyn_cast(E)) + return this->DeclarationChecker(DR, Set, C); + else if (const ArraySubscriptExpr *AS = dyn_cast(E)) + return this->ArraySubChecker(AS, Set, C); + else if (const CallExpr* CE = dyn_cast(E)) + this->CallExprChecker(CE, C, Set); + return nullptr; +} + +void UnsequencedModificationChecker::ReturnStmtChecker(const ReturnStmt* RS, UBList& Set, CheckerContext& C) const +{ + std::shared_ptr ub = this->DetermineTypeExpr(RS->getRetValue(), Set, C); + if (ub) + Set.push(ub, UBUSED); +} + +std::shared_ptr +UnsequencedModificationChecker::UnaryOperatorChecker(const UnaryOperator* UO, + UBList& Set, + CheckerContext &C) const +{ + std::shared_ptr UB = this->DetermineTypeExpr(UO->getSubExpr(), Set, C); + if (!UB) + return nullptr; + if (UO->isDecrementOp() || UO->isIncrementOp()) + Set.push(UB, UBMODIFIED); + else + { + UB->changeType(UB_POINTER); + return UB; + } + return nullptr; +} + +std::shared_ptr +UnsequencedModificationChecker::DeclStmtChecker(const DeclStmt* DS, UBList& Set, + CheckerContext& C) const +{ + if (DS->isSingleDecl()) + { + std::cout << "SingleDecl" << std::endl; + if (const VarDecl* VD = dyn_cast(DS->getSingleDecl())) + { + if (VD->hasInit()) + { + std::shared_ptr ptr = this->DetermineTypeExpr(VD->getInit(), Set, C); + if (ptr) + Set.push(ptr, UBUSED); + } + return std::make_shared(VD); + } + } + else + std::cout << "GroupDecl" << std::endl; + return nullptr; +} + +std::shared_ptr +UnsequencedModificationChecker::DeclarationChecker(const DeclRefExpr* DR, UBList& Set, + CheckerContext& C) const +{ + if (const VarDecl *VD = dyn_cast(DR->getDecl())) + return std::make_shared(VD); + return nullptr; +} + +std::shared_ptr +UnsequencedModificationChecker::ArraySubChecker(const ArraySubscriptExpr* AS, + UBList& Set, CheckerContext& C) const +{ + SVal index = C.getState()->getSVal(AS->getIdx(), C.getLocationContext()); + const DeclRefExpr *DR = dyn_cast(AS->getBase()->IgnoreImpCasts()); + if (DR) + { + const VarDecl *VD = dyn_cast(DR->getDecl()); + if (VD) + return std::make_shared(VD, index); + } + return nullptr; +} + +void +UnsequencedModificationChecker::BinOpUnsequencedChecker(const BinaryOperator* Ope, + CheckerContext &C, + UBList &Set) const +{ + + if (Ope->isAssignmentOp() || Ope->isCompoundAssignmentOp()) + { + std::shared_ptr ptr = DetermineTypeExpr(Ope->getLHS(), Set, C); + if (ptr) + Set.push(ptr, UBMODIFIED); + + ptr = DetermineTypeExpr(Ope->getRHS(), Set, C); + if (ptr) + Set.push(ptr, UBUSED); + } + else + { + std::shared_ptr ptr = DetermineTypeExpr(Ope->getLHS(), Set, C); + if (ptr) + Set.push(ptr, UBUSED); + ptr = DetermineTypeExpr(Ope->getRHS(), Set, C); + if (ptr) + Set.push(ptr, UBUSED); + if ((ptr = Set.find_UB())) + { + ExplodedNode *N = C.generateErrorNode(); + if (!N) + return; + + if (!BT) + BT.reset( + new BuiltinBug(this, "Operation leads to an undefined behaviour")); + + SmallString<256> sbuf; + llvm::raw_svector_ostream OS(sbuf); + + + OS << "Unsequenced modifications to '"; + if (ptr->type == UB_ARRAY) + { + OS << *ptr->vd << "["; + ptr->idx.dumpToStream(OS); + OS << "]"; + } + else if (ptr->type == UB_POINTER) + OS << "*" << *ptr->vd; + else + OS << *ptr->vd; + OS << "'"; + + auto report = llvm::make_unique(*BT, OS.str(), N); + + C.emitReport(std::move(report)); + } + } +} + +void +UnsequencedModificationChecker::CallExprChecker(const CallExpr* CE, + CheckerContext &C, + UBList &Set) const +{ + const Expr *const *args = CE->getArgs(); + std::shared_ptr ptr; + for (unsigned i = 0; i < CE->getNumArgs(); i++) + { + ptr = this->DetermineTypeExpr(args[i], Set, C); + if (ptr) + Set.push(ptr, UBUSED); + } + + if ((ptr = Set.find_UB())) + { + ExplodedNode *N = C.generateErrorNode(); + if (!N) + return; + + if (!BT) + BT.reset( + new BuiltinBug(this, "Operation leads to an undefined behaviour")); + + SmallString<256> sbuf; + llvm::raw_svector_ostream OS(sbuf); + + + OS << "Unsequenced modifications to '"; + if (ptr->type == UB_ARRAY) + { + OS << *ptr->vd << "["; + ptr->idx.dumpToStream(OS); + OS << "]"; + } + else if (ptr->type == UB_POINTER) + OS << "*" << *ptr->vd; + else + OS << *ptr->vd; + OS << "'"; + + auto report = llvm::make_unique(*BT, OS.str(), N); + + C.emitReport(std::move(report)); + } + + const FunctionDecl *FD = CE->getDirectCallee(); + if (FD && (FD = FD->getDefinition()) && FD->hasBody()) + { + const Stmt *Body = FD->getBody(); + const CompoundStmt *CS; + UBList Bodyset; + if (Body && (CS = dyn_cast(Body))) + { + for (auto it = CS->body_begin(); it != CS->body_end(); it++) + { + UBList Tmpset = UBList(); + std::shared_ptr ub = this->DetermineType(*it, Tmpset,C); + /* True for all non local */ + if (ub && ub->vd->hasGlobalStorage()) + Set.push(ub, UBUSED); + for (auto elt = Tmpset.list.begin(); elt != Tmpset.list.end(); elt++) + { + if (elt->ub->vd->hasGlobalStorage()) + Bodyset.pushCallExpr(elt->ub, elt->action); + } + } + } + for (auto it = Bodyset.list.begin(); it != Bodyset.list.end(); it++) + Set.push(it->ub, it->action); + } + +} + +void UnsequencedModificationChecker::checkPreStmt(const Stmt *S, + CheckerContext &C) const { + + UBList Set = UBList(); + if (const Expr* E = dyn_cast(S)) + this->DetermineTypeExpr(E, Set, C); +} + +void ento::registerUnsequencedModificationChecker(CheckerManager &mgr) { + mgr.registerChecker(); +}