1//=== MallocChecker.cpp - A malloc/free checker -------------------*- C++ -*--// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file defines malloc/free checker, which checks for potential memory 11// leaks, double free, and use-after-free problems. 12// 13//===----------------------------------------------------------------------===// 14 15#include "ClangSACheckers.h" 16#include "InterCheckerAPI.h" 17#include "clang/StaticAnalyzer/Core/Checker.h" 18#include "clang/StaticAnalyzer/Core/CheckerManager.h" 19#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" 20#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" 21#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" 22#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 23#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" 24#include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h" 25#include "clang/Basic/SourceManager.h" 26#include "llvm/ADT/ImmutableMap.h" 27#include "llvm/ADT/SmallString.h" 28#include "llvm/ADT/STLExtras.h" 29#include <climits> 30 31using namespace clang; 32using namespace ento; 33 34namespace { 35 36class RefState { 37 enum Kind { // Reference to allocated memory. 38 Allocated, 39 // Reference to released/freed memory. 40 Released, 41 // The responsibility for freeing resources has transfered from 42 // this reference. A relinquished symbol should not be freed. 43 Relinquished } K; 44 const Stmt *S; 45 46public: 47 RefState(Kind k, const Stmt *s) : K(k), S(s) {} 48 49 bool isAllocated() const { return K == Allocated; } 50 bool isReleased() const { return K == Released; } 51 bool isRelinquished() const { return K == Relinquished; } 52 53 const Stmt *getStmt() const { return S; } 54 55 bool operator==(const RefState &X) const { 56 return K == X.K && S == X.S; 57 } 58 59 static RefState getAllocated(const Stmt *s) { 60 return RefState(Allocated, s); 61 } 62 static RefState getReleased(const Stmt *s) { return RefState(Released, s); } 63 static RefState getRelinquished(const Stmt *s) { 64 return RefState(Relinquished, s); 65 } 66 67 void Profile(llvm::FoldingSetNodeID &ID) const { 68 ID.AddInteger(K); 69 ID.AddPointer(S); 70 } 71}; 72 73/// \class ReallocPair 74/// \brief Stores information about the symbol being reallocated by a call to 75/// 'realloc' to allow modeling failed reallocation later in the path. 76struct ReallocPair { 77 // \brief The symbol which realloc reallocated. 78 SymbolRef ReallocatedSym; 79 // \brief The flag is true if the symbol does not need to be freed after 80 // reallocation fails. 81 bool IsFreeOnFailure; 82 83 ReallocPair(SymbolRef S, bool F) : ReallocatedSym(S), IsFreeOnFailure(F) {} 84 void Profile(llvm::FoldingSetNodeID &ID) const { 85 ID.AddInteger(IsFreeOnFailure); 86 ID.AddPointer(ReallocatedSym); 87 } 88 bool operator==(const ReallocPair &X) const { 89 return ReallocatedSym == X.ReallocatedSym && 90 IsFreeOnFailure == X.IsFreeOnFailure; 91 } 92}; 93 94typedef std::pair<const Stmt*, const MemRegion*> LeakInfo; 95 96class MallocChecker : public Checker<check::DeadSymbols, 97 check::EndPath, 98 check::PreStmt<ReturnStmt>, 99 check::PreStmt<CallExpr>, 100 check::PostStmt<CallExpr>, 101 check::PostStmt<BlockExpr>, 102 check::PreObjCMessage, 103 check::Location, 104 check::Bind, 105 eval::Assume, 106 check::RegionChanges> 107{ 108 mutable OwningPtr<BugType> BT_DoubleFree; 109 mutable OwningPtr<BugType> BT_Leak; 110 mutable OwningPtr<BugType> BT_UseFree; 111 mutable OwningPtr<BugType> BT_BadFree; 112 mutable IdentifierInfo *II_malloc, *II_free, *II_realloc, *II_calloc, 113 *II_valloc, *II_reallocf, *II_strndup, *II_strdup; 114 115public: 116 MallocChecker() : II_malloc(0), II_free(0), II_realloc(0), II_calloc(0), 117 II_valloc(0), II_reallocf(0), II_strndup(0), II_strdup(0) {} 118 119 /// In pessimistic mode, the checker assumes that it does not know which 120 /// functions might free the memory. 121 struct ChecksFilter { 122 DefaultBool CMallocPessimistic; 123 DefaultBool CMallocOptimistic; 124 }; 125 126 ChecksFilter Filter; 127 128 void checkPreStmt(const CallExpr *S, CheckerContext &C) const; 129 void checkPostStmt(const CallExpr *CE, CheckerContext &C) const; 130 void checkPreObjCMessage(const ObjCMethodCall &Call, CheckerContext &C) const; 131 void checkPostStmt(const BlockExpr *BE, CheckerContext &C) const; 132 void checkDeadSymbols(SymbolReaper &SymReaper, CheckerContext &C) const; 133 void checkEndPath(CheckerContext &C) const; 134 void checkPreStmt(const ReturnStmt *S, CheckerContext &C) const; 135 ProgramStateRef evalAssume(ProgramStateRef state, SVal Cond, 136 bool Assumption) const; 137 void checkLocation(SVal l, bool isLoad, const Stmt *S, 138 CheckerContext &C) const; 139 void checkBind(SVal location, SVal val, const Stmt*S, 140 CheckerContext &C) const; 141 ProgramStateRef 142 checkRegionChanges(ProgramStateRef state, 143 const StoreManager::InvalidatedSymbols *invalidated, 144 ArrayRef<const MemRegion *> ExplicitRegions, 145 ArrayRef<const MemRegion *> Regions, 146 const CallEvent *Call) const; 147 bool wantsRegionChangeUpdate(ProgramStateRef state) const { 148 return true; 149 } 150 151 void printState(raw_ostream &Out, ProgramStateRef State, 152 const char *NL, const char *Sep) const; 153 154private: 155 void initIdentifierInfo(ASTContext &C) const; 156 157 /// Check if this is one of the functions which can allocate/reallocate memory 158 /// pointed to by one of its arguments. 159 bool isMemFunction(const FunctionDecl *FD, ASTContext &C) const; 160 bool isFreeFunction(const FunctionDecl *FD, ASTContext &C) const; 161 bool isAllocationFunction(const FunctionDecl *FD, ASTContext &C) const; 162 163 static ProgramStateRef MallocMemReturnsAttr(CheckerContext &C, 164 const CallExpr *CE, 165 const OwnershipAttr* Att); 166 static ProgramStateRef MallocMemAux(CheckerContext &C, const CallExpr *CE, 167 const Expr *SizeEx, SVal Init, 168 ProgramStateRef state) { 169 return MallocMemAux(C, CE, 170 state->getSVal(SizeEx, C.getLocationContext()), 171 Init, state); 172 } 173 174 static ProgramStateRef MallocMemAux(CheckerContext &C, const CallExpr *CE, 175 SVal SizeEx, SVal Init, 176 ProgramStateRef state); 177 178 /// Update the RefState to reflect the new memory allocation. 179 static ProgramStateRef MallocUpdateRefState(CheckerContext &C, 180 const CallExpr *CE, 181 ProgramStateRef state); 182 183 ProgramStateRef FreeMemAttr(CheckerContext &C, const CallExpr *CE, 184 const OwnershipAttr* Att) const; 185 ProgramStateRef FreeMemAux(CheckerContext &C, const CallExpr *CE, 186 ProgramStateRef state, unsigned Num, 187 bool Hold, 188 bool &ReleasedAllocated) const; 189 ProgramStateRef FreeMemAux(CheckerContext &C, const Expr *Arg, 190 const Expr *ParentExpr, 191 ProgramStateRef state, 192 bool Hold, 193 bool &ReleasedAllocated) const; 194 195 ProgramStateRef ReallocMem(CheckerContext &C, const CallExpr *CE, 196 bool FreesMemOnFailure) const; 197 static ProgramStateRef CallocMem(CheckerContext &C, const CallExpr *CE); 198 199 ///\brief Check if the memory associated with this symbol was released. 200 bool isReleased(SymbolRef Sym, CheckerContext &C) const; 201 202 bool checkUseAfterFree(SymbolRef Sym, CheckerContext &C, 203 const Stmt *S = 0) const; 204 205 /// Check if the function is not known to us. So, for example, we could 206 /// conservatively assume it can free/reallocate it's pointer arguments. 207 bool doesNotFreeMemory(const CallEvent *Call, 208 ProgramStateRef State) const; 209 210 static bool SummarizeValue(raw_ostream &os, SVal V); 211 static bool SummarizeRegion(raw_ostream &os, const MemRegion *MR); 212 void ReportBadFree(CheckerContext &C, SVal ArgVal, SourceRange range) const; 213 214 /// Find the location of the allocation for Sym on the path leading to the 215 /// exploded node N. 216 LeakInfo getAllocationSite(const ExplodedNode *N, SymbolRef Sym, 217 CheckerContext &C) const; 218 219 void reportLeak(SymbolRef Sym, ExplodedNode *N, CheckerContext &C) const; 220 221 /// The bug visitor which allows us to print extra diagnostics along the 222 /// BugReport path. For example, showing the allocation site of the leaked 223 /// region. 224 class MallocBugVisitor : public BugReporterVisitorImpl<MallocBugVisitor> { 225 protected: 226 enum NotificationMode { 227 Normal, 228 ReallocationFailed 229 }; 230 231 // The allocated region symbol tracked by the main analysis. 232 SymbolRef Sym; 233 234 // The mode we are in, i.e. what kind of diagnostics will be emitted. 235 NotificationMode Mode; 236 237 // A symbol from when the primary region should have been reallocated. 238 SymbolRef FailedReallocSymbol; 239 240 bool IsLeak; 241 242 public: 243 MallocBugVisitor(SymbolRef S, bool isLeak = false) 244 : Sym(S), Mode(Normal), FailedReallocSymbol(0), IsLeak(isLeak) {} 245 246 virtual ~MallocBugVisitor() {} 247 248 void Profile(llvm::FoldingSetNodeID &ID) const { 249 static int X = 0; 250 ID.AddPointer(&X); 251 ID.AddPointer(Sym); 252 } 253 254 inline bool isAllocated(const RefState *S, const RefState *SPrev, 255 const Stmt *Stmt) { 256 // Did not track -> allocated. Other state (released) -> allocated. 257 return (Stmt && isa<CallExpr>(Stmt) && 258 (S && S->isAllocated()) && (!SPrev || !SPrev->isAllocated())); 259 } 260 261 inline bool isReleased(const RefState *S, const RefState *SPrev, 262 const Stmt *Stmt) { 263 // Did not track -> released. Other state (allocated) -> released. 264 return (Stmt && isa<CallExpr>(Stmt) && 265 (S && S->isReleased()) && (!SPrev || !SPrev->isReleased())); 266 } 267 268 inline bool isRelinquished(const RefState *S, const RefState *SPrev, 269 const Stmt *Stmt) { 270 // Did not track -> relinquished. Other state (allocated) -> relinquished. 271 return (Stmt && (isa<CallExpr>(Stmt) || isa<ObjCMessageExpr>(Stmt) || 272 isa<ObjCPropertyRefExpr>(Stmt)) && 273 (S && S->isRelinquished()) && 274 (!SPrev || !SPrev->isRelinquished())); 275 } 276 277 inline bool isReallocFailedCheck(const RefState *S, const RefState *SPrev, 278 const Stmt *Stmt) { 279 // If the expression is not a call, and the state change is 280 // released -> allocated, it must be the realloc return value 281 // check. If we have to handle more cases here, it might be cleaner just 282 // to track this extra bit in the state itself. 283 return ((!Stmt || !isa<CallExpr>(Stmt)) && 284 (S && S->isAllocated()) && (SPrev && !SPrev->isAllocated())); 285 } 286 287 PathDiagnosticPiece *VisitNode(const ExplodedNode *N, 288 const ExplodedNode *PrevN, 289 BugReporterContext &BRC, 290 BugReport &BR); 291 292 PathDiagnosticPiece* getEndPath(BugReporterContext &BRC, 293 const ExplodedNode *EndPathNode, 294 BugReport &BR) { 295 if (!IsLeak) 296 return 0; 297 298 PathDiagnosticLocation L = 299 PathDiagnosticLocation::createEndOfPath(EndPathNode, 300 BRC.getSourceManager()); 301 // Do not add the statement itself as a range in case of leak. 302 return new PathDiagnosticEventPiece(L, BR.getDescription(), false); 303 } 304 305 private: 306 class StackHintGeneratorForReallocationFailed 307 : public StackHintGeneratorForSymbol { 308 public: 309 StackHintGeneratorForReallocationFailed(SymbolRef S, StringRef M) 310 : StackHintGeneratorForSymbol(S, M) {} 311 312 virtual std::string getMessageForArg(const Expr *ArgE, unsigned ArgIndex) { 313 SmallString<200> buf; 314 llvm::raw_svector_ostream os(buf); 315 316 os << "Reallocation of "; 317 // Printed parameters start at 1, not 0. 318 printOrdinal(++ArgIndex, os); 319 os << " parameter failed"; 320 321 return os.str(); 322 } 323 324 virtual std::string getMessageForReturn(const CallExpr *CallExpr) { 325 return "Reallocation of returned value failed"; 326 } 327 }; 328 }; 329}; 330} // end anonymous namespace 331 332typedef llvm::ImmutableMap<SymbolRef, RefState> RegionStateTy; 333typedef llvm::ImmutableMap<SymbolRef, ReallocPair > ReallocMap; 334class RegionState {}; 335class ReallocPairs {}; 336namespace clang { 337namespace ento { 338 template <> 339 struct ProgramStateTrait<RegionState> 340 : public ProgramStatePartialTrait<RegionStateTy> { 341 static void *GDMIndex() { static int x; return &x; } 342 }; 343 344 template <> 345 struct ProgramStateTrait<ReallocPairs> 346 : public ProgramStatePartialTrait<ReallocMap> { 347 static void *GDMIndex() { static int x; return &x; } 348 }; 349} 350} 351 352namespace { 353class StopTrackingCallback : public SymbolVisitor { 354 ProgramStateRef state; 355public: 356 StopTrackingCallback(ProgramStateRef st) : state(st) {} 357 ProgramStateRef getState() const { return state; } 358 359 bool VisitSymbol(SymbolRef sym) { 360 state = state->remove<RegionState>(sym); 361 return true; 362 } 363}; 364} // end anonymous namespace 365 366void MallocChecker::initIdentifierInfo(ASTContext &Ctx) const { 367 if (II_malloc) 368 return; 369 II_malloc = &Ctx.Idents.get("malloc"); 370 II_free = &Ctx.Idents.get("free"); 371 II_realloc = &Ctx.Idents.get("realloc"); 372 II_reallocf = &Ctx.Idents.get("reallocf"); 373 II_calloc = &Ctx.Idents.get("calloc"); 374 II_valloc = &Ctx.Idents.get("valloc"); 375 II_strdup = &Ctx.Idents.get("strdup"); 376 II_strndup = &Ctx.Idents.get("strndup"); 377} 378 379bool MallocChecker::isMemFunction(const FunctionDecl *FD, ASTContext &C) const { 380 if (isFreeFunction(FD, C)) 381 return true; 382 383 if (isAllocationFunction(FD, C)) 384 return true; 385 386 return false; 387} 388 389bool MallocChecker::isAllocationFunction(const FunctionDecl *FD, 390 ASTContext &C) const { 391 if (!FD) 392 return false; 393 394 if (FD->getKind() == Decl::Function) { 395 IdentifierInfo *FunI = FD->getIdentifier(); 396 initIdentifierInfo(C); 397 398 if (FunI == II_malloc || FunI == II_realloc || 399 FunI == II_reallocf || FunI == II_calloc || FunI == II_valloc || 400 FunI == II_strdup || FunI == II_strndup) 401 return true; 402 } 403 404 if (Filter.CMallocOptimistic && FD->hasAttrs()) 405 for (specific_attr_iterator<OwnershipAttr> 406 i = FD->specific_attr_begin<OwnershipAttr>(), 407 e = FD->specific_attr_end<OwnershipAttr>(); 408 i != e; ++i) 409 if ((*i)->getOwnKind() == OwnershipAttr::Returns) 410 return true; 411 return false; 412} 413 414bool MallocChecker::isFreeFunction(const FunctionDecl *FD, ASTContext &C) const { 415 if (!FD) 416 return false; 417 418 if (FD->getKind() == Decl::Function) { 419 IdentifierInfo *FunI = FD->getIdentifier(); 420 initIdentifierInfo(C); 421 422 if (FunI == II_free || FunI == II_realloc || FunI == II_reallocf) 423 return true; 424 } 425 426 if (Filter.CMallocOptimistic && FD->hasAttrs()) 427 for (specific_attr_iterator<OwnershipAttr> 428 i = FD->specific_attr_begin<OwnershipAttr>(), 429 e = FD->specific_attr_end<OwnershipAttr>(); 430 i != e; ++i) 431 if ((*i)->getOwnKind() == OwnershipAttr::Takes || 432 (*i)->getOwnKind() == OwnershipAttr::Holds) 433 return true; 434 return false; 435} 436 437void MallocChecker::checkPostStmt(const CallExpr *CE, CheckerContext &C) const { 438 const FunctionDecl *FD = C.getCalleeDecl(CE); 439 if (!FD) 440 return; 441 442 ProgramStateRef State = C.getState(); 443 bool ReleasedAllocatedMemory = false; 444 445 if (FD->getKind() == Decl::Function) { 446 initIdentifierInfo(C.getASTContext()); 447 IdentifierInfo *FunI = FD->getIdentifier(); 448 449 if (FunI == II_malloc || FunI == II_valloc) { 450 if (CE->getNumArgs() < 1) 451 return; 452 State = MallocMemAux(C, CE, CE->getArg(0), UndefinedVal(), State); 453 } else if (FunI == II_realloc) { 454 State = ReallocMem(C, CE, false); 455 } else if (FunI == II_reallocf) { 456 State = ReallocMem(C, CE, true); 457 } else if (FunI == II_calloc) { 458 State = CallocMem(C, CE); 459 } else if (FunI == II_free) { 460 State = FreeMemAux(C, CE, State, 0, false, ReleasedAllocatedMemory); 461 } else if (FunI == II_strdup) { 462 State = MallocUpdateRefState(C, CE, State); 463 } else if (FunI == II_strndup) { 464 State = MallocUpdateRefState(C, CE, State); 465 } 466 } 467 468 if (Filter.CMallocOptimistic) { 469 // Check all the attributes, if there are any. 470 // There can be multiple of these attributes. 471 if (FD->hasAttrs()) 472 for (specific_attr_iterator<OwnershipAttr> 473 i = FD->specific_attr_begin<OwnershipAttr>(), 474 e = FD->specific_attr_end<OwnershipAttr>(); 475 i != e; ++i) { 476 switch ((*i)->getOwnKind()) { 477 case OwnershipAttr::Returns: 478 State = MallocMemReturnsAttr(C, CE, *i); 479 break; 480 case OwnershipAttr::Takes: 481 case OwnershipAttr::Holds: 482 State = FreeMemAttr(C, CE, *i); 483 break; 484 } 485 } 486 } 487 C.addTransition(State); 488} 489 490static bool isFreeWhenDoneSetToZero(const ObjCMethodCall &Call) { 491 Selector S = Call.getSelector(); 492 for (unsigned i = 1; i < S.getNumArgs(); ++i) 493 if (S.getNameForSlot(i).equals("freeWhenDone")) 494 if (Call.getArgSVal(i).isConstant(0)) 495 return true; 496 497 return false; 498} 499 500void MallocChecker::checkPreObjCMessage(const ObjCMethodCall &Call, 501 CheckerContext &C) const { 502 // If the first selector is dataWithBytesNoCopy, assume that the memory will 503 // be released with 'free' by the new object. 504 // Ex: [NSData dataWithBytesNoCopy:bytes length:10]; 505 // Unless 'freeWhenDone' param set to 0. 506 // TODO: Check that the memory was allocated with malloc. 507 bool ReleasedAllocatedMemory = false; 508 Selector S = Call.getSelector(); 509 if ((S.getNameForSlot(0) == "dataWithBytesNoCopy" || 510 S.getNameForSlot(0) == "initWithBytesNoCopy" || 511 S.getNameForSlot(0) == "initWithCharactersNoCopy") && 512 !isFreeWhenDoneSetToZero(Call)){ 513 unsigned int argIdx = 0; 514 C.addTransition(FreeMemAux(C, Call.getArgExpr(argIdx), 515 Call.getOriginExpr(), C.getState(), true, 516 ReleasedAllocatedMemory)); 517 } 518} 519 520ProgramStateRef MallocChecker::MallocMemReturnsAttr(CheckerContext &C, 521 const CallExpr *CE, 522 const OwnershipAttr* Att) { 523 if (Att->getModule() != "malloc") 524 return 0; 525 526 OwnershipAttr::args_iterator I = Att->args_begin(), E = Att->args_end(); 527 if (I != E) { 528 return MallocMemAux(C, CE, CE->getArg(*I), UndefinedVal(), C.getState()); 529 } 530 return MallocMemAux(C, CE, UnknownVal(), UndefinedVal(), C.getState()); 531} 532 533ProgramStateRef MallocChecker::MallocMemAux(CheckerContext &C, 534 const CallExpr *CE, 535 SVal Size, SVal Init, 536 ProgramStateRef state) { 537 538 // Bind the return value to the symbolic value from the heap region. 539 // TODO: We could rewrite post visit to eval call; 'malloc' does not have 540 // side effects other than what we model here. 541 unsigned Count = C.blockCount(); 542 SValBuilder &svalBuilder = C.getSValBuilder(); 543 const LocationContext *LCtx = C.getPredecessor()->getLocationContext(); 544 DefinedSVal RetVal = 545 cast<DefinedSVal>(svalBuilder.getConjuredHeapSymbolVal(CE, LCtx, Count)); 546 state = state->BindExpr(CE, C.getLocationContext(), RetVal); 547 548 // We expect the malloc functions to return a pointer. 549 if (!isa<Loc>(RetVal)) 550 return 0; 551 552 // Fill the region with the initialization value. 553 state = state->bindDefault(RetVal, Init); 554 555 // Set the region's extent equal to the Size parameter. 556 const SymbolicRegion *R = 557 dyn_cast_or_null<SymbolicRegion>(RetVal.getAsRegion()); 558 if (!R) 559 return 0; 560 if (isa<DefinedOrUnknownSVal>(Size)) { 561 SValBuilder &svalBuilder = C.getSValBuilder(); 562 DefinedOrUnknownSVal Extent = R->getExtent(svalBuilder); 563 DefinedOrUnknownSVal DefinedSize = cast<DefinedOrUnknownSVal>(Size); 564 DefinedOrUnknownSVal extentMatchesSize = 565 svalBuilder.evalEQ(state, Extent, DefinedSize); 566 567 state = state->assume(extentMatchesSize, true); 568 assert(state); 569 } 570 571 return MallocUpdateRefState(C, CE, state); 572} 573 574ProgramStateRef MallocChecker::MallocUpdateRefState(CheckerContext &C, 575 const CallExpr *CE, 576 ProgramStateRef state) { 577 // Get the return value. 578 SVal retVal = state->getSVal(CE, C.getLocationContext()); 579 580 // We expect the malloc functions to return a pointer. 581 if (!isa<Loc>(retVal)) 582 return 0; 583 584 SymbolRef Sym = retVal.getAsLocSymbol(); 585 assert(Sym); 586 587 // Set the symbol's state to Allocated. 588 return state->set<RegionState>(Sym, RefState::getAllocated(CE)); 589 590} 591 592ProgramStateRef MallocChecker::FreeMemAttr(CheckerContext &C, 593 const CallExpr *CE, 594 const OwnershipAttr* Att) const { 595 if (Att->getModule() != "malloc") 596 return 0; 597 598 ProgramStateRef State = C.getState(); 599 bool ReleasedAllocated = false; 600 601 for (OwnershipAttr::args_iterator I = Att->args_begin(), E = Att->args_end(); 602 I != E; ++I) { 603 ProgramStateRef StateI = FreeMemAux(C, CE, State, *I, 604 Att->getOwnKind() == OwnershipAttr::Holds, 605 ReleasedAllocated); 606 if (StateI) 607 State = StateI; 608 } 609 return State; 610} 611 612ProgramStateRef MallocChecker::FreeMemAux(CheckerContext &C, 613 const CallExpr *CE, 614 ProgramStateRef state, 615 unsigned Num, 616 bool Hold, 617 bool &ReleasedAllocated) const { 618 if (CE->getNumArgs() < (Num + 1)) 619 return 0; 620 621 return FreeMemAux(C, CE->getArg(Num), CE, state, Hold, ReleasedAllocated); 622} 623 624ProgramStateRef MallocChecker::FreeMemAux(CheckerContext &C, 625 const Expr *ArgExpr, 626 const Expr *ParentExpr, 627 ProgramStateRef state, 628 bool Hold, 629 bool &ReleasedAllocated) const { 630 631 SVal ArgVal = state->getSVal(ArgExpr, C.getLocationContext()); 632 if (!isa<DefinedOrUnknownSVal>(ArgVal)) 633 return 0; 634 DefinedOrUnknownSVal location = cast<DefinedOrUnknownSVal>(ArgVal); 635 636 // Check for null dereferences. 637 if (!isa<Loc>(location)) 638 return 0; 639 640 // The explicit NULL case, no operation is performed. 641 ProgramStateRef notNullState, nullState; 642 llvm::tie(notNullState, nullState) = state->assume(location); 643 if (nullState && !notNullState) 644 return 0; 645 646 // Unknown values could easily be okay 647 // Undefined values are handled elsewhere 648 if (ArgVal.isUnknownOrUndef()) 649 return 0; 650 651 const MemRegion *R = ArgVal.getAsRegion(); 652 653 // Nonlocs can't be freed, of course. 654 // Non-region locations (labels and fixed addresses) also shouldn't be freed. 655 if (!R) { 656 ReportBadFree(C, ArgVal, ArgExpr->getSourceRange()); 657 return 0; 658 } 659 660 R = R->StripCasts(); 661 662 // Blocks might show up as heap data, but should not be free()d 663 if (isa<BlockDataRegion>(R)) { 664 ReportBadFree(C, ArgVal, ArgExpr->getSourceRange()); 665 return 0; 666 } 667 668 const MemSpaceRegion *MS = R->getMemorySpace(); 669 670 // Parameters, locals, statics, and globals shouldn't be freed. 671 if (!(isa<UnknownSpaceRegion>(MS) || isa<HeapSpaceRegion>(MS))) { 672 // FIXME: at the time this code was written, malloc() regions were 673 // represented by conjured symbols, which are all in UnknownSpaceRegion. 674 // This means that there isn't actually anything from HeapSpaceRegion 675 // that should be freed, even though we allow it here. 676 // Of course, free() can work on memory allocated outside the current 677 // function, so UnknownSpaceRegion is always a possibility. 678 // False negatives are better than false positives. 679 680 ReportBadFree(C, ArgVal, ArgExpr->getSourceRange()); 681 return 0; 682 } 683 684 const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R); 685 // Various cases could lead to non-symbol values here. 686 // For now, ignore them. 687 if (!SR) 688 return 0; 689 690 SymbolRef Sym = SR->getSymbol(); 691 const RefState *RS = state->get<RegionState>(Sym); 692 693 // Check double free. 694 if (RS && (RS->isReleased() || RS->isRelinquished())) { 695 if (ExplodedNode *N = C.generateSink()) { 696 if (!BT_DoubleFree) 697 BT_DoubleFree.reset( 698 new BugType("Double free", "Memory Error")); 699 BugReport *R = new BugReport(*BT_DoubleFree, 700 (RS->isReleased() ? "Attempt to free released memory" : 701 "Attempt to free non-owned memory"), N); 702 R->addRange(ArgExpr->getSourceRange()); 703 R->markInteresting(Sym); 704 R->addVisitor(new MallocBugVisitor(Sym)); 705 C.EmitReport(R); 706 } 707 return 0; 708 } 709 710 ReleasedAllocated = (RS != 0); 711 712 // Normal free. 713 if (Hold) 714 return state->set<RegionState>(Sym, RefState::getRelinquished(ParentExpr)); 715 return state->set<RegionState>(Sym, RefState::getReleased(ParentExpr)); 716} 717 718bool MallocChecker::SummarizeValue(raw_ostream &os, SVal V) { 719 if (nonloc::ConcreteInt *IntVal = dyn_cast<nonloc::ConcreteInt>(&V)) 720 os << "an integer (" << IntVal->getValue() << ")"; 721 else if (loc::ConcreteInt *ConstAddr = dyn_cast<loc::ConcreteInt>(&V)) 722 os << "a constant address (" << ConstAddr->getValue() << ")"; 723 else if (loc::GotoLabel *Label = dyn_cast<loc::GotoLabel>(&V)) 724 os << "the address of the label '" << Label->getLabel()->getName() << "'"; 725 else 726 return false; 727 728 return true; 729} 730 731bool MallocChecker::SummarizeRegion(raw_ostream &os, 732 const MemRegion *MR) { 733 switch (MR->getKind()) { 734 case MemRegion::FunctionTextRegionKind: { 735 const FunctionDecl *FD = cast<FunctionTextRegion>(MR)->getDecl(); 736 if (FD) 737 os << "the address of the function '" << *FD << '\''; 738 else 739 os << "the address of a function"; 740 return true; 741 } 742 case MemRegion::BlockTextRegionKind: 743 os << "block text"; 744 return true; 745 case MemRegion::BlockDataRegionKind: 746 // FIXME: where the block came from? 747 os << "a block"; 748 return true; 749 default: { 750 const MemSpaceRegion *MS = MR->getMemorySpace(); 751 752 if (isa<StackLocalsSpaceRegion>(MS)) { 753 const VarRegion *VR = dyn_cast<VarRegion>(MR); 754 const VarDecl *VD; 755 if (VR) 756 VD = VR->getDecl(); 757 else 758 VD = NULL; 759 760 if (VD) 761 os << "the address of the local variable '" << VD->getName() << "'"; 762 else 763 os << "the address of a local stack variable"; 764 return true; 765 } 766 767 if (isa<StackArgumentsSpaceRegion>(MS)) { 768 const VarRegion *VR = dyn_cast<VarRegion>(MR); 769 const VarDecl *VD; 770 if (VR) 771 VD = VR->getDecl(); 772 else 773 VD = NULL; 774 775 if (VD) 776 os << "the address of the parameter '" << VD->getName() << "'"; 777 else 778 os << "the address of a parameter"; 779 return true; 780 } 781 782 if (isa<GlobalsSpaceRegion>(MS)) { 783 const VarRegion *VR = dyn_cast<VarRegion>(MR); 784 const VarDecl *VD; 785 if (VR) 786 VD = VR->getDecl(); 787 else 788 VD = NULL; 789 790 if (VD) { 791 if (VD->isStaticLocal()) 792 os << "the address of the static variable '" << VD->getName() << "'"; 793 else 794 os << "the address of the global variable '" << VD->getName() << "'"; 795 } else 796 os << "the address of a global variable"; 797 return true; 798 } 799 800 return false; 801 } 802 } 803} 804 805void MallocChecker::ReportBadFree(CheckerContext &C, SVal ArgVal, 806 SourceRange range) const { 807 if (ExplodedNode *N = C.generateSink()) { 808 if (!BT_BadFree) 809 BT_BadFree.reset(new BugType("Bad free", "Memory Error")); 810 811 SmallString<100> buf; 812 llvm::raw_svector_ostream os(buf); 813 814 const MemRegion *MR = ArgVal.getAsRegion(); 815 if (MR) { 816 while (const ElementRegion *ER = dyn_cast<ElementRegion>(MR)) 817 MR = ER->getSuperRegion(); 818 819 // Special case for alloca() 820 if (isa<AllocaRegion>(MR)) 821 os << "Argument to free() was allocated by alloca(), not malloc()"; 822 else { 823 os << "Argument to free() is "; 824 if (SummarizeRegion(os, MR)) 825 os << ", which is not memory allocated by malloc()"; 826 else 827 os << "not memory allocated by malloc()"; 828 } 829 } else { 830 os << "Argument to free() is "; 831 if (SummarizeValue(os, ArgVal)) 832 os << ", which is not memory allocated by malloc()"; 833 else 834 os << "not memory allocated by malloc()"; 835 } 836 837 BugReport *R = new BugReport(*BT_BadFree, os.str(), N); 838 R->markInteresting(MR); 839 R->addRange(range); 840 C.EmitReport(R); 841 } 842} 843 844ProgramStateRef MallocChecker::ReallocMem(CheckerContext &C, 845 const CallExpr *CE, 846 bool FreesOnFail) const { 847 if (CE->getNumArgs() < 2) 848 return 0; 849 850 ProgramStateRef state = C.getState(); 851 const Expr *arg0Expr = CE->getArg(0); 852 const LocationContext *LCtx = C.getLocationContext(); 853 SVal Arg0Val = state->getSVal(arg0Expr, LCtx); 854 if (!isa<DefinedOrUnknownSVal>(Arg0Val)) 855 return 0; 856 DefinedOrUnknownSVal arg0Val = cast<DefinedOrUnknownSVal>(Arg0Val); 857 858 SValBuilder &svalBuilder = C.getSValBuilder(); 859 860 DefinedOrUnknownSVal PtrEQ = 861 svalBuilder.evalEQ(state, arg0Val, svalBuilder.makeNull()); 862 863 // Get the size argument. If there is no size arg then give up. 864 const Expr *Arg1 = CE->getArg(1); 865 if (!Arg1) 866 return 0; 867 868 // Get the value of the size argument. 869 SVal Arg1ValG = state->getSVal(Arg1, LCtx); 870 if (!isa<DefinedOrUnknownSVal>(Arg1ValG)) 871 return 0; 872 DefinedOrUnknownSVal Arg1Val = cast<DefinedOrUnknownSVal>(Arg1ValG); 873 874 // Compare the size argument to 0. 875 DefinedOrUnknownSVal SizeZero = 876 svalBuilder.evalEQ(state, Arg1Val, 877 svalBuilder.makeIntValWithPtrWidth(0, false)); 878 879 ProgramStateRef StatePtrIsNull, StatePtrNotNull; 880 llvm::tie(StatePtrIsNull, StatePtrNotNull) = state->assume(PtrEQ); 881 ProgramStateRef StateSizeIsZero, StateSizeNotZero; 882 llvm::tie(StateSizeIsZero, StateSizeNotZero) = state->assume(SizeZero); 883 // We only assume exceptional states if they are definitely true; if the 884 // state is under-constrained, assume regular realloc behavior. 885 bool PrtIsNull = StatePtrIsNull && !StatePtrNotNull; 886 bool SizeIsZero = StateSizeIsZero && !StateSizeNotZero; 887 888 // If the ptr is NULL and the size is not 0, the call is equivalent to 889 // malloc(size). 890 if ( PrtIsNull && !SizeIsZero) { 891 ProgramStateRef stateMalloc = MallocMemAux(C, CE, CE->getArg(1), 892 UndefinedVal(), StatePtrIsNull); 893 return stateMalloc; 894 } 895 896 if (PrtIsNull && SizeIsZero) 897 return 0; 898 899 // Get the from and to pointer symbols as in toPtr = realloc(fromPtr, size). 900 assert(!PrtIsNull); 901 SymbolRef FromPtr = arg0Val.getAsSymbol(); 902 SVal RetVal = state->getSVal(CE, LCtx); 903 SymbolRef ToPtr = RetVal.getAsSymbol(); 904 if (!FromPtr || !ToPtr) 905 return 0; 906 907 bool ReleasedAllocated = false; 908 909 // If the size is 0, free the memory. 910 if (SizeIsZero) 911 if (ProgramStateRef stateFree = FreeMemAux(C, CE, StateSizeIsZero, 0, 912 false, ReleasedAllocated)){ 913 // The semantics of the return value are: 914 // If size was equal to 0, either NULL or a pointer suitable to be passed 915 // to free() is returned. We just free the input pointer and do not add 916 // any constrains on the output pointer. 917 return stateFree; 918 } 919 920 // Default behavior. 921 if (ProgramStateRef stateFree = 922 FreeMemAux(C, CE, state, 0, false, ReleasedAllocated)) { 923 924 ProgramStateRef stateRealloc = MallocMemAux(C, CE, CE->getArg(1), 925 UnknownVal(), stateFree); 926 if (!stateRealloc) 927 return 0; 928 929 // Record the info about the reallocated symbol so that we could properly 930 // process failed reallocation. 931 stateRealloc = stateRealloc->set<ReallocPairs>(ToPtr, 932 ReallocPair(FromPtr, FreesOnFail || !ReleasedAllocated)); 933 // The reallocated symbol should stay alive for as long as the new symbol. 934 C.getSymbolManager().addSymbolDependency(ToPtr, FromPtr); 935 return stateRealloc; 936 } 937 return 0; 938} 939 940ProgramStateRef MallocChecker::CallocMem(CheckerContext &C, const CallExpr *CE){ 941 if (CE->getNumArgs() < 2) 942 return 0; 943 944 ProgramStateRef state = C.getState(); 945 SValBuilder &svalBuilder = C.getSValBuilder(); 946 const LocationContext *LCtx = C.getLocationContext(); 947 SVal count = state->getSVal(CE->getArg(0), LCtx); 948 SVal elementSize = state->getSVal(CE->getArg(1), LCtx); 949 SVal TotalSize = svalBuilder.evalBinOp(state, BO_Mul, count, elementSize, 950 svalBuilder.getContext().getSizeType()); 951 SVal zeroVal = svalBuilder.makeZeroVal(svalBuilder.getContext().CharTy); 952 953 return MallocMemAux(C, CE, TotalSize, zeroVal, state); 954} 955 956LeakInfo 957MallocChecker::getAllocationSite(const ExplodedNode *N, SymbolRef Sym, 958 CheckerContext &C) const { 959 const LocationContext *LeakContext = N->getLocationContext(); 960 // Walk the ExplodedGraph backwards and find the first node that referred to 961 // the tracked symbol. 962 const ExplodedNode *AllocNode = N; 963 const MemRegion *ReferenceRegion = 0; 964 965 while (N) { 966 ProgramStateRef State = N->getState(); 967 if (!State->get<RegionState>(Sym)) 968 break; 969 970 // Find the most recent expression bound to the symbol in the current 971 // context. 972 if (!ReferenceRegion) { 973 if (const MemRegion *MR = C.getLocationRegionIfPostStore(N)) { 974 SVal Val = State->getSVal(MR); 975 if (Val.getAsLocSymbol() == Sym) 976 ReferenceRegion = MR; 977 } 978 } 979 980 // Allocation node, is the last node in the current context in which the 981 // symbol was tracked. 982 if (N->getLocationContext() == LeakContext) 983 AllocNode = N; 984 N = N->pred_empty() ? NULL : *(N->pred_begin()); 985 } 986 987 ProgramPoint P = AllocNode->getLocation(); 988 const Stmt *AllocationStmt = 0; 989 if (CallExitEnd *Exit = dyn_cast<CallExitEnd>(&P)) 990 AllocationStmt = Exit->getCalleeContext()->getCallSite(); 991 else if (StmtPoint *SP = dyn_cast<StmtPoint>(&P)) 992 AllocationStmt = SP->getStmt(); 993 994 return LeakInfo(AllocationStmt, ReferenceRegion); 995} 996 997void MallocChecker::reportLeak(SymbolRef Sym, ExplodedNode *N, 998 CheckerContext &C) const { 999 assert(N); 1000 if (!BT_Leak) { 1001 BT_Leak.reset(new BugType("Memory leak", "Memory Error")); 1002 // Leaks should not be reported if they are post-dominated by a sink: 1003 // (1) Sinks are higher importance bugs. 1004 // (2) NoReturnFunctionChecker uses sink nodes to represent paths ending 1005 // with __noreturn functions such as assert() or exit(). We choose not 1006 // to report leaks on such paths. 1007 BT_Leak->setSuppressOnSink(true); 1008 } 1009 1010 // Most bug reports are cached at the location where they occurred. 1011 // With leaks, we want to unique them by the location where they were 1012 // allocated, and only report a single path. 1013 PathDiagnosticLocation LocUsedForUniqueing; 1014 const Stmt *AllocStmt = 0; 1015 const MemRegion *Region = 0; 1016 llvm::tie(AllocStmt, Region) = getAllocationSite(N, Sym, C); 1017 if (AllocStmt) 1018 LocUsedForUniqueing = PathDiagnosticLocation::createBegin(AllocStmt, 1019 C.getSourceManager(), N->getLocationContext()); 1020 1021 SmallString<200> buf; 1022 llvm::raw_svector_ostream os(buf); 1023 os << "Memory is never released; potential leak"; 1024 if (Region && Region->canPrintPretty()) { 1025 os << " of memory pointed to by '"; 1026 Region->printPretty(os); 1027 os << '\''; 1028 } 1029 1030 BugReport *R = new BugReport(*BT_Leak, os.str(), N, LocUsedForUniqueing); 1031 R->markInteresting(Sym); 1032 R->addVisitor(new MallocBugVisitor(Sym, true)); 1033 C.EmitReport(R); 1034} 1035 1036void MallocChecker::checkDeadSymbols(SymbolReaper &SymReaper, 1037 CheckerContext &C) const 1038{ 1039 if (!SymReaper.hasDeadSymbols()) 1040 return; 1041 1042 ProgramStateRef state = C.getState(); 1043 RegionStateTy RS = state->get<RegionState>(); 1044 RegionStateTy::Factory &F = state->get_context<RegionState>(); 1045 1046 bool generateReport = false; 1047 llvm::SmallVector<SymbolRef, 2> Errors; 1048 for (RegionStateTy::iterator I = RS.begin(), E = RS.end(); I != E; ++I) { 1049 if (SymReaper.isDead(I->first)) { 1050 if (I->second.isAllocated()) { 1051 generateReport = true; 1052 Errors.push_back(I->first); 1053 } 1054 // Remove the dead symbol from the map. 1055 RS = F.remove(RS, I->first); 1056 1057 } 1058 } 1059 1060 // Cleanup the Realloc Pairs Map. 1061 ReallocMap RP = state->get<ReallocPairs>(); 1062 for (ReallocMap::iterator I = RP.begin(), E = RP.end(); I != E; ++I) { 1063 if (SymReaper.isDead(I->first) || 1064 SymReaper.isDead(I->second.ReallocatedSym)) { 1065 state = state->remove<ReallocPairs>(I->first); 1066 } 1067 } 1068 1069 // Generate leak node. 1070 static SimpleProgramPointTag Tag("MallocChecker : DeadSymbolsLeak"); 1071 ExplodedNode *N = C.addTransition(C.getState(), C.getPredecessor(), &Tag); 1072 1073 if (generateReport) { 1074 for (llvm::SmallVector<SymbolRef, 2>::iterator 1075 I = Errors.begin(), E = Errors.end(); I != E; ++I) { 1076 reportLeak(*I, N, C); 1077 } 1078 } 1079 C.addTransition(state->set<RegionState>(RS), N); 1080} 1081 1082void MallocChecker::checkEndPath(CheckerContext &C) const { 1083 ProgramStateRef state = C.getState(); 1084 RegionStateTy M = state->get<RegionState>(); 1085 1086 // If inside inlined call, skip it. 1087 if (C.getLocationContext()->getParent() != 0) 1088 return; 1089 1090 for (RegionStateTy::iterator I = M.begin(), E = M.end(); I != E; ++I) { 1091 RefState RS = I->second; 1092 if (RS.isAllocated()) { 1093 ExplodedNode *N = C.addTransition(state); 1094 if (N) 1095 reportLeak(I->first, N, C); 1096 } 1097 } 1098} 1099 1100void MallocChecker::checkPreStmt(const CallExpr *CE, CheckerContext &C) const { 1101 // We will check for double free in the post visit. 1102 if (isFreeFunction(C.getCalleeDecl(CE), C.getASTContext())) 1103 return; 1104 1105 // Check use after free, when a freed pointer is passed to a call. 1106 ProgramStateRef State = C.getState(); 1107 for (CallExpr::const_arg_iterator I = CE->arg_begin(), 1108 E = CE->arg_end(); I != E; ++I) { 1109 const Expr *A = *I; 1110 if (A->getType().getTypePtr()->isAnyPointerType()) { 1111 SymbolRef Sym = State->getSVal(A, C.getLocationContext()).getAsSymbol(); 1112 if (!Sym) 1113 continue; 1114 if (checkUseAfterFree(Sym, C, A)) 1115 return; 1116 } 1117 } 1118} 1119 1120void MallocChecker::checkPreStmt(const ReturnStmt *S, CheckerContext &C) const { 1121 const Expr *E = S->getRetValue(); 1122 if (!E) 1123 return; 1124 1125 // Check if we are returning a symbol. 1126 ProgramStateRef State = C.getState(); 1127 SVal RetVal = State->getSVal(E, C.getLocationContext()); 1128 SymbolRef Sym = RetVal.getAsSymbol(); 1129 if (!Sym) 1130 // If we are returning a field of the allocated struct or an array element, 1131 // the callee could still free the memory. 1132 // TODO: This logic should be a part of generic symbol escape callback. 1133 if (const MemRegion *MR = RetVal.getAsRegion()) 1134 if (isa<FieldRegion>(MR) || isa<ElementRegion>(MR)) 1135 if (const SymbolicRegion *BMR = 1136 dyn_cast<SymbolicRegion>(MR->getBaseRegion())) 1137 Sym = BMR->getSymbol(); 1138 1139 // Check if we are returning freed memory. 1140 if (Sym) 1141 if (checkUseAfterFree(Sym, C, E)) 1142 return; 1143 1144 // If this function body is not inlined, stop tracking any returned symbols. 1145 if (C.getLocationContext()->getParent() == 0) { 1146 State = 1147 State->scanReachableSymbols<StopTrackingCallback>(RetVal).getState(); 1148 C.addTransition(State); 1149 } 1150} 1151 1152// TODO: Blocks should be either inlined or should call invalidate regions 1153// upon invocation. After that's in place, special casing here will not be 1154// needed. 1155void MallocChecker::checkPostStmt(const BlockExpr *BE, 1156 CheckerContext &C) const { 1157 1158 // Scan the BlockDecRefExprs for any object the retain count checker 1159 // may be tracking. 1160 if (!BE->getBlockDecl()->hasCaptures()) 1161 return; 1162 1163 ProgramStateRef state = C.getState(); 1164 const BlockDataRegion *R = 1165 cast<BlockDataRegion>(state->getSVal(BE, 1166 C.getLocationContext()).getAsRegion()); 1167 1168 BlockDataRegion::referenced_vars_iterator I = R->referenced_vars_begin(), 1169 E = R->referenced_vars_end(); 1170 1171 if (I == E) 1172 return; 1173 1174 SmallVector<const MemRegion*, 10> Regions; 1175 const LocationContext *LC = C.getLocationContext(); 1176 MemRegionManager &MemMgr = C.getSValBuilder().getRegionManager(); 1177 1178 for ( ; I != E; ++I) { 1179 const VarRegion *VR = *I; 1180 if (VR->getSuperRegion() == R) { 1181 VR = MemMgr.getVarRegion(VR->getDecl(), LC); 1182 } 1183 Regions.push_back(VR); 1184 } 1185 1186 state = 1187 state->scanReachableSymbols<StopTrackingCallback>(Regions.data(), 1188 Regions.data() + Regions.size()).getState(); 1189 C.addTransition(state); 1190} 1191 1192bool MallocChecker::isReleased(SymbolRef Sym, CheckerContext &C) const { 1193 assert(Sym); 1194 const RefState *RS = C.getState()->get<RegionState>(Sym); 1195 return (RS && RS->isReleased()); 1196} 1197 1198bool MallocChecker::checkUseAfterFree(SymbolRef Sym, CheckerContext &C, 1199 const Stmt *S) const { 1200 if (isReleased(Sym, C)) { 1201 if (ExplodedNode *N = C.generateSink()) { 1202 if (!BT_UseFree) 1203 BT_UseFree.reset(new BugType("Use-after-free", "Memory Error")); 1204 1205 BugReport *R = new BugReport(*BT_UseFree, 1206 "Use of memory after it is freed",N); 1207 if (S) 1208 R->addRange(S->getSourceRange()); 1209 R->markInteresting(Sym); 1210 R->addVisitor(new MallocBugVisitor(Sym)); 1211 C.EmitReport(R); 1212 return true; 1213 } 1214 } 1215 return false; 1216} 1217 1218// Check if the location is a freed symbolic region. 1219void MallocChecker::checkLocation(SVal l, bool isLoad, const Stmt *S, 1220 CheckerContext &C) const { 1221 SymbolRef Sym = l.getLocSymbolInBase(); 1222 if (Sym) 1223 checkUseAfterFree(Sym, C, S); 1224} 1225 1226//===----------------------------------------------------------------------===// 1227// Check various ways a symbol can be invalidated. 1228// TODO: This logic (the next 3 functions) is copied/similar to the 1229// RetainRelease checker. We might want to factor this out. 1230//===----------------------------------------------------------------------===// 1231 1232// Stop tracking symbols when a value escapes as a result of checkBind. 1233// A value escapes in three possible cases: 1234// (1) we are binding to something that is not a memory region. 1235// (2) we are binding to a memregion that does not have stack storage 1236// (3) we are binding to a memregion with stack storage that the store 1237// does not understand. 1238void MallocChecker::checkBind(SVal loc, SVal val, const Stmt *S, 1239 CheckerContext &C) const { 1240 // Are we storing to something that causes the value to "escape"? 1241 bool escapes = true; 1242 ProgramStateRef state = C.getState(); 1243 1244 if (loc::MemRegionVal *regionLoc = dyn_cast<loc::MemRegionVal>(&loc)) { 1245 escapes = !regionLoc->getRegion()->hasStackStorage(); 1246 1247 if (!escapes) { 1248 // To test (3), generate a new state with the binding added. If it is 1249 // the same state, then it escapes (since the store cannot represent 1250 // the binding). 1251 // Do this only if we know that the store is not supposed to generate the 1252 // same state. 1253 SVal StoredVal = state->getSVal(regionLoc->getRegion()); 1254 if (StoredVal != val) 1255 escapes = (state == (state->bindLoc(*regionLoc, val))); 1256 } 1257 } 1258 1259 // If our store can represent the binding and we aren't storing to something 1260 // that doesn't have local storage then just return and have the simulation 1261 // state continue as is. 1262 if (!escapes) 1263 return; 1264 1265 // Otherwise, find all symbols referenced by 'val' that we are tracking 1266 // and stop tracking them. 1267 state = state->scanReachableSymbols<StopTrackingCallback>(val).getState(); 1268 C.addTransition(state); 1269} 1270 1271// If a symbolic region is assumed to NULL (or another constant), stop tracking 1272// it - assuming that allocation failed on this path. 1273ProgramStateRef MallocChecker::evalAssume(ProgramStateRef state, 1274 SVal Cond, 1275 bool Assumption) const { 1276 RegionStateTy RS = state->get<RegionState>(); 1277 for (RegionStateTy::iterator I = RS.begin(), E = RS.end(); I != E; ++I) { 1278 // If the symbol is assumed to be NULL, remove it from consideration. 1279 if (state->getConstraintManager().isNull(state, I.getKey()).isTrue()) 1280 state = state->remove<RegionState>(I.getKey()); 1281 } 1282 1283 // Realloc returns 0 when reallocation fails, which means that we should 1284 // restore the state of the pointer being reallocated. 1285 ReallocMap RP = state->get<ReallocPairs>(); 1286 for (ReallocMap::iterator I = RP.begin(), E = RP.end(); I != E; ++I) { 1287 // If the symbol is assumed to be NULL, remove it from consideration. 1288 if (state->getConstraintManager().isNull(state, I.getKey()).isTrue()) { 1289 SymbolRef ReallocSym = I.getData().ReallocatedSym; 1290 if (const RefState *RS = state->get<RegionState>(ReallocSym)) { 1291 if (RS->isReleased() && ! I.getData().IsFreeOnFailure) 1292 state = state->set<RegionState>(ReallocSym, 1293 RefState::getAllocated(RS->getStmt())); 1294 } 1295 state = state->remove<ReallocPairs>(I.getKey()); 1296 } 1297 } 1298 1299 return state; 1300} 1301 1302// Check if the function is known to us. So, for example, we could 1303// conservatively assume it can free/reallocate its pointer arguments. 1304// (We assume that the pointers cannot escape through calls to system 1305// functions not handled by this checker.) 1306bool MallocChecker::doesNotFreeMemory(const CallEvent *Call, 1307 ProgramStateRef State) const { 1308 assert(Call); 1309 1310 // For now, assume that any C++ call can free memory. 1311 // TODO: If we want to be more optimistic here, we'll need to make sure that 1312 // regions escape to C++ containers. They seem to do that even now, but for 1313 // mysterious reasons. 1314 if (!(isa<FunctionCall>(Call) || isa<ObjCMethodCall>(Call))) 1315 return false; 1316 1317 // Check Objective-C messages by selector name. 1318 if (const ObjCMethodCall *Msg = dyn_cast<ObjCMethodCall>(Call)) { 1319 // If it's not a framework call, or if it takes a callback, assume it 1320 // can free memory. 1321 if (!Call->isInSystemHeader() || Call->hasNonZeroCallbackArg()) 1322 return false; 1323 1324 Selector S = Msg->getSelector(); 1325 1326 // Whitelist the ObjC methods which do free memory. 1327 // - Anything containing 'freeWhenDone' param set to 1. 1328 // Ex: dataWithBytesNoCopy:length:freeWhenDone. 1329 for (unsigned i = 1; i < S.getNumArgs(); ++i) { 1330 if (S.getNameForSlot(i).equals("freeWhenDone")) { 1331 if (Call->getArgSVal(i).isConstant(1)) 1332 return false; 1333 else 1334 return true; 1335 } 1336 } 1337 1338 // If the first selector ends with NoCopy, assume that the ownership is 1339 // transferred as well. 1340 // Ex: [NSData dataWithBytesNoCopy:bytes length:10]; 1341 StringRef FirstSlot = S.getNameForSlot(0); 1342 if (FirstSlot.endswith("NoCopy")) 1343 return false; 1344 1345 // If the first selector starts with addPointer, insertPointer, 1346 // or replacePointer, assume we are dealing with NSPointerArray or similar. 1347 // This is similar to C++ containers (vector); we still might want to check 1348 // that the pointers get freed by following the container itself. 1349 if (FirstSlot.startswith("addPointer") || 1350 FirstSlot.startswith("insertPointer") || 1351 FirstSlot.startswith("replacePointer")) { 1352 return false; 1353 } 1354 1355 // Otherwise, assume that the method does not free memory. 1356 // Most framework methods do not free memory. 1357 return true; 1358 } 1359 1360 // At this point the only thing left to handle is straight function calls. 1361 const FunctionDecl *FD = cast<FunctionCall>(Call)->getDecl(); 1362 if (!FD) 1363 return false; 1364 1365 ASTContext &ASTC = State->getStateManager().getContext(); 1366 1367 // If it's one of the allocation functions we can reason about, we model 1368 // its behavior explicitly. 1369 if (isMemFunction(FD, ASTC)) 1370 return true; 1371 1372 // If it's not a system call, assume it frees memory. 1373 if (!Call->isInSystemHeader()) 1374 return false; 1375 1376 // White list the system functions whose arguments escape. 1377 const IdentifierInfo *II = FD->getIdentifier(); 1378 if (!II) 1379 return false; 1380 StringRef FName = II->getName(); 1381 1382 // White list the 'XXXNoCopy' CoreFoundation functions. 1383 // We specifically check these before 1384 if (FName.endswith("NoCopy")) { 1385 // Look for the deallocator argument. We know that the memory ownership 1386 // is not transferred only if the deallocator argument is 1387 // 'kCFAllocatorNull'. 1388 for (unsigned i = 1; i < Call->getNumArgs(); ++i) { 1389 const Expr *ArgE = Call->getArgExpr(i)->IgnoreParenCasts(); 1390 if (const DeclRefExpr *DE = dyn_cast<DeclRefExpr>(ArgE)) { 1391 StringRef DeallocatorName = DE->getFoundDecl()->getName(); 1392 if (DeallocatorName == "kCFAllocatorNull") 1393 return true; 1394 } 1395 } 1396 return false; 1397 } 1398 1399 // Associating streams with malloced buffers. The pointer can escape if 1400 // 'closefn' is specified (and if that function does free memory), 1401 // but it will not if closefn is not specified. 1402 // Currently, we do not inspect the 'closefn' function (PR12101). 1403 if (FName == "funopen") 1404 if (Call->getNumArgs() >= 4 && Call->getArgSVal(4).isConstant(0)) 1405 return true; 1406 1407 // Do not warn on pointers passed to 'setbuf' when used with std streams, 1408 // these leaks might be intentional when setting the buffer for stdio. 1409 // http://stackoverflow.com/questions/2671151/who-frees-setvbuf-buffer 1410 if (FName == "setbuf" || FName =="setbuffer" || 1411 FName == "setlinebuf" || FName == "setvbuf") { 1412 if (Call->getNumArgs() >= 1) { 1413 const Expr *ArgE = Call->getArgExpr(0)->IgnoreParenCasts(); 1414 if (const DeclRefExpr *ArgDRE = dyn_cast<DeclRefExpr>(ArgE)) 1415 if (const VarDecl *D = dyn_cast<VarDecl>(ArgDRE->getDecl())) 1416 if (D->getCanonicalDecl()->getName().find("std") != StringRef::npos) 1417 return false; 1418 } 1419 } 1420 1421 // A bunch of other functions which either take ownership of a pointer or 1422 // wrap the result up in a struct or object, meaning it can be freed later. 1423 // (See RetainCountChecker.) Not all the parameters here are invalidated, 1424 // but the Malloc checker cannot differentiate between them. The right way 1425 // of doing this would be to implement a pointer escapes callback. 1426 if (FName == "CGBitmapContextCreate" || 1427 FName == "CGBitmapContextCreateWithData" || 1428 FName == "CVPixelBufferCreateWithBytes" || 1429 FName == "CVPixelBufferCreateWithPlanarBytes" || 1430 FName == "OSAtomicEnqueue") { 1431 return false; 1432 } 1433 1434 // Handle cases where we know a buffer's /address/ can escape. 1435 // Note that the above checks handle some special cases where we know that 1436 // even though the address escapes, it's still our responsibility to free the 1437 // buffer. 1438 if (Call->argumentsMayEscape()) 1439 return false; 1440 1441 // Otherwise, assume that the function does not free memory. 1442 // Most system calls do not free the memory. 1443 return true; 1444} 1445 1446// If the symbol we are tracking is invalidated, but not explicitly (ex: the &p 1447// escapes, when we are tracking p), do not track the symbol as we cannot reason 1448// about it anymore. 1449ProgramStateRef 1450MallocChecker::checkRegionChanges(ProgramStateRef State, 1451 const StoreManager::InvalidatedSymbols *invalidated, 1452 ArrayRef<const MemRegion *> ExplicitRegions, 1453 ArrayRef<const MemRegion *> Regions, 1454 const CallEvent *Call) const { 1455 if (!invalidated || invalidated->empty()) 1456 return State; 1457 llvm::SmallPtrSet<SymbolRef, 8> WhitelistedSymbols; 1458 1459 // If it's a call which might free or reallocate memory, we assume that all 1460 // regions (explicit and implicit) escaped. 1461 1462 // Otherwise, whitelist explicit pointers; we still can track them. 1463 if (!Call || doesNotFreeMemory(Call, State)) { 1464 for (ArrayRef<const MemRegion *>::iterator I = ExplicitRegions.begin(), 1465 E = ExplicitRegions.end(); I != E; ++I) { 1466 if (const SymbolicRegion *R = (*I)->StripCasts()->getAs<SymbolicRegion>()) 1467 WhitelistedSymbols.insert(R->getSymbol()); 1468 } 1469 } 1470 1471 for (StoreManager::InvalidatedSymbols::const_iterator I=invalidated->begin(), 1472 E = invalidated->end(); I!=E; ++I) { 1473 SymbolRef sym = *I; 1474 if (WhitelistedSymbols.count(sym)) 1475 continue; 1476 // The symbol escaped. Note, we assume that if the symbol is released, 1477 // passing it out will result in a use after free. We also keep tracking 1478 // relinquished symbols. 1479 if (const RefState *RS = State->get<RegionState>(sym)) { 1480 if (RS->isAllocated()) 1481 State = State->remove<RegionState>(sym); 1482 } 1483 } 1484 return State; 1485} 1486 1487static SymbolRef findFailedReallocSymbol(ProgramStateRef currState, 1488 ProgramStateRef prevState) { 1489 ReallocMap currMap = currState->get<ReallocPairs>(); 1490 ReallocMap prevMap = prevState->get<ReallocPairs>(); 1491 1492 for (ReallocMap::iterator I = prevMap.begin(), E = prevMap.end(); 1493 I != E; ++I) { 1494 SymbolRef sym = I.getKey(); 1495 if (!currMap.lookup(sym)) 1496 return sym; 1497 } 1498 1499 return NULL; 1500} 1501 1502PathDiagnosticPiece * 1503MallocChecker::MallocBugVisitor::VisitNode(const ExplodedNode *N, 1504 const ExplodedNode *PrevN, 1505 BugReporterContext &BRC, 1506 BugReport &BR) { 1507 ProgramStateRef state = N->getState(); 1508 ProgramStateRef statePrev = PrevN->getState(); 1509 1510 const RefState *RS = state->get<RegionState>(Sym); 1511 const RefState *RSPrev = statePrev->get<RegionState>(Sym); 1512 if (!RS) 1513 return 0; 1514 1515 const Stmt *S = 0; 1516 const char *Msg = 0; 1517 StackHintGeneratorForSymbol *StackHint = 0; 1518 1519 // Retrieve the associated statement. 1520 ProgramPoint ProgLoc = N->getLocation(); 1521 if (StmtPoint *SP = dyn_cast<StmtPoint>(&ProgLoc)) 1522 S = SP->getStmt(); 1523 else if (CallExitEnd *Exit = dyn_cast<CallExitEnd>(&ProgLoc)) 1524 S = Exit->getCalleeContext()->getCallSite(); 1525 // If an assumption was made on a branch, it should be caught 1526 // here by looking at the state transition. 1527 else if (BlockEdge *Edge = dyn_cast<BlockEdge>(&ProgLoc)) { 1528 const CFGBlock *srcBlk = Edge->getSrc(); 1529 S = srcBlk->getTerminator(); 1530 } 1531 if (!S) 1532 return 0; 1533 1534 // FIXME: We will eventually need to handle non-statement-based events 1535 // (__attribute__((cleanup))). 1536 1537 // Find out if this is an interesting point and what is the kind. 1538 if (Mode == Normal) { 1539 if (isAllocated(RS, RSPrev, S)) { 1540 Msg = "Memory is allocated"; 1541 StackHint = new StackHintGeneratorForSymbol(Sym, 1542 "Returned allocated memory"); 1543 } else if (isReleased(RS, RSPrev, S)) { 1544 Msg = "Memory is released"; 1545 StackHint = new StackHintGeneratorForSymbol(Sym, 1546 "Returned released memory"); 1547 } else if (isRelinquished(RS, RSPrev, S)) { 1548 Msg = "Memory ownership is transfered"; 1549 StackHint = new StackHintGeneratorForSymbol(Sym, ""); 1550 } else if (isReallocFailedCheck(RS, RSPrev, S)) { 1551 Mode = ReallocationFailed; 1552 Msg = "Reallocation failed"; 1553 StackHint = new StackHintGeneratorForReallocationFailed(Sym, 1554 "Reallocation failed"); 1555 1556 if (SymbolRef sym = findFailedReallocSymbol(state, statePrev)) { 1557 // Is it possible to fail two reallocs WITHOUT testing in between? 1558 assert((!FailedReallocSymbol || FailedReallocSymbol == sym) && 1559 "We only support one failed realloc at a time."); 1560 BR.markInteresting(sym); 1561 FailedReallocSymbol = sym; 1562 } 1563 } 1564 1565 // We are in a special mode if a reallocation failed later in the path. 1566 } else if (Mode == ReallocationFailed) { 1567 assert(FailedReallocSymbol && "No symbol to look for."); 1568 1569 // Is this is the first appearance of the reallocated symbol? 1570 if (!statePrev->get<RegionState>(FailedReallocSymbol)) { 1571 // We're at the reallocation point. 1572 Msg = "Attempt to reallocate memory"; 1573 StackHint = new StackHintGeneratorForSymbol(Sym, 1574 "Returned reallocated memory"); 1575 FailedReallocSymbol = NULL; 1576 Mode = Normal; 1577 } 1578 } 1579 1580 if (!Msg) 1581 return 0; 1582 assert(StackHint); 1583 1584 // Generate the extra diagnostic. 1585 PathDiagnosticLocation Pos(S, BRC.getSourceManager(), 1586 N->getLocationContext()); 1587 return new PathDiagnosticEventPiece(Pos, Msg, true, StackHint); 1588} 1589 1590void MallocChecker::printState(raw_ostream &Out, ProgramStateRef State, 1591 const char *NL, const char *Sep) const { 1592 1593 RegionStateTy RS = State->get<RegionState>(); 1594 1595 if (!RS.isEmpty()) 1596 Out << "Has Malloc data" << NL; 1597} 1598 1599#define REGISTER_CHECKER(name) \ 1600void ento::register##name(CheckerManager &mgr) {\ 1601 registerCStringCheckerBasic(mgr); \ 1602 mgr.registerChecker<MallocChecker>()->Filter.C##name = true;\ 1603} 1604 1605REGISTER_CHECKER(MallocPessimistic) 1606REGISTER_CHECKER(MallocOptimistic) 1607