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