clang  6.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 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  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(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 
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  ProgramStateRef State = Succ->getState();
118  SVal S = State->getSVal(E, Succ->getLocationContext());
119  if (ZeroSymbol == S.getAsSymbol() && SFC == Succ->getStackFrame()) {
120  Satisfied = true;
121 
122  // Construct a new PathDiagnosticPiece.
123  ProgramPoint P = Succ->getLocation();
126 
127  if (!L.isValid() || !L.asLocation().isValid())
128  return nullptr;
129 
130  return std::make_shared<PathDiagnosticEventPiece>(
131  L, "Division with compared value made here");
132  }
133 
134  return nullptr;
135 }
136 
137 bool TestAfterDivZeroChecker::isZero(SVal S, CheckerContext &C) const {
139 
140  if (!DSV)
141  return false;
142 
144  return !CM.assume(C.getState(), *DSV, true);
145 }
146 
147 void TestAfterDivZeroChecker::setDivZeroMap(SVal Var, CheckerContext &C) const {
148  SymbolRef SR = Var.getAsSymbol();
149  if (!SR)
150  return;
151 
152  ProgramStateRef State = C.getState();
153  State =
154  State->add<DivZeroMap>(ZeroState(SR, C.getBlockID(), C.getStackFrame()));
155  C.addTransition(State);
156 }
157 
158 bool TestAfterDivZeroChecker::hasDivZeroMap(SVal Var,
159  const CheckerContext &C) const {
160  SymbolRef SR = Var.getAsSymbol();
161  if (!SR)
162  return false;
163 
164  ZeroState ZS(SR, C.getBlockID(), C.getStackFrame());
165  return C.getState()->contains<DivZeroMap>(ZS);
166 }
167 
168 void TestAfterDivZeroChecker::reportBug(SVal Val, CheckerContext &C) const {
169  if (ExplodedNode *N = C.generateErrorNode(C.getState())) {
170  if (!DivZeroBug)
171  DivZeroBug.reset(new BuiltinBug(this, "Division by zero"));
172 
173  auto R = llvm::make_unique<BugReport>(
174  *DivZeroBug, "Value being compared against zero has already been used "
175  "for division",
176  N);
177 
178  R->addVisitor(llvm::make_unique<DivisionBRVisitor>(Val.getAsSymbol(),
179  C.getStackFrame()));
180  C.emitReport(std::move(R));
181  }
182 }
183 
184 void TestAfterDivZeroChecker::checkEndFunction(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 {
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 }
virtual ProgramStateRef assume(ProgramStateRef state, DefinedSVal Cond, bool Assumption)=0
ExplodedNode * generateErrorNode(ProgramStateRef State=nullptr, const ProgramPointTag *Tag=nullptr)
Generate a transition to a node that will be used to report an error.
bool operator==(CanQual< T > x, CanQual< U > y)
Stmt - This represents one statement.
Definition: Stmt.h:66
ExplodedNode * addTransition(ProgramStateRef State=nullptr, const ProgramPointTag *Tag=nullptr)
Generates a new transition in the program state graph (ExplodedGraph).
Opcode getOpcode() const
Definition: Expr.h:3026
StringRef P
const ProgramStateRef & getState() const
SVal getSVal(const Stmt *S) const
Get the value of arbitrary expressions at this point in the path.
#define REGISTER_SET_WITH_PROGRAMSTATE(Name, Elem)
Declares an immutable set of type NameTy, suitable for placement into the ProgramState.
Symbolic value.
Definition: SymExpr.h:29
LineState State
This class provides a convenience implementation for clone() using the Curiously-Recurring Template P...
Optional< T > getLocationAs() const LLVM_LVALUE_FUNCTION
BinaryOperatorKind
const LocationContext * getLocationContext() const
A builtin binary operation expression such as "x + y" or "x <= y".
Definition: Expr.h:2985
static PathDiagnosticLocation create(const Decl *D, const SourceManager &SM)
Create a location corresponding to the given declaration.
SymbolRef getAsSymbol(bool IncludeBaseRegions=false) const
If this SVal wraps a symbol return that SymbolRef.
Definition: SVals.cpp:116
Expr - This represents one expression.
Definition: Expr.h:106
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:1717
Optional< T > getAs() const
Convert to the specified SVal type, returning None if this SVal is not of the desired type...
Definition: SVals.h:100
ConstraintManager & getConstraintManager()
void emitReport(std::unique_ptr< BugReport > R)
Emit the diagnostics report.
#define false
Definition: stdbool.h:33
CHECKER * registerChecker()
Used to register checkers.
ProgramPoint getLocation() const
getLocation - Returns the edge associated with the given node.
SVal - This represents a symbolic expression, which can be either an L-value or an R-value...
Definition: SVals.h:63
ImplicitCastExpr - Allows us to explicitly represent implicit type conversions, which have no direct ...
Definition: Expr.h:2822
bool operator<(DeclarationName LHS, DeclarationName RHS)
Ordering on two declaration names.
Expr * getLHS() const
Definition: Expr.h:3029
unsigned getBlockID() const
Get the blockID.
Dataflow Directional Tag Classes.
bool isValid() const
Return true if this is a valid SourceLocation object.
llvm::APInt getValue() const
Definition: Expr.h:1279
const StackFrameContext * getStackFrame() const
const ProgramStateRef & getState() const
X
Add a minimal nested name specifier fixit hint to allow lookup of a tag name from an outer enclosing ...
Definition: SemaDecl.cpp:13010
Expr * getRHS() const
Definition: Expr.h:3031
const StackFrameContext * getStackFrame() const
This class provides an interface through which checkers can create individual bug reports...
Definition: BugReporter.h:55
static bool isComparisonOp(Opcode Opc)
Definition: Expr.h:3075
SourceManager & getSourceManager()
Definition: BugReporter.h:565