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 81using namespace clang; 82using namespace ento; 83using namespace iterator; 84 85namespace { 86 87class 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 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, 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 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 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 320void 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 347void 348IteratorModeling::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 421void 422IteratorModeling::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 445void 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 503void 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 533void 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 559void 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 585void 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 623void 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 667void 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 673void 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 678void 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 683void 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 695bool 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 725void 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 762namespace { 763 764bool isSimpleComparisonOperator(OverloadedOperatorKind OK) { 765 return OK == OO_EqualEqual || OK == OO_ExclaimEqual; 766} 767 768bool isSimpleComparisonOperator(BinaryOperatorKind OK) { 769 return OK == BO_EQ || OK == BO_NE; 770} 771 772ProgramStateRef 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 784ProgramStateRef 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 816bool 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 828const 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 844void ento::registerIteratorModeling(CheckerManager &mgr) { 845 mgr.registerChecker<IteratorModeling>(); 846} 847 848bool ento::shouldRegisterIteratorModeling(const CheckerManager &mgr) { 849 return true; 850} 851