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