contrib/llvm/tools/clang/lib/StaticAnalyzer/Checkers/TestAfterDivZeroChecker.cpp

   1 //== TestAfterDivZeroChecker.cpp - Test after division by zero checker --*--==//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This defines TestAfterDivZeroChecker, a builtin check that performs checks
  11 //  for division by zero where the division occurs before comparison with zero.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "ClangSACheckers.h"
  16 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
  17 #include "clang/StaticAnalyzer/Core/Checker.h"
  18 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
  19 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
  20 #include "llvm/ADT/FoldingSet.h"
  21
  22 using namespace clang;
  23 using namespace ento;
  24
  25 namespace {
  26
  27 class ZeroState {
  28 private:
  29   SymbolRef ZeroSymbol;
  30   unsigned BlockID;
  31   const StackFrameContext *SFC;
  32
  33 public:
  34   ZeroState(SymbolRef S, unsigned B, const StackFrameContext *SFC)
  35       : ZeroSymbol(S), BlockID(B), SFC(SFC) {}
  36
  37   const StackFrameContext *getStackFrameContext() const { return SFC; }
  38
  39   bool operator==(const ZeroState &X) const {
  40     return BlockID == X.BlockID && SFC == X.SFC && ZeroSymbol == X.ZeroSymbol;
  41   }
  42
  43   bool operator<(const ZeroState &X) const {
  44     if (BlockID != X.BlockID)
  45       return BlockID < X.BlockID;
  46     if (SFC != X.SFC)
  47       return SFC < X.SFC;
  48     return ZeroSymbol < X.ZeroSymbol;
  49   }
  50
  51   void Profile(llvm::FoldingSetNodeID &ID) const {
  52     ID.AddInteger(BlockID);
  53     ID.AddPointer(SFC);
  54     ID.AddPointer(ZeroSymbol);
  55   }
  56 };
  57
  58 class DivisionBRVisitor : public BugReporterVisitorImpl<DivisionBRVisitor> {
  59 private:
  60   SymbolRef ZeroSymbol;
  61   const StackFrameContext *SFC;
  62   bool Satisfied;
  63
  64 public:
  65   DivisionBRVisitor(SymbolRef ZeroSymbol, const StackFrameContext *SFC)
  66       : ZeroSymbol(ZeroSymbol), SFC(SFC), Satisfied(false) {}
  67
  68   void Profile(llvm::FoldingSetNodeID &ID) const override {
  69     ID.Add(ZeroSymbol);
  70     ID.Add(SFC);
  71   }
  72
  73   PathDiagnosticPiece *VisitNode(const ExplodedNode *Succ,
  74                                  const ExplodedNode *Pred,
  75                                  BugReporterContext &BRC,
  76                                  BugReport &BR) override;
  77 };
  78
  79 class TestAfterDivZeroChecker
  80     : public Checker<check::PreStmt<BinaryOperator>, check::BranchCondition,
  81                      check::EndFunction> {
  82   mutable std::unique_ptr<BuiltinBug> DivZeroBug;
  83   void reportBug(SVal Val, CheckerContext &C) const;
  84
  85 public:
  86   void checkPreStmt(const BinaryOperator *B, CheckerContext &C) const;
  87   void checkBranchCondition(const Stmt *Condition, CheckerContext &C) const;
  88   void checkEndFunction(CheckerContext &C) const;
  89   void setDivZeroMap(SVal Var, CheckerContext &C) const;
  90   bool hasDivZeroMap(SVal Var, const CheckerContext &C) const;
  91   bool isZero(SVal S, CheckerContext &C) const;
  92 };
  93 } // end anonymous namespace
  94
  95 REGISTER_SET_WITH_PROGRAMSTATE(DivZeroMap, ZeroState)
  96
  97 PathDiagnosticPiece *DivisionBRVisitor::VisitNode(const ExplodedNode *Succ,
  98                                                   const ExplodedNode *Pred,
  99                                                   BugReporterContext &BRC,
 100                                                   BugReport &BR) {
 101   if (Satisfied)
 102     return nullptr;
 103
 104   const Expr *E = nullptr;
 105
 106   if (Optional<PostStmt> P = Succ->getLocationAs<PostStmt>())
 107     if (const BinaryOperator *BO = P->getStmtAs<BinaryOperator>()) {
 108       BinaryOperator::Opcode Op = BO->getOpcode();
 109       if (Op == BO_Div || Op == BO_Rem || Op == BO_DivAssign ||
 110           Op == BO_RemAssign) {
 111         E = BO->getRHS();
 112       }
 113     }
 114
 115   if (!E)
 116     return nullptr;
 117
 118   ProgramStateRef State = Succ->getState();
 119   SVal S = State->getSVal(E, Succ->getLocationContext());
 120   if (ZeroSymbol == S.getAsSymbol() && SFC == Succ->getStackFrame()) {
 121     Satisfied = true;
 122
 123     // Construct a new PathDiagnosticPiece.
 124     ProgramPoint P = Succ->getLocation();
 125     PathDiagnosticLocation L =
 126         PathDiagnosticLocation::create(P, BRC.getSourceManager());
 127
 128     if (!L.isValid() || !L.asLocation().isValid())
 129       return nullptr;
 130
 131     return new PathDiagnosticEventPiece(
 132         L, "Division with compared value made here");
 133   }
 134
 135   return nullptr;
 136 }
 137
 138 bool TestAfterDivZeroChecker::isZero(SVal S, CheckerContext &C) const {
 139   Optional<DefinedSVal> DSV = S.getAs<DefinedSVal>();
 140
 141   if (!DSV)
 142     return false;
 143
 144   ConstraintManager &CM = C.getConstraintManager();
 145   return !CM.assume(C.getState(), *DSV, true);
 146 }
 147
 148 void TestAfterDivZeroChecker::setDivZeroMap(SVal Var, CheckerContext &C) const {
 149   SymbolRef SR = Var.getAsSymbol();
 150   if (!SR)
 151     return;
 152
 153   ProgramStateRef State = C.getState();
 154   State =
 155       State->add<DivZeroMap>(ZeroState(SR, C.getBlockID(), C.getStackFrame()));
 156   C.addTransition(State);
 157 }
 158
 159 bool TestAfterDivZeroChecker::hasDivZeroMap(SVal Var,
 160                                             const CheckerContext &C) const {
 161   SymbolRef SR = Var.getAsSymbol();
 162   if (!SR)
 163     return false;
 164
 165   ZeroState ZS(SR, C.getBlockID(), C.getStackFrame());
 166   return C.getState()->contains<DivZeroMap>(ZS);
 167 }
 168
 169 void TestAfterDivZeroChecker::reportBug(SVal Val, CheckerContext &C) const {
 170   if (ExplodedNode *N = C.generateErrorNode(C.getState())) {
 171     if (!DivZeroBug)
 172       DivZeroBug.reset(new BuiltinBug(this, "Division by zero"));
 173
 174     auto R = llvm::make_unique<BugReport>(
 175         *DivZeroBug, "Value being compared against zero has already been used "
 176                      "for division",
 177         N);
 178
 179     R->addVisitor(llvm::make_unique<DivisionBRVisitor>(Val.getAsSymbol(),
 180                                                        C.getStackFrame()));
 181     C.emitReport(std::move(R));
 182   }
 183 }
 184
 185 void TestAfterDivZeroChecker::checkEndFunction(CheckerContext &C) const {
 186   ProgramStateRef State = C.getState();
 187
 188   DivZeroMapTy DivZeroes = State->get<DivZeroMap>();
 189   if (DivZeroes.isEmpty())
 190     return;
 191
 192   DivZeroMapTy::Factory &F = State->get_context<DivZeroMap>();
 193   for (llvm::ImmutableSet<ZeroState>::iterator I = DivZeroes.begin(),
 194                                                E = DivZeroes.end();
 195        I != E; ++I) {
 196     ZeroState ZS = *I;
 197     if (ZS.getStackFrameContext() == C.getStackFrame())
 198       DivZeroes = F.remove(DivZeroes, ZS);
 199   }
 200   C.addTransition(State->set<DivZeroMap>(DivZeroes));
 201 }
 202
 203 void TestAfterDivZeroChecker::checkPreStmt(const BinaryOperator *B,
 204                                            CheckerContext &C) const {
 205   BinaryOperator::Opcode Op = B->getOpcode();
 206   if (Op == BO_Div || Op == BO_Rem || Op == BO_DivAssign ||
 207       Op == BO_RemAssign) {
 208     SVal S = C.getSVal(B->getRHS());
 209
 210     if (!isZero(S, C))
 211       setDivZeroMap(S, C);
 212   }
 213 }
 214
 215 void TestAfterDivZeroChecker::checkBranchCondition(const Stmt *Condition,
 216                                                    CheckerContext &C) const {
 217   if (const BinaryOperator *B = dyn_cast<BinaryOperator>(Condition)) {
 218     if (B->isComparisonOp()) {
 219       const IntegerLiteral *IntLiteral = dyn_cast<IntegerLiteral>(B->getRHS());
 220       bool LRHS = true;
 221       if (!IntLiteral) {
 222         IntLiteral = dyn_cast<IntegerLiteral>(B->getLHS());
 223         LRHS = false;
 224       }
 225
 226       if (!IntLiteral || IntLiteral->getValue() != 0)
 227         return;
 228
 229       SVal Val = C.getSVal(LRHS ? B->getLHS() : B->getRHS());
 230       if (hasDivZeroMap(Val, C))
 231         reportBug(Val, C);
 232     }
 233   } else if (const UnaryOperator *U = dyn_cast<UnaryOperator>(Condition)) {
 234     if (U->getOpcode() == UO_LNot) {
 235       SVal Val;
 236       if (const ImplicitCastExpr *I =
 237               dyn_cast<ImplicitCastExpr>(U->getSubExpr()))
 238         Val = C.getSVal(I->getSubExpr());
 239
 240       if (hasDivZeroMap(Val, C))
 241         reportBug(Val, C);
 242       else {
 243         Val = C.getSVal(U->getSubExpr());
 244         if (hasDivZeroMap(Val, C))
 245           reportBug(Val, C);
 246       }
 247     }
 248   } else if (const ImplicitCastExpr *IE =
 249                  dyn_cast<ImplicitCastExpr>(Condition)) {
 250     SVal Val = C.getSVal(IE->getSubExpr());
 251
 252     if (hasDivZeroMap(Val, C))
 253       reportBug(Val, C);
 254     else {
 255       SVal Val = C.getSVal(Condition);
 256
 257       if (hasDivZeroMap(Val, C))
 258         reportBug(Val, C);
 259     }
 260   }
 261 }
 262
 263 void ento::registerTestAfterDivZeroChecker(CheckerManager &mgr) {
 264   mgr.registerChecker<TestAfterDivZeroChecker>();
 265 }