clang  8.0.0svn
TestAfterDivZeroChecker.cpp
Go to the documentation of this file.
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"
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  BugReporterContext &BRC,
75  BugReport &BR) override;
76 };
77 
78 class TestAfterDivZeroChecker
79  : public Checker<check::PreStmt<BinaryOperator>, check::BranchCondition,
80  check::EndFunction> {
81  mutable std::unique_ptr<BuiltinBug> DivZeroBug;
82  void reportBug(SVal Val, CheckerContext &C) const;
83 
84 public:
85  void checkPreStmt(const BinaryOperator *B, CheckerContext &C) const;
86  void checkBranchCondition(const Stmt *Condition, CheckerContext &C) const;
87  void checkEndFunction(const ReturnStmt *RS, CheckerContext &C) const;
88  void setDivZeroMap(SVal Var, CheckerContext &C) const;
89  bool hasDivZeroMap(SVal Var, const CheckerContext &C) const;
90  bool isZero(SVal S, CheckerContext &C) const;
91 };
92 } // end anonymous namespace
93 
94 REGISTER_SET_WITH_PROGRAMSTATE(DivZeroMap, ZeroState)
95 
96 std::shared_ptr<PathDiagnosticPiece>
97 DivisionBRVisitor::VisitNode(const ExplodedNode *Succ,
98  BugReporterContext &BRC, BugReport &BR) {
99  if (Satisfied)
100  return nullptr;
101 
102  const Expr *E = nullptr;
103 
104  if (Optional<PostStmt> P = Succ->getLocationAs<PostStmt>())
105  if (const BinaryOperator *BO = P->getStmtAs<BinaryOperator>()) {
106  BinaryOperator::Opcode Op = BO->getOpcode();
107  if (Op == BO_Div || Op == BO_Rem || Op == BO_DivAssign ||
108  Op == BO_RemAssign) {
109  E = BO->getRHS();
110  }
111  }
112 
113  if (!E)
114  return nullptr;
115 
116  SVal S = Succ->getSVal(E);
117  if (ZeroSymbol == S.getAsSymbol() && SFC == Succ->getStackFrame()) {
118  Satisfied = true;
119 
120  // Construct a new PathDiagnosticPiece.
121  ProgramPoint P = Succ->getLocation();
122  PathDiagnosticLocation L =
123  PathDiagnosticLocation::create(P, BRC.getSourceManager());
124 
125  if (!L.isValid() || !L.asLocation().isValid())
126  return nullptr;
127 
128  return std::make_shared<PathDiagnosticEventPiece>(
129  L, "Division with compared value made here");
130  }
131 
132  return nullptr;
133 }
134 
135 bool TestAfterDivZeroChecker::isZero(SVal S, CheckerContext &C) const {
136  Optional<DefinedSVal> DSV = S.getAs<DefinedSVal>();
137 
138  if (!DSV)
139  return false;
140 
141  ConstraintManager &CM = C.getConstraintManager();
142  return !CM.assume(C.getState(), *DSV, true);
143 }
144 
145 void TestAfterDivZeroChecker::setDivZeroMap(SVal Var, CheckerContext &C) const {
146  SymbolRef SR = Var.getAsSymbol();
147  if (!SR)
148  return;
149 
150  ProgramStateRef State = C.getState();
151  State =
152  State->add<DivZeroMap>(ZeroState(SR, C.getBlockID(), C.getStackFrame()));
153  C.addTransition(State);
154 }
155 
156 bool TestAfterDivZeroChecker::hasDivZeroMap(SVal Var,
157  const CheckerContext &C) const {
158  SymbolRef SR = Var.getAsSymbol();
159  if (!SR)
160  return false;
161 
162  ZeroState ZS(SR, C.getBlockID(), C.getStackFrame());
163  return C.getState()->contains<DivZeroMap>(ZS);
164 }
165 
166 void TestAfterDivZeroChecker::reportBug(SVal Val, CheckerContext &C) const {
167  if (ExplodedNode *N = C.generateErrorNode(C.getState())) {
168  if (!DivZeroBug)
169  DivZeroBug.reset(new BuiltinBug(this, "Division by zero"));
170 
171  auto R = llvm::make_unique<BugReport>(
172  *DivZeroBug, "Value being compared against zero has already been used "
173  "for division",
174  N);
175 
176  R->addVisitor(llvm::make_unique<DivisionBRVisitor>(Val.getAsSymbol(),
177  C.getStackFrame()));
178  C.emitReport(std::move(R));
179  }
180 }
181 
182 void TestAfterDivZeroChecker::checkEndFunction(const ReturnStmt *,
183  CheckerContext &C) const {
184  ProgramStateRef State = C.getState();
185 
186  DivZeroMapTy DivZeroes = State->get<DivZeroMap>();
187  if (DivZeroes.isEmpty())
188  return;
189 
190  DivZeroMapTy::Factory &F = State->get_context<DivZeroMap>();
191  for (llvm::ImmutableSet<ZeroState>::iterator I = DivZeroes.begin(),
192  E = DivZeroes.end();
193  I != E; ++I) {
194  ZeroState ZS = *I;
195  if (ZS.getStackFrameContext() == C.getStackFrame())
196  DivZeroes = F.remove(DivZeroes, ZS);
197  }
198  C.addTransition(State->set<DivZeroMap>(DivZeroes));
199 }
200 
201 void TestAfterDivZeroChecker::checkPreStmt(const BinaryOperator *B,
202  CheckerContext &C) const {
204  if (Op == BO_Div || Op == BO_Rem || Op == BO_DivAssign ||
205  Op == BO_RemAssign) {
206  SVal S = C.getSVal(B->getRHS());
207 
208  if (!isZero(S, C))
209  setDivZeroMap(S, C);
210  }
211 }
212 
213 void TestAfterDivZeroChecker::checkBranchCondition(const Stmt *Condition,
214  CheckerContext &C) const {
215  if (const BinaryOperator *B = dyn_cast<BinaryOperator>(Condition)) {
216  if (B->isComparisonOp()) {
217  const IntegerLiteral *IntLiteral = dyn_cast<IntegerLiteral>(B->getRHS());
218  bool LRHS = true;
219  if (!IntLiteral) {
220  IntLiteral = dyn_cast<IntegerLiteral>(B->getLHS());
221  LRHS = false;
222  }
223 
224  if (!IntLiteral || IntLiteral->getValue() != 0)
225  return;
226 
227  SVal Val = C.getSVal(LRHS ? B->getLHS() : B->getRHS());
228  if (hasDivZeroMap(Val, C))
229  reportBug(Val, C);
230  }
231  } else if (const UnaryOperator *U = dyn_cast<UnaryOperator>(Condition)) {
232  if (U->getOpcode() == UO_LNot) {
233  SVal Val;
234  if (const ImplicitCastExpr *I =
235  dyn_cast<ImplicitCastExpr>(U->getSubExpr()))
236  Val = C.getSVal(I->getSubExpr());
237 
238  if (hasDivZeroMap(Val, C))
239  reportBug(Val, C);
240  else {
241  Val = C.getSVal(U->getSubExpr());
242  if (hasDivZeroMap(Val, C))
243  reportBug(Val, C);
244  }
245  }
246  } else if (const ImplicitCastExpr *IE =
247  dyn_cast<ImplicitCastExpr>(Condition)) {
248  SVal Val = C.getSVal(IE->getSubExpr());
249 
250  if (hasDivZeroMap(Val, C))
251  reportBug(Val, C);
252  else {
253  SVal Val = C.getSVal(Condition);
254 
255  if (hasDivZeroMap(Val, C))
256  reportBug(Val, C);
257  }
258  }
259 }
260 
261 void ento::registerTestAfterDivZeroChecker(CheckerManager &mgr) {
262  mgr.registerChecker<TestAfterDivZeroChecker>();
263 }
bool operator==(CanQual< T > x, CanQual< U > y)
const SymExpr * SymbolRef
Stmt - This represents one statement.
Definition: Stmt.h:66
IntrusiveRefCntPtr< const ProgramState > ProgramStateRef
Opcode getOpcode() const
Definition: Expr.h:3283
StringRef P
bool isZero(ProgramStateRef State, const NonLoc &Val)
LineState State
BinaryOperatorKind
A builtin binary operation expression such as "x + y" or "x <= y".
Definition: Expr.h:3248
static PathDiagnosticLocation create(const Decl *D, const SourceManager &SM)
Create a location corresponding to the given declaration.
This represents one expression.
Definition: Expr.h:106
ReturnStmt - This represents a return, optionally of an expression: return; return 4;...
Definition: Stmt.h:2226
UnaryOperator - This represents the unary-expression&#39;s (except sizeof and alignof), the postinc/postdec operators from postfix-expression, and various extensions.
Definition: Expr.h:1907
#define false
Definition: stdbool.h:33
ImplicitCastExpr - Allows us to explicitly represent implicit type conversions, which have no direct ...
Definition: Expr.h:3066
bool operator<(DeclarationName LHS, DeclarationName RHS)
Ordering on two declaration names.
Expr * getLHS() const
Definition: Expr.h:3288
#define REGISTER_SET_WITH_PROGRAMSTATE(Name, Elem)
Declares an immutable set of type NameTy, suitable for placement into the ProgramState.
Dataflow Directional Tag Classes.
llvm::APInt getValue() const
Definition: Expr.h:1303
const StackFrameContext * getStackFrame() const
X
Add a minimal nested name specifier fixit hint to allow lookup of a tag name from an outer enclosing ...
Definition: SemaDecl.cpp:13961
Expr * getRHS() const
Definition: Expr.h:3290
static bool isComparisonOp(Opcode Opc)
Definition: Expr.h:3338