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