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