MallocChecker.cpp revision febdc324faaf1678a4f41497fd691efe54e145c9
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 "clang/StaticAnalyzer/Core/Checker.h" 17#include "clang/StaticAnalyzer/Core/CheckerManager.h" 18#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" 19#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" 20#include "clang/StaticAnalyzer/Core/PathSensitive/ObjCMessage.h" 21#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 22#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" 23#include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h" 24#include "clang/Basic/SourceManager.h" 25#include "llvm/ADT/ImmutableMap.h" 26#include "llvm/ADT/SmallString.h" 27#include "llvm/ADT/STLExtras.h" 28using namespace clang; 29using namespace ento; 30 31namespace { 32 33class RefState { 34 enum Kind { AllocateUnchecked, AllocateFailed, Released, Escaped, 35 Relinquished } K; 36 const Stmt *S; 37 38public: 39 RefState(Kind k, const Stmt *s) : K(k), S(s) {} 40 41 bool isAllocated() const { return K == AllocateUnchecked; } 42 //bool isFailed() const { return K == AllocateFailed; } 43 bool isReleased() const { return K == Released; } 44 //bool isEscaped() const { return K == Escaped; } 45 //bool isRelinquished() const { return K == Relinquished; } 46 const Stmt *getStmt() const { return S; } 47 48 bool operator==(const RefState &X) const { 49 return K == X.K && S == X.S; 50 } 51 52 static RefState getAllocateUnchecked(const Stmt *s) { 53 return RefState(AllocateUnchecked, s); 54 } 55 static RefState getAllocateFailed() { 56 return RefState(AllocateFailed, 0); 57 } 58 static RefState getReleased(const Stmt *s) { return RefState(Released, s); } 59 static RefState getEscaped(const Stmt *s) { return RefState(Escaped, s); } 60 static RefState getRelinquished(const Stmt *s) { 61 return RefState(Relinquished, s); 62 } 63 64 void Profile(llvm::FoldingSetNodeID &ID) const { 65 ID.AddInteger(K); 66 ID.AddPointer(S); 67 } 68}; 69 70struct ReallocPair { 71 SymbolRef ReallocatedSym; 72 bool IsFreeOnFailure; 73 ReallocPair(SymbolRef S, bool F) : ReallocatedSym(S), IsFreeOnFailure(F) {} 74 void Profile(llvm::FoldingSetNodeID &ID) const { 75 ID.AddInteger(IsFreeOnFailure); 76 ID.AddPointer(ReallocatedSym); 77 } 78 bool operator==(const ReallocPair &X) const { 79 return ReallocatedSym == X.ReallocatedSym && 80 IsFreeOnFailure == X.IsFreeOnFailure; 81 } 82}; 83 84class MallocChecker : public Checker<check::DeadSymbols, 85 check::EndPath, 86 check::PreStmt<ReturnStmt>, 87 check::PreStmt<CallExpr>, 88 check::PostStmt<CallExpr>, 89 check::Location, 90 check::Bind, 91 eval::Assume, 92 check::RegionChanges> 93{ 94 mutable OwningPtr<BugType> BT_DoubleFree; 95 mutable OwningPtr<BugType> BT_Leak; 96 mutable OwningPtr<BugType> BT_UseFree; 97 mutable OwningPtr<BugType> BT_BadFree; 98 mutable IdentifierInfo *II_malloc, *II_free, *II_realloc, *II_calloc, 99 *II_valloc, *II_reallocf; 100 101public: 102 MallocChecker() : II_malloc(0), II_free(0), II_realloc(0), II_calloc(0), 103 II_valloc(0), II_reallocf(0) {} 104 105 /// In pessimistic mode, the checker assumes that it does not know which 106 /// functions might free the memory. 107 struct ChecksFilter { 108 DefaultBool CMallocPessimistic; 109 DefaultBool CMallocOptimistic; 110 }; 111 112 ChecksFilter Filter; 113 114 void checkPreStmt(const CallExpr *S, CheckerContext &C) const; 115 void checkPostStmt(const CallExpr *CE, CheckerContext &C) const; 116 void checkDeadSymbols(SymbolReaper &SymReaper, CheckerContext &C) const; 117 void checkEndPath(CheckerContext &C) const; 118 void checkPreStmt(const ReturnStmt *S, CheckerContext &C) const; 119 ProgramStateRef evalAssume(ProgramStateRef state, SVal Cond, 120 bool Assumption) const; 121 void checkLocation(SVal l, bool isLoad, const Stmt *S, 122 CheckerContext &C) const; 123 void checkBind(SVal location, SVal val, const Stmt*S, 124 CheckerContext &C) const; 125 ProgramStateRef 126 checkRegionChanges(ProgramStateRef state, 127 const StoreManager::InvalidatedSymbols *invalidated, 128 ArrayRef<const MemRegion *> ExplicitRegions, 129 ArrayRef<const MemRegion *> Regions, 130 const CallOrObjCMessage *Call) const; 131 bool wantsRegionChangeUpdate(ProgramStateRef state) const { 132 return true; 133 } 134 135private: 136 void initIdentifierInfo(ASTContext &C) const; 137 138 /// Check if this is one of the functions which can allocate/reallocate memory 139 /// pointed to by one of its arguments. 140 bool isMemFunction(const FunctionDecl *FD, ASTContext &C) const; 141 142 static void MallocMem(CheckerContext &C, const CallExpr *CE); 143 static void MallocMemReturnsAttr(CheckerContext &C, const CallExpr *CE, 144 const OwnershipAttr* Att); 145 static ProgramStateRef MallocMemAux(CheckerContext &C, const CallExpr *CE, 146 const Expr *SizeEx, SVal Init, 147 ProgramStateRef state) { 148 return MallocMemAux(C, CE, 149 state->getSVal(SizeEx, C.getLocationContext()), 150 Init, state); 151 } 152 static ProgramStateRef MallocMemAux(CheckerContext &C, const CallExpr *CE, 153 SVal SizeEx, SVal Init, 154 ProgramStateRef state); 155 156 void FreeMem(CheckerContext &C, const CallExpr *CE) const; 157 void FreeMemAttr(CheckerContext &C, const CallExpr *CE, 158 const OwnershipAttr* Att) const; 159 ProgramStateRef FreeMemAux(CheckerContext &C, const CallExpr *CE, 160 ProgramStateRef state, unsigned Num, 161 bool Hold) const; 162 163 void ReallocMem(CheckerContext &C, const CallExpr *CE, 164 bool FreesMemOnFailure) const; 165 static void CallocMem(CheckerContext &C, const CallExpr *CE); 166 167 bool checkEscape(SymbolRef Sym, const Stmt *S, CheckerContext &C) const; 168 bool checkUseAfterFree(SymbolRef Sym, CheckerContext &C, 169 const Stmt *S = 0) const; 170 171 /// Check if the function is not known to us. So, for example, we could 172 /// conservatively assume it can free/reallocate it's pointer arguments. 173 bool hasUnknownBehavior(const FunctionDecl *FD, ProgramStateRef State) const; 174 175 static bool SummarizeValue(raw_ostream &os, SVal V); 176 static bool SummarizeRegion(raw_ostream &os, const MemRegion *MR); 177 void ReportBadFree(CheckerContext &C, SVal ArgVal, SourceRange range) const; 178 179 void reportLeak(SymbolRef Sym, ExplodedNode *N, CheckerContext &C) const; 180 181 /// The bug visitor which allows us to print extra diagnostics along the 182 /// BugReport path. For example, showing the allocation site of the leaked 183 /// region. 184 class MallocBugVisitor : public BugReporterVisitor { 185 protected: 186 enum NotificationMode { 187 Normal, 188 Complete, 189 ReallocationFailed 190 }; 191 192 // The allocated region symbol tracked by the main analysis. 193 SymbolRef Sym; 194 NotificationMode Mode; 195 196 public: 197 MallocBugVisitor(SymbolRef S) : Sym(S), Mode(Normal) {} 198 virtual ~MallocBugVisitor() {} 199 200 void Profile(llvm::FoldingSetNodeID &ID) const { 201 static int X = 0; 202 ID.AddPointer(&X); 203 ID.AddPointer(Sym); 204 } 205 206 inline bool isAllocated(const RefState *S, const RefState *SPrev, 207 const Stmt *Stmt) { 208 // Did not track -> allocated. Other state (released) -> allocated. 209 return (Stmt && isa<CallExpr>(Stmt) && 210 (S && S->isAllocated()) && (!SPrev || !SPrev->isAllocated())); 211 } 212 213 inline bool isReleased(const RefState *S, const RefState *SPrev, 214 const Stmt *Stmt) { 215 // Did not track -> released. Other state (allocated) -> released. 216 return (Stmt && isa<CallExpr>(Stmt) && 217 (S && S->isReleased()) && (!SPrev || !SPrev->isReleased())); 218 } 219 220 inline bool isReallocFailedCheck(const RefState *S, const RefState *SPrev, 221 const Stmt *Stmt) { 222 // If the expression is not a call, and the state change is 223 // released -> allocated, it must be the realloc return value 224 // check. If we have to handle more cases here, it might be cleaner just 225 // to track this extra bit in the state itself. 226 return ((!Stmt || !isa<CallExpr>(Stmt)) && 227 (S && S->isAllocated()) && (SPrev && !SPrev->isAllocated())); 228 } 229 230 PathDiagnosticPiece *VisitNode(const ExplodedNode *N, 231 const ExplodedNode *PrevN, 232 BugReporterContext &BRC, 233 BugReport &BR); 234 }; 235}; 236} // end anonymous namespace 237 238typedef llvm::ImmutableMap<SymbolRef, RefState> RegionStateTy; 239typedef llvm::ImmutableMap<SymbolRef, ReallocPair > ReallocMap; 240class RegionState {}; 241class ReallocPairs {}; 242namespace clang { 243namespace ento { 244 template <> 245 struct ProgramStateTrait<RegionState> 246 : public ProgramStatePartialTrait<RegionStateTy> { 247 static void *GDMIndex() { static int x; return &x; } 248 }; 249 250 template <> 251 struct ProgramStateTrait<ReallocPairs> 252 : public ProgramStatePartialTrait<ReallocMap> { 253 static void *GDMIndex() { static int x; return &x; } 254 }; 255} 256} 257 258namespace { 259class StopTrackingCallback : public SymbolVisitor { 260 ProgramStateRef state; 261public: 262 StopTrackingCallback(ProgramStateRef st) : state(st) {} 263 ProgramStateRef getState() const { return state; } 264 265 bool VisitSymbol(SymbolRef sym) { 266 state = state->remove<RegionState>(sym); 267 return true; 268 } 269}; 270} // end anonymous namespace 271 272void MallocChecker::initIdentifierInfo(ASTContext &Ctx) const { 273 if (!II_malloc) 274 II_malloc = &Ctx.Idents.get("malloc"); 275 if (!II_free) 276 II_free = &Ctx.Idents.get("free"); 277 if (!II_realloc) 278 II_realloc = &Ctx.Idents.get("realloc"); 279 if (!II_reallocf) 280 II_reallocf = &Ctx.Idents.get("reallocf"); 281 if (!II_calloc) 282 II_calloc = &Ctx.Idents.get("calloc"); 283 if (!II_valloc) 284 II_valloc = &Ctx.Idents.get("valloc"); 285} 286 287bool MallocChecker::isMemFunction(const FunctionDecl *FD, ASTContext &C) const { 288 if (!FD) 289 return false; 290 IdentifierInfo *FunI = FD->getIdentifier(); 291 if (!FunI) 292 return false; 293 294 initIdentifierInfo(C); 295 296 // TODO: Add more here : ex: reallocf! 297 if (FunI == II_malloc || FunI == II_free || FunI == II_realloc || 298 FunI == II_reallocf || FunI == II_calloc || FunI == II_valloc) 299 return true; 300 301 if (Filter.CMallocOptimistic && FD->hasAttrs() && 302 FD->specific_attr_begin<OwnershipAttr>() != 303 FD->specific_attr_end<OwnershipAttr>()) 304 return true; 305 306 307 return false; 308} 309 310void MallocChecker::checkPostStmt(const CallExpr *CE, CheckerContext &C) const { 311 const FunctionDecl *FD = C.getCalleeDecl(CE); 312 if (!FD) 313 return; 314 315 initIdentifierInfo(C.getASTContext()); 316 IdentifierInfo *FunI = FD->getIdentifier(); 317 if (!FunI) 318 return; 319 320 if (FunI == II_malloc || FunI == II_valloc) { 321 MallocMem(C, CE); 322 return; 323 } else if (FunI == II_realloc) { 324 ReallocMem(C, CE, false); 325 return; 326 } else if (FunI == II_reallocf) { 327 ReallocMem(C, CE, true); 328 return; 329 } else if (FunI == II_calloc) { 330 CallocMem(C, CE); 331 return; 332 }else if (FunI == II_free) { 333 FreeMem(C, CE); 334 return; 335 } 336 337 if (Filter.CMallocOptimistic) 338 // Check all the attributes, if there are any. 339 // There can be multiple of these attributes. 340 if (FD->hasAttrs()) { 341 for (specific_attr_iterator<OwnershipAttr> 342 i = FD->specific_attr_begin<OwnershipAttr>(), 343 e = FD->specific_attr_end<OwnershipAttr>(); 344 i != e; ++i) { 345 switch ((*i)->getOwnKind()) { 346 case OwnershipAttr::Returns: { 347 MallocMemReturnsAttr(C, CE, *i); 348 return; 349 } 350 case OwnershipAttr::Takes: 351 case OwnershipAttr::Holds: { 352 FreeMemAttr(C, CE, *i); 353 return; 354 } 355 } 356 } 357 } 358} 359 360void MallocChecker::MallocMem(CheckerContext &C, const CallExpr *CE) { 361 ProgramStateRef state = MallocMemAux(C, CE, CE->getArg(0), UndefinedVal(), 362 C.getState()); 363 C.addTransition(state); 364} 365 366void MallocChecker::MallocMemReturnsAttr(CheckerContext &C, const CallExpr *CE, 367 const OwnershipAttr* Att) { 368 if (Att->getModule() != "malloc") 369 return; 370 371 OwnershipAttr::args_iterator I = Att->args_begin(), E = Att->args_end(); 372 if (I != E) { 373 ProgramStateRef state = 374 MallocMemAux(C, CE, CE->getArg(*I), UndefinedVal(), C.getState()); 375 C.addTransition(state); 376 return; 377 } 378 ProgramStateRef state = MallocMemAux(C, CE, UnknownVal(), UndefinedVal(), 379 C.getState()); 380 C.addTransition(state); 381} 382 383ProgramStateRef MallocChecker::MallocMemAux(CheckerContext &C, 384 const CallExpr *CE, 385 SVal Size, SVal Init, 386 ProgramStateRef state) { 387 SValBuilder &svalBuilder = C.getSValBuilder(); 388 389 // Get the return value. 390 SVal retVal = state->getSVal(CE, C.getLocationContext()); 391 392 // We expect the malloc functions to return a pointer. 393 if (!isa<Loc>(retVal)) 394 return 0; 395 396 // Fill the region with the initialization value. 397 state = state->bindDefault(retVal, Init); 398 399 // Set the region's extent equal to the Size parameter. 400 const SymbolicRegion *R = 401 dyn_cast_or_null<SymbolicRegion>(retVal.getAsRegion()); 402 if (!R || !isa<DefinedOrUnknownSVal>(Size)) 403 return 0; 404 405 DefinedOrUnknownSVal Extent = R->getExtent(svalBuilder); 406 DefinedOrUnknownSVal DefinedSize = cast<DefinedOrUnknownSVal>(Size); 407 DefinedOrUnknownSVal extentMatchesSize = 408 svalBuilder.evalEQ(state, Extent, DefinedSize); 409 410 state = state->assume(extentMatchesSize, true); 411 assert(state); 412 413 SymbolRef Sym = retVal.getAsLocSymbol(); 414 assert(Sym); 415 416 // Set the symbol's state to Allocated. 417 return state->set<RegionState>(Sym, RefState::getAllocateUnchecked(CE)); 418} 419 420void MallocChecker::FreeMem(CheckerContext &C, const CallExpr *CE) const { 421 ProgramStateRef state = FreeMemAux(C, CE, C.getState(), 0, false); 422 423 if (state) 424 C.addTransition(state); 425} 426 427void MallocChecker::FreeMemAttr(CheckerContext &C, const CallExpr *CE, 428 const OwnershipAttr* Att) const { 429 if (Att->getModule() != "malloc") 430 return; 431 432 for (OwnershipAttr::args_iterator I = Att->args_begin(), E = Att->args_end(); 433 I != E; ++I) { 434 ProgramStateRef state = 435 FreeMemAux(C, CE, C.getState(), *I, 436 Att->getOwnKind() == OwnershipAttr::Holds); 437 if (state) 438 C.addTransition(state); 439 } 440} 441 442ProgramStateRef MallocChecker::FreeMemAux(CheckerContext &C, 443 const CallExpr *CE, 444 ProgramStateRef state, 445 unsigned Num, 446 bool Hold) const { 447 const Expr *ArgExpr = CE->getArg(Num); 448 SVal ArgVal = state->getSVal(ArgExpr, C.getLocationContext()); 449 if (!isa<DefinedOrUnknownSVal>(ArgVal)) 450 return 0; 451 DefinedOrUnknownSVal location = cast<DefinedOrUnknownSVal>(ArgVal); 452 453 // Check for null dereferences. 454 if (!isa<Loc>(location)) 455 return 0; 456 457 // The explicit NULL case, no operation is performed. 458 ProgramStateRef notNullState, nullState; 459 llvm::tie(notNullState, nullState) = state->assume(location); 460 if (nullState && !notNullState) 461 return 0; 462 463 // Unknown values could easily be okay 464 // Undefined values are handled elsewhere 465 if (ArgVal.isUnknownOrUndef()) 466 return 0; 467 468 const MemRegion *R = ArgVal.getAsRegion(); 469 470 // Nonlocs can't be freed, of course. 471 // Non-region locations (labels and fixed addresses) also shouldn't be freed. 472 if (!R) { 473 ReportBadFree(C, ArgVal, ArgExpr->getSourceRange()); 474 return 0; 475 } 476 477 R = R->StripCasts(); 478 479 // Blocks might show up as heap data, but should not be free()d 480 if (isa<BlockDataRegion>(R)) { 481 ReportBadFree(C, ArgVal, ArgExpr->getSourceRange()); 482 return 0; 483 } 484 485 const MemSpaceRegion *MS = R->getMemorySpace(); 486 487 // Parameters, locals, statics, and globals shouldn't be freed. 488 if (!(isa<UnknownSpaceRegion>(MS) || isa<HeapSpaceRegion>(MS))) { 489 // FIXME: at the time this code was written, malloc() regions were 490 // represented by conjured symbols, which are all in UnknownSpaceRegion. 491 // This means that there isn't actually anything from HeapSpaceRegion 492 // that should be freed, even though we allow it here. 493 // Of course, free() can work on memory allocated outside the current 494 // function, so UnknownSpaceRegion is always a possibility. 495 // False negatives are better than false positives. 496 497 ReportBadFree(C, ArgVal, ArgExpr->getSourceRange()); 498 return 0; 499 } 500 501 const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R); 502 // Various cases could lead to non-symbol values here. 503 // For now, ignore them. 504 if (!SR) 505 return 0; 506 507 SymbolRef Sym = SR->getSymbol(); 508 const RefState *RS = state->get<RegionState>(Sym); 509 510 // If the symbol has not been tracked, return. This is possible when free() is 511 // called on a pointer that does not get its pointee directly from malloc(). 512 // Full support of this requires inter-procedural analysis. 513 if (!RS) 514 return 0; 515 516 // Check double free. 517 if (RS->isReleased()) { 518 if (ExplodedNode *N = C.generateSink()) { 519 if (!BT_DoubleFree) 520 BT_DoubleFree.reset( 521 new BugType("Double free", "Memory Error")); 522 BugReport *R = new BugReport(*BT_DoubleFree, 523 "Attempt to free released memory", N); 524 R->addRange(ArgExpr->getSourceRange()); 525 R->addVisitor(new MallocBugVisitor(Sym)); 526 C.EmitReport(R); 527 } 528 return 0; 529 } 530 531 // Normal free. 532 if (Hold) 533 return state->set<RegionState>(Sym, RefState::getRelinquished(CE)); 534 return state->set<RegionState>(Sym, RefState::getReleased(CE)); 535} 536 537bool MallocChecker::SummarizeValue(raw_ostream &os, SVal V) { 538 if (nonloc::ConcreteInt *IntVal = dyn_cast<nonloc::ConcreteInt>(&V)) 539 os << "an integer (" << IntVal->getValue() << ")"; 540 else if (loc::ConcreteInt *ConstAddr = dyn_cast<loc::ConcreteInt>(&V)) 541 os << "a constant address (" << ConstAddr->getValue() << ")"; 542 else if (loc::GotoLabel *Label = dyn_cast<loc::GotoLabel>(&V)) 543 os << "the address of the label '" << Label->getLabel()->getName() << "'"; 544 else 545 return false; 546 547 return true; 548} 549 550bool MallocChecker::SummarizeRegion(raw_ostream &os, 551 const MemRegion *MR) { 552 switch (MR->getKind()) { 553 case MemRegion::FunctionTextRegionKind: { 554 const FunctionDecl *FD = cast<FunctionTextRegion>(MR)->getDecl(); 555 if (FD) 556 os << "the address of the function '" << *FD << '\''; 557 else 558 os << "the address of a function"; 559 return true; 560 } 561 case MemRegion::BlockTextRegionKind: 562 os << "block text"; 563 return true; 564 case MemRegion::BlockDataRegionKind: 565 // FIXME: where the block came from? 566 os << "a block"; 567 return true; 568 default: { 569 const MemSpaceRegion *MS = MR->getMemorySpace(); 570 571 if (isa<StackLocalsSpaceRegion>(MS)) { 572 const VarRegion *VR = dyn_cast<VarRegion>(MR); 573 const VarDecl *VD; 574 if (VR) 575 VD = VR->getDecl(); 576 else 577 VD = NULL; 578 579 if (VD) 580 os << "the address of the local variable '" << VD->getName() << "'"; 581 else 582 os << "the address of a local stack variable"; 583 return true; 584 } 585 586 if (isa<StackArgumentsSpaceRegion>(MS)) { 587 const VarRegion *VR = dyn_cast<VarRegion>(MR); 588 const VarDecl *VD; 589 if (VR) 590 VD = VR->getDecl(); 591 else 592 VD = NULL; 593 594 if (VD) 595 os << "the address of the parameter '" << VD->getName() << "'"; 596 else 597 os << "the address of a parameter"; 598 return true; 599 } 600 601 if (isa<GlobalsSpaceRegion>(MS)) { 602 const VarRegion *VR = dyn_cast<VarRegion>(MR); 603 const VarDecl *VD; 604 if (VR) 605 VD = VR->getDecl(); 606 else 607 VD = NULL; 608 609 if (VD) { 610 if (VD->isStaticLocal()) 611 os << "the address of the static variable '" << VD->getName() << "'"; 612 else 613 os << "the address of the global variable '" << VD->getName() << "'"; 614 } else 615 os << "the address of a global variable"; 616 return true; 617 } 618 619 return false; 620 } 621 } 622} 623 624void MallocChecker::ReportBadFree(CheckerContext &C, SVal ArgVal, 625 SourceRange range) const { 626 if (ExplodedNode *N = C.generateSink()) { 627 if (!BT_BadFree) 628 BT_BadFree.reset(new BugType("Bad free", "Memory Error")); 629 630 SmallString<100> buf; 631 llvm::raw_svector_ostream os(buf); 632 633 const MemRegion *MR = ArgVal.getAsRegion(); 634 if (MR) { 635 while (const ElementRegion *ER = dyn_cast<ElementRegion>(MR)) 636 MR = ER->getSuperRegion(); 637 638 // Special case for alloca() 639 if (isa<AllocaRegion>(MR)) 640 os << "Argument to free() was allocated by alloca(), not malloc()"; 641 else { 642 os << "Argument to free() is "; 643 if (SummarizeRegion(os, MR)) 644 os << ", which is not memory allocated by malloc()"; 645 else 646 os << "not memory allocated by malloc()"; 647 } 648 } else { 649 os << "Argument to free() is "; 650 if (SummarizeValue(os, ArgVal)) 651 os << ", which is not memory allocated by malloc()"; 652 else 653 os << "not memory allocated by malloc()"; 654 } 655 656 BugReport *R = new BugReport(*BT_BadFree, os.str(), N); 657 R->addRange(range); 658 C.EmitReport(R); 659 } 660} 661 662void MallocChecker::ReallocMem(CheckerContext &C, const CallExpr *CE, 663 bool FreesOnFail) const { 664 ProgramStateRef state = C.getState(); 665 const Expr *arg0Expr = CE->getArg(0); 666 const LocationContext *LCtx = C.getLocationContext(); 667 SVal Arg0Val = state->getSVal(arg0Expr, LCtx); 668 if (!isa<DefinedOrUnknownSVal>(Arg0Val)) 669 return; 670 DefinedOrUnknownSVal arg0Val = cast<DefinedOrUnknownSVal>(Arg0Val); 671 672 SValBuilder &svalBuilder = C.getSValBuilder(); 673 674 DefinedOrUnknownSVal PtrEQ = 675 svalBuilder.evalEQ(state, arg0Val, svalBuilder.makeNull()); 676 677 // Get the size argument. If there is no size arg then give up. 678 const Expr *Arg1 = CE->getArg(1); 679 if (!Arg1) 680 return; 681 682 // Get the value of the size argument. 683 SVal Arg1ValG = state->getSVal(Arg1, LCtx); 684 if (!isa<DefinedOrUnknownSVal>(Arg1ValG)) 685 return; 686 DefinedOrUnknownSVal Arg1Val = cast<DefinedOrUnknownSVal>(Arg1ValG); 687 688 // Compare the size argument to 0. 689 DefinedOrUnknownSVal SizeZero = 690 svalBuilder.evalEQ(state, Arg1Val, 691 svalBuilder.makeIntValWithPtrWidth(0, false)); 692 693 ProgramStateRef StatePtrIsNull, StatePtrNotNull; 694 llvm::tie(StatePtrIsNull, StatePtrNotNull) = state->assume(PtrEQ); 695 ProgramStateRef StateSizeIsZero, StateSizeNotZero; 696 llvm::tie(StateSizeIsZero, StateSizeNotZero) = state->assume(SizeZero); 697 // We only assume exceptional states if they are definitely true; if the 698 // state is under-constrained, assume regular realloc behavior. 699 bool PrtIsNull = StatePtrIsNull && !StatePtrNotNull; 700 bool SizeIsZero = StateSizeIsZero && !StateSizeNotZero; 701 702 // If the ptr is NULL and the size is not 0, the call is equivalent to 703 // malloc(size). 704 if ( PrtIsNull && !SizeIsZero) { 705 ProgramStateRef stateMalloc = MallocMemAux(C, CE, CE->getArg(1), 706 UndefinedVal(), StatePtrIsNull); 707 C.addTransition(stateMalloc); 708 return; 709 } 710 711 if (PrtIsNull && SizeIsZero) 712 return; 713 714 // Get the from and to pointer symbols as in toPtr = realloc(fromPtr, size). 715 assert(!PrtIsNull); 716 SymbolRef FromPtr = arg0Val.getAsSymbol(); 717 SVal RetVal = state->getSVal(CE, LCtx); 718 SymbolRef ToPtr = RetVal.getAsSymbol(); 719 if (!FromPtr || !ToPtr) 720 return; 721 722 // If the size is 0, free the memory. 723 if (SizeIsZero) 724 if (ProgramStateRef stateFree = FreeMemAux(C, CE, StateSizeIsZero,0,false)){ 725 // The semantics of the return value are: 726 // If size was equal to 0, either NULL or a pointer suitable to be passed 727 // to free() is returned. 728 stateFree = stateFree->set<ReallocPairs>(ToPtr, 729 ReallocPair(FromPtr, FreesOnFail)); 730 C.getSymbolManager().addSymbolDependency(ToPtr, FromPtr); 731 C.addTransition(stateFree); 732 return; 733 } 734 735 // Default behavior. 736 if (ProgramStateRef stateFree = FreeMemAux(C, CE, state, 0, false)) { 737 // FIXME: We should copy the content of the original buffer. 738 ProgramStateRef stateRealloc = MallocMemAux(C, CE, CE->getArg(1), 739 UnknownVal(), stateFree); 740 if (!stateRealloc) 741 return; 742 stateRealloc = stateRealloc->set<ReallocPairs>(ToPtr, 743 ReallocPair(FromPtr, FreesOnFail)); 744 C.getSymbolManager().addSymbolDependency(ToPtr, FromPtr); 745 C.addTransition(stateRealloc); 746 return; 747 } 748} 749 750void MallocChecker::CallocMem(CheckerContext &C, const CallExpr *CE) { 751 ProgramStateRef state = C.getState(); 752 SValBuilder &svalBuilder = C.getSValBuilder(); 753 const LocationContext *LCtx = C.getLocationContext(); 754 SVal count = state->getSVal(CE->getArg(0), LCtx); 755 SVal elementSize = state->getSVal(CE->getArg(1), LCtx); 756 SVal TotalSize = svalBuilder.evalBinOp(state, BO_Mul, count, elementSize, 757 svalBuilder.getContext().getSizeType()); 758 SVal zeroVal = svalBuilder.makeZeroVal(svalBuilder.getContext().CharTy); 759 760 C.addTransition(MallocMemAux(C, CE, TotalSize, zeroVal, state)); 761} 762 763void MallocChecker::reportLeak(SymbolRef Sym, ExplodedNode *N, 764 CheckerContext &C) const { 765 assert(N); 766 if (!BT_Leak) { 767 BT_Leak.reset(new BugType("Memory leak", "Memory Error")); 768 // Leaks should not be reported if they are post-dominated by a sink: 769 // (1) Sinks are higher importance bugs. 770 // (2) NoReturnFunctionChecker uses sink nodes to represent paths ending 771 // with __noreturn functions such as assert() or exit(). We choose not 772 // to report leaks on such paths. 773 BT_Leak->setSuppressOnSink(true); 774 } 775 776 BugReport *R = new BugReport(*BT_Leak, 777 "Memory is never released; potential memory leak", N); 778 R->addVisitor(new MallocBugVisitor(Sym)); 779 C.EmitReport(R); 780} 781 782void MallocChecker::checkDeadSymbols(SymbolReaper &SymReaper, 783 CheckerContext &C) const 784{ 785 if (!SymReaper.hasDeadSymbols()) 786 return; 787 788 ProgramStateRef state = C.getState(); 789 RegionStateTy RS = state->get<RegionState>(); 790 RegionStateTy::Factory &F = state->get_context<RegionState>(); 791 792 bool generateReport = false; 793 llvm::SmallVector<SymbolRef, 2> Errors; 794 for (RegionStateTy::iterator I = RS.begin(), E = RS.end(); I != E; ++I) { 795 if (SymReaper.isDead(I->first)) { 796 if (I->second.isAllocated()) { 797 generateReport = true; 798 Errors.push_back(I->first); 799 } 800 // Remove the dead symbol from the map. 801 RS = F.remove(RS, I->first); 802 803 } 804 } 805 806 // Cleanup the Realloc Pairs Map. 807 ReallocMap RP = state->get<ReallocPairs>(); 808 for (ReallocMap::iterator I = RP.begin(), E = RP.end(); I != E; ++I) { 809 if (SymReaper.isDead(I->first) || 810 SymReaper.isDead(I->second.ReallocatedSym)) { 811 state = state->remove<ReallocPairs>(I->first); 812 } 813 } 814 815 ExplodedNode *N = C.addTransition(state->set<RegionState>(RS)); 816 817 if (N && generateReport) { 818 for (llvm::SmallVector<SymbolRef, 2>::iterator 819 I = Errors.begin(), E = Errors.end(); I != E; ++I) { 820 reportLeak(*I, N, C); 821 } 822 } 823} 824 825void MallocChecker::checkEndPath(CheckerContext &C) const { 826 ProgramStateRef state = C.getState(); 827 RegionStateTy M = state->get<RegionState>(); 828 829 for (RegionStateTy::iterator I = M.begin(), E = M.end(); I != E; ++I) { 830 RefState RS = I->second; 831 if (RS.isAllocated()) { 832 ExplodedNode *N = C.addTransition(state); 833 if (N) 834 reportLeak(I->first, N, C); 835 } 836 } 837} 838 839bool MallocChecker::checkEscape(SymbolRef Sym, const Stmt *S, 840 CheckerContext &C) const { 841 ProgramStateRef state = C.getState(); 842 const RefState *RS = state->get<RegionState>(Sym); 843 if (!RS) 844 return false; 845 846 if (RS->isAllocated()) { 847 state = state->set<RegionState>(Sym, RefState::getEscaped(S)); 848 C.addTransition(state); 849 return true; 850 } 851 return false; 852} 853 854void MallocChecker::checkPreStmt(const CallExpr *CE, CheckerContext &C) const { 855 if (isMemFunction(C.getCalleeDecl(CE), C.getASTContext())) 856 return; 857 858 // Check use after free, when a freed pointer is passed to a call. 859 ProgramStateRef State = C.getState(); 860 for (CallExpr::const_arg_iterator I = CE->arg_begin(), 861 E = CE->arg_end(); I != E; ++I) { 862 const Expr *A = *I; 863 if (A->getType().getTypePtr()->isAnyPointerType()) { 864 SymbolRef Sym = State->getSVal(A, C.getLocationContext()).getAsSymbol(); 865 if (!Sym) 866 continue; 867 if (checkUseAfterFree(Sym, C, A)) 868 return; 869 } 870 } 871} 872 873void MallocChecker::checkPreStmt(const ReturnStmt *S, CheckerContext &C) const { 874 const Expr *E = S->getRetValue(); 875 if (!E) 876 return; 877 878 // Check if we are returning a symbol. 879 SymbolRef Sym = C.getState()->getSVal(E, C.getLocationContext()).getAsSymbol(); 880 if (!Sym) 881 return; 882 883 // Check if we are returning freed memory. 884 if (checkUseAfterFree(Sym, C, E)) 885 return; 886 887 // Check if the symbol is escaping. 888 checkEscape(Sym, E, C); 889} 890 891bool MallocChecker::checkUseAfterFree(SymbolRef Sym, CheckerContext &C, 892 const Stmt *S) const { 893 assert(Sym); 894 const RefState *RS = C.getState()->get<RegionState>(Sym); 895 if (RS && RS->isReleased()) { 896 if (ExplodedNode *N = C.generateSink()) { 897 if (!BT_UseFree) 898 BT_UseFree.reset(new BugType("Use-after-free", "Memory Error")); 899 900 BugReport *R = new BugReport(*BT_UseFree, 901 "Use of memory after it is freed",N); 902 if (S) 903 R->addRange(S->getSourceRange()); 904 R->addVisitor(new MallocBugVisitor(Sym)); 905 C.EmitReport(R); 906 return true; 907 } 908 } 909 return false; 910} 911 912// Check if the location is a freed symbolic region. 913void MallocChecker::checkLocation(SVal l, bool isLoad, const Stmt *S, 914 CheckerContext &C) const { 915 SymbolRef Sym = l.getLocSymbolInBase(); 916 if (Sym) 917 checkUseAfterFree(Sym, C); 918} 919 920//===----------------------------------------------------------------------===// 921// Check various ways a symbol can be invalidated. 922// TODO: This logic (the next 3 functions) is copied/similar to the 923// RetainRelease checker. We might want to factor this out. 924//===----------------------------------------------------------------------===// 925 926// Stop tracking symbols when a value escapes as a result of checkBind. 927// A value escapes in three possible cases: 928// (1) we are binding to something that is not a memory region. 929// (2) we are binding to a memregion that does not have stack storage 930// (3) we are binding to a memregion with stack storage that the store 931// does not understand. 932void MallocChecker::checkBind(SVal loc, SVal val, const Stmt *S, 933 CheckerContext &C) const { 934 // Are we storing to something that causes the value to "escape"? 935 bool escapes = true; 936 ProgramStateRef state = C.getState(); 937 938 if (loc::MemRegionVal *regionLoc = dyn_cast<loc::MemRegionVal>(&loc)) { 939 escapes = !regionLoc->getRegion()->hasStackStorage(); 940 941 if (!escapes) { 942 // To test (3), generate a new state with the binding added. If it is 943 // the same state, then it escapes (since the store cannot represent 944 // the binding). 945 escapes = (state == (state->bindLoc(*regionLoc, val))); 946 } 947 if (!escapes) { 948 // Case 4: We do not currently model what happens when a symbol is 949 // assigned to a struct field, so be conservative here and let the symbol 950 // go. TODO: This could definitely be improved upon. 951 escapes = !isa<VarRegion>(regionLoc->getRegion()); 952 } 953 } 954 955 // If our store can represent the binding and we aren't storing to something 956 // that doesn't have local storage then just return and have the simulation 957 // state continue as is. 958 if (!escapes) 959 return; 960 961 // Otherwise, find all symbols referenced by 'val' that we are tracking 962 // and stop tracking them. 963 state = state->scanReachableSymbols<StopTrackingCallback>(val).getState(); 964 C.addTransition(state); 965} 966 967// If a symbolic region is assumed to NULL (or another constant), stop tracking 968// it - assuming that allocation failed on this path. 969ProgramStateRef MallocChecker::evalAssume(ProgramStateRef state, 970 SVal Cond, 971 bool Assumption) const { 972 RegionStateTy RS = state->get<RegionState>(); 973 for (RegionStateTy::iterator I = RS.begin(), E = RS.end(); I != E; ++I) { 974 // If the symbol is assumed to NULL or another constant, this will 975 // return an APSInt*. 976 if (state->getSymVal(I.getKey())) 977 state = state->remove<RegionState>(I.getKey()); 978 } 979 980 // Realloc returns 0 when reallocation fails, which means that we should 981 // restore the state of the pointer being reallocated. 982 ReallocMap RP = state->get<ReallocPairs>(); 983 for (ReallocMap::iterator I = RP.begin(), E = RP.end(); I != E; ++I) { 984 // If the symbol is assumed to NULL or another constant, this will 985 // return an APSInt*. 986 if (state->getSymVal(I.getKey())) { 987 SymbolRef ReallocSym = I.getData().ReallocatedSym; 988 const RefState *RS = state->get<RegionState>(ReallocSym); 989 if (RS) { 990 if (RS->isReleased() && ! I.getData().IsFreeOnFailure) 991 state = state->set<RegionState>(ReallocSym, 992 RefState::getAllocateUnchecked(RS->getStmt())); 993 } 994 state = state->remove<ReallocPairs>(I.getKey()); 995 } 996 } 997 998 return state; 999} 1000 1001// Check if the function is not known to us. So, for example, we could 1002// conservatively assume it can free/reallocate it's pointer arguments. 1003// (We assume that the pointers cannot escape through calls to system 1004// functions not handled by this checker.) 1005bool MallocChecker::hasUnknownBehavior(const FunctionDecl *FD, 1006 ProgramStateRef State) const { 1007 ASTContext &ASTC = State->getStateManager().getContext(); 1008 1009 // If it's one of the allocation functions we can reason about, we model it's 1010 // behavior explicitly. 1011 if (isMemFunction(FD, ASTC)) { 1012 return false; 1013 } 1014 1015 // If it's a system call, we know it does not free the memory. 1016 SourceManager &SM = ASTC.getSourceManager(); 1017 if (SM.isInSystemHeader(FD->getLocation())) { 1018 return false; 1019 } 1020 1021 // Otherwise, assume that the function can free memory. 1022 return true; 1023} 1024 1025// If the symbol we are tracking is invalidated, but not explicitly (ex: the &p 1026// escapes, when we are tracking p), do not track the symbol as we cannot reason 1027// about it anymore. 1028ProgramStateRef 1029MallocChecker::checkRegionChanges(ProgramStateRef State, 1030 const StoreManager::InvalidatedSymbols *invalidated, 1031 ArrayRef<const MemRegion *> ExplicitRegions, 1032 ArrayRef<const MemRegion *> Regions, 1033 const CallOrObjCMessage *Call) const { 1034 if (!invalidated) 1035 return State; 1036 llvm::SmallPtrSet<SymbolRef, 8> WhitelistedSymbols; 1037 1038 const FunctionDecl *FD = (Call ? 1039 dyn_cast_or_null<FunctionDecl>(Call->getDecl()) :0); 1040 1041 // If it's a call which might free or reallocate memory, we assume that all 1042 // regions (explicit and implicit) escaped. Otherwise, whitelist explicit 1043 // pointers; we still can track them. 1044 if (!(FD && hasUnknownBehavior(FD, State))) { 1045 for (ArrayRef<const MemRegion *>::iterator I = ExplicitRegions.begin(), 1046 E = ExplicitRegions.end(); I != E; ++I) { 1047 if (const SymbolicRegion *R = (*I)->StripCasts()->getAs<SymbolicRegion>()) 1048 WhitelistedSymbols.insert(R->getSymbol()); 1049 } 1050 } 1051 1052 for (StoreManager::InvalidatedSymbols::const_iterator I=invalidated->begin(), 1053 E = invalidated->end(); I!=E; ++I) { 1054 SymbolRef sym = *I; 1055 if (WhitelistedSymbols.count(sym)) 1056 continue; 1057 // The symbol escaped. 1058 if (const RefState *RS = State->get<RegionState>(sym)) 1059 State = State->set<RegionState>(sym, RefState::getEscaped(RS->getStmt())); 1060 } 1061 return State; 1062} 1063 1064PathDiagnosticPiece * 1065MallocChecker::MallocBugVisitor::VisitNode(const ExplodedNode *N, 1066 const ExplodedNode *PrevN, 1067 BugReporterContext &BRC, 1068 BugReport &BR) { 1069 const RefState *RS = N->getState()->get<RegionState>(Sym); 1070 const RefState *RSPrev = PrevN->getState()->get<RegionState>(Sym); 1071 if (!RS && !RSPrev) 1072 return 0; 1073 1074 const Stmt *S = 0; 1075 const char *Msg = 0; 1076 1077 // Retrieve the associated statement. 1078 ProgramPoint ProgLoc = N->getLocation(); 1079 if (isa<StmtPoint>(ProgLoc)) 1080 S = cast<StmtPoint>(ProgLoc).getStmt(); 1081 // If an assumption was made on a branch, it should be caught 1082 // here by looking at the state transition. 1083 if (isa<BlockEdge>(ProgLoc)) { 1084 const CFGBlock *srcBlk = cast<BlockEdge>(ProgLoc).getSrc(); 1085 S = srcBlk->getTerminator(); 1086 } 1087 if (!S) 1088 return 0; 1089 1090 // Find out if this is an interesting point and what is the kind. 1091 if (Mode == Normal) { 1092 if (isAllocated(RS, RSPrev, S)) 1093 Msg = "Memory is allocated"; 1094 else if (isReleased(RS, RSPrev, S)) 1095 Msg = "Memory is released"; 1096 else if (isReallocFailedCheck(RS, RSPrev, S)) { 1097 Mode = ReallocationFailed; 1098 Msg = "Reallocation failed"; 1099 } 1100 1101 // We are in a special mode if a reallocation failed later in the path. 1102 } else if (Mode == ReallocationFailed) { 1103 // Generate a special diagnostic for the first realloc we find. 1104 if (!isAllocated(RS, RSPrev, S) && !isReleased(RS, RSPrev, S)) 1105 return 0; 1106 1107 // Check that the name of the function is realloc. 1108 const CallExpr *CE = dyn_cast<CallExpr>(S); 1109 if (!CE) 1110 return 0; 1111 const FunctionDecl *funDecl = CE->getDirectCallee(); 1112 if (!funDecl) 1113 return 0; 1114 StringRef FunName = funDecl->getName(); 1115 if (!(FunName.equals("realloc") || FunName.equals("reallocf"))) 1116 return 0; 1117 Msg = "Attempt to reallocate memory"; 1118 Mode = Normal; 1119 } 1120 1121 if (!Msg) 1122 return 0; 1123 1124 // Generate the extra diagnostic. 1125 PathDiagnosticLocation Pos(S, BRC.getSourceManager(), 1126 N->getLocationContext()); 1127 return new PathDiagnosticEventPiece(Pos, Msg); 1128} 1129 1130 1131#define REGISTER_CHECKER(name) \ 1132void ento::register##name(CheckerManager &mgr) {\ 1133 mgr.registerChecker<MallocChecker>()->Filter.C##name = true;\ 1134} 1135 1136REGISTER_CHECKER(MallocPessimistic) 1137REGISTER_CHECKER(MallocOptimistic) 1138