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 BugReporterVisitor {
  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   std::shared_ptr<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(const ReturnStmt *RS, 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 std::shared_ptr<PathDiagnosticPiece>
  98 DivisionBRVisitor::VisitNode(const ExplodedNode *Succ, const ExplodedNode *Pred,
  99                              BugReporterContext &BRC, BugReport &BR) {
 100   if (Satisfied)
 101     return nullptr;
 102
 103   const Expr *E = nullptr;
 104
 105   if (Optional<PostStmt> P = Succ->getLocationAs<PostStmt>())
 106     if (const BinaryOperator *BO = P->getStmtAs<BinaryOperator>()) {
 107       BinaryOperator::Opcode Op = BO->getOpcode();
 108       if (Op == BO_Div || Op == BO_Rem || Op == BO_DivAssign ||
 109           Op == BO_RemAssign) {
 110         E = BO->getRHS();
 111       }
 112     }
 113
 114   if (!E)
 115     return nullptr;
 116
 117   SVal S = Succ->getSVal(E);
 118   if (ZeroSymbol == S.getAsSymbol() && SFC == Succ->getStackFrame()) {
 119     Satisfied = true;
 120
 121     // Construct a new PathDiagnosticPiece.
 122     ProgramPoint P = Succ->getLocation();
 123     PathDiagnosticLocation L =
 124         PathDiagnosticLocation::create(P, BRC.getSourceManager());
 125
 126     if (!L.isValid() || !L.asLocation().isValid())
 127       return nullptr;
 128
 129     return std::make_shared<PathDiagnosticEventPiece>(
 130         L, "Division with compared value made here");
 131   }
 132
 133   return nullptr;
 134 }
 135
 136 bool TestAfterDivZeroChecker::isZero(SVal S, CheckerContext &C) const {
 137   Optional<DefinedSVal> DSV = S.getAs<DefinedSVal>();
 138
 139   if (!DSV)
 140     return false;
 141
 142   ConstraintManager &CM = C.getConstraintManager();
 143   return !CM.assume(C.getState(), *DSV, true);
 144 }
 145
 146 void TestAfterDivZeroChecker::setDivZeroMap(SVal Var, CheckerContext &C) const {
 147   SymbolRef SR = Var.getAsSymbol();
 148   if (!SR)
 149     return;
 150
 151   ProgramStateRef State = C.getState();
 152   State =
 153       State->add<DivZeroMap>(ZeroState(SR, C.getBlockID(), C.getStackFrame()));
 154   C.addTransition(State);
 155 }
 156
 157 bool TestAfterDivZeroChecker::hasDivZeroMap(SVal Var,
 158                                             const CheckerContext &C) const {
 159   SymbolRef SR = Var.getAsSymbol();
 160   if (!SR)
 161     return false;
 162
 163   ZeroState ZS(SR, C.getBlockID(), C.getStackFrame());
 164   return C.getState()->contains<DivZeroMap>(ZS);
 165 }
 166
 167 void TestAfterDivZeroChecker::reportBug(SVal Val, CheckerContext &C) const {
 168   if (ExplodedNode *N = C.generateErrorNode(C.getState())) {
 169     if (!DivZeroBug)
 170       DivZeroBug.reset(new BuiltinBug(this, "Division by zero"));
 171
 172     auto R = llvm::make_unique<BugReport>(
 173         *DivZeroBug, "Value being compared against zero has already been used "
 174                      "for division",
 175         N);
 176
 177     R->addVisitor(llvm::make_unique<DivisionBRVisitor>(Val.getAsSymbol(),
 178                                                        C.getStackFrame()));
 179     C.emitReport(std::move(R));
 180   }
 181 }
 182
 183 void TestAfterDivZeroChecker::checkEndFunction(const ReturnStmt *RS,
 184                                                CheckerContext &C) const {
 185   ProgramStateRef State = C.getState();
 186
 187   DivZeroMapTy DivZeroes = State->get<DivZeroMap>();
 188   if (DivZeroes.isEmpty())
 189     return;
 190
 191   DivZeroMapTy::Factory &F = State->get_context<DivZeroMap>();
 192   for (llvm::ImmutableSet<ZeroState>::iterator I = DivZeroes.begin(),
 193                                                E = DivZeroes.end();
 194        I != E; ++I) {
 195     ZeroState ZS = *I;
 196     if (ZS.getStackFrameContext() == C.getStackFrame())
 197       DivZeroes = F.remove(DivZeroes, ZS);
 198   }
 199   C.addTransition(State->set<DivZeroMap>(DivZeroes));
 200 }
 201
 202 void TestAfterDivZeroChecker::checkPreStmt(const BinaryOperator *B,
 203                                            CheckerContext &C) const {
 204   BinaryOperator::Opcode Op = B->getOpcode();
 205   if (Op == BO_Div || Op == BO_Rem || Op == BO_DivAssign ||
 206       Op == BO_RemAssign) {
 207     SVal S = C.getSVal(B->getRHS());
 208
 209     if (!isZero(S, C))
 210       setDivZeroMap(S, C);
 211   }
 212 }
 213
 214 void TestAfterDivZeroChecker::checkBranchCondition(const Stmt *Condition,
 215                                                    CheckerContext &C) const {
 216   if (const BinaryOperator *B = dyn_cast<BinaryOperator>(Condition)) {
 217     if (B->isComparisonOp()) {
 218       const IntegerLiteral *IntLiteral = dyn_cast<IntegerLiteral>(B->getRHS());
 219       bool LRHS = true;
 220       if (!IntLiteral) {
 221         IntLiteral = dyn_cast<IntegerLiteral>(B->getLHS());
 222         LRHS = false;
 223       }
 224
 225       if (!IntLiteral || IntLiteral->getValue() != 0)
 226         return;
 227
 228       SVal Val = C.getSVal(LRHS ? B->getLHS() : B->getRHS());
 229       if (hasDivZeroMap(Val, C))
 230         reportBug(Val, C);
 231     }
 232   } else if (const UnaryOperator *U = dyn_cast<UnaryOperator>(Condition)) {
 233     if (U->getOpcode() == UO_LNot) {
 234       SVal Val;
 235       if (const ImplicitCastExpr *I =
 236               dyn_cast<ImplicitCastExpr>(U->getSubExpr()))
 237         Val = C.getSVal(I->getSubExpr());
 238
 239       if (hasDivZeroMap(Val, C))
 240         reportBug(Val, C);
 241       else {
 242         Val = C.getSVal(U->getSubExpr());
 243         if (hasDivZeroMap(Val, C))
 244           reportBug(Val, C);
 245       }
 246     }
 247   } else if (const ImplicitCastExpr *IE =
 248                  dyn_cast<ImplicitCastExpr>(Condition)) {
 249     SVal Val = C.getSVal(IE->getSubExpr());
 250
 251     if (hasDivZeroMap(Val, C))
 252       reportBug(Val, C);
 253     else {
 254       SVal Val = C.getSVal(Condition);
 255
 256       if (hasDivZeroMap(Val, C))
 257         reportBug(Val, C);
 258     }
 259   }
 260 }
 261
 262 void ento::registerTestAfterDivZeroChecker(CheckerManager &mgr) {
 263   mgr.registerChecker<TestAfterDivZeroChecker>();
 264 }