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