 |
|
 |
|
| Files: |
1 |
|
Branches Taken: |
67.5% |
54 / 80 |
| Generated: |
2010-02-10 01:31 |
|
Branches Executed: |
95.0% |
76 / 80 |
| |
|
Line Coverage: |
95.1% |
156 / 164 |
| |
 |
|
 |
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 "GRExprEngineExperimentalChecks.h"
16 : #include "clang/Checker/PathSensitive/CheckerVisitor.h"
17 : #include "clang/Checker/PathSensitive/GRState.h"
18 : #include "clang/Checker/PathSensitive/GRStateTrait.h"
19 : #include "clang/Checker/PathSensitive/SymbolManager.h"
20 : #include "llvm/ADT/ImmutableMap.h"
21 : using namespace clang;
22 :
23 : namespace {
24 :
25 : class RefState {
26 : enum Kind { AllocateUnchecked, AllocateFailed, Released, Escaped } K;
27 : const Stmt *S;
28 :
29 : public:
30 22: RefState(Kind k, const Stmt *s) : K(k), S(s) {}
31 :
32 17: bool isAllocated() const { return K == AllocateUnchecked; }
33 4: bool isReleased() const { return K == Released; }
34 : bool isEscaped() const { return K == Escaped; }
35 :
36 3: bool operator==(const RefState &X) const {
3: branch 0 taken
0: branch 1 not taken
3: branch 2 taken
0: branch 3 not taken
37 3: return K == X.K && S == X.S;
38 : }
39 :
40 10: static RefState getAllocateUnchecked(const Stmt *s) {
41 10: return RefState(AllocateUnchecked, s);
42 : }
43 4: static RefState getAllocateFailed() {
44 4: return RefState(AllocateFailed, 0);
45 : }
46 4: static RefState getReleased(const Stmt *s) { return RefState(Released, s); }
47 4: static RefState getEscaped(const Stmt *s) { return RefState(Escaped, s); }
48 :
49 26: void Profile(llvm::FoldingSetNodeID &ID) const {
50 26: ID.AddInteger(K);
51 26: ID.AddPointer(S);
52 26: }
53 : };
54 :
55 : class RegionState {};
56 :
10: branch 1 taken
0: branch 2 not taken
0: branch 5 not taken
0: branch 6 not taken
57 10: class MallocChecker : public CheckerVisitor<MallocChecker> {
58 : BuiltinBug *BT_DoubleFree;
59 : BuiltinBug *BT_Leak;
60 : IdentifierInfo *II_malloc, *II_free, *II_realloc;
61 :
62 : public:
63 10: MallocChecker()
64 10: : BT_DoubleFree(0), BT_Leak(0), II_malloc(0), II_free(0), II_realloc(0) {}
65 : static void *getTag();
66 : bool EvalCallExpr(CheckerContext &C, const CallExpr *CE);
67 : void EvalDeadSymbols(CheckerContext &C,const Stmt *S,SymbolReaper &SymReaper);
68 : void EvalEndPath(GREndPathNodeBuilder &B, void *tag, GRExprEngine &Eng);
69 : void PreVisitReturnStmt(CheckerContext &C, const ReturnStmt *S);
70 : const GRState *EvalAssume(const GRState *state, SVal Cond, bool Assumption);
71 :
72 : private:
73 : void MallocMem(CheckerContext &C, const CallExpr *CE);
74 : const GRState *MallocMemAux(CheckerContext &C, const CallExpr *CE,
75 : const Expr *SizeEx, const GRState *state);
76 : void FreeMem(CheckerContext &C, const CallExpr *CE);
77 : const GRState *FreeMemAux(CheckerContext &C, const CallExpr *CE,
78 : const GRState *state);
79 :
80 : void ReallocMem(CheckerContext &C, const CallExpr *CE);
81 : };
82 : } // end anonymous namespace
83 :
84 : typedef llvm::ImmutableMap<SymbolRef, RefState> RegionStateTy;
85 :
86 : namespace clang {
87 : template <>
88 : struct GRStateTrait<RegionState>
89 : : public GRStatePartialTrait<llvm::ImmutableMap<SymbolRef, RefState> > {
90 113: static void *GDMIndex() { return MallocChecker::getTag(); }
91 : };
92 : }
93 :
94 10: void clang::RegisterMallocChecker(GRExprEngine &Eng) {
95 10: Eng.registerCheck(new MallocChecker());
96 10: }
97 :
98 123: void *MallocChecker::getTag() {
99 : static int x;
100 123: return &x;
101 : }
102 :
103 14: bool MallocChecker::EvalCallExpr(CheckerContext &C, const CallExpr *CE) {
104 14: const GRState *state = C.getState();
105 14: const Expr *Callee = CE->getCallee();
106 14: SVal L = state->getSVal(Callee);
107 :
108 14: const FunctionDecl *FD = L.getAsFunctionDecl();
0: branch 0 not taken
14: branch 1 taken
109 14: if (!FD)
110 0: return false;
111 :
112 14: ASTContext &Ctx = C.getASTContext();
9: branch 0 taken
5: branch 1 taken
113 14: if (!II_malloc)
114 9: II_malloc = &Ctx.Idents.get("malloc");
9: branch 0 taken
5: branch 1 taken
115 14: if (!II_free)
116 9: II_free = &Ctx.Idents.get("free");
9: branch 0 taken
5: branch 1 taken
117 14: if (!II_realloc)
118 9: II_realloc = &Ctx.Idents.get("realloc");
119 :
8: branch 1 taken
6: branch 2 taken
120 14: if (FD->getIdentifier() == II_malloc) {
121 8: MallocMem(C, CE);
122 8: return true;
123 : }
124 :
4: branch 1 taken
2: branch 2 taken
125 6: if (FD->getIdentifier() == II_free) {
126 4: FreeMem(C, CE);
127 4: return true;
128 : }
129 :
1: branch 1 taken
1: branch 2 taken
130 2: if (FD->getIdentifier() == II_realloc) {
131 1: ReallocMem(C, CE);
132 1: return true;
133 : }
134 :
135 1: return false;
136 : }
137 :
138 8: void MallocChecker::MallocMem(CheckerContext &C, const CallExpr *CE) {
139 8: const GRState *state = MallocMemAux(C, CE, CE->getArg(0), C.getState());
140 8: C.addTransition(state);
141 8: }
142 :
143 : const GRState *MallocChecker::MallocMemAux(CheckerContext &C,
144 : const CallExpr *CE,
145 : const Expr *SizeEx,
146 10: const GRState *state) {
147 10: unsigned Count = C.getNodeBuilder().getCurrentBlockCount();
148 10: ValueManager &ValMgr = C.getValueManager();
149 :
150 10: SVal RetVal = ValMgr.getConjuredSymbolVal(NULL, CE, CE->getType(), Count);
151 :
152 10: SVal Size = state->getSVal(SizeEx);
153 :
154 : state = C.getEngine().getStoreManager().setExtent(state, RetVal.getAsRegion(),
155 10: Size);
156 :
157 10: state = state->BindExpr(CE, RetVal);
158 :
159 10: SymbolRef Sym = RetVal.getAsLocSymbol();
0: branch 0 not taken
10: branch 1 taken
160 10: assert(Sym);
161 : // Set the symbol's state to Allocated.
162 10: return state->set<RegionState>(Sym, RefState::getAllocateUnchecked(CE));
163 : }
164 :
165 4: void MallocChecker::FreeMem(CheckerContext &C, const CallExpr *CE) {
166 4: const GRState *state = FreeMemAux(C, CE, C.getState());
167 :
3: branch 0 taken
1: branch 1 taken
168 4: if (state)
169 3: C.addTransition(state);
170 4: }
171 :
172 : const GRState *MallocChecker::FreeMemAux(CheckerContext &C, const CallExpr *CE,
173 5: const GRState *state) {
174 5: SVal ArgVal = state->getSVal(CE->getArg(0));
175 5: SymbolRef Sym = ArgVal.getAsLocSymbol();
0: branch 0 not taken
5: branch 1 taken
176 5: assert(Sym);
177 :
178 5: const RefState *RS = state->get<RegionState>(Sym);
179 :
180 : // If the symbol has not been tracked, return. This is possible when free() is
181 : // called on a pointer that does not get its pointee directly from malloc().
182 : // Full support of this requires inter-procedural analysis.
1: branch 0 taken
4: branch 1 taken
183 5: if (!RS)
184 1: return state;
185 :
186 : // Check double free.
1: branch 1 taken
3: branch 2 taken
187 4: if (RS->isReleased()) {
188 1: ExplodedNode *N = C.GenerateSink();
1: branch 0 taken
0: branch 1 not taken
189 1: if (N) {
1: branch 0 taken
0: branch 1 not taken
190 1: if (!BT_DoubleFree)
191 : BT_DoubleFree = new BuiltinBug("Double free",
192 1: "Try to free a memory block that has been released");
193 : // FIXME: should find where it's freed last time.
194 : BugReport *R = new BugReport(*BT_DoubleFree,
195 1: BT_DoubleFree->getDescription(), N);
196 1: C.EmitReport(R);
197 : }
198 1: return NULL;
199 : }
200 :
201 : // Normal free.
202 3: return state->set<RegionState>(Sym, RefState::getReleased(CE));
203 : }
204 :
205 1: void MallocChecker::ReallocMem(CheckerContext &C, const CallExpr *CE) {
206 1: const GRState *state = C.getState();
207 1: const Expr *Arg0 = CE->getArg(0);
208 1: DefinedOrUnknownSVal Arg0Val=cast<DefinedOrUnknownSVal>(state->getSVal(Arg0));
209 :
210 1: ValueManager &ValMgr = C.getValueManager();
211 1: SValuator &SVator = C.getSValuator();
212 :
213 1: DefinedOrUnknownSVal PtrEQ = SVator.EvalEQ(state, Arg0Val, ValMgr.makeNull());
214 :
215 : // If the ptr is NULL, the call is equivalent to malloc(size).
1: branch 2 taken
0: branch 3 not taken
216 1: if (const GRState *stateEqual = state->Assume(PtrEQ, true)) {
217 : // Hack: set the NULL symbolic region to released to suppress false warning.
218 : // In the future we should add more states for allocated regions, e.g.,
219 : // CheckedNull, CheckedNonNull.
220 :
221 1: SymbolRef Sym = Arg0Val.getAsLocSymbol();
1: branch 0 taken
0: branch 1 not taken
222 1: if (Sym)
223 1: stateEqual = stateEqual->set<RegionState>(Sym, RefState::getReleased(CE));
224 :
225 1: const GRState *stateMalloc = MallocMemAux(C, CE, CE->getArg(1), stateEqual);
226 1: C.addTransition(stateMalloc);
227 : }
228 :
1: branch 2 taken
0: branch 3 not taken
229 1: if (const GRState *stateNotEqual = state->Assume(PtrEQ, false)) {
230 1: const Expr *Arg1 = CE->getArg(1);
231 : DefinedOrUnknownSVal Arg1Val =
232 1: cast<DefinedOrUnknownSVal>(stateNotEqual->getSVal(Arg1));
233 : DefinedOrUnknownSVal SizeZero = SVator.EvalEQ(stateNotEqual, Arg1Val,
234 1: ValMgr.makeIntValWithPtrWidth(0, false));
235 :
0: branch 2 not taken
1: branch 3 taken
236 1: if (const GRState *stateSizeZero = stateNotEqual->Assume(SizeZero, true)) {
237 0: const GRState *stateFree = FreeMemAux(C, CE, stateSizeZero);
0: branch 0 not taken
0: branch 1 not taken
238 0: if (stateFree)
239 0: C.addTransition(stateFree->BindExpr(CE, UndefinedVal(), true));
240 : }
241 :
1: branch 2 taken
0: branch 3 not taken
242 1: if (const GRState *stateSizeNotZero=stateNotEqual->Assume(SizeZero,false)) {
243 1: const GRState *stateFree = FreeMemAux(C, CE, stateSizeNotZero);
1: branch 0 taken
0: branch 1 not taken
244 1: if (stateFree) {
245 : // FIXME: We should copy the content of the original buffer.
246 : const GRState *stateRealloc = MallocMemAux(C, CE, CE->getArg(1),
247 1: stateFree);
248 1: C.addTransition(stateRealloc);
249 : }
250 1: }
251 1: }
252 1: }
253 :
254 : void MallocChecker::EvalDeadSymbols(CheckerContext &C, const Stmt *S,
255 4: SymbolReaper &SymReaper) {
4: branch 3 taken
4: branch 4 taken
256 12: for (SymbolReaper::dead_iterator I = SymReaper.dead_begin(),
257 4: E = SymReaper.dead_end(); I != E; ++I) {
258 4: SymbolRef Sym = *I;
259 4: const GRState *state = C.getState();
260 4: const RefState *RS = state->get<RegionState>(Sym);
0: branch 0 not taken
4: branch 1 taken
261 4: if (!RS)
262 0: return;
263 :
1: branch 1 taken
3: branch 2 taken
264 4: if (RS->isAllocated()) {
265 1: ExplodedNode *N = C.GenerateSink();
1: branch 0 taken
0: branch 1 not taken
266 1: if (N) {
1: branch 0 taken
0: branch 1 not taken
267 1: if (!BT_Leak)
268 : BT_Leak = new BuiltinBug("Memory leak",
269 1: "Allocated memory never released. Potential memory leak.");
270 : // FIXME: where it is allocated.
271 1: BugReport *R = new BugReport(*BT_Leak, BT_Leak->getDescription(), N);
272 1: C.EmitReport(R);
273 : }
274 : }
275 : }
276 : }
277 :
278 : void MallocChecker::EvalEndPath(GREndPathNodeBuilder &B, void *tag,
279 8: GRExprEngine &Eng) {
280 8: SaveAndRestore<bool> OldHasGen(B.HasGeneratedNode);
281 8: const GRState *state = B.getState();
282 : typedef llvm::ImmutableMap<SymbolRef, RefState> SymMap;
283 8: SymMap M = state->get<RegionState>();
284 :
9: branch 4 taken
8: branch 5 taken
285 17: for (SymMap::iterator I = M.begin(), E = M.end(); I != E; ++I) {
286 9: RefState RS = I->second;
1: branch 1 taken
8: branch 2 taken
287 9: if (RS.isAllocated()) {
288 1: ExplodedNode *N = B.generateNode(state, tag, B.getPredecessor());
1: branch 0 taken
0: branch 1 not taken
289 1: if (N) {
1: branch 0 taken
0: branch 1 not taken
290 1: if (!BT_Leak)
291 : BT_Leak = new BuiltinBug("Memory leak",
292 1: "Allocated memory never released. Potential memory leak.");
293 1: BugReport *R = new BugReport(*BT_Leak, BT_Leak->getDescription(), N);
294 1: Eng.getBugReporter().EmitReport(R);
295 : }
296 : }
297 8: }
298 8: }
299 :
300 5: void MallocChecker::PreVisitReturnStmt(CheckerContext &C, const ReturnStmt *S) {
301 5: const Expr *RetE = S->getRetValue();
1: branch 0 taken
4: branch 1 taken
302 5: if (!RetE)
303 1: return;
304 :
305 4: const GRState *state = C.getState();
306 :
307 4: SymbolRef Sym = state->getSVal(RetE).getAsSymbol();
308 :
0: branch 0 not taken
4: branch 1 taken
309 4: if (!Sym)
310 0: return;
311 :
312 4: const RefState *RS = state->get<RegionState>(Sym);
0: branch 0 not taken
4: branch 1 taken
313 4: if (!RS)
314 0: return;
315 :
316 : // FIXME: check other cases.
4: branch 1 taken
0: branch 2 not taken
317 4: if (RS->isAllocated())
318 4: state = state->set<RegionState>(Sym, RefState::getEscaped(S));
319 :
320 4: C.addTransition(state);
321 : }
322 :
323 : const GRState *MallocChecker::EvalAssume(const GRState *state, SVal Cond,
324 26: bool Assumption) {
325 : // If a symblic region is assumed to NULL, set its state to AllocateFailed.
326 : // FIXME: should also check symbols assumed to non-null.
327 :
328 26: RegionStateTy RS = state->get<RegionState>();
329 :
25: branch 4 taken
26: branch 5 taken
330 51: for (RegionStateTy::iterator I = RS.begin(), E = RS.end(); I != E; ++I) {
4: branch 2 taken
21: branch 3 taken
331 25: if (state->getSymVal(I.getKey()))
332 4: state = state->set<RegionState>(I.getKey(),RefState::getAllocateFailed());
333 26: }
334 :
335 26: return state;
336 0: }
Generated: 2010-02-10 01:31 by zcov