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