clang  14.0.0git
IteratorRangeChecker.cpp
Go to the documentation of this file.
1 //===-- IteratorRangeChecker.cpp ----------------------------------*- C++ -*--//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // Defines a checker for dereference of the past-the-end iterator and
10 // out-of-range increments and decrements.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
15 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
16 #include "clang/StaticAnalyzer/Core/Checker.h"
17 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
18 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
19 
20 
21 #include "Iterator.h"
22 
23 using namespace clang;
24 using namespace ento;
25 using namespace iterator;
26 
27 namespace {
28 
29 class IteratorRangeChecker
30  : public Checker<check::PreCall, check::PreStmt<UnaryOperator>,
31  check::PreStmt<BinaryOperator>,
32  check::PreStmt<ArraySubscriptExpr>,
33  check::PreStmt<MemberExpr>> {
34 
35  std::unique_ptr<BugType> OutOfRangeBugType;
36 
37  void verifyDereference(CheckerContext &C, SVal Val) const;
38  void verifyIncrement(CheckerContext &C, SVal Iter) const;
39  void verifyDecrement(CheckerContext &C, SVal Iter) const;
40  void verifyRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op,
41  SVal LHS, SVal RHS) const;
42  void verifyAdvance(CheckerContext &C, SVal LHS, SVal RHS) const;
43  void verifyPrev(CheckerContext &C, SVal LHS, SVal RHS) const;
44  void verifyNext(CheckerContext &C, SVal LHS, SVal RHS) const;
45  void reportBug(const StringRef &Message, SVal Val, CheckerContext &C,
46  ExplodedNode *ErrNode) const;
47 
48 public:
49  IteratorRangeChecker();
50 
51  void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
52  void checkPreStmt(const UnaryOperator *UO, CheckerContext &C) const;
53  void checkPreStmt(const BinaryOperator *BO, CheckerContext &C) const;
54  void checkPreStmt(const ArraySubscriptExpr *ASE, CheckerContext &C) const;
55  void checkPreStmt(const MemberExpr *ME, CheckerContext &C) const;
56 
57  using AdvanceFn = void (IteratorRangeChecker::*)(CheckerContext &, SVal,
58  SVal) const;
59 
60  CallDescriptionMap<AdvanceFn> AdvanceFunctions = {
61  {{{"std", "advance"}, 2}, &IteratorRangeChecker::verifyAdvance},
62  {{{"std", "prev"}, 2}, &IteratorRangeChecker::verifyPrev},
63  {{{"std", "next"}, 2}, &IteratorRangeChecker::verifyNext},
64  };
65 };
66 
67 bool isPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos);
68 bool isAheadOfRange(ProgramStateRef State, const IteratorPosition &Pos);
69 bool isBehindPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos);
70 bool isZero(ProgramStateRef State, const NonLoc &Val);
71 
72 } //namespace
73 
74 IteratorRangeChecker::IteratorRangeChecker() {
75  OutOfRangeBugType.reset(
76  new BugType(this, "Iterator out of range", "Misuse of STL APIs"));
77 }
78 
79 void IteratorRangeChecker::checkPreCall(const CallEvent &Call,
80  CheckerContext &C) const {
81  // Check for out of range access
82  const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
83  if (!Func)
84  return;
85 
86  if (Func->isOverloadedOperator()) {
87  if (isIncrementOperator(Func->getOverloadedOperator())) {
88  // Check for out-of-range incrementions
89  if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
90  verifyIncrement(C, InstCall->getCXXThisVal());
91  } else {
92  if (Call.getNumArgs() >= 1) {
93  verifyIncrement(C, Call.getArgSVal(0));
94  }
95  }
96  } else if (isDecrementOperator(Func->getOverloadedOperator())) {
97  // Check for out-of-range decrementions
98  if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
99  verifyDecrement(C, InstCall->getCXXThisVal());
100  } else {
101  if (Call.getNumArgs() >= 1) {
102  verifyDecrement(C, Call.getArgSVal(0));
103  }
104  }
105  } else if (isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) {
106  if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
107  // Check for out-of-range incrementions and decrementions
108  if (Call.getNumArgs() >= 1 &&
109  Call.getArgExpr(0)->getType()->isIntegralOrEnumerationType()) {
110  verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(),
111  InstCall->getCXXThisVal(),
112  Call.getArgSVal(0));
113  }
114  } else {
115  if (Call.getNumArgs() >= 2 &&
116  Call.getArgExpr(1)->getType()->isIntegralOrEnumerationType()) {
117  verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(),
118  Call.getArgSVal(0), Call.getArgSVal(1));
119  }
120  }
121  } else if (isDereferenceOperator(Func->getOverloadedOperator())) {
122  // Check for dereference of out-of-range iterators
123  if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
124  verifyDereference(C, InstCall->getCXXThisVal());
125  } else {
126  verifyDereference(C, Call.getArgSVal(0));
127  }
128  }
129  } else {
130  const AdvanceFn *Verifier = AdvanceFunctions.lookup(Call);
131  if (Verifier) {
132  if (Call.getNumArgs() > 1) {
133  (this->**Verifier)(C, Call.getArgSVal(0), Call.getArgSVal(1));
134  } else {
135  auto &BVF = C.getSValBuilder().getBasicValueFactory();
136  (this->**Verifier)(
137  C, Call.getArgSVal(0),
138  nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
139  }
140  }
141  }
142 }
143 
144 void IteratorRangeChecker::checkPreStmt(const UnaryOperator *UO,
145  CheckerContext &C) const {
146  if (isa<CXXThisExpr>(UO->getSubExpr()))
147  return;
148 
149  ProgramStateRef State = C.getState();
150  UnaryOperatorKind OK = UO->getOpcode();
151  SVal SubVal = State->getSVal(UO->getSubExpr(), C.getLocationContext());
152 
153  if (isDereferenceOperator(OK)) {
154  verifyDereference(C, SubVal);
155  } else if (isIncrementOperator(OK)) {
156  verifyIncrement(C, SubVal);
157  } else if (isDecrementOperator(OK)) {
158  verifyDecrement(C, SubVal);
159  }
160 }
161 
162 void IteratorRangeChecker::checkPreStmt(const BinaryOperator *BO,
163  CheckerContext &C) const {
164  ProgramStateRef State = C.getState();
165  BinaryOperatorKind OK = BO->getOpcode();
166  SVal LVal = State->getSVal(BO->getLHS(), C.getLocationContext());
167 
168  if (isDereferenceOperator(OK)) {
169  verifyDereference(C, LVal);
170  } else if (isRandomIncrOrDecrOperator(OK)) {
171  SVal RVal = State->getSVal(BO->getRHS(), C.getLocationContext());
172  if (!BO->getRHS()->getType()->isIntegralOrEnumerationType())
173  return;
174  verifyRandomIncrOrDecr(C, BinaryOperator::getOverloadedOperator(OK), LVal,
175  RVal);
176  }
177 }
178 
179 void IteratorRangeChecker::checkPreStmt(const ArraySubscriptExpr *ASE,
180  CheckerContext &C) const {
181  ProgramStateRef State = C.getState();
182  SVal LVal = State->getSVal(ASE->getLHS(), C.getLocationContext());
183  verifyDereference(C, LVal);
184 }
185 
186 void IteratorRangeChecker::checkPreStmt(const MemberExpr *ME,
187  CheckerContext &C) const {
188  if (!ME->isArrow() || ME->isImplicitAccess())
189  return;
190 
191  ProgramStateRef State = C.getState();
192  SVal BaseVal = State->getSVal(ME->getBase(), C.getLocationContext());
193  verifyDereference(C, BaseVal);
194 }
195 
196 void IteratorRangeChecker::verifyDereference(CheckerContext &C,
197  SVal Val) const {
198  auto State = C.getState();
199  const auto *Pos = getIteratorPosition(State, Val);
200  if (Pos && isPastTheEnd(State, *Pos)) {
201  auto *N = C.generateErrorNode(State);
202  if (!N)
203  return;
204  reportBug("Past-the-end iterator dereferenced.", Val, C, N);
205  return;
206  }
207 }
208 
209 void IteratorRangeChecker::verifyIncrement(CheckerContext &C, SVal Iter) const {
210  auto &BVF = C.getSValBuilder().getBasicValueFactory();
211  verifyRandomIncrOrDecr(C, OO_Plus, Iter,
212  nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
213 }
214 
215 void IteratorRangeChecker::verifyDecrement(CheckerContext &C, SVal Iter) const {
216  auto &BVF = C.getSValBuilder().getBasicValueFactory();
217  verifyRandomIncrOrDecr(C, OO_Minus, Iter,
218  nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
219 }
220 
221 void IteratorRangeChecker::verifyRandomIncrOrDecr(CheckerContext &C,
222  OverloadedOperatorKind Op,
223  SVal LHS, SVal RHS) const {
224  auto State = C.getState();
225 
226  auto Value = RHS;
227  if (auto ValAsLoc = RHS.getAs<Loc>()) {
228  Value = State->getRawSVal(*ValAsLoc);
229  }
230 
231  if (Value.isUnknownOrUndef())
232  return;
233 
234  // Incremention or decremention by 0 is never a bug.
235  if (isZero(State, Value.castAs<NonLoc>()))
236  return;
237 
238  // The result may be the past-end iterator of the container, but any other
239  // out of range position is undefined behaviour
240  auto StateAfter = advancePosition(State, LHS, Op, Value);
241  if (!StateAfter)
242  return;
243 
244  const auto *PosAfter = getIteratorPosition(StateAfter, LHS);
245  assert(PosAfter &&
246  "Iterator should have position after successful advancement");
247  if (isAheadOfRange(State, *PosAfter)) {
248  auto *N = C.generateErrorNode(State);
249  if (!N)
250  return;
251  reportBug("Iterator decremented ahead of its valid range.", LHS,
252  C, N);
253  }
254  if (isBehindPastTheEnd(State, *PosAfter)) {
255  auto *N = C.generateErrorNode(State);
256  if (!N)
257  return;
258  reportBug("Iterator incremented behind the past-the-end "
259  "iterator.", LHS, C, N);
260  }
261 }
262 
263 void IteratorRangeChecker::verifyAdvance(CheckerContext &C, SVal LHS,
264  SVal RHS) const {
265  verifyRandomIncrOrDecr(C, OO_PlusEqual, LHS, RHS);
266 }
267 
268 void IteratorRangeChecker::verifyPrev(CheckerContext &C, SVal LHS,
269  SVal RHS) const {
270  verifyRandomIncrOrDecr(C, OO_Minus, LHS, RHS);
271 }
272 
273 void IteratorRangeChecker::verifyNext(CheckerContext &C, SVal LHS,
274  SVal RHS) const {
275  verifyRandomIncrOrDecr(C, OO_Plus, LHS, RHS);
276 }
277 
278 void IteratorRangeChecker::reportBug(const StringRef &Message, SVal Val,
279  CheckerContext &C,
280  ExplodedNode *ErrNode) const {
281  auto R = std::make_unique<PathSensitiveBugReport>(*OutOfRangeBugType, Message,
282  ErrNode);
283 
284  const auto *Pos = getIteratorPosition(C.getState(), Val);
285  assert(Pos && "Iterator without known position cannot be out-of-range.");
286 
287  R->markInteresting(Val);
288  R->markInteresting(Pos->getContainer());
289  C.emitReport(std::move(R));
290 }
291 
292 namespace {
293 
294 bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
295 bool isGreater(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
296 bool isEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
297 
298 bool isZero(ProgramStateRef State, const NonLoc &Val) {
299  auto &BVF = State->getBasicVals();
300  return compare(State, Val,
301  nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(0))),
302  BO_EQ);
303 }
304 
305 bool isPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos) {
306  const auto *Cont = Pos.getContainer();
307  const auto *CData = getContainerData(State, Cont);
308  if (!CData)
309  return false;
310 
311  const auto End = CData->getEnd();
312  if (End) {
313  if (isEqual(State, Pos.getOffset(), End)) {
314  return true;
315  }
316  }
317 
318  return false;
319 }
320 
321 bool isAheadOfRange(ProgramStateRef State, const IteratorPosition &Pos) {
322  const auto *Cont = Pos.getContainer();
323  const auto *CData = getContainerData(State, Cont);
324  if (!CData)
325  return false;
326 
327  const auto Beg = CData->getBegin();
328  if (Beg) {
329  if (isLess(State, Pos.getOffset(), Beg)) {
330  return true;
331  }
332  }
333 
334  return false;
335 }
336 
337 bool isBehindPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos) {
338  const auto *Cont = Pos.getContainer();
339  const auto *CData = getContainerData(State, Cont);
340  if (!CData)
341  return false;
342 
343  const auto End = CData->getEnd();
344  if (End) {
345  if (isGreater(State, Pos.getOffset(), End)) {
346  return true;
347  }
348  }
349 
350  return false;
351 }
352 
353 bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
354  return compare(State, Sym1, Sym2, BO_LT);
355 }
356 
357 bool isGreater(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
358  return compare(State, Sym1, Sym2, BO_GT);
359 }
360 
361 bool isEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
362  return compare(State, Sym1, Sym2, BO_EQ);
363 }
364 
365 } // namespace
366 
367 void ento::registerIteratorRangeChecker(CheckerManager &mgr) {
368  mgr.registerChecker<IteratorRangeChecker>();
369 }
370 
371 bool ento::shouldRegisterIteratorRangeChecker(const CheckerManager &mgr) {
372  return true;
373 }
clang::ento::ProgramStateRef
IntrusiveRefCntPtr< const ProgramState > ProgramStateRef
Definition: ProgramState_Fwd.h:37
AttributeLangSupport::C
@ C
Definition: SemaDeclAttr.cpp:54
clang::ento::SymbolRef
const SymExpr * SymbolRef
Definition: SymExpr.h:110
clang::MemberExpr::isImplicitAccess
bool isImplicitAccess() const
Determine whether the base of this explicit is implicit.
Definition: Expr.h:3360
clang::UnaryOperator
UnaryOperator - This represents the unary-expression's (except sizeof and alignof),...
Definition: Expr.h:2157
clang::index::SymbolRole::Call
@ Call
clang::BinaryOperator::getOpcode
Opcode getOpcode() const
Definition: Expr.h:3847
End
SourceLocation End
Definition: USRLocFinder.cpp:167
CallEvent.h
BuiltinCheckerRegistration.h
clang::BinaryOperator
A builtin binary operation expression such as "x + y" or "x <= y".
Definition: Expr.h:3803
clang::MemberExpr::isArrow
bool isArrow() const
Definition: Expr.h:3346
clang::ento::iterator::getIteratorPosition
const IteratorPosition * getIteratorPosition(ProgramStateRef State, const SVal &Val)
Definition: Iterator.cpp:184
clang::ento::iterator::isIncrementOperator
bool isIncrementOperator(OverloadedOperatorKind OK)
Definition: Iterator.cpp:153
clang::ento::iterator::isDereferenceOperator
bool isDereferenceOperator(OverloadedOperatorKind OK)
Definition: Iterator.cpp:140
clang::ArraySubscriptExpr::getLHS
Expr * getLHS()
An array access can be written A[4] or 4[A] (both are equivalent).
Definition: Expr.h:2668
clang::OverloadedOperatorKind
OverloadedOperatorKind
Enumeration specifying the different kinds of C++ overloaded operators.
Definition: OperatorKinds.h:21
clang::ento::iterator::getContainerData
const ContainerData * getContainerData(ProgramStateRef State, const MemRegion *Cont)
Definition: Iterator.cpp:179
clang::MemberExpr::getBase
Expr * getBase() const
Definition: Expr.h:3239
BugType.h
clang::BinaryOperator::getLHS
Expr * getLHS() const
Definition: Expr.h:3852
Iterator.h
Value
Value
Definition: UninitializedValues.cpp:102
clang::ArraySubscriptExpr
ArraySubscriptExpr - [C99 6.5.2.1] Array Subscripting.
Definition: Expr.h:2639
State
LineState State
Definition: UnwrappedLineFormatter.cpp:986
clang::UnaryOperatorKind
UnaryOperatorKind
Definition: OperationKinds.h:30
clang::BinaryOperatorKind
BinaryOperatorKind
Definition: OperationKinds.h:25
CheckerContext.h
clang::ento::iterator::compare
bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2, BinaryOperator::Opcode Opc)
Definition: Iterator.cpp:299
Checker.h
clang::UnaryOperator::getSubExpr
Expr * getSubExpr() const
Definition: Expr.h:2204
clang
Definition: CalledOnceCheck.h:17
clang::ento::iterator::isRandomIncrOrDecrOperator
bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK)
Definition: Iterator.cpp:169
clang::UnaryOperator::getOpcode
Opcode getOpcode() const
Definition: Expr.h:2199
clang::BinaryOperator::getRHS
Expr * getRHS() const
Definition: Expr.h:3854
clang::Expr::getType
QualType getType() const
Definition: Expr.h:141
clang::BinaryOperator::getOverloadedOperator
static OverloadedOperatorKind getOverloadedOperator(Opcode Opc)
Retrieve the overloaded operator kind that corresponds to the given binary opcode.
Definition: Expr.cpp:2104
clang::MemberExpr
MemberExpr - [C99 6.5.2.3] Structure and Union Members.
Definition: Expr.h:3162
clang::ento::iterator::isDecrementOperator
bool isDecrementOperator(OverloadedOperatorKind OK)
Definition: Iterator.cpp:161
clang::Type::isIntegralOrEnumerationType
bool isIntegralOrEnumerationType() const
Determine whether this type is an integral or enumeration type.
Definition: Type.h:7058
clang::ento::iterator::advancePosition
ProgramStateRef advancePosition(ProgramStateRef State, const SVal &Iter, OverloadedOperatorKind Op, const SVal &Distance)
Definition: Iterator.cpp:224
Generated on Tue Oct 26 2021 11:02:25 for clang by   doxygen 1.8.17