1 //===-- IteratorModeling.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 modeling-checker for modeling STL iterator-like iterators.
10 //
11 //===----------------------------------------------------------------------===//
12 //
13 // In the code, iterator can be represented as a:
14 // * type-I: typedef-ed pointer. Operations over such iterator, such as
15 // comparisons or increments, are modeled straightforwardly by the
16 // analyzer.
17 // * type-II: structure with its method bodies available. Operations over such
18 // iterator are inlined by the analyzer, and results of modeling
19 // these operations are exposing implementation details of the
20 // iterators, which is not necessarily helping.
21 // * type-III: completely opaque structure. Operations over such iterator are
22 // modeled conservatively, producing conjured symbols everywhere.
23 //
24 // To handle all these types in a common way we introduce a structure called
25 // IteratorPosition which is an abstraction of the position the iterator
26 // represents using symbolic expressions. The checker handles all the
27 // operations on this structure.
28 //
29 // Additionally, depending on the circumstances, operators of types II and III
30 // can be represented as:
31 // * type-IIa, type-IIIa: conjured structure symbols - when returned by value
32 // from conservatively evaluated methods such as
33 // `.begin()`.
34 // * type-IIb, type-IIIb: memory regions of iterator-typed objects, such as
35 // variables or temporaries, when the iterator object is
36 // currently treated as an lvalue.
37 // * type-IIc, type-IIIc: compound values of iterator-typed objects, when the
38 // iterator object is treated as an rvalue taken of a
39 // particular lvalue, eg. a copy of "type-a" iterator
40 // object, or an iterator that existed before the
41 // analysis has started.
42 //
43 // To handle any of these three different representations stored in an SVal we
44 // use setter and getters functions which separate the three cases. To store
45 // them we use a pointer union of symbol and memory region.
46 //
47 // The checker works the following way: We record the begin and the
48 // past-end iterator for all containers whenever their `.begin()` and `.end()`
49 // are called. Since the Constraint Manager cannot handle such SVals we need
50 // to take over its role. We post-check equality and non-equality comparisons
51 // and record that the two sides are equal if we are in the 'equal' branch
52 // (true-branch for `==` and false-branch for `!=`).
53 //
54 // In case of type-I or type-II iterators we get a concrete integer as a result
55 // of the comparison (1 or 0) but in case of type-III we only get a Symbol. In
56 // this latter case we record the symbol and reload it in evalAssume() and do
57 // the propagation there. We also handle (maybe double) negated comparisons
58 // which are represented in the form of (x == 0 or x != 0) where x is the
59 // comparison itself.
60 //
61 // Since `SimpleConstraintManager` cannot handle complex symbolic expressions
62 // we only use expressions of the format S, S+n or S-n for iterator positions
63 // where S is a conjured symbol and n is an unsigned concrete integer. When
64 // making an assumption e.g. `S1 + n == S2 + m` we store `S1 - S2 == m - n` as
65 // a constraint which we later retrieve when doing an actual comparison.
66
67 #include "clang/AST/DeclTemplate.h"
68 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
69 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
70 #include "clang/StaticAnalyzer/Core/Checker.h"
71 #include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h"
72 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
73 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
74 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h"
75 #include "llvm/ADT/STLExtras.h"
76
77 #include "Iterator.h"
78
79 #include <utility>
80
81 using namespace clang;
82 using namespace ento;
83 using namespace iterator;
84
85 namespace {
86
87 class IteratorModeling
88 : public Checker<check::PostCall, check::PostStmt<UnaryOperator>,
89 check::PostStmt<BinaryOperator>,
90 check::PostStmt<MaterializeTemporaryExpr>,
91 check::Bind, check::LiveSymbols, check::DeadSymbols> {
92
93 using AdvanceFn = void (IteratorModeling::*)(CheckerContext &, const Expr *,
94 SVal, SVal, SVal) const;
95
96 void handleOverloadedOperator(CheckerContext &C, const CallEvent &Call,
97 OverloadedOperatorKind Op) const;
98 void handleAdvanceLikeFunction(CheckerContext &C, const CallEvent &Call,
99 const Expr *OrigExpr,
100 const AdvanceFn *Handler) const;
101
102 void handleComparison(CheckerContext &C, const Expr *CE, SVal RetVal,
103 SVal LVal, SVal RVal, OverloadedOperatorKind Op) const;
104 void processComparison(CheckerContext &C, ProgramStateRef State,
105 SymbolRef Sym1, SymbolRef Sym2, SVal RetVal,
106 OverloadedOperatorKind Op) const;
107 void handleIncrement(CheckerContext &C, SVal RetVal, SVal Iter,
108 bool Postfix) const;
109 void handleDecrement(CheckerContext &C, SVal RetVal, SVal Iter,
110 bool Postfix) const;
111 void handleRandomIncrOrDecr(CheckerContext &C, const Expr *CE,
112 OverloadedOperatorKind Op, SVal RetVal,
113 SVal Iterator, SVal Amount) const;
114 void handlePtrIncrOrDecr(CheckerContext &C, const Expr *Iterator,
115 OverloadedOperatorKind OK, SVal Offset) const;
116 void handleAdvance(CheckerContext &C, const Expr *CE, SVal RetVal, SVal Iter,
117 SVal Amount) const;
118 void handlePrev(CheckerContext &C, const Expr *CE, SVal RetVal, SVal Iter,
119 SVal Amount) const;
120 void handleNext(CheckerContext &C, const Expr *CE, SVal RetVal, SVal Iter,
121 SVal Amount) const;
122 void assignToContainer(CheckerContext &C, const Expr *CE, SVal RetVal,
123 const MemRegion *Cont) const;
124 bool noChangeInAdvance(CheckerContext &C, SVal Iter, const Expr *CE) const;
125 void printState(raw_ostream &Out, ProgramStateRef State, const char *NL,
126 const char *Sep) const override;
127
128 // std::advance, std::prev & std::next
129 CallDescriptionMap<AdvanceFn> AdvanceLikeFunctions = {
130 // template<class InputIt, class Distance>
131 // void advance(InputIt& it, Distance n);
132 {{{"std", "advance"}, 2}, &IteratorModeling::handleAdvance},
133
134 // template<class BidirIt>
135 // BidirIt prev(
136 // BidirIt it,
137 // typename std::iterator_traits<BidirIt>::difference_type n = 1);
138 {{{"std", "prev"}, 2}, &IteratorModeling::handlePrev},
139
140 // template<class ForwardIt>
141 // ForwardIt next(
142 // ForwardIt it,
143 // typename std::iterator_traits<ForwardIt>::difference_type n = 1);
144 {{{"std", "next"}, 2}, &IteratorModeling::handleNext},
145 };
146
147 public:
148 IteratorModeling() = default;
149
150 void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
151 void checkBind(SVal Loc, SVal Val, const Stmt *S, CheckerContext &C) const;
152 void checkPostStmt(const UnaryOperator *UO, CheckerContext &C) const;
153 void checkPostStmt(const BinaryOperator *BO, CheckerContext &C) const;
154 void checkPostStmt(const MaterializeTemporaryExpr *MTE,
155 CheckerContext &C) const;
156 void checkLiveSymbols(ProgramStateRef State, SymbolReaper &SR) const;
157 void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
158 };
159
160 bool isSimpleComparisonOperator(OverloadedOperatorKind OK);
161 bool isSimpleComparisonOperator(BinaryOperatorKind OK);
162 ProgramStateRef removeIteratorPosition(ProgramStateRef State, SVal Val);
163 ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1,
164 SymbolRef Sym2, bool Equal);
165 bool isBoundThroughLazyCompoundVal(const Environment &Env,
166 const MemRegion *Reg);
167 const ExplodedNode *findCallEnter(const ExplodedNode *Node, const Expr *Call);
168
169 } // namespace
170
checkPostCall(const CallEvent & Call,CheckerContext & C) const171 void IteratorModeling::checkPostCall(const CallEvent &Call,
172 CheckerContext &C) const {
173 // Record new iterator positions and iterator position changes
174 const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
175 if (!Func)
176 return;
177
178 if (Func->isOverloadedOperator()) {
179 const auto Op = Func->getOverloadedOperator();
180 handleOverloadedOperator(C, Call, Op);
181 return;
182 }
183
184 const auto *OrigExpr = Call.getOriginExpr();
185 if (!OrigExpr)
186 return;
187
188 const AdvanceFn *Handler = AdvanceLikeFunctions.lookup(Call);
189 if (Handler) {
190 handleAdvanceLikeFunction(C, Call, OrigExpr, Handler);
191 return;
192 }
193
194 if (!isIteratorType(Call.getResultType()))
195 return;
196
197 auto State = C.getState();
198
199 // Already bound to container?
200 if (getIteratorPosition(State, Call.getReturnValue()))
201 return;
202
203 // Copy-like and move constructors
204 if (isa<CXXConstructorCall>(&Call) && Call.getNumArgs() == 1) {
205 if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(0))) {
206 State = setIteratorPosition(State, Call.getReturnValue(), *Pos);
207 if (cast<CXXConstructorDecl>(Func)->isMoveConstructor()) {
208 State = removeIteratorPosition(State, Call.getArgSVal(0));
209 }
210 C.addTransition(State);
211 return;
212 }
213 }
214
215 // Assumption: if return value is an iterator which is not yet bound to a
216 // container, then look for the first iterator argument of the
217 // same type as the return value and bind the return value to
218 // the same container. This approach works for STL algorithms.
219 // FIXME: Add a more conservative mode
220 for (unsigned i = 0; i < Call.getNumArgs(); ++i) {
221 if (isIteratorType(Call.getArgExpr(i)->getType()) &&
222 Call.getArgExpr(i)->getType().getNonReferenceType().getDesugaredType(
223 C.getASTContext()).getTypePtr() ==
224 Call.getResultType().getDesugaredType(C.getASTContext()).getTypePtr()) {
225 if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(i))) {
226 assignToContainer(C, OrigExpr, Call.getReturnValue(),
227 Pos->getContainer());
228 return;
229 }
230 }
231 }
232 }
233
checkBind(SVal Loc,SVal Val,const Stmt * S,CheckerContext & C) const234 void IteratorModeling::checkBind(SVal Loc, SVal Val, const Stmt *S,
235 CheckerContext &C) const {
236 auto State = C.getState();
237 const auto *Pos = getIteratorPosition(State, Val);
238 if (Pos) {
239 State = setIteratorPosition(State, Loc, *Pos);
240 C.addTransition(State);
241 } else {
242 const auto *OldPos = getIteratorPosition(State, Loc);
243 if (OldPos) {
244 State = removeIteratorPosition(State, Loc);
245 C.addTransition(State);
246 }
247 }
248 }
249
checkPostStmt(const UnaryOperator * UO,CheckerContext & C) const250 void IteratorModeling::checkPostStmt(const UnaryOperator *UO,
251 CheckerContext &C) const {
252 UnaryOperatorKind OK = UO->getOpcode();
253 if (!isIncrementOperator(OK) && !isDecrementOperator(OK))
254 return;
255
256 auto &SVB = C.getSValBuilder();
257 handlePtrIncrOrDecr(C, UO->getSubExpr(),
258 isIncrementOperator(OK) ? OO_Plus : OO_Minus,
259 SVB.makeArrayIndex(1));
260 }
261
checkPostStmt(const BinaryOperator * BO,CheckerContext & C) const262 void IteratorModeling::checkPostStmt(const BinaryOperator *BO,
263 CheckerContext &C) const {
264 const ProgramStateRef State = C.getState();
265 const BinaryOperatorKind OK = BO->getOpcode();
266 const Expr *const LHS = BO->getLHS();
267 const Expr *const RHS = BO->getRHS();
268 const SVal LVal = State->getSVal(LHS, C.getLocationContext());
269 const SVal RVal = State->getSVal(RHS, C.getLocationContext());
270
271 if (isSimpleComparisonOperator(BO->getOpcode())) {
272 SVal Result = State->getSVal(BO, C.getLocationContext());
273 handleComparison(C, BO, Result, LVal, RVal,
274 BinaryOperator::getOverloadedOperator(OK));
275 } else if (isRandomIncrOrDecrOperator(OK)) {
276 // In case of operator+ the iterator can be either on the LHS (eg.: it + 1),
277 // or on the RHS (eg.: 1 + it). Both cases are modeled.
278 const bool IsIterOnLHS = BO->getLHS()->getType()->isPointerType();
279 const Expr *const &IterExpr = IsIterOnLHS ? LHS : RHS;
280 const Expr *const &AmountExpr = IsIterOnLHS ? RHS : LHS;
281
282 // The non-iterator side must have an integral or enumeration type.
283 if (!AmountExpr->getType()->isIntegralOrEnumerationType())
284 return;
285 SVal AmountVal = IsIterOnLHS ? RVal : LVal;
286 handlePtrIncrOrDecr(C, IterExpr, BinaryOperator::getOverloadedOperator(OK),
287 AmountVal);
288 }
289 }
290
checkPostStmt(const MaterializeTemporaryExpr * MTE,CheckerContext & C) const291 void IteratorModeling::checkPostStmt(const MaterializeTemporaryExpr *MTE,
292 CheckerContext &C) const {
293 /* Transfer iterator state to temporary objects */
294 auto State = C.getState();
295 const auto *Pos = getIteratorPosition(State, C.getSVal(MTE->getSubExpr()));
296 if (!Pos)
297 return;
298 State = setIteratorPosition(State, C.getSVal(MTE), *Pos);
299 C.addTransition(State);
300 }
301
checkLiveSymbols(ProgramStateRef State,SymbolReaper & SR) const302 void IteratorModeling::checkLiveSymbols(ProgramStateRef State,
303 SymbolReaper &SR) const {
304 // Keep symbolic expressions of iterator positions alive
305 auto RegionMap = State->get<IteratorRegionMap>();
306 for (const IteratorPosition &Pos : llvm::make_second_range(RegionMap)) {
307 for (SymbolRef Sym : Pos.getOffset()->symbols())
308 if (isa<SymbolData>(Sym))
309 SR.markLive(Sym);
310 }
311
312 auto SymbolMap = State->get<IteratorSymbolMap>();
313 for (const IteratorPosition &Pos : llvm::make_second_range(SymbolMap)) {
314 for (SymbolRef Sym : Pos.getOffset()->symbols())
315 if (isa<SymbolData>(Sym))
316 SR.markLive(Sym);
317 }
318 }
319
checkDeadSymbols(SymbolReaper & SR,CheckerContext & C) const320 void IteratorModeling::checkDeadSymbols(SymbolReaper &SR,
321 CheckerContext &C) const {
322 // Cleanup
323 auto State = C.getState();
324
325 auto RegionMap = State->get<IteratorRegionMap>();
326 for (const auto &Reg : RegionMap) {
327 if (!SR.isLiveRegion(Reg.first)) {
328 // The region behind the `LazyCompoundVal` is often cleaned up before
329 // the `LazyCompoundVal` itself. If there are iterator positions keyed
330 // by these regions their cleanup must be deferred.
331 if (!isBoundThroughLazyCompoundVal(State->getEnvironment(), Reg.first)) {
332 State = State->remove<IteratorRegionMap>(Reg.first);
333 }
334 }
335 }
336
337 auto SymbolMap = State->get<IteratorSymbolMap>();
338 for (const auto &Sym : SymbolMap) {
339 if (!SR.isLive(Sym.first)) {
340 State = State->remove<IteratorSymbolMap>(Sym.first);
341 }
342 }
343
344 C.addTransition(State);
345 }
346
347 void
handleOverloadedOperator(CheckerContext & C,const CallEvent & Call,OverloadedOperatorKind Op) const348 IteratorModeling::handleOverloadedOperator(CheckerContext &C,
349 const CallEvent &Call,
350 OverloadedOperatorKind Op) const {
351 if (isSimpleComparisonOperator(Op)) {
352 const auto *OrigExpr = Call.getOriginExpr();
353 if (!OrigExpr)
354 return;
355
356 if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
357 handleComparison(C, OrigExpr, Call.getReturnValue(),
358 InstCall->getCXXThisVal(), Call.getArgSVal(0), Op);
359 return;
360 }
361
362 handleComparison(C, OrigExpr, Call.getReturnValue(), Call.getArgSVal(0),
363 Call.getArgSVal(1), Op);
364 return;
365 } else if (isRandomIncrOrDecrOperator(Op)) {
366 const auto *OrigExpr = Call.getOriginExpr();
367 if (!OrigExpr)
368 return;
369
370 if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
371 if (Call.getNumArgs() >= 1 &&
372 Call.getArgExpr(0)->getType()->isIntegralOrEnumerationType()) {
373 handleRandomIncrOrDecr(C, OrigExpr, Op, Call.getReturnValue(),
374 InstCall->getCXXThisVal(), Call.getArgSVal(0));
375 return;
376 }
377 } else if (Call.getNumArgs() >= 2) {
378 const Expr *FirstArg = Call.getArgExpr(0);
379 const Expr *SecondArg = Call.getArgExpr(1);
380 const QualType FirstType = FirstArg->getType();
381 const QualType SecondType = SecondArg->getType();
382
383 if (FirstType->isIntegralOrEnumerationType() ||
384 SecondType->isIntegralOrEnumerationType()) {
385 // In case of operator+ the iterator can be either on the LHS (eg.:
386 // it + 1), or on the RHS (eg.: 1 + it). Both cases are modeled.
387 const bool IsIterFirst = FirstType->isStructureOrClassType();
388 const SVal FirstArg = Call.getArgSVal(0);
389 const SVal SecondArg = Call.getArgSVal(1);
390 SVal Iterator = IsIterFirst ? FirstArg : SecondArg;
391 SVal Amount = IsIterFirst ? SecondArg : FirstArg;
392
393 handleRandomIncrOrDecr(C, OrigExpr, Op, Call.getReturnValue(),
394 Iterator, Amount);
395 return;
396 }
397 }
398 } else if (isIncrementOperator(Op)) {
399 if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
400 handleIncrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(),
401 Call.getNumArgs());
402 return;
403 }
404
405 handleIncrement(C, Call.getReturnValue(), Call.getArgSVal(0),
406 Call.getNumArgs());
407 return;
408 } else if (isDecrementOperator(Op)) {
409 if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
410 handleDecrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(),
411 Call.getNumArgs());
412 return;
413 }
414
415 handleDecrement(C, Call.getReturnValue(), Call.getArgSVal(0),
416 Call.getNumArgs());
417 return;
418 }
419 }
420
421 void
handleAdvanceLikeFunction(CheckerContext & C,const CallEvent & Call,const Expr * OrigExpr,const AdvanceFn * Handler) const422 IteratorModeling::handleAdvanceLikeFunction(CheckerContext &C,
423 const CallEvent &Call,
424 const Expr *OrigExpr,
425 const AdvanceFn *Handler) const {
426 if (!C.wasInlined) {
427 (this->**Handler)(C, OrigExpr, Call.getReturnValue(),
428 Call.getArgSVal(0), Call.getArgSVal(1));
429 return;
430 }
431
432 // If std::advance() was inlined, but a non-standard function it calls inside
433 // was not, then we have to model it explicitly
434 const auto *IdInfo = cast<FunctionDecl>(Call.getDecl())->getIdentifier();
435 if (IdInfo) {
436 if (IdInfo->getName() == "advance") {
437 if (noChangeInAdvance(C, Call.getArgSVal(0), OrigExpr)) {
438 (this->**Handler)(C, OrigExpr, Call.getReturnValue(),
439 Call.getArgSVal(0), Call.getArgSVal(1));
440 }
441 }
442 }
443 }
444
handleComparison(CheckerContext & C,const Expr * CE,SVal RetVal,SVal LVal,SVal RVal,OverloadedOperatorKind Op) const445 void IteratorModeling::handleComparison(CheckerContext &C, const Expr *CE,
446 SVal RetVal, SVal LVal, SVal RVal,
447 OverloadedOperatorKind Op) const {
448 // Record the operands and the operator of the comparison for the next
449 // evalAssume, if the result is a symbolic expression. If it is a concrete
450 // value (only one branch is possible), then transfer the state between
451 // the operands according to the operator and the result
452 auto State = C.getState();
453 const auto *LPos = getIteratorPosition(State, LVal);
454 const auto *RPos = getIteratorPosition(State, RVal);
455 const MemRegion *Cont = nullptr;
456 if (LPos) {
457 Cont = LPos->getContainer();
458 } else if (RPos) {
459 Cont = RPos->getContainer();
460 }
461 if (!Cont)
462 return;
463
464 // At least one of the iterators has recorded positions. If one of them does
465 // not then create a new symbol for the offset.
466 SymbolRef Sym;
467 if (!LPos || !RPos) {
468 auto &SymMgr = C.getSymbolManager();
469 Sym = SymMgr.conjureSymbol(CE, C.getLocationContext(),
470 C.getASTContext().LongTy, C.blockCount());
471 State = assumeNoOverflow(State, Sym, 4);
472 }
473
474 if (!LPos) {
475 State = setIteratorPosition(State, LVal,
476 IteratorPosition::getPosition(Cont, Sym));
477 LPos = getIteratorPosition(State, LVal);
478 } else if (!RPos) {
479 State = setIteratorPosition(State, RVal,
480 IteratorPosition::getPosition(Cont, Sym));
481 RPos = getIteratorPosition(State, RVal);
482 }
483
484 // If the value for which we just tried to set a new iterator position is
485 // an `SVal`for which no iterator position can be set then the setting was
486 // unsuccessful. We cannot handle the comparison in this case.
487 if (!LPos || !RPos)
488 return;
489
490 // We cannot make assumptions on `UnknownVal`. Let us conjure a symbol
491 // instead.
492 if (RetVal.isUnknown()) {
493 auto &SymMgr = C.getSymbolManager();
494 auto *LCtx = C.getLocationContext();
495 RetVal = nonloc::SymbolVal(SymMgr.conjureSymbol(
496 CE, LCtx, C.getASTContext().BoolTy, C.blockCount()));
497 State = State->BindExpr(CE, LCtx, RetVal);
498 }
499
500 processComparison(C, State, LPos->getOffset(), RPos->getOffset(), RetVal, Op);
501 }
502
processComparison(CheckerContext & C,ProgramStateRef State,SymbolRef Sym1,SymbolRef Sym2,SVal RetVal,OverloadedOperatorKind Op) const503 void IteratorModeling::processComparison(CheckerContext &C,
504 ProgramStateRef State, SymbolRef Sym1,
505 SymbolRef Sym2, SVal RetVal,
506 OverloadedOperatorKind Op) const {
507 if (const auto TruthVal = RetVal.getAs<nonloc::ConcreteInt>()) {
508 if ((State = relateSymbols(State, Sym1, Sym2,
509 (Op == OO_EqualEqual) ==
510 (TruthVal->getValue() != 0)))) {
511 C.addTransition(State);
512 } else {
513 C.generateSink(State, C.getPredecessor());
514 }
515 return;
516 }
517
518 const auto ConditionVal = RetVal.getAs<DefinedSVal>();
519 if (!ConditionVal)
520 return;
521
522 if (auto StateTrue = relateSymbols(State, Sym1, Sym2, Op == OO_EqualEqual)) {
523 StateTrue = StateTrue->assume(*ConditionVal, true);
524 C.addTransition(StateTrue);
525 }
526
527 if (auto StateFalse = relateSymbols(State, Sym1, Sym2, Op != OO_EqualEqual)) {
528 StateFalse = StateFalse->assume(*ConditionVal, false);
529 C.addTransition(StateFalse);
530 }
531 }
532
handleIncrement(CheckerContext & C,SVal RetVal,SVal Iter,bool Postfix) const533 void IteratorModeling::handleIncrement(CheckerContext &C, SVal RetVal,
534 SVal Iter, bool Postfix) const {
535 // Increment the symbolic expressions which represents the position of the
536 // iterator
537 auto State = C.getState();
538 auto &BVF = C.getSymbolManager().getBasicVals();
539
540 const auto *Pos = getIteratorPosition(State, Iter);
541 if (!Pos)
542 return;
543
544 auto NewState =
545 advancePosition(State, Iter, OO_Plus,
546 nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
547 assert(NewState &&
548 "Advancing position by concrete int should always be successful");
549
550 const auto *NewPos = getIteratorPosition(NewState, Iter);
551 assert(NewPos &&
552 "Iterator should have position after successful advancement");
553
554 State = setIteratorPosition(State, Iter, *NewPos);
555 State = setIteratorPosition(State, RetVal, Postfix ? *Pos : *NewPos);
556 C.addTransition(State);
557 }
558
handleDecrement(CheckerContext & C,SVal RetVal,SVal Iter,bool Postfix) const559 void IteratorModeling::handleDecrement(CheckerContext &C, SVal RetVal,
560 SVal Iter, bool Postfix) const {
561 // Decrement the symbolic expressions which represents the position of the
562 // iterator
563 auto State = C.getState();
564 auto &BVF = C.getSymbolManager().getBasicVals();
565
566 const auto *Pos = getIteratorPosition(State, Iter);
567 if (!Pos)
568 return;
569
570 auto NewState =
571 advancePosition(State, Iter, OO_Minus,
572 nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
573 assert(NewState &&
574 "Advancing position by concrete int should always be successful");
575
576 const auto *NewPos = getIteratorPosition(NewState, Iter);
577 assert(NewPos &&
578 "Iterator should have position after successful advancement");
579
580 State = setIteratorPosition(State, Iter, *NewPos);
581 State = setIteratorPosition(State, RetVal, Postfix ? *Pos : *NewPos);
582 C.addTransition(State);
583 }
584
handleRandomIncrOrDecr(CheckerContext & C,const Expr * CE,OverloadedOperatorKind Op,SVal RetVal,SVal Iterator,SVal Amount) const585 void IteratorModeling::handleRandomIncrOrDecr(CheckerContext &C, const Expr *CE,
586 OverloadedOperatorKind Op,
587 SVal RetVal, SVal Iterator,
588 SVal Amount) const {
589 // Increment or decrement the symbolic expressions which represents the
590 // position of the iterator
591 auto State = C.getState();
592
593 const auto *Pos = getIteratorPosition(State, Iterator);
594 if (!Pos)
595 return;
596
597 const auto *Value = &Amount;
598 SVal Val;
599 if (auto LocAmount = Amount.getAs<Loc>()) {
600 Val = State->getRawSVal(*LocAmount);
601 Value = &Val;
602 }
603
604 const auto &TgtVal =
605 (Op == OO_PlusEqual || Op == OO_MinusEqual) ? Iterator : RetVal;
606
607 // `AdvancedState` is a state where the position of `LHS` is advanced. We
608 // only need this state to retrieve the new position, but we do not want
609 // to change the position of `LHS` (in every case).
610 auto AdvancedState = advancePosition(State, Iterator, Op, *Value);
611 if (AdvancedState) {
612 const auto *NewPos = getIteratorPosition(AdvancedState, Iterator);
613 assert(NewPos &&
614 "Iterator should have position after successful advancement");
615
616 State = setIteratorPosition(State, TgtVal, *NewPos);
617 C.addTransition(State);
618 } else {
619 assignToContainer(C, CE, TgtVal, Pos->getContainer());
620 }
621 }
622
handlePtrIncrOrDecr(CheckerContext & C,const Expr * Iterator,OverloadedOperatorKind OK,SVal Offset) const623 void IteratorModeling::handlePtrIncrOrDecr(CheckerContext &C,
624 const Expr *Iterator,
625 OverloadedOperatorKind OK,
626 SVal Offset) const {
627 if (!isa<DefinedSVal>(Offset))
628 return;
629
630 QualType PtrType = Iterator->getType();
631 if (!PtrType->isPointerType())
632 return;
633 QualType ElementType = PtrType->getPointeeType();
634
635 ProgramStateRef State = C.getState();
636 SVal OldVal = State->getSVal(Iterator, C.getLocationContext());
637
638 const IteratorPosition *OldPos = getIteratorPosition(State, OldVal);
639 if (!OldPos)
640 return;
641
642 SVal NewVal;
643 if (OK == OO_Plus || OK == OO_PlusEqual) {
644 NewVal = State->getLValue(ElementType, Offset, OldVal);
645 } else {
646 auto &SVB = C.getSValBuilder();
647 SVal NegatedOffset = SVB.evalMinus(Offset.castAs<NonLoc>());
648 NewVal = State->getLValue(ElementType, NegatedOffset, OldVal);
649 }
650
651 // `AdvancedState` is a state where the position of `Old` is advanced. We
652 // only need this state to retrieve the new position, but we do not want
653 // ever to change the position of `OldVal`.
654 auto AdvancedState = advancePosition(State, OldVal, OK, Offset);
655 if (AdvancedState) {
656 const IteratorPosition *NewPos = getIteratorPosition(AdvancedState, OldVal);
657 assert(NewPos &&
658 "Iterator should have position after successful advancement");
659
660 ProgramStateRef NewState = setIteratorPosition(State, NewVal, *NewPos);
661 C.addTransition(NewState);
662 } else {
663 assignToContainer(C, Iterator, NewVal, OldPos->getContainer());
664 }
665 }
666
handleAdvance(CheckerContext & C,const Expr * CE,SVal RetVal,SVal Iter,SVal Amount) const667 void IteratorModeling::handleAdvance(CheckerContext &C, const Expr *CE,
668 SVal RetVal, SVal Iter,
669 SVal Amount) const {
670 handleRandomIncrOrDecr(C, CE, OO_PlusEqual, RetVal, Iter, Amount);
671 }
672
handlePrev(CheckerContext & C,const Expr * CE,SVal RetVal,SVal Iter,SVal Amount) const673 void IteratorModeling::handlePrev(CheckerContext &C, const Expr *CE,
674 SVal RetVal, SVal Iter, SVal Amount) const {
675 handleRandomIncrOrDecr(C, CE, OO_Minus, RetVal, Iter, Amount);
676 }
677
handleNext(CheckerContext & C,const Expr * CE,SVal RetVal,SVal Iter,SVal Amount) const678 void IteratorModeling::handleNext(CheckerContext &C, const Expr *CE,
679 SVal RetVal, SVal Iter, SVal Amount) const {
680 handleRandomIncrOrDecr(C, CE, OO_Plus, RetVal, Iter, Amount);
681 }
682
assignToContainer(CheckerContext & C,const Expr * CE,SVal RetVal,const MemRegion * Cont) const683 void IteratorModeling::assignToContainer(CheckerContext &C, const Expr *CE,
684 SVal RetVal,
685 const MemRegion *Cont) const {
686 Cont = Cont->getMostDerivedObjectRegion();
687
688 auto State = C.getState();
689 const auto *LCtx = C.getLocationContext();
690 State = createIteratorPosition(State, RetVal, Cont, CE, LCtx, C.blockCount());
691
692 C.addTransition(State);
693 }
694
noChangeInAdvance(CheckerContext & C,SVal Iter,const Expr * CE) const695 bool IteratorModeling::noChangeInAdvance(CheckerContext &C, SVal Iter,
696 const Expr *CE) const {
697 // Compare the iterator position before and after the call. (To be called
698 // from `checkPostCall()`.)
699 const auto StateAfter = C.getState();
700
701 const auto *PosAfter = getIteratorPosition(StateAfter, Iter);
702 // If we have no position after the call of `std::advance`, then we are not
703 // interested. (Modeling of an inlined `std::advance()` should not remove the
704 // position in any case.)
705 if (!PosAfter)
706 return false;
707
708 const ExplodedNode *N = findCallEnter(C.getPredecessor(), CE);
709 assert(N && "Any call should have a `CallEnter` node.");
710
711 const auto StateBefore = N->getState();
712 const auto *PosBefore = getIteratorPosition(StateBefore, Iter);
713 // FIXME: `std::advance()` should not create a new iterator position but
714 // change existing ones. However, in case of iterators implemented as
715 // pointers the handling of parameters in `std::advance()`-like
716 // functions is still incomplete which may result in cases where
717 // the new position is assigned to the wrong pointer. This causes
718 // crash if we use an assertion here.
719 if (!PosBefore)
720 return false;
721
722 return PosBefore->getOffset() == PosAfter->getOffset();
723 }
724
printState(raw_ostream & Out,ProgramStateRef State,const char * NL,const char * Sep) const725 void IteratorModeling::printState(raw_ostream &Out, ProgramStateRef State,
726 const char *NL, const char *Sep) const {
727 auto SymbolMap = State->get<IteratorSymbolMap>();
728 auto RegionMap = State->get<IteratorRegionMap>();
729 // Use a counter to add newlines before every line except the first one.
730 unsigned Count = 0;
731
732 if (!SymbolMap.isEmpty() || !RegionMap.isEmpty()) {
733 Out << Sep << "Iterator Positions :" << NL;
734 for (const auto &Sym : SymbolMap) {
735 if (Count++)
736 Out << NL;
737
738 Sym.first->dumpToStream(Out);
739 Out << " : ";
740 const auto Pos = Sym.second;
741 Out << (Pos.isValid() ? "Valid" : "Invalid") << " ; Container == ";
742 Pos.getContainer()->dumpToStream(Out);
743 Out<<" ; Offset == ";
744 Pos.getOffset()->dumpToStream(Out);
745 }
746
747 for (const auto &Reg : RegionMap) {
748 if (Count++)
749 Out << NL;
750
751 Reg.first->dumpToStream(Out);
752 Out << " : ";
753 const auto Pos = Reg.second;
754 Out << (Pos.isValid() ? "Valid" : "Invalid") << " ; Container == ";
755 Pos.getContainer()->dumpToStream(Out);
756 Out<<" ; Offset == ";
757 Pos.getOffset()->dumpToStream(Out);
758 }
759 }
760 }
761
762 namespace {
763
isSimpleComparisonOperator(OverloadedOperatorKind OK)764 bool isSimpleComparisonOperator(OverloadedOperatorKind OK) {
765 return OK == OO_EqualEqual || OK == OO_ExclaimEqual;
766 }
767
isSimpleComparisonOperator(BinaryOperatorKind OK)768 bool isSimpleComparisonOperator(BinaryOperatorKind OK) {
769 return OK == BO_EQ || OK == BO_NE;
770 }
771
removeIteratorPosition(ProgramStateRef State,SVal Val)772 ProgramStateRef removeIteratorPosition(ProgramStateRef State, SVal Val) {
773 if (auto Reg = Val.getAsRegion()) {
774 Reg = Reg->getMostDerivedObjectRegion();
775 return State->remove<IteratorRegionMap>(Reg);
776 } else if (const auto Sym = Val.getAsSymbol()) {
777 return State->remove<IteratorSymbolMap>(Sym);
778 } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
779 return State->remove<IteratorRegionMap>(LCVal->getRegion());
780 }
781 return nullptr;
782 }
783
relateSymbols(ProgramStateRef State,SymbolRef Sym1,SymbolRef Sym2,bool Equal)784 ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1,
785 SymbolRef Sym2, bool Equal) {
786 auto &SVB = State->getStateManager().getSValBuilder();
787
788 // FIXME: This code should be reworked as follows:
789 // 1. Subtract the operands using evalBinOp().
790 // 2. Assume that the result doesn't overflow.
791 // 3. Compare the result to 0.
792 // 4. Assume the result of the comparison.
793 const auto comparison =
794 SVB.evalBinOp(State, BO_EQ, nonloc::SymbolVal(Sym1),
795 nonloc::SymbolVal(Sym2), SVB.getConditionType());
796
797 assert(isa<DefinedSVal>(comparison) &&
798 "Symbol comparison must be a `DefinedSVal`");
799
800 auto NewState = State->assume(comparison.castAs<DefinedSVal>(), Equal);
801 if (!NewState)
802 return nullptr;
803
804 if (const auto CompSym = comparison.getAsSymbol()) {
805 assert(isa<SymIntExpr>(CompSym) &&
806 "Symbol comparison must be a `SymIntExpr`");
807 assert(BinaryOperator::isComparisonOp(
808 cast<SymIntExpr>(CompSym)->getOpcode()) &&
809 "Symbol comparison must be a comparison");
810 return assumeNoOverflow(NewState, cast<SymIntExpr>(CompSym)->getLHS(), 2);
811 }
812
813 return NewState;
814 }
815
isBoundThroughLazyCompoundVal(const Environment & Env,const MemRegion * Reg)816 bool isBoundThroughLazyCompoundVal(const Environment &Env,
817 const MemRegion *Reg) {
818 for (const auto &Binding : Env) {
819 if (const auto LCVal = Binding.second.getAs<nonloc::LazyCompoundVal>()) {
820 if (LCVal->getRegion() == Reg)
821 return true;
822 }
823 }
824
825 return false;
826 }
827
findCallEnter(const ExplodedNode * Node,const Expr * Call)828 const ExplodedNode *findCallEnter(const ExplodedNode *Node, const Expr *Call) {
829 while (Node) {
830 ProgramPoint PP = Node->getLocation();
831 if (auto Enter = PP.getAs<CallEnter>()) {
832 if (Enter->getCallExpr() == Call)
833 break;
834 }
835
836 Node = Node->getFirstPred();
837 }
838
839 return Node;
840 }
841
842 } // namespace
843
registerIteratorModeling(CheckerManager & mgr)844 void ento::registerIteratorModeling(CheckerManager &mgr) {
845 mgr.registerChecker<IteratorModeling>();
846 }
847
shouldRegisterIteratorModeling(const CheckerManager & mgr)848 bool ento::shouldRegisterIteratorModeling(const CheckerManager &mgr) {
849 return true;
850 }
851