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