1 //=== MallocChecker.cpp - A malloc/free checker -------------------*- C++ -*--//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines malloc/free checker, which checks for potential memory
11 // leaks, double free, and use-after-free problems.
13 //===----------------------------------------------------------------------===//
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/ProgramState.h"
21 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
22 #include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h"
23 #include "llvm/ADT/ImmutableMap.h"
24 using namespace clang;
30 enum Kind { AllocateUnchecked, AllocateFailed, Released, Escaped,
35 RefState(Kind k, const Stmt *s) : K(k), S(s) {}
37 bool isAllocated() const { return K == AllocateUnchecked; }
38 //bool isFailed() const { return K == AllocateFailed; }
39 bool isReleased() const { return K == Released; }
40 //bool isEscaped() const { return K == Escaped; }
41 //bool isRelinquished() const { return K == Relinquished; }
43 bool operator==(const RefState &X) const {
44 return K == X.K && S == X.S;
47 static RefState getAllocateUnchecked(const Stmt *s) {
48 return RefState(AllocateUnchecked, s);
50 static RefState getAllocateFailed() {
51 return RefState(AllocateFailed, 0);
53 static RefState getReleased(const Stmt *s) { return RefState(Released, s); }
54 static RefState getEscaped(const Stmt *s) { return RefState(Escaped, s); }
55 static RefState getRelinquished(const Stmt *s) {
56 return RefState(Relinquished, s);
59 void Profile(llvm::FoldingSetNodeID &ID) const {
67 class MallocChecker : public Checker<eval::Call, check::DeadSymbols, check::EndPath, check::PreStmt<ReturnStmt>, check::Location,
68 check::Bind, eval::Assume> {
69 mutable llvm::OwningPtr<BuiltinBug> BT_DoubleFree;
70 mutable llvm::OwningPtr<BuiltinBug> BT_Leak;
71 mutable llvm::OwningPtr<BuiltinBug> BT_UseFree;
72 mutable llvm::OwningPtr<BuiltinBug> BT_UseRelinquished;
73 mutable llvm::OwningPtr<BuiltinBug> BT_BadFree;
74 mutable IdentifierInfo *II_malloc, *II_free, *II_realloc, *II_calloc;
77 MallocChecker() : II_malloc(0), II_free(0), II_realloc(0), II_calloc(0) {}
79 bool evalCall(const CallExpr *CE, CheckerContext &C) const;
80 void checkDeadSymbols(SymbolReaper &SymReaper, CheckerContext &C) const;
81 void checkEndPath(EndOfFunctionNodeBuilder &B, ExprEngine &Eng) const;
82 void checkPreStmt(const ReturnStmt *S, CheckerContext &C) const;
83 const ProgramState *evalAssume(const ProgramState *state, SVal Cond,
84 bool Assumption) const;
85 void checkLocation(SVal l, bool isLoad, const Stmt *S,
86 CheckerContext &C) const;
87 void checkBind(SVal location, SVal val, const Stmt*S,
88 CheckerContext &C) const;
91 static void MallocMem(CheckerContext &C, const CallExpr *CE);
92 static void MallocMemReturnsAttr(CheckerContext &C, const CallExpr *CE,
93 const OwnershipAttr* Att);
94 static const ProgramState *MallocMemAux(CheckerContext &C, const CallExpr *CE,
95 const Expr *SizeEx, SVal Init,
96 const ProgramState *state) {
97 return MallocMemAux(C, CE, state->getSVal(SizeEx), Init, state);
99 static const ProgramState *MallocMemAux(CheckerContext &C, const CallExpr *CE,
100 SVal SizeEx, SVal Init,
101 const ProgramState *state);
103 void FreeMem(CheckerContext &C, const CallExpr *CE) const;
104 void FreeMemAttr(CheckerContext &C, const CallExpr *CE,
105 const OwnershipAttr* Att) const;
106 const ProgramState *FreeMemAux(CheckerContext &C, const CallExpr *CE,
107 const ProgramState *state, unsigned Num, bool Hold) const;
109 void ReallocMem(CheckerContext &C, const CallExpr *CE) const;
110 static void CallocMem(CheckerContext &C, const CallExpr *CE);
112 static bool SummarizeValue(raw_ostream &os, SVal V);
113 static bool SummarizeRegion(raw_ostream &os, const MemRegion *MR);
114 void ReportBadFree(CheckerContext &C, SVal ArgVal, SourceRange range) const;
116 } // end anonymous namespace
118 typedef llvm::ImmutableMap<SymbolRef, RefState> RegionStateTy;
123 struct ProgramStateTrait<RegionState>
124 : public ProgramStatePartialTrait<RegionStateTy> {
125 static void *GDMIndex() { static int x; return &x; }
130 bool MallocChecker::evalCall(const CallExpr *CE, CheckerContext &C) const {
131 const ProgramState *state = C.getState();
132 const Expr *Callee = CE->getCallee();
133 SVal L = state->getSVal(Callee);
135 const FunctionDecl *FD = L.getAsFunctionDecl();
139 ASTContext &Ctx = C.getASTContext();
141 II_malloc = &Ctx.Idents.get("malloc");
143 II_free = &Ctx.Idents.get("free");
145 II_realloc = &Ctx.Idents.get("realloc");
147 II_calloc = &Ctx.Idents.get("calloc");
149 if (FD->getIdentifier() == II_malloc) {
154 if (FD->getIdentifier() == II_free) {
159 if (FD->getIdentifier() == II_realloc) {
164 if (FD->getIdentifier() == II_calloc) {
169 // Check all the attributes, if there are any.
170 // There can be multiple of these attributes.
172 if (FD->hasAttrs()) {
173 for (specific_attr_iterator<OwnershipAttr>
174 i = FD->specific_attr_begin<OwnershipAttr>(),
175 e = FD->specific_attr_end<OwnershipAttr>();
177 switch ((*i)->getOwnKind()) {
178 case OwnershipAttr::Returns: {
179 MallocMemReturnsAttr(C, CE, *i);
183 case OwnershipAttr::Takes:
184 case OwnershipAttr::Holds: {
185 FreeMemAttr(C, CE, *i);
197 void MallocChecker::MallocMem(CheckerContext &C, const CallExpr *CE) {
198 const ProgramState *state = MallocMemAux(C, CE, CE->getArg(0), UndefinedVal(),
200 C.addTransition(state);
203 void MallocChecker::MallocMemReturnsAttr(CheckerContext &C, const CallExpr *CE,
204 const OwnershipAttr* Att) {
205 if (Att->getModule() != "malloc")
208 OwnershipAttr::args_iterator I = Att->args_begin(), E = Att->args_end();
210 const ProgramState *state =
211 MallocMemAux(C, CE, CE->getArg(*I), UndefinedVal(), C.getState());
212 C.addTransition(state);
215 const ProgramState *state = MallocMemAux(C, CE, UnknownVal(), UndefinedVal(),
217 C.addTransition(state);
220 const ProgramState *MallocChecker::MallocMemAux(CheckerContext &C,
222 SVal Size, SVal Init,
223 const ProgramState *state) {
224 unsigned Count = C.getCurrentBlockCount();
225 SValBuilder &svalBuilder = C.getSValBuilder();
227 // Set the return value.
228 SVal retVal = svalBuilder.getConjuredSymbolVal(NULL, CE, CE->getType(), Count);
229 state = state->BindExpr(CE, retVal);
231 // Fill the region with the initialization value.
232 state = state->bindDefault(retVal, Init);
234 // Set the region's extent equal to the Size parameter.
235 const SymbolicRegion *R = cast<SymbolicRegion>(retVal.getAsRegion());
236 DefinedOrUnknownSVal Extent = R->getExtent(svalBuilder);
237 DefinedOrUnknownSVal DefinedSize = cast<DefinedOrUnknownSVal>(Size);
238 DefinedOrUnknownSVal extentMatchesSize =
239 svalBuilder.evalEQ(state, Extent, DefinedSize);
241 state = state->assume(extentMatchesSize, true);
244 SymbolRef Sym = retVal.getAsLocSymbol();
247 // Set the symbol's state to Allocated.
248 return state->set<RegionState>(Sym, RefState::getAllocateUnchecked(CE));
251 void MallocChecker::FreeMem(CheckerContext &C, const CallExpr *CE) const {
252 const ProgramState *state = FreeMemAux(C, CE, C.getState(), 0, false);
255 C.addTransition(state);
258 void MallocChecker::FreeMemAttr(CheckerContext &C, const CallExpr *CE,
259 const OwnershipAttr* Att) const {
260 if (Att->getModule() != "malloc")
263 for (OwnershipAttr::args_iterator I = Att->args_begin(), E = Att->args_end();
265 const ProgramState *state = FreeMemAux(C, CE, C.getState(), *I,
266 Att->getOwnKind() == OwnershipAttr::Holds);
268 C.addTransition(state);
272 const ProgramState *MallocChecker::FreeMemAux(CheckerContext &C, const CallExpr *CE,
273 const ProgramState *state, unsigned Num,
275 const Expr *ArgExpr = CE->getArg(Num);
276 SVal ArgVal = state->getSVal(ArgExpr);
278 DefinedOrUnknownSVal location = cast<DefinedOrUnknownSVal>(ArgVal);
280 // Check for null dereferences.
281 if (!isa<Loc>(location))
284 // FIXME: Technically using 'Assume' here can result in a path
285 // bifurcation. In such cases we need to return two states, not just one.
286 const ProgramState *notNullState, *nullState;
287 llvm::tie(notNullState, nullState) = state->assume(location);
289 // The explicit NULL case, no operation is performed.
290 if (nullState && !notNullState)
293 assert(notNullState);
295 // Unknown values could easily be okay
296 // Undefined values are handled elsewhere
297 if (ArgVal.isUnknownOrUndef())
300 const MemRegion *R = ArgVal.getAsRegion();
302 // Nonlocs can't be freed, of course.
303 // Non-region locations (labels and fixed addresses) also shouldn't be freed.
305 ReportBadFree(C, ArgVal, ArgExpr->getSourceRange());
311 // Blocks might show up as heap data, but should not be free()d
312 if (isa<BlockDataRegion>(R)) {
313 ReportBadFree(C, ArgVal, ArgExpr->getSourceRange());
317 const MemSpaceRegion *MS = R->getMemorySpace();
319 // Parameters, locals, statics, and globals shouldn't be freed.
320 if (!(isa<UnknownSpaceRegion>(MS) || isa<HeapSpaceRegion>(MS))) {
321 // FIXME: at the time this code was written, malloc() regions were
322 // represented by conjured symbols, which are all in UnknownSpaceRegion.
323 // This means that there isn't actually anything from HeapSpaceRegion
324 // that should be freed, even though we allow it here.
325 // Of course, free() can work on memory allocated outside the current
326 // function, so UnknownSpaceRegion is always a possibility.
327 // False negatives are better than false positives.
329 ReportBadFree(C, ArgVal, ArgExpr->getSourceRange());
333 const SymbolicRegion *SR = dyn_cast<SymbolicRegion>(R);
334 // Various cases could lead to non-symbol values here.
335 // For now, ignore them.
339 SymbolRef Sym = SR->getSymbol();
340 const RefState *RS = state->get<RegionState>(Sym);
342 // If the symbol has not been tracked, return. This is possible when free() is
343 // called on a pointer that does not get its pointee directly from malloc().
344 // Full support of this requires inter-procedural analysis.
348 // Check double free.
349 if (RS->isReleased()) {
350 if (ExplodedNode *N = C.generateSink()) {
353 new BuiltinBug("Double free",
354 "Try to free a memory block that has been released"));
355 // FIXME: should find where it's freed last time.
356 BugReport *R = new BugReport(*BT_DoubleFree,
357 BT_DoubleFree->getDescription(), N);
365 return notNullState->set<RegionState>(Sym, RefState::getRelinquished(CE));
366 return notNullState->set<RegionState>(Sym, RefState::getReleased(CE));
369 bool MallocChecker::SummarizeValue(raw_ostream &os, SVal V) {
370 if (nonloc::ConcreteInt *IntVal = dyn_cast<nonloc::ConcreteInt>(&V))
371 os << "an integer (" << IntVal->getValue() << ")";
372 else if (loc::ConcreteInt *ConstAddr = dyn_cast<loc::ConcreteInt>(&V))
373 os << "a constant address (" << ConstAddr->getValue() << ")";
374 else if (loc::GotoLabel *Label = dyn_cast<loc::GotoLabel>(&V))
375 os << "the address of the label '" << Label->getLabel()->getName() << "'";
382 bool MallocChecker::SummarizeRegion(raw_ostream &os,
383 const MemRegion *MR) {
384 switch (MR->getKind()) {
385 case MemRegion::FunctionTextRegionKind: {
386 const FunctionDecl *FD = cast<FunctionTextRegion>(MR)->getDecl();
388 os << "the address of the function '" << *FD << '\'';
390 os << "the address of a function";
393 case MemRegion::BlockTextRegionKind:
396 case MemRegion::BlockDataRegionKind:
397 // FIXME: where the block came from?
401 const MemSpaceRegion *MS = MR->getMemorySpace();
403 switch (MS->getKind()) {
404 case MemRegion::StackLocalsSpaceRegionKind: {
405 const VarRegion *VR = dyn_cast<VarRegion>(MR);
413 os << "the address of the local variable '" << VD->getName() << "'";
415 os << "the address of a local stack variable";
418 case MemRegion::StackArgumentsSpaceRegionKind: {
419 const VarRegion *VR = dyn_cast<VarRegion>(MR);
427 os << "the address of the parameter '" << VD->getName() << "'";
429 os << "the address of a parameter";
432 case MemRegion::NonStaticGlobalSpaceRegionKind:
433 case MemRegion::StaticGlobalSpaceRegionKind: {
434 const VarRegion *VR = dyn_cast<VarRegion>(MR);
442 if (VD->isStaticLocal())
443 os << "the address of the static variable '" << VD->getName() << "'";
445 os << "the address of the global variable '" << VD->getName() << "'";
447 os << "the address of a global variable";
457 void MallocChecker::ReportBadFree(CheckerContext &C, SVal ArgVal,
458 SourceRange range) const {
459 if (ExplodedNode *N = C.generateSink()) {
461 BT_BadFree.reset(new BuiltinBug("Bad free"));
463 llvm::SmallString<100> buf;
464 llvm::raw_svector_ostream os(buf);
466 const MemRegion *MR = ArgVal.getAsRegion();
468 while (const ElementRegion *ER = dyn_cast<ElementRegion>(MR))
469 MR = ER->getSuperRegion();
471 // Special case for alloca()
472 if (isa<AllocaRegion>(MR))
473 os << "Argument to free() was allocated by alloca(), not malloc()";
475 os << "Argument to free() is ";
476 if (SummarizeRegion(os, MR))
477 os << ", which is not memory allocated by malloc()";
479 os << "not memory allocated by malloc()";
482 os << "Argument to free() is ";
483 if (SummarizeValue(os, ArgVal))
484 os << ", which is not memory allocated by malloc()";
486 os << "not memory allocated by malloc()";
489 BugReport *R = new BugReport(*BT_BadFree, os.str(), N);
495 void MallocChecker::ReallocMem(CheckerContext &C, const CallExpr *CE) const {
496 const ProgramState *state = C.getState();
497 const Expr *arg0Expr = CE->getArg(0);
498 DefinedOrUnknownSVal arg0Val
499 = cast<DefinedOrUnknownSVal>(state->getSVal(arg0Expr));
501 SValBuilder &svalBuilder = C.getSValBuilder();
503 DefinedOrUnknownSVal PtrEQ =
504 svalBuilder.evalEQ(state, arg0Val, svalBuilder.makeNull());
506 // Get the size argument. If there is no size arg then give up.
507 const Expr *Arg1 = CE->getArg(1);
511 // Get the value of the size argument.
512 DefinedOrUnknownSVal Arg1Val =
513 cast<DefinedOrUnknownSVal>(state->getSVal(Arg1));
515 // Compare the size argument to 0.
516 DefinedOrUnknownSVal SizeZero =
517 svalBuilder.evalEQ(state, Arg1Val,
518 svalBuilder.makeIntValWithPtrWidth(0, false));
520 // If the ptr is NULL and the size is not 0, the call is equivalent to
522 const ProgramState *stateEqual = state->assume(PtrEQ, true);
523 if (stateEqual && state->assume(SizeZero, false)) {
524 // Hack: set the NULL symbolic region to released to suppress false warning.
525 // In the future we should add more states for allocated regions, e.g.,
526 // CheckedNull, CheckedNonNull.
528 SymbolRef Sym = arg0Val.getAsLocSymbol();
530 stateEqual = stateEqual->set<RegionState>(Sym, RefState::getReleased(CE));
532 const ProgramState *stateMalloc = MallocMemAux(C, CE, CE->getArg(1),
533 UndefinedVal(), stateEqual);
534 C.addTransition(stateMalloc);
537 if (const ProgramState *stateNotEqual = state->assume(PtrEQ, false)) {
538 // If the size is 0, free the memory.
539 if (const ProgramState *stateSizeZero = stateNotEqual->assume(SizeZero, true))
540 if (const ProgramState *stateFree =
541 FreeMemAux(C, CE, stateSizeZero, 0, false)) {
543 // Bind the return value to NULL because it is now free.
544 C.addTransition(stateFree->BindExpr(CE, svalBuilder.makeNull(), true));
546 if (const ProgramState *stateSizeNotZero = stateNotEqual->assume(SizeZero,false))
547 if (const ProgramState *stateFree = FreeMemAux(C, CE, stateSizeNotZero,
549 // FIXME: We should copy the content of the original buffer.
550 const ProgramState *stateRealloc = MallocMemAux(C, CE, CE->getArg(1),
551 UnknownVal(), stateFree);
552 C.addTransition(stateRealloc);
557 void MallocChecker::CallocMem(CheckerContext &C, const CallExpr *CE) {
558 const ProgramState *state = C.getState();
559 SValBuilder &svalBuilder = C.getSValBuilder();
561 SVal count = state->getSVal(CE->getArg(0));
562 SVal elementSize = state->getSVal(CE->getArg(1));
563 SVal TotalSize = svalBuilder.evalBinOp(state, BO_Mul, count, elementSize,
564 svalBuilder.getContext().getSizeType());
565 SVal zeroVal = svalBuilder.makeZeroVal(svalBuilder.getContext().CharTy);
567 C.addTransition(MallocMemAux(C, CE, TotalSize, zeroVal, state));
570 void MallocChecker::checkDeadSymbols(SymbolReaper &SymReaper,
571 CheckerContext &C) const
573 if (!SymReaper.hasDeadSymbols())
576 const ProgramState *state = C.getState();
577 RegionStateTy RS = state->get<RegionState>();
578 RegionStateTy::Factory &F = state->get_context<RegionState>();
580 bool generateReport = false;
582 for (RegionStateTy::iterator I = RS.begin(), E = RS.end(); I != E; ++I) {
583 if (SymReaper.isDead(I->first)) {
584 if (I->second.isAllocated())
585 generateReport = true;
587 // Remove the dead symbol from the map.
588 RS = F.remove(RS, I->first);
593 ExplodedNode *N = C.generateNode(state->set<RegionState>(RS));
595 // FIXME: This does not handle when we have multiple leaks at a single
597 if (N && generateReport) {
599 BT_Leak.reset(new BuiltinBug("Memory leak",
600 "Allocated memory never released. Potential memory leak."));
601 // FIXME: where it is allocated.
602 BugReport *R = new BugReport(*BT_Leak, BT_Leak->getDescription(), N);
607 void MallocChecker::checkEndPath(EndOfFunctionNodeBuilder &B,
608 ExprEngine &Eng) const {
609 const ProgramState *state = B.getState();
610 RegionStateTy M = state->get<RegionState>();
612 for (RegionStateTy::iterator I = M.begin(), E = M.end(); I != E; ++I) {
613 RefState RS = I->second;
614 if (RS.isAllocated()) {
615 ExplodedNode *N = B.generateNode(state);
618 BT_Leak.reset(new BuiltinBug("Memory leak",
619 "Allocated memory never released. Potential memory leak."));
620 BugReport *R = new BugReport(*BT_Leak, BT_Leak->getDescription(), N);
621 Eng.getBugReporter().EmitReport(R);
627 void MallocChecker::checkPreStmt(const ReturnStmt *S, CheckerContext &C) const {
628 const Expr *retExpr = S->getRetValue();
632 const ProgramState *state = C.getState();
634 SymbolRef Sym = state->getSVal(retExpr).getAsSymbol();
638 const RefState *RS = state->get<RegionState>(Sym);
642 // FIXME: check other cases.
643 if (RS->isAllocated())
644 state = state->set<RegionState>(Sym, RefState::getEscaped(S));
646 C.addTransition(state);
649 const ProgramState *MallocChecker::evalAssume(const ProgramState *state, SVal Cond,
650 bool Assumption) const {
651 // If a symblic region is assumed to NULL, set its state to AllocateFailed.
652 // FIXME: should also check symbols assumed to non-null.
654 RegionStateTy RS = state->get<RegionState>();
656 for (RegionStateTy::iterator I = RS.begin(), E = RS.end(); I != E; ++I) {
657 // If the symbol is assumed to NULL, this will return an APSInt*.
658 if (state->getSymVal(I.getKey()))
659 state = state->set<RegionState>(I.getKey(),RefState::getAllocateFailed());
665 // Check if the location is a freed symbolic region.
666 void MallocChecker::checkLocation(SVal l, bool isLoad, const Stmt *S,
667 CheckerContext &C) const {
668 SymbolRef Sym = l.getLocSymbolInBase();
670 const RefState *RS = C.getState()->get<RegionState>(Sym);
671 if (RS && RS->isReleased()) {
672 if (ExplodedNode *N = C.generateNode()) {
674 BT_UseFree.reset(new BuiltinBug("Use dynamically allocated memory "
675 "after it is freed."));
677 BugReport *R = new BugReport(*BT_UseFree, BT_UseFree->getDescription(),
685 void MallocChecker::checkBind(SVal location, SVal val,
686 const Stmt *BindS, CheckerContext &C) const {
687 // The PreVisitBind implements the same algorithm as already used by the
688 // Objective C ownership checker: if the pointer escaped from this scope by
689 // assignment, let it go. However, assigning to fields of a stack-storage
690 // structure does not transfer ownership.
692 const ProgramState *state = C.getState();
693 DefinedOrUnknownSVal l = cast<DefinedOrUnknownSVal>(location);
695 // Check for null dereferences.
699 // Before checking if the state is null, check if 'val' has a RefState.
700 // Only then should we check for null and bifurcate the state.
701 SymbolRef Sym = val.getLocSymbolInBase();
703 if (const RefState *RS = state->get<RegionState>(Sym)) {
704 // If ptr is NULL, no operation is performed.
705 const ProgramState *notNullState, *nullState;
706 llvm::tie(notNullState, nullState) = state->assume(l);
708 // Generate a transition for 'nullState' to record the assumption
709 // that the state was null.
711 C.addTransition(nullState);
716 if (RS->isAllocated()) {
717 // Something we presently own is being assigned somewhere.
718 const MemRegion *AR = location.getAsRegion();
721 AR = AR->StripCasts()->getBaseRegion();
723 // If it is on the stack, we still own it.
724 if (AR->hasStackNonParametersStorage())
727 // If the state can't represent this binding, we still own it.
728 if (notNullState == (notNullState->bindLoc(cast<Loc>(location),
732 // We no longer own this pointer.
734 notNullState->set<RegionState>(Sym,
735 RefState::getRelinquished(BindS));
739 C.addTransition(notNullState);
744 void ento::registerMallocChecker(CheckerManager &mgr) {
745 mgr.registerChecker<MallocChecker>();