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