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