MallocChecker.cpp revision 785950e59424dca7ce0081bebf13c0acd2c4fff6
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 llvm::SmallVector<SymbolRef, 2> Errors; 1065 for (RegionStateTy::iterator I = RS.begin(), E = RS.end(); I != E; ++I) { 1066 if (SymReaper.isDead(I->first)) { 1067 if (I->second.isAllocated()) 1068 Errors.push_back(I->first); 1069 // Remove the dead symbol from the map. 1070 RS = F.remove(RS, I->first); 1071 1072 } 1073 } 1074 1075 // Cleanup the Realloc Pairs Map. 1076 ReallocMap RP = state->get<ReallocPairs>(); 1077 for (ReallocMap::iterator I = RP.begin(), E = RP.end(); I != E; ++I) { 1078 if (SymReaper.isDead(I->first) || 1079 SymReaper.isDead(I->second.ReallocatedSym)) { 1080 state = state->remove<ReallocPairs>(I->first); 1081 } 1082 } 1083 1084 // Generate leak node. 1085 ExplodedNode *N = C.getPredecessor(); 1086 if (!Errors.empty()) { 1087 static SimpleProgramPointTag Tag("MallocChecker : DeadSymbolsLeak"); 1088 N = C.addTransition(C.getState(), C.getPredecessor(), &Tag); 1089 for (llvm::SmallVector<SymbolRef, 2>::iterator 1090 I = Errors.begin(), E = Errors.end(); I != E; ++I) { 1091 reportLeak(*I, N, C); 1092 } 1093 } 1094 1095 C.addTransition(state->set<RegionState>(RS), N); 1096} 1097 1098void MallocChecker::checkEndPath(CheckerContext &C) const { 1099 ProgramStateRef state = C.getState(); 1100 RegionStateTy M = state->get<RegionState>(); 1101 1102 // If inside inlined call, skip it. 1103 if (C.getLocationContext()->getParent() != 0) 1104 return; 1105 1106 for (RegionStateTy::iterator I = M.begin(), E = M.end(); I != E; ++I) { 1107 RefState RS = I->second; 1108 if (RS.isAllocated()) { 1109 ExplodedNode *N = C.addTransition(state); 1110 if (N) 1111 reportLeak(I->first, N, C); 1112 } 1113 } 1114} 1115 1116void MallocChecker::checkPreStmt(const CallExpr *CE, CheckerContext &C) const { 1117 // We will check for double free in the post visit. 1118 if (isFreeFunction(C.getCalleeDecl(CE), C.getASTContext())) 1119 return; 1120 1121 // Check use after free, when a freed pointer is passed to a call. 1122 ProgramStateRef State = C.getState(); 1123 for (CallExpr::const_arg_iterator I = CE->arg_begin(), 1124 E = CE->arg_end(); I != E; ++I) { 1125 const Expr *A = *I; 1126 if (A->getType().getTypePtr()->isAnyPointerType()) { 1127 SymbolRef Sym = State->getSVal(A, C.getLocationContext()).getAsSymbol(); 1128 if (!Sym) 1129 continue; 1130 if (checkUseAfterFree(Sym, C, A)) 1131 return; 1132 } 1133 } 1134} 1135 1136void MallocChecker::checkPreStmt(const ReturnStmt *S, CheckerContext &C) const { 1137 const Expr *E = S->getRetValue(); 1138 if (!E) 1139 return; 1140 1141 // Check if we are returning a symbol. 1142 ProgramStateRef State = C.getState(); 1143 SVal RetVal = State->getSVal(E, C.getLocationContext()); 1144 SymbolRef Sym = RetVal.getAsSymbol(); 1145 if (!Sym) 1146 // If we are returning a field of the allocated struct or an array element, 1147 // the callee could still free the memory. 1148 // TODO: This logic should be a part of generic symbol escape callback. 1149 if (const MemRegion *MR = RetVal.getAsRegion()) 1150 if (isa<FieldRegion>(MR) || isa<ElementRegion>(MR)) 1151 if (const SymbolicRegion *BMR = 1152 dyn_cast<SymbolicRegion>(MR->getBaseRegion())) 1153 Sym = BMR->getSymbol(); 1154 1155 // Check if we are returning freed memory. 1156 if (Sym) 1157 if (checkUseAfterFree(Sym, C, E)) 1158 return; 1159 1160 // If this function body is not inlined, stop tracking any returned symbols. 1161 if (C.getLocationContext()->getParent() == 0) { 1162 State = 1163 State->scanReachableSymbols<StopTrackingCallback>(RetVal).getState(); 1164 C.addTransition(State); 1165 } 1166} 1167 1168// TODO: Blocks should be either inlined or should call invalidate regions 1169// upon invocation. After that's in place, special casing here will not be 1170// needed. 1171void MallocChecker::checkPostStmt(const BlockExpr *BE, 1172 CheckerContext &C) const { 1173 1174 // Scan the BlockDecRefExprs for any object the retain count checker 1175 // may be tracking. 1176 if (!BE->getBlockDecl()->hasCaptures()) 1177 return; 1178 1179 ProgramStateRef state = C.getState(); 1180 const BlockDataRegion *R = 1181 cast<BlockDataRegion>(state->getSVal(BE, 1182 C.getLocationContext()).getAsRegion()); 1183 1184 BlockDataRegion::referenced_vars_iterator I = R->referenced_vars_begin(), 1185 E = R->referenced_vars_end(); 1186 1187 if (I == E) 1188 return; 1189 1190 SmallVector<const MemRegion*, 10> Regions; 1191 const LocationContext *LC = C.getLocationContext(); 1192 MemRegionManager &MemMgr = C.getSValBuilder().getRegionManager(); 1193 1194 for ( ; I != E; ++I) { 1195 const VarRegion *VR = *I; 1196 if (VR->getSuperRegion() == R) { 1197 VR = MemMgr.getVarRegion(VR->getDecl(), LC); 1198 } 1199 Regions.push_back(VR); 1200 } 1201 1202 state = 1203 state->scanReachableSymbols<StopTrackingCallback>(Regions.data(), 1204 Regions.data() + Regions.size()).getState(); 1205 C.addTransition(state); 1206} 1207 1208bool MallocChecker::isReleased(SymbolRef Sym, CheckerContext &C) const { 1209 assert(Sym); 1210 const RefState *RS = C.getState()->get<RegionState>(Sym); 1211 return (RS && RS->isReleased()); 1212} 1213 1214bool MallocChecker::checkUseAfterFree(SymbolRef Sym, CheckerContext &C, 1215 const Stmt *S) const { 1216 if (isReleased(Sym, C)) { 1217 if (ExplodedNode *N = C.generateSink()) { 1218 if (!BT_UseFree) 1219 BT_UseFree.reset(new BugType("Use-after-free", "Memory Error")); 1220 1221 BugReport *R = new BugReport(*BT_UseFree, 1222 "Use of memory after it is freed",N); 1223 if (S) 1224 R->addRange(S->getSourceRange()); 1225 R->markInteresting(Sym); 1226 R->addVisitor(new MallocBugVisitor(Sym)); 1227 C.emitReport(R); 1228 return true; 1229 } 1230 } 1231 return false; 1232} 1233 1234// Check if the location is a freed symbolic region. 1235void MallocChecker::checkLocation(SVal l, bool isLoad, const Stmt *S, 1236 CheckerContext &C) const { 1237 SymbolRef Sym = l.getLocSymbolInBase(); 1238 if (Sym) 1239 checkUseAfterFree(Sym, C, S); 1240} 1241 1242//===----------------------------------------------------------------------===// 1243// Check various ways a symbol can be invalidated. 1244// TODO: This logic (the next 3 functions) is copied/similar to the 1245// RetainRelease checker. We might want to factor this out. 1246//===----------------------------------------------------------------------===// 1247 1248// Stop tracking symbols when a value escapes as a result of checkBind. 1249// A value escapes in three possible cases: 1250// (1) we are binding to something that is not a memory region. 1251// (2) we are binding to a memregion that does not have stack storage 1252// (3) we are binding to a memregion with stack storage that the store 1253// does not understand. 1254void MallocChecker::checkBind(SVal loc, SVal val, const Stmt *S, 1255 CheckerContext &C) const { 1256 // Are we storing to something that causes the value to "escape"? 1257 bool escapes = true; 1258 ProgramStateRef state = C.getState(); 1259 1260 if (loc::MemRegionVal *regionLoc = dyn_cast<loc::MemRegionVal>(&loc)) { 1261 escapes = !regionLoc->getRegion()->hasStackStorage(); 1262 1263 if (!escapes) { 1264 // To test (3), generate a new state with the binding added. If it is 1265 // the same state, then it escapes (since the store cannot represent 1266 // the binding). 1267 // Do this only if we know that the store is not supposed to generate the 1268 // same state. 1269 SVal StoredVal = state->getSVal(regionLoc->getRegion()); 1270 if (StoredVal != val) 1271 escapes = (state == (state->bindLoc(*regionLoc, val))); 1272 } 1273 } 1274 1275 // If our store can represent the binding and we aren't storing to something 1276 // that doesn't have local storage then just return and have the simulation 1277 // state continue as is. 1278 if (!escapes) 1279 return; 1280 1281 // Otherwise, find all symbols referenced by 'val' that we are tracking 1282 // and stop tracking them. 1283 state = state->scanReachableSymbols<StopTrackingCallback>(val).getState(); 1284 C.addTransition(state); 1285} 1286 1287// If a symbolic region is assumed to NULL (or another constant), stop tracking 1288// it - assuming that allocation failed on this path. 1289ProgramStateRef MallocChecker::evalAssume(ProgramStateRef state, 1290 SVal Cond, 1291 bool Assumption) const { 1292 RegionStateTy RS = state->get<RegionState>(); 1293 for (RegionStateTy::iterator I = RS.begin(), E = RS.end(); I != E; ++I) { 1294 // If the symbol is assumed to be NULL, remove it from consideration. 1295 ConstraintManager &CMgr = state->getConstraintManager(); 1296 ConditionTruthVal AllocFailed = CMgr.isNull(state, I.getKey()); 1297 if (AllocFailed.isConstrainedTrue()) 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 ConstraintManager &CMgr = state->getConstraintManager(); 1307 ConditionTruthVal AllocFailed = CMgr.isNull(state, I.getKey()); 1308 if (!AllocFailed.isConstrainedTrue()) 1309 continue; 1310 1311 SymbolRef ReallocSym = I.getData().ReallocatedSym; 1312 if (const RefState *RS = state->get<RegionState>(ReallocSym)) { 1313 if (RS->isReleased()) { 1314 if (I.getData().Kind == RPToBeFreedAfterFailure) 1315 state = state->set<RegionState>(ReallocSym, 1316 RefState::getAllocated(RS->getStmt())); 1317 else if (I.getData().Kind == RPDoNotTrackAfterFailure) 1318 state = state->remove<RegionState>(ReallocSym); 1319 else 1320 assert(I.getData().Kind == RPIsFreeOnFailure); 1321 } 1322 } 1323 state = state->remove<ReallocPairs>(I.getKey()); 1324 } 1325 1326 return state; 1327} 1328 1329// Check if the function is known to us. So, for example, we could 1330// conservatively assume it can free/reallocate its pointer arguments. 1331// (We assume that the pointers cannot escape through calls to system 1332// functions not handled by this checker.) 1333bool MallocChecker::doesNotFreeMemory(const CallEvent *Call, 1334 ProgramStateRef State) const { 1335 assert(Call); 1336 1337 // For now, assume that any C++ call can free memory. 1338 // TODO: If we want to be more optimistic here, we'll need to make sure that 1339 // regions escape to C++ containers. They seem to do that even now, but for 1340 // mysterious reasons. 1341 if (!(isa<FunctionCall>(Call) || isa<ObjCMethodCall>(Call))) 1342 return false; 1343 1344 // Check Objective-C messages by selector name. 1345 if (const ObjCMethodCall *Msg = dyn_cast<ObjCMethodCall>(Call)) { 1346 // If it's not a framework call, or if it takes a callback, assume it 1347 // can free memory. 1348 if (!Call->isInSystemHeader() || Call->hasNonZeroCallbackArg()) 1349 return false; 1350 1351 Selector S = Msg->getSelector(); 1352 1353 // Whitelist the ObjC methods which do free memory. 1354 // - Anything containing 'freeWhenDone' param set to 1. 1355 // Ex: dataWithBytesNoCopy:length:freeWhenDone. 1356 for (unsigned i = 1; i < S.getNumArgs(); ++i) { 1357 if (S.getNameForSlot(i).equals("freeWhenDone")) { 1358 if (Call->getArgSVal(i).isConstant(1)) 1359 return false; 1360 else 1361 return true; 1362 } 1363 } 1364 1365 // If the first selector ends with NoCopy, assume that the ownership is 1366 // transferred as well. 1367 // Ex: [NSData dataWithBytesNoCopy:bytes length:10]; 1368 StringRef FirstSlot = S.getNameForSlot(0); 1369 if (FirstSlot.endswith("NoCopy")) 1370 return false; 1371 1372 // If the first selector starts with addPointer, insertPointer, 1373 // or replacePointer, assume we are dealing with NSPointerArray or similar. 1374 // This is similar to C++ containers (vector); we still might want to check 1375 // that the pointers get freed by following the container itself. 1376 if (FirstSlot.startswith("addPointer") || 1377 FirstSlot.startswith("insertPointer") || 1378 FirstSlot.startswith("replacePointer")) { 1379 return false; 1380 } 1381 1382 // Otherwise, assume that the method does not free memory. 1383 // Most framework methods do not free memory. 1384 return true; 1385 } 1386 1387 // At this point the only thing left to handle is straight function calls. 1388 const FunctionDecl *FD = cast<FunctionCall>(Call)->getDecl(); 1389 if (!FD) 1390 return false; 1391 1392 ASTContext &ASTC = State->getStateManager().getContext(); 1393 1394 // If it's one of the allocation functions we can reason about, we model 1395 // its behavior explicitly. 1396 if (isMemFunction(FD, ASTC)) 1397 return true; 1398 1399 // If it's not a system call, assume it frees memory. 1400 if (!Call->isInSystemHeader()) 1401 return false; 1402 1403 // White list the system functions whose arguments escape. 1404 const IdentifierInfo *II = FD->getIdentifier(); 1405 if (!II) 1406 return false; 1407 StringRef FName = II->getName(); 1408 1409 // White list the 'XXXNoCopy' CoreFoundation functions. 1410 // We specifically check these before 1411 if (FName.endswith("NoCopy")) { 1412 // Look for the deallocator argument. We know that the memory ownership 1413 // is not transferred only if the deallocator argument is 1414 // 'kCFAllocatorNull'. 1415 for (unsigned i = 1; i < Call->getNumArgs(); ++i) { 1416 const Expr *ArgE = Call->getArgExpr(i)->IgnoreParenCasts(); 1417 if (const DeclRefExpr *DE = dyn_cast<DeclRefExpr>(ArgE)) { 1418 StringRef DeallocatorName = DE->getFoundDecl()->getName(); 1419 if (DeallocatorName == "kCFAllocatorNull") 1420 return true; 1421 } 1422 } 1423 return false; 1424 } 1425 1426 // Associating streams with malloced buffers. The pointer can escape if 1427 // 'closefn' is specified (and if that function does free memory), 1428 // but it will not if closefn is not specified. 1429 // Currently, we do not inspect the 'closefn' function (PR12101). 1430 if (FName == "funopen") 1431 if (Call->getNumArgs() >= 4 && Call->getArgSVal(4).isConstant(0)) 1432 return true; 1433 1434 // Do not warn on pointers passed to 'setbuf' when used with std streams, 1435 // these leaks might be intentional when setting the buffer for stdio. 1436 // http://stackoverflow.com/questions/2671151/who-frees-setvbuf-buffer 1437 if (FName == "setbuf" || FName =="setbuffer" || 1438 FName == "setlinebuf" || FName == "setvbuf") { 1439 if (Call->getNumArgs() >= 1) { 1440 const Expr *ArgE = Call->getArgExpr(0)->IgnoreParenCasts(); 1441 if (const DeclRefExpr *ArgDRE = dyn_cast<DeclRefExpr>(ArgE)) 1442 if (const VarDecl *D = dyn_cast<VarDecl>(ArgDRE->getDecl())) 1443 if (D->getCanonicalDecl()->getName().find("std") != StringRef::npos) 1444 return false; 1445 } 1446 } 1447 1448 // A bunch of other functions which either take ownership of a pointer or 1449 // wrap the result up in a struct or object, meaning it can be freed later. 1450 // (See RetainCountChecker.) Not all the parameters here are invalidated, 1451 // but the Malloc checker cannot differentiate between them. The right way 1452 // of doing this would be to implement a pointer escapes callback. 1453 if (FName == "CGBitmapContextCreate" || 1454 FName == "CGBitmapContextCreateWithData" || 1455 FName == "CVPixelBufferCreateWithBytes" || 1456 FName == "CVPixelBufferCreateWithPlanarBytes" || 1457 FName == "OSAtomicEnqueue") { 1458 return false; 1459 } 1460 1461 // Handle cases where we know a buffer's /address/ can escape. 1462 // Note that the above checks handle some special cases where we know that 1463 // even though the address escapes, it's still our responsibility to free the 1464 // buffer. 1465 if (Call->argumentsMayEscape()) 1466 return false; 1467 1468 // Otherwise, assume that the function does not free memory. 1469 // Most system calls do not free the memory. 1470 return true; 1471} 1472 1473// If the symbol we are tracking is invalidated, but not explicitly (ex: the &p 1474// escapes, when we are tracking p), do not track the symbol as we cannot reason 1475// about it anymore. 1476ProgramStateRef 1477MallocChecker::checkRegionChanges(ProgramStateRef State, 1478 const StoreManager::InvalidatedSymbols *invalidated, 1479 ArrayRef<const MemRegion *> ExplicitRegions, 1480 ArrayRef<const MemRegion *> Regions, 1481 const CallEvent *Call) const { 1482 if (!invalidated || invalidated->empty()) 1483 return State; 1484 llvm::SmallPtrSet<SymbolRef, 8> WhitelistedSymbols; 1485 1486 // If it's a call which might free or reallocate memory, we assume that all 1487 // regions (explicit and implicit) escaped. 1488 1489 // Otherwise, whitelist explicit pointers; we still can track them. 1490 if (!Call || doesNotFreeMemory(Call, State)) { 1491 for (ArrayRef<const MemRegion *>::iterator I = ExplicitRegions.begin(), 1492 E = ExplicitRegions.end(); I != E; ++I) { 1493 if (const SymbolicRegion *R = (*I)->StripCasts()->getAs<SymbolicRegion>()) 1494 WhitelistedSymbols.insert(R->getSymbol()); 1495 } 1496 } 1497 1498 for (StoreManager::InvalidatedSymbols::const_iterator I=invalidated->begin(), 1499 E = invalidated->end(); I!=E; ++I) { 1500 SymbolRef sym = *I; 1501 if (WhitelistedSymbols.count(sym)) 1502 continue; 1503 // The symbol escaped. Note, we assume that if the symbol is released, 1504 // passing it out will result in a use after free. We also keep tracking 1505 // relinquished symbols. 1506 if (const RefState *RS = State->get<RegionState>(sym)) { 1507 if (RS->isAllocated()) 1508 State = State->remove<RegionState>(sym); 1509 } 1510 } 1511 return State; 1512} 1513 1514static SymbolRef findFailedReallocSymbol(ProgramStateRef currState, 1515 ProgramStateRef prevState) { 1516 ReallocMap currMap = currState->get<ReallocPairs>(); 1517 ReallocMap prevMap = prevState->get<ReallocPairs>(); 1518 1519 for (ReallocMap::iterator I = prevMap.begin(), E = prevMap.end(); 1520 I != E; ++I) { 1521 SymbolRef sym = I.getKey(); 1522 if (!currMap.lookup(sym)) 1523 return sym; 1524 } 1525 1526 return NULL; 1527} 1528 1529PathDiagnosticPiece * 1530MallocChecker::MallocBugVisitor::VisitNode(const ExplodedNode *N, 1531 const ExplodedNode *PrevN, 1532 BugReporterContext &BRC, 1533 BugReport &BR) { 1534 ProgramStateRef state = N->getState(); 1535 ProgramStateRef statePrev = PrevN->getState(); 1536 1537 const RefState *RS = state->get<RegionState>(Sym); 1538 const RefState *RSPrev = statePrev->get<RegionState>(Sym); 1539 if (!RS) 1540 return 0; 1541 1542 const Stmt *S = 0; 1543 const char *Msg = 0; 1544 StackHintGeneratorForSymbol *StackHint = 0; 1545 1546 // Retrieve the associated statement. 1547 ProgramPoint ProgLoc = N->getLocation(); 1548 if (StmtPoint *SP = dyn_cast<StmtPoint>(&ProgLoc)) 1549 S = SP->getStmt(); 1550 else if (CallExitEnd *Exit = dyn_cast<CallExitEnd>(&ProgLoc)) 1551 S = Exit->getCalleeContext()->getCallSite(); 1552 // If an assumption was made on a branch, it should be caught 1553 // here by looking at the state transition. 1554 else if (BlockEdge *Edge = dyn_cast<BlockEdge>(&ProgLoc)) { 1555 const CFGBlock *srcBlk = Edge->getSrc(); 1556 S = srcBlk->getTerminator(); 1557 } 1558 if (!S) 1559 return 0; 1560 1561 // FIXME: We will eventually need to handle non-statement-based events 1562 // (__attribute__((cleanup))). 1563 1564 // Find out if this is an interesting point and what is the kind. 1565 if (Mode == Normal) { 1566 if (isAllocated(RS, RSPrev, S)) { 1567 Msg = "Memory is allocated"; 1568 StackHint = new StackHintGeneratorForSymbol(Sym, 1569 "Returned allocated memory"); 1570 } else if (isReleased(RS, RSPrev, S)) { 1571 Msg = "Memory is released"; 1572 StackHint = new StackHintGeneratorForSymbol(Sym, 1573 "Returned released memory"); 1574 } else if (isRelinquished(RS, RSPrev, S)) { 1575 Msg = "Memory ownership is transfered"; 1576 StackHint = new StackHintGeneratorForSymbol(Sym, ""); 1577 } else if (isReallocFailedCheck(RS, RSPrev, S)) { 1578 Mode = ReallocationFailed; 1579 Msg = "Reallocation failed"; 1580 StackHint = new StackHintGeneratorForReallocationFailed(Sym, 1581 "Reallocation failed"); 1582 1583 if (SymbolRef sym = findFailedReallocSymbol(state, statePrev)) { 1584 // Is it possible to fail two reallocs WITHOUT testing in between? 1585 assert((!FailedReallocSymbol || FailedReallocSymbol == sym) && 1586 "We only support one failed realloc at a time."); 1587 BR.markInteresting(sym); 1588 FailedReallocSymbol = sym; 1589 } 1590 } 1591 1592 // We are in a special mode if a reallocation failed later in the path. 1593 } else if (Mode == ReallocationFailed) { 1594 assert(FailedReallocSymbol && "No symbol to look for."); 1595 1596 // Is this is the first appearance of the reallocated symbol? 1597 if (!statePrev->get<RegionState>(FailedReallocSymbol)) { 1598 // We're at the reallocation point. 1599 Msg = "Attempt to reallocate memory"; 1600 StackHint = new StackHintGeneratorForSymbol(Sym, 1601 "Returned reallocated memory"); 1602 FailedReallocSymbol = NULL; 1603 Mode = Normal; 1604 } 1605 } 1606 1607 if (!Msg) 1608 return 0; 1609 assert(StackHint); 1610 1611 // Generate the extra diagnostic. 1612 PathDiagnosticLocation Pos(S, BRC.getSourceManager(), 1613 N->getLocationContext()); 1614 return new PathDiagnosticEventPiece(Pos, Msg, true, StackHint); 1615} 1616 1617void MallocChecker::printState(raw_ostream &Out, ProgramStateRef State, 1618 const char *NL, const char *Sep) const { 1619 1620 RegionStateTy RS = State->get<RegionState>(); 1621 1622 if (!RS.isEmpty()) 1623 Out << "Has Malloc data" << NL; 1624} 1625 1626#define REGISTER_CHECKER(name) \ 1627void ento::register##name(CheckerManager &mgr) {\ 1628 registerCStringCheckerBasic(mgr); \ 1629 mgr.registerChecker<MallocChecker>()->Filter.C##name = true;\ 1630} 1631 1632REGISTER_CHECKER(MallocPessimistic) 1633REGISTER_CHECKER(MallocOptimistic) 1634