blob: f3dd8033af863e98f88811dc365f5cf930a85d21 [file] [log] [blame]
Jordy Roseccbf7ee2010-07-06 23:11:01 +00001//= CStringChecker.h - Checks calls to C string functions ----------*- 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 defines CStringChecker, which is an assortment of checks on calls
11// to functions in <string.h>.
12//
13//===----------------------------------------------------------------------===//
14
15#include "GRExprEngineExperimentalChecks.h"
16#include "clang/Checker/BugReporter/BugType.h"
17#include "clang/Checker/PathSensitive/CheckerVisitor.h"
Jordy Rosea5261542010-08-14 21:02:52 +000018#include "clang/Checker/PathSensitive/GRStateTrait.h"
Jordy Roseccbf7ee2010-07-06 23:11:01 +000019#include "llvm/ADT/StringSwitch.h"
20
21using namespace clang;
22
23namespace {
24class CStringChecker : public CheckerVisitor<CStringChecker> {
Jordy Rosee64f3112010-08-16 07:51:42 +000025 BugType *BT_Null, *BT_Bounds, *BT_BoundsWrite, *BT_Overlap, *BT_NotCString;
Jordy Roseccbf7ee2010-07-06 23:11:01 +000026public:
27 CStringChecker()
Jordy Rosee64f3112010-08-16 07:51:42 +000028 : BT_Null(0), BT_Bounds(0), BT_BoundsWrite(0), BT_Overlap(0), BT_NotCString(0)
29 {}
Jordy Roseccbf7ee2010-07-06 23:11:01 +000030 static void *getTag() { static int tag; return &tag; }
31
Ted Kremenek9c149532010-12-01 21:57:22 +000032 bool evalCallExpr(CheckerContext &C, const CallExpr *CE);
Jordy Rosea5261542010-08-14 21:02:52 +000033 void PreVisitDeclStmt(CheckerContext &C, const DeclStmt *DS);
34 void MarkLiveSymbols(const GRState *state, SymbolReaper &SR);
Ted Kremenek9c149532010-12-01 21:57:22 +000035 void evalDeadSymbols(CheckerContext &C, SymbolReaper &SR);
Jordy Rosea5261542010-08-14 21:02:52 +000036 bool WantsRegionChangeUpdate(const GRState *state);
37
38 const GRState *EvalRegionChanges(const GRState *state,
39 const MemRegion * const *Begin,
40 const MemRegion * const *End,
41 bool*);
Jordy Roseccbf7ee2010-07-06 23:11:01 +000042
Jordy Rosed325ffb2010-07-08 23:57:29 +000043 typedef void (CStringChecker::*FnCheck)(CheckerContext &, const CallExpr *);
Jordy Roseccbf7ee2010-07-06 23:11:01 +000044
Ted Kremenek9c149532010-12-01 21:57:22 +000045 void evalMemcpy(CheckerContext &C, const CallExpr *CE);
46 void evalMemmove(CheckerContext &C, const CallExpr *CE);
47 void evalBcopy(CheckerContext &C, const CallExpr *CE);
48 void evalCopyCommon(CheckerContext &C, const GRState *state,
Jordy Rosed325ffb2010-07-08 23:57:29 +000049 const Expr *Size, const Expr *Source, const Expr *Dest,
50 bool Restricted = false);
51
Ted Kremenek9c149532010-12-01 21:57:22 +000052 void evalMemcmp(CheckerContext &C, const CallExpr *CE);
Jordy Roseccbf7ee2010-07-06 23:11:01 +000053
Ted Kremenekc8413fd2010-12-02 07:49:45 +000054 void evalstrLength(CheckerContext &C, const CallExpr *CE);
Jordy Rose19c5dd12010-07-27 01:37:31 +000055
Ted Kremenek9c149532010-12-01 21:57:22 +000056 void evalStrcpy(CheckerContext &C, const CallExpr *CE);
57 void evalStpcpy(CheckerContext &C, const CallExpr *CE);
Ted Kremenekc8413fd2010-12-02 07:49:45 +000058 void evalStrcpyCommon(CheckerContext &C, const CallExpr *CE, bool returnEnd);
Jordy Rosee64f3112010-08-16 07:51:42 +000059
Jordy Roseccbf7ee2010-07-06 23:11:01 +000060 // Utility methods
Jordy Rosed325ffb2010-07-08 23:57:29 +000061 std::pair<const GRState*, const GRState*>
Ted Kremenek28f47b92010-12-01 22:16:56 +000062 assumeZero(CheckerContext &C, const GRState *state, SVal V, QualType Ty);
Jordy Rosed325ffb2010-07-08 23:57:29 +000063
Ted Kremenekc8413fd2010-12-02 07:49:45 +000064 const GRState *setCStringLength(const GRState *state, const MemRegion *MR,
65 SVal strLength);
66 SVal getCStringLengthForRegion(CheckerContext &C, const GRState *&state,
Jordy Rosea5261542010-08-14 21:02:52 +000067 const Expr *Ex, const MemRegion *MR);
Ted Kremenekc8413fd2010-12-02 07:49:45 +000068 SVal getCStringLength(CheckerContext &C, const GRState *&state,
Jordy Rose19c5dd12010-07-27 01:37:31 +000069 const Expr *Ex, SVal Buf);
70
Jordy Rosee64f3112010-08-16 07:51:42 +000071 const GRState *InvalidateBuffer(CheckerContext &C, const GRState *state,
72 const Expr *Ex, SVal V);
73
Jordy Rose19c5dd12010-07-27 01:37:31 +000074 bool SummarizeRegion(llvm::raw_ostream& os, ASTContext& Ctx,
75 const MemRegion *MR);
76
77 // Re-usable checks
Ted Kremenekc8413fd2010-12-02 07:49:45 +000078 const GRState *checkNonNull(CheckerContext &C, const GRState *state,
Jordy Rosed325ffb2010-07-08 23:57:29 +000079 const Expr *S, SVal l);
Jordy Roseccbf7ee2010-07-06 23:11:01 +000080 const GRState *CheckLocation(CheckerContext &C, const GRState *state,
Jordy Rosee64f3112010-08-16 07:51:42 +000081 const Expr *S, SVal l,
82 bool IsDestination = false);
Jordy Roseccbf7ee2010-07-06 23:11:01 +000083 const GRState *CheckBufferAccess(CheckerContext &C, const GRState *state,
84 const Expr *Size,
85 const Expr *FirstBuf,
Jordy Rosee64f3112010-08-16 07:51:42 +000086 const Expr *SecondBuf = NULL,
87 bool FirstIsDestination = false);
Jordy Roseccbf7ee2010-07-06 23:11:01 +000088 const GRState *CheckOverlap(CheckerContext &C, const GRState *state,
Jordy Rosed325ffb2010-07-08 23:57:29 +000089 const Expr *Size, const Expr *First,
90 const Expr *Second);
Ted Kremenekc8413fd2010-12-02 07:49:45 +000091 void emitOverlapBug(CheckerContext &C, const GRState *state,
Jordy Roseccbf7ee2010-07-06 23:11:01 +000092 const Stmt *First, const Stmt *Second);
93};
Jordy Rosea5261542010-08-14 21:02:52 +000094
95class CStringLength {
96public:
97 typedef llvm::ImmutableMap<const MemRegion *, SVal> EntryMap;
98};
Jordy Roseccbf7ee2010-07-06 23:11:01 +000099} //end anonymous namespace
100
Jordy Rosea5261542010-08-14 21:02:52 +0000101namespace clang {
102 template <>
103 struct GRStateTrait<CStringLength>
104 : public GRStatePartialTrait<CStringLength::EntryMap> {
105 static void *GDMIndex() { return CStringChecker::getTag(); }
106 };
107}
108
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000109void clang::RegisterCStringChecker(GRExprEngine &Eng) {
110 Eng.registerCheck(new CStringChecker());
111}
112
Jordy Rosed325ffb2010-07-08 23:57:29 +0000113//===----------------------------------------------------------------------===//
114// Individual checks and utility methods.
115//===----------------------------------------------------------------------===//
116
117std::pair<const GRState*, const GRState*>
Ted Kremenek28f47b92010-12-01 22:16:56 +0000118CStringChecker::assumeZero(CheckerContext &C, const GRState *state, SVal V,
Jordy Rosed325ffb2010-07-08 23:57:29 +0000119 QualType Ty) {
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000120 DefinedSVal *val = dyn_cast<DefinedSVal>(&V);
121 if (!val)
Jordy Rosed325ffb2010-07-08 23:57:29 +0000122 return std::pair<const GRState*, const GRState *>(state, state);
Jordy Rosea6b808c2010-07-07 07:48:06 +0000123
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000124 SValBuilder &svalBuilder = C.getSValBuilder();
125 DefinedOrUnknownSVal zero = svalBuilder.makeZeroVal(Ty);
126 return state->assume(svalBuilder.evalEQ(state, *val, zero));
Jordy Rosed325ffb2010-07-08 23:57:29 +0000127}
Jordy Rosea6b808c2010-07-07 07:48:06 +0000128
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000129const GRState *CStringChecker::checkNonNull(CheckerContext &C,
Jordy Rosed325ffb2010-07-08 23:57:29 +0000130 const GRState *state,
131 const Expr *S, SVal l) {
132 // If a previous check has failed, propagate the failure.
133 if (!state)
134 return NULL;
135
136 const GRState *stateNull, *stateNonNull;
Ted Kremenek28f47b92010-12-01 22:16:56 +0000137 llvm::tie(stateNull, stateNonNull) = assumeZero(C, state, l, S->getType());
Jordy Rosed325ffb2010-07-08 23:57:29 +0000138
139 if (stateNull && !stateNonNull) {
Ted Kremenekd048c6e2010-12-20 21:19:09 +0000140 ExplodedNode *N = C.generateSink(stateNull);
Jordy Rosea6b808c2010-07-07 07:48:06 +0000141 if (!N)
142 return NULL;
143
Jordy Rosed325ffb2010-07-08 23:57:29 +0000144 if (!BT_Null)
145 BT_Null = new BuiltinBug("API",
Jordy Rosea6b808c2010-07-07 07:48:06 +0000146 "Null pointer argument in call to byte string function");
147
148 // Generate a report for this bug.
Jordy Rosed325ffb2010-07-08 23:57:29 +0000149 BuiltinBug *BT = static_cast<BuiltinBug*>(BT_Null);
Jordy Rosea6b808c2010-07-07 07:48:06 +0000150 EnhancedBugReport *report = new EnhancedBugReport(*BT,
151 BT->getDescription(), N);
152
153 report->addRange(S->getSourceRange());
154 report->addVisitorCreator(bugreporter::registerTrackNullOrUndefValue, S);
155 C.EmitReport(report);
156 return NULL;
157 }
158
159 // From here on, assume that the value is non-null.
Jordy Rosed325ffb2010-07-08 23:57:29 +0000160 assert(stateNonNull);
161 return stateNonNull;
Jordy Rosea6b808c2010-07-07 07:48:06 +0000162}
163
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000164// FIXME: This was originally copied from ArrayBoundChecker.cpp. Refactor?
165const GRState *CStringChecker::CheckLocation(CheckerContext &C,
166 const GRState *state,
Jordy Rosee64f3112010-08-16 07:51:42 +0000167 const Expr *S, SVal l,
168 bool IsDestination) {
Jordy Rosed325ffb2010-07-08 23:57:29 +0000169 // If a previous check has failed, propagate the failure.
170 if (!state)
171 return NULL;
172
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000173 // Check for out of bound array element access.
174 const MemRegion *R = l.getAsRegion();
175 if (!R)
176 return state;
177
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000178 const ElementRegion *ER = dyn_cast<ElementRegion>(R);
179 if (!ER)
180 return state;
181
Zhongxing Xu018220c2010-08-11 06:10:55 +0000182 assert(ER->getValueType() == C.getASTContext().CharTy &&
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000183 "CheckLocation should only be called with char* ElementRegions");
184
185 // Get the size of the array.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000186 const SubRegion *superReg = cast<SubRegion>(ER->getSuperRegion());
187 SValBuilder &svalBuilder = C.getSValBuilder();
188 SVal Extent = svalBuilder.convertToArrayIndex(superReg->getExtent(svalBuilder));
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000189 DefinedOrUnknownSVal Size = cast<DefinedOrUnknownSVal>(Extent);
190
191 // Get the index of the accessed element.
Gabor Greif89b06582010-09-09 10:51:37 +0000192 DefinedOrUnknownSVal Idx = cast<DefinedOrUnknownSVal>(ER->getIndex());
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000193
Ted Kremenek28f47b92010-12-01 22:16:56 +0000194 const GRState *StInBound = state->assumeInBound(Idx, Size, true);
195 const GRState *StOutBound = state->assumeInBound(Idx, Size, false);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000196 if (StOutBound && !StInBound) {
Ted Kremenekd048c6e2010-12-20 21:19:09 +0000197 ExplodedNode *N = C.generateSink(StOutBound);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000198 if (!N)
199 return NULL;
200
Jordy Rosee64f3112010-08-16 07:51:42 +0000201 BuiltinBug *BT;
202 if (IsDestination) {
203 if (!BT_BoundsWrite) {
204 BT_BoundsWrite = new BuiltinBug("Out-of-bound array access",
205 "Byte string function overflows destination buffer");
206 }
207 BT = static_cast<BuiltinBug*>(BT_BoundsWrite);
208 } else {
209 if (!BT_Bounds) {
210 BT_Bounds = new BuiltinBug("Out-of-bound array access",
211 "Byte string function accesses out-of-bound array element");
212 }
213 BT = static_cast<BuiltinBug*>(BT_Bounds);
214 }
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000215
216 // FIXME: It would be nice to eventually make this diagnostic more clear,
217 // e.g., by referencing the original declaration or by saying *why* this
218 // reference is outside the range.
219
220 // Generate a report for this bug.
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000221 RangedBugReport *report = new RangedBugReport(*BT, BT->getDescription(), N);
222
223 report->addRange(S->getSourceRange());
224 C.EmitReport(report);
225 return NULL;
226 }
227
228 // Array bound check succeeded. From this point forward the array bound
229 // should always succeed.
230 return StInBound;
231}
232
233const GRState *CStringChecker::CheckBufferAccess(CheckerContext &C,
234 const GRState *state,
235 const Expr *Size,
236 const Expr *FirstBuf,
Jordy Rosee64f3112010-08-16 07:51:42 +0000237 const Expr *SecondBuf,
238 bool FirstIsDestination) {
Jordy Rosed325ffb2010-07-08 23:57:29 +0000239 // If a previous check has failed, propagate the failure.
240 if (!state)
241 return NULL;
242
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000243 SValBuilder &svalBuilder = C.getSValBuilder();
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000244 ASTContext &Ctx = C.getASTContext();
245
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000246 QualType sizeTy = Size->getType();
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000247 QualType PtrTy = Ctx.getPointerType(Ctx.CharTy);
248
Jordy Rosea6b808c2010-07-07 07:48:06 +0000249 // Check that the first buffer is non-null.
250 SVal BufVal = state->getSVal(FirstBuf);
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000251 state = checkNonNull(C, state, FirstBuf, BufVal);
Jordy Rosea6b808c2010-07-07 07:48:06 +0000252 if (!state)
253 return NULL;
254
Jordy Rosed325ffb2010-07-08 23:57:29 +0000255 // Get the access length and make sure it is known.
256 SVal LengthVal = state->getSVal(Size);
257 NonLoc *Length = dyn_cast<NonLoc>(&LengthVal);
258 if (!Length)
259 return state;
260
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000261 // Compute the offset of the last element to be accessed: size-1.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000262 NonLoc One = cast<NonLoc>(svalBuilder.makeIntVal(1, sizeTy));
263 NonLoc LastOffset = cast<NonLoc>(svalBuilder.evalBinOpNN(state, BO_Sub,
264 *Length, One, sizeTy));
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000265
Jordy Rosea6b808c2010-07-07 07:48:06 +0000266 // Check that the first buffer is sufficently long.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000267 SVal BufStart = svalBuilder.evalCast(BufVal, PtrTy, FirstBuf->getType());
Jordy Roseb6a40262010-08-05 23:11:30 +0000268 if (Loc *BufLoc = dyn_cast<Loc>(&BufStart)) {
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000269 SVal BufEnd = svalBuilder.evalBinOpLN(state, BO_Add, *BufLoc,
270 LastOffset, PtrTy);
Jordy Rosee64f3112010-08-16 07:51:42 +0000271 state = CheckLocation(C, state, FirstBuf, BufEnd, FirstIsDestination);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000272
Jordy Roseb6a40262010-08-05 23:11:30 +0000273 // If the buffer isn't large enough, abort.
274 if (!state)
275 return NULL;
276 }
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000277
278 // If there's a second buffer, check it as well.
279 if (SecondBuf) {
280 BufVal = state->getSVal(SecondBuf);
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000281 state = checkNonNull(C, state, SecondBuf, BufVal);
Jordy Rosea6b808c2010-07-07 07:48:06 +0000282 if (!state)
283 return NULL;
284
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000285 BufStart = svalBuilder.evalCast(BufVal, PtrTy, SecondBuf->getType());
Jordy Roseb6a40262010-08-05 23:11:30 +0000286 if (Loc *BufLoc = dyn_cast<Loc>(&BufStart)) {
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000287 SVal BufEnd = svalBuilder.evalBinOpLN(state, BO_Add, *BufLoc,
288 LastOffset, PtrTy);
Jordy Roseb6a40262010-08-05 23:11:30 +0000289 state = CheckLocation(C, state, SecondBuf, BufEnd);
290 }
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000291 }
292
293 // Large enough or not, return this state!
294 return state;
295}
296
297const GRState *CStringChecker::CheckOverlap(CheckerContext &C,
298 const GRState *state,
Jordy Rosed325ffb2010-07-08 23:57:29 +0000299 const Expr *Size,
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000300 const Expr *First,
Jordy Rosed325ffb2010-07-08 23:57:29 +0000301 const Expr *Second) {
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000302 // Do a simple check for overlap: if the two arguments are from the same
303 // buffer, see if the end of the first is greater than the start of the second
304 // or vice versa.
305
Jordy Rosed325ffb2010-07-08 23:57:29 +0000306 // If a previous check has failed, propagate the failure.
307 if (!state)
308 return NULL;
309
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000310 const GRState *stateTrue, *stateFalse;
311
312 // Get the buffer values and make sure they're known locations.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000313 SVal firstVal = state->getSVal(First);
314 SVal secondVal = state->getSVal(Second);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000315
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000316 Loc *firstLoc = dyn_cast<Loc>(&firstVal);
317 if (!firstLoc)
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000318 return state;
319
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000320 Loc *secondLoc = dyn_cast<Loc>(&secondVal);
321 if (!secondLoc)
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000322 return state;
323
324 // Are the two values the same?
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000325 SValBuilder &svalBuilder = C.getSValBuilder();
326 llvm::tie(stateTrue, stateFalse) =
327 state->assume(svalBuilder.evalEQ(state, *firstLoc, *secondLoc));
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000328
329 if (stateTrue && !stateFalse) {
330 // If the values are known to be equal, that's automatically an overlap.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000331 emitOverlapBug(C, stateTrue, First, Second);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000332 return NULL;
333 }
334
Ted Kremenek28f47b92010-12-01 22:16:56 +0000335 // assume the two expressions are not equal.
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000336 assert(stateFalse);
337 state = stateFalse;
338
339 // Which value comes first?
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000340 ASTContext &Ctx = svalBuilder.getContext();
341 QualType cmpTy = Ctx.IntTy;
342 SVal reverse = svalBuilder.evalBinOpLL(state, BO_GT,
343 *firstLoc, *secondLoc, cmpTy);
344 DefinedOrUnknownSVal *reverseTest = dyn_cast<DefinedOrUnknownSVal>(&reverse);
345 if (!reverseTest)
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000346 return state;
347
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000348 llvm::tie(stateTrue, stateFalse) = state->assume(*reverseTest);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000349 if (stateTrue) {
350 if (stateFalse) {
351 // If we don't know which one comes first, we can't perform this test.
352 return state;
353 } else {
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000354 // Switch the values so that firstVal is before secondVal.
355 Loc *tmpLoc = firstLoc;
356 firstLoc = secondLoc;
357 secondLoc = tmpLoc;
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000358
359 // Switch the Exprs as well, so that they still correspond.
360 const Expr *tmpExpr = First;
361 First = Second;
362 Second = tmpExpr;
363 }
364 }
365
366 // Get the length, and make sure it too is known.
367 SVal LengthVal = state->getSVal(Size);
368 NonLoc *Length = dyn_cast<NonLoc>(&LengthVal);
369 if (!Length)
370 return state;
371
372 // Convert the first buffer's start address to char*.
373 // Bail out if the cast fails.
374 QualType CharPtrTy = Ctx.getPointerType(Ctx.CharTy);
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000375 SVal FirstStart = svalBuilder.evalCast(*firstLoc, CharPtrTy, First->getType());
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000376 Loc *FirstStartLoc = dyn_cast<Loc>(&FirstStart);
377 if (!FirstStartLoc)
378 return state;
379
380 // Compute the end of the first buffer. Bail out if THAT fails.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000381 SVal FirstEnd = svalBuilder.evalBinOpLN(state, BO_Add,
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000382 *FirstStartLoc, *Length, CharPtrTy);
383 Loc *FirstEndLoc = dyn_cast<Loc>(&FirstEnd);
384 if (!FirstEndLoc)
385 return state;
386
387 // Is the end of the first buffer past the start of the second buffer?
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000388 SVal Overlap = svalBuilder.evalBinOpLL(state, BO_GT,
389 *FirstEndLoc, *secondLoc, cmpTy);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000390 DefinedOrUnknownSVal *OverlapTest = dyn_cast<DefinedOrUnknownSVal>(&Overlap);
391 if (!OverlapTest)
392 return state;
393
Ted Kremenek28f47b92010-12-01 22:16:56 +0000394 llvm::tie(stateTrue, stateFalse) = state->assume(*OverlapTest);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000395
396 if (stateTrue && !stateFalse) {
397 // Overlap!
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000398 emitOverlapBug(C, stateTrue, First, Second);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000399 return NULL;
400 }
401
Ted Kremenek28f47b92010-12-01 22:16:56 +0000402 // assume the two expressions don't overlap.
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000403 assert(stateFalse);
404 return stateFalse;
405}
406
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000407void CStringChecker::emitOverlapBug(CheckerContext &C, const GRState *state,
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000408 const Stmt *First, const Stmt *Second) {
Ted Kremenekd048c6e2010-12-20 21:19:09 +0000409 ExplodedNode *N = C.generateSink(state);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000410 if (!N)
411 return;
412
413 if (!BT_Overlap)
414 BT_Overlap = new BugType("Unix API", "Improper arguments");
415
416 // Generate a report for this bug.
417 RangedBugReport *report =
418 new RangedBugReport(*BT_Overlap,
419 "Arguments must not be overlapping buffers", N);
420 report->addRange(First->getSourceRange());
421 report->addRange(Second->getSourceRange());
422
423 C.EmitReport(report);
424}
425
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000426const GRState *CStringChecker::setCStringLength(const GRState *state,
Jordy Rosee64f3112010-08-16 07:51:42 +0000427 const MemRegion *MR,
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000428 SVal strLength) {
429 assert(!strLength.isUndef() && "Attempt to set an undefined string length");
430 if (strLength.isUnknown())
Jordy Rosee64f3112010-08-16 07:51:42 +0000431 return state;
432
433 MR = MR->StripCasts();
434
435 switch (MR->getKind()) {
436 case MemRegion::StringRegionKind:
437 // FIXME: This can happen if we strcpy() into a string region. This is
438 // undefined [C99 6.4.5p6], but we should still warn about it.
439 return state;
440
441 case MemRegion::SymbolicRegionKind:
442 case MemRegion::AllocaRegionKind:
443 case MemRegion::VarRegionKind:
444 case MemRegion::FieldRegionKind:
445 case MemRegion::ObjCIvarRegionKind:
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000446 return state->set<CStringLength>(MR, strLength);
Jordy Rosee64f3112010-08-16 07:51:42 +0000447
448 case MemRegion::ElementRegionKind:
449 // FIXME: Handle element regions by upper-bounding the parent region's
450 // string length.
451 return state;
452
453 default:
454 // Other regions (mostly non-data) can't have a reliable C string length.
455 // For now, just ignore the change.
456 // FIXME: These are rare but not impossible. We should output some kind of
457 // warning for things like strcpy((char[]){'a', 0}, "b");
458 return state;
459 }
460}
461
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000462SVal CStringChecker::getCStringLengthForRegion(CheckerContext &C,
Jordy Rosea5261542010-08-14 21:02:52 +0000463 const GRState *&state,
464 const Expr *Ex,
465 const MemRegion *MR) {
466 // If there's a recorded length, go ahead and return it.
467 const SVal *Recorded = state->get<CStringLength>(MR);
468 if (Recorded)
469 return *Recorded;
470
471 // Otherwise, get a new symbol and update the state.
472 unsigned Count = C.getNodeBuilder().getCurrentBlockCount();
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000473 SValBuilder &svalBuilder = C.getSValBuilder();
474 QualType sizeTy = svalBuilder.getContext().getSizeType();
475 SVal strLength = svalBuilder.getMetadataSymbolVal(getTag(), MR, Ex, sizeTy, Count);
476 state = state->set<CStringLength>(MR, strLength);
477 return strLength;
Jordy Rosea5261542010-08-14 21:02:52 +0000478}
479
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000480SVal CStringChecker::getCStringLength(CheckerContext &C, const GRState *&state,
Jordy Rose19c5dd12010-07-27 01:37:31 +0000481 const Expr *Ex, SVal Buf) {
482 const MemRegion *MR = Buf.getAsRegion();
483 if (!MR) {
484 // If we can't get a region, see if it's something we /know/ isn't a
485 // C string. In the context of locations, the only time we can issue such
486 // a warning is for labels.
487 if (loc::GotoLabel *Label = dyn_cast<loc::GotoLabel>(&Buf)) {
Ted Kremenekd048c6e2010-12-20 21:19:09 +0000488 if (ExplodedNode *N = C.generateNode(state)) {
Jordy Rose19c5dd12010-07-27 01:37:31 +0000489 if (!BT_NotCString)
490 BT_NotCString = new BuiltinBug("API",
491 "Argument is not a null-terminated string.");
492
493 llvm::SmallString<120> buf;
494 llvm::raw_svector_ostream os(buf);
495 os << "Argument to byte string function is the address of the label '"
496 << Label->getLabel()->getID()->getName()
497 << "', which is not a null-terminated string";
498
499 // Generate a report for this bug.
500 EnhancedBugReport *report = new EnhancedBugReport(*BT_NotCString,
501 os.str(), N);
502
503 report->addRange(Ex->getSourceRange());
504 C.EmitReport(report);
505 }
506
507 return UndefinedVal();
508 }
509
Jordy Rosea5261542010-08-14 21:02:52 +0000510 // If it's not a region and not a label, give up.
511 return UnknownVal();
Jordy Rose19c5dd12010-07-27 01:37:31 +0000512 }
513
Jordy Rosea5261542010-08-14 21:02:52 +0000514 // If we have a region, strip casts from it and see if we can figure out
515 // its length. For anything we can't figure out, just return UnknownVal.
516 MR = MR->StripCasts();
517
518 switch (MR->getKind()) {
519 case MemRegion::StringRegionKind: {
520 // Modifying the contents of string regions is undefined [C99 6.4.5p6],
521 // so we can assume that the byte length is the correct C string length.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000522 SValBuilder &svalBuilder = C.getSValBuilder();
523 QualType sizeTy = svalBuilder.getContext().getSizeType();
524 const StringLiteral *strLit = cast<StringRegion>(MR)->getStringLiteral();
525 return svalBuilder.makeIntVal(strLit->getByteLength(), sizeTy);
Jordy Rosea5261542010-08-14 21:02:52 +0000526 }
527 case MemRegion::SymbolicRegionKind:
528 case MemRegion::AllocaRegionKind:
529 case MemRegion::VarRegionKind:
530 case MemRegion::FieldRegionKind:
531 case MemRegion::ObjCIvarRegionKind:
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000532 return getCStringLengthForRegion(C, state, Ex, MR);
Jordy Rosea5261542010-08-14 21:02:52 +0000533 case MemRegion::CompoundLiteralRegionKind:
534 // FIXME: Can we track this? Is it necessary?
535 return UnknownVal();
536 case MemRegion::ElementRegionKind:
537 // FIXME: How can we handle this? It's not good enough to subtract the
538 // offset from the base string length; consider "123\x00567" and &a[5].
539 return UnknownVal();
540 default:
541 // Other regions (mostly non-data) can't have a reliable C string length.
542 // In this case, an error is emitted and UndefinedVal is returned.
543 // The caller should always be prepared to handle this case.
Ted Kremenekd048c6e2010-12-20 21:19:09 +0000544 if (ExplodedNode *N = C.generateNode(state)) {
Jordy Rosea5261542010-08-14 21:02:52 +0000545 if (!BT_NotCString)
546 BT_NotCString = new BuiltinBug("API",
547 "Argument is not a null-terminated string.");
548
549 llvm::SmallString<120> buf;
550 llvm::raw_svector_ostream os(buf);
551
552 os << "Argument to byte string function is ";
553
554 if (SummarizeRegion(os, C.getASTContext(), MR))
555 os << ", which is not a null-terminated string";
556 else
557 os << "not a null-terminated string";
558
559 // Generate a report for this bug.
560 EnhancedBugReport *report = new EnhancedBugReport(*BT_NotCString,
561 os.str(), N);
562
563 report->addRange(Ex->getSourceRange());
564 C.EmitReport(report);
565 }
566
567 return UndefinedVal();
568 }
Jordy Rose19c5dd12010-07-27 01:37:31 +0000569}
570
Jordy Rosee64f3112010-08-16 07:51:42 +0000571const GRState *CStringChecker::InvalidateBuffer(CheckerContext &C,
572 const GRState *state,
573 const Expr *E, SVal V) {
574 Loc *L = dyn_cast<Loc>(&V);
575 if (!L)
576 return state;
577
578 // FIXME: This is a simplified version of what's in CFRefCount.cpp -- it makes
579 // some assumptions about the value that CFRefCount can't. Even so, it should
580 // probably be refactored.
581 if (loc::MemRegionVal* MR = dyn_cast<loc::MemRegionVal>(L)) {
582 const MemRegion *R = MR->getRegion()->StripCasts();
583
584 // Are we dealing with an ElementRegion? If so, we should be invalidating
585 // the super-region.
586 if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
587 R = ER->getSuperRegion();
588 // FIXME: What about layers of ElementRegions?
589 }
590
591 // Invalidate this region.
592 unsigned Count = C.getNodeBuilder().getCurrentBlockCount();
593 return state->InvalidateRegion(R, E, Count, NULL);
594 }
595
596 // If we have a non-region value by chance, just remove the binding.
597 // FIXME: is this necessary or correct? This handles the non-Region
598 // cases. Is it ever valid to store to these?
599 return state->unbindLoc(*L);
600}
601
Jordy Rose19c5dd12010-07-27 01:37:31 +0000602bool CStringChecker::SummarizeRegion(llvm::raw_ostream& os, ASTContext& Ctx,
603 const MemRegion *MR) {
604 const TypedRegion *TR = dyn_cast<TypedRegion>(MR);
605 if (!TR)
606 return false;
607
608 switch (TR->getKind()) {
609 case MemRegion::FunctionTextRegionKind: {
610 const FunctionDecl *FD = cast<FunctionTextRegion>(TR)->getDecl();
611 if (FD)
612 os << "the address of the function '" << FD << "'";
613 else
614 os << "the address of a function";
615 return true;
616 }
617 case MemRegion::BlockTextRegionKind:
618 os << "block text";
619 return true;
620 case MemRegion::BlockDataRegionKind:
621 os << "a block";
622 return true;
623 case MemRegion::CXXThisRegionKind:
Zhongxing Xu02fe28c2010-11-26 08:52:48 +0000624 case MemRegion::CXXTempObjectRegionKind:
625 os << "a C++ temp object of type " << TR->getValueType().getAsString();
Jordy Rose19c5dd12010-07-27 01:37:31 +0000626 return true;
627 case MemRegion::VarRegionKind:
Zhongxing Xu018220c2010-08-11 06:10:55 +0000628 os << "a variable of type" << TR->getValueType().getAsString();
Jordy Rose19c5dd12010-07-27 01:37:31 +0000629 return true;
630 case MemRegion::FieldRegionKind:
Zhongxing Xu018220c2010-08-11 06:10:55 +0000631 os << "a field of type " << TR->getValueType().getAsString();
Jordy Rose19c5dd12010-07-27 01:37:31 +0000632 return true;
633 case MemRegion::ObjCIvarRegionKind:
Zhongxing Xu018220c2010-08-11 06:10:55 +0000634 os << "an instance variable of type " << TR->getValueType().getAsString();
Jordy Rose19c5dd12010-07-27 01:37:31 +0000635 return true;
636 default:
637 return false;
638 }
639}
640
Jordy Rosed325ffb2010-07-08 23:57:29 +0000641//===----------------------------------------------------------------------===//
Ted Kremenek9c149532010-12-01 21:57:22 +0000642// evaluation of individual function calls.
Jordy Rosed325ffb2010-07-08 23:57:29 +0000643//===----------------------------------------------------------------------===//
644
Ted Kremenek9c149532010-12-01 21:57:22 +0000645void CStringChecker::evalCopyCommon(CheckerContext &C, const GRState *state,
Jordy Rosed325ffb2010-07-08 23:57:29 +0000646 const Expr *Size, const Expr *Dest,
647 const Expr *Source, bool Restricted) {
648 // See if the size argument is zero.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000649 SVal sizeVal = state->getSVal(Size);
650 QualType sizeTy = Size->getType();
Jordy Rosed325ffb2010-07-08 23:57:29 +0000651
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000652 const GRState *stateZeroSize, *stateNonZeroSize;
653 llvm::tie(stateZeroSize, stateNonZeroSize) = assumeZero(C, state, sizeVal, sizeTy);
Jordy Rosed325ffb2010-07-08 23:57:29 +0000654
655 // If the size is zero, there won't be any actual memory access.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000656 if (stateZeroSize)
657 C.addTransition(stateZeroSize);
Jordy Rosed325ffb2010-07-08 23:57:29 +0000658
659 // If the size can be nonzero, we have to check the other arguments.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000660 if (stateNonZeroSize) {
661 state = stateNonZeroSize;
Jordy Rosee64f3112010-08-16 07:51:42 +0000662 state = CheckBufferAccess(C, state, Size, Dest, Source,
663 /* FirstIsDst = */ true);
Jordy Rosed325ffb2010-07-08 23:57:29 +0000664 if (Restricted)
665 state = CheckOverlap(C, state, Size, Dest, Source);
Jordy Rosee64f3112010-08-16 07:51:42 +0000666
667 if (state) {
668 // Invalidate the destination.
669 // FIXME: Even if we can't perfectly model the copy, we should see if we
670 // can use LazyCompoundVals to copy the source values into the destination.
671 // This would probably remove any existing bindings past the end of the
672 // copied region, but that's still an improvement over blank invalidation.
673 state = InvalidateBuffer(C, state, Dest, state->getSVal(Dest));
Jordy Rosed325ffb2010-07-08 23:57:29 +0000674 C.addTransition(state);
Jordy Rosee64f3112010-08-16 07:51:42 +0000675 }
Jordy Rosed325ffb2010-07-08 23:57:29 +0000676 }
677}
678
679
Ted Kremenek9c149532010-12-01 21:57:22 +0000680void CStringChecker::evalMemcpy(CheckerContext &C, const CallExpr *CE) {
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000681 // void *memcpy(void *restrict dst, const void *restrict src, size_t n);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000682 // The return value is the address of the destination buffer.
Jordy Rosed325ffb2010-07-08 23:57:29 +0000683 const Expr *Dest = CE->getArg(0);
684 const GRState *state = C.getState();
685 state = state->BindExpr(CE, state->getSVal(Dest));
Ted Kremenek9c149532010-12-01 21:57:22 +0000686 evalCopyCommon(C, state, CE->getArg(2), Dest, CE->getArg(1), true);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000687}
688
Ted Kremenek9c149532010-12-01 21:57:22 +0000689void CStringChecker::evalMemmove(CheckerContext &C, const CallExpr *CE) {
Jordy Rosed325ffb2010-07-08 23:57:29 +0000690 // void *memmove(void *dst, const void *src, size_t n);
691 // The return value is the address of the destination buffer.
692 const Expr *Dest = CE->getArg(0);
693 const GRState *state = C.getState();
694 state = state->BindExpr(CE, state->getSVal(Dest));
Ted Kremenek9c149532010-12-01 21:57:22 +0000695 evalCopyCommon(C, state, CE->getArg(2), Dest, CE->getArg(1));
Jordy Rosed325ffb2010-07-08 23:57:29 +0000696}
697
Ted Kremenek9c149532010-12-01 21:57:22 +0000698void CStringChecker::evalBcopy(CheckerContext &C, const CallExpr *CE) {
Jordy Rosed325ffb2010-07-08 23:57:29 +0000699 // void bcopy(const void *src, void *dst, size_t n);
Ted Kremenek9c149532010-12-01 21:57:22 +0000700 evalCopyCommon(C, C.getState(), CE->getArg(2), CE->getArg(1), CE->getArg(0));
Jordy Rosed325ffb2010-07-08 23:57:29 +0000701}
702
Ted Kremenek9c149532010-12-01 21:57:22 +0000703void CStringChecker::evalMemcmp(CheckerContext &C, const CallExpr *CE) {
Jordy Rosebc56d1f2010-07-07 08:15:01 +0000704 // int memcmp(const void *s1, const void *s2, size_t n);
705 const Expr *Left = CE->getArg(0);
706 const Expr *Right = CE->getArg(1);
707 const Expr *Size = CE->getArg(2);
708
709 const GRState *state = C.getState();
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000710 SValBuilder &svalBuilder = C.getSValBuilder();
Jordy Rosebc56d1f2010-07-07 08:15:01 +0000711
Jordy Rosed325ffb2010-07-08 23:57:29 +0000712 // See if the size argument is zero.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000713 SVal sizeVal = state->getSVal(Size);
714 QualType sizeTy = Size->getType();
Jordy Rosebc56d1f2010-07-07 08:15:01 +0000715
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000716 const GRState *stateZeroSize, *stateNonZeroSize;
717 llvm::tie(stateZeroSize, stateNonZeroSize) =
718 assumeZero(C, state, sizeVal, sizeTy);
Jordy Rosebc56d1f2010-07-07 08:15:01 +0000719
Jordy Rosed325ffb2010-07-08 23:57:29 +0000720 // If the size can be zero, the result will be 0 in that case, and we don't
721 // have to check either of the buffers.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000722 if (stateZeroSize) {
723 state = stateZeroSize;
724 state = state->BindExpr(CE, svalBuilder.makeZeroVal(CE->getType()));
Jordy Rosed325ffb2010-07-08 23:57:29 +0000725 C.addTransition(state);
Jordy Rosebc56d1f2010-07-07 08:15:01 +0000726 }
727
Jordy Rosed325ffb2010-07-08 23:57:29 +0000728 // If the size can be nonzero, we have to check the other arguments.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000729 if (stateNonZeroSize) {
730 state = stateNonZeroSize;
Jordy Rosed325ffb2010-07-08 23:57:29 +0000731 // If we know the two buffers are the same, we know the result is 0.
732 // First, get the two buffers' addresses. Another checker will have already
733 // made sure they're not undefined.
734 DefinedOrUnknownSVal LV = cast<DefinedOrUnknownSVal>(state->getSVal(Left));
735 DefinedOrUnknownSVal RV = cast<DefinedOrUnknownSVal>(state->getSVal(Right));
Jordy Rosebc56d1f2010-07-07 08:15:01 +0000736
Jordy Rosed325ffb2010-07-08 23:57:29 +0000737 // See if they are the same.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000738 DefinedOrUnknownSVal SameBuf = svalBuilder.evalEQ(state, LV, RV);
Jordy Rosed325ffb2010-07-08 23:57:29 +0000739 const GRState *StSameBuf, *StNotSameBuf;
Ted Kremenek28f47b92010-12-01 22:16:56 +0000740 llvm::tie(StSameBuf, StNotSameBuf) = state->assume(SameBuf);
Jordy Rosed325ffb2010-07-08 23:57:29 +0000741
742 // If the two arguments might be the same buffer, we know the result is zero,
743 // and we only need to check one size.
744 if (StSameBuf) {
745 state = StSameBuf;
746 state = CheckBufferAccess(C, state, Size, Left);
747 if (state) {
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000748 state = StSameBuf->BindExpr(CE, svalBuilder.makeZeroVal(CE->getType()));
Jordy Rosed325ffb2010-07-08 23:57:29 +0000749 C.addTransition(state);
750 }
751 }
752
753 // If the two arguments might be different buffers, we have to check the
754 // size of both of them.
755 if (StNotSameBuf) {
756 state = StNotSameBuf;
757 state = CheckBufferAccess(C, state, Size, Left, Right);
758 if (state) {
759 // The return value is the comparison result, which we don't know.
760 unsigned Count = C.getNodeBuilder().getCurrentBlockCount();
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000761 SVal CmpV = svalBuilder.getConjuredSymbolVal(NULL, CE, Count);
Jordy Rosed325ffb2010-07-08 23:57:29 +0000762 state = state->BindExpr(CE, CmpV);
763 C.addTransition(state);
764 }
765 }
766 }
Jordy Rosebc56d1f2010-07-07 08:15:01 +0000767}
768
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000769void CStringChecker::evalstrLength(CheckerContext &C, const CallExpr *CE) {
Jordy Rose19c5dd12010-07-27 01:37:31 +0000770 // size_t strlen(const char *s);
771 const GRState *state = C.getState();
772 const Expr *Arg = CE->getArg(0);
773 SVal ArgVal = state->getSVal(Arg);
774
775 // Check that the argument is non-null.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000776 state = checkNonNull(C, state, Arg, ArgVal);
Jordy Rose19c5dd12010-07-27 01:37:31 +0000777
778 if (state) {
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000779 SVal strLength = getCStringLength(C, state, Arg, ArgVal);
Jordy Rosea5261542010-08-14 21:02:52 +0000780
781 // If the argument isn't a valid C string, there's no valid state to
782 // transition to.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000783 if (strLength.isUndef())
Jordy Rosea5261542010-08-14 21:02:52 +0000784 return;
785
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000786 // If getCStringLength couldn't figure out the length, conjure a return
Jordy Rosea5261542010-08-14 21:02:52 +0000787 // value, so it can be used in constraints, at least.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000788 if (strLength.isUnknown()) {
Jordy Rosea5261542010-08-14 21:02:52 +0000789 unsigned Count = C.getNodeBuilder().getCurrentBlockCount();
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000790 strLength = C.getSValBuilder().getConjuredSymbolVal(NULL, CE, Count);
Jordy Rose19c5dd12010-07-27 01:37:31 +0000791 }
Jordy Rosea5261542010-08-14 21:02:52 +0000792
793 // Bind the return value.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000794 state = state->BindExpr(CE, strLength);
Jordy Rosea5261542010-08-14 21:02:52 +0000795 C.addTransition(state);
Jordy Rose19c5dd12010-07-27 01:37:31 +0000796 }
797}
798
Ted Kremenek9c149532010-12-01 21:57:22 +0000799void CStringChecker::evalStrcpy(CheckerContext &C, const CallExpr *CE) {
Jordy Rosee64f3112010-08-16 07:51:42 +0000800 // char *strcpy(char *restrict dst, const char *restrict src);
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000801 evalStrcpyCommon(C, CE, /* returnEnd = */ false);
Jordy Rosee64f3112010-08-16 07:51:42 +0000802}
803
Ted Kremenek9c149532010-12-01 21:57:22 +0000804void CStringChecker::evalStpcpy(CheckerContext &C, const CallExpr *CE) {
Jordy Rosee64f3112010-08-16 07:51:42 +0000805 // char *stpcpy(char *restrict dst, const char *restrict src);
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000806 evalStrcpyCommon(C, CE, /* returnEnd = */ true);
Jordy Rosee64f3112010-08-16 07:51:42 +0000807}
808
Ted Kremenek9c149532010-12-01 21:57:22 +0000809void CStringChecker::evalStrcpyCommon(CheckerContext &C, const CallExpr *CE,
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000810 bool returnEnd) {
Jordy Rosee64f3112010-08-16 07:51:42 +0000811 const GRState *state = C.getState();
812
813 // Check that the destination is non-null
814 const Expr *Dst = CE->getArg(0);
815 SVal DstVal = state->getSVal(Dst);
816
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000817 state = checkNonNull(C, state, Dst, DstVal);
Jordy Rosee64f3112010-08-16 07:51:42 +0000818 if (!state)
819 return;
820
821 // Check that the source is non-null.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000822 const Expr *srcExpr = CE->getArg(1);
823 SVal srcVal = state->getSVal(srcExpr);
824 state = checkNonNull(C, state, srcExpr, srcVal);
Jordy Rosee64f3112010-08-16 07:51:42 +0000825 if (!state)
826 return;
827
828 // Get the string length of the source.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000829 SVal strLength = getCStringLength(C, state, srcExpr, srcVal);
Jordy Rosee64f3112010-08-16 07:51:42 +0000830
831 // If the source isn't a valid C string, give up.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000832 if (strLength.isUndef())
Jordy Rosee64f3112010-08-16 07:51:42 +0000833 return;
834
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000835 SVal Result = (returnEnd ? UnknownVal() : DstVal);
Jordy Rosee64f3112010-08-16 07:51:42 +0000836
837 // If the destination is a MemRegion, try to check for a buffer overflow and
838 // record the new string length.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000839 if (loc::MemRegionVal *dstRegVal = dyn_cast<loc::MemRegionVal>(&DstVal)) {
Jordy Rosee64f3112010-08-16 07:51:42 +0000840 // If the length is known, we can check for an overflow.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000841 if (NonLoc *knownStrLength = dyn_cast<NonLoc>(&strLength)) {
842 SVal lastElement =
843 C.getSValBuilder().evalBinOpLN(state, BO_Add, *dstRegVal,
844 *knownStrLength, Dst->getType());
Jordy Rosee64f3112010-08-16 07:51:42 +0000845
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000846 state = CheckLocation(C, state, Dst, lastElement, /* IsDst = */ true);
Jordy Rosee64f3112010-08-16 07:51:42 +0000847 if (!state)
848 return;
849
850 // If this is a stpcpy-style copy, the last element is the return value.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000851 if (returnEnd)
852 Result = lastElement;
Jordy Rosee64f3112010-08-16 07:51:42 +0000853 }
854
855 // Invalidate the destination. This must happen before we set the C string
856 // length because invalidation will clear the length.
857 // FIXME: Even if we can't perfectly model the copy, we should see if we
858 // can use LazyCompoundVals to copy the source values into the destination.
859 // This would probably remove any existing bindings past the end of the
860 // string, but that's still an improvement over blank invalidation.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000861 state = InvalidateBuffer(C, state, Dst, *dstRegVal);
Jordy Rosee64f3112010-08-16 07:51:42 +0000862
863 // Set the C string length of the destination.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000864 state = setCStringLength(state, dstRegVal->getRegion(), strLength);
Jordy Rosee64f3112010-08-16 07:51:42 +0000865 }
866
867 // If this is a stpcpy-style copy, but we were unable to check for a buffer
868 // overflow, we still need a result. Conjure a return value.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000869 if (returnEnd && Result.isUnknown()) {
870 SValBuilder &svalBuilder = C.getSValBuilder();
Jordy Rosee64f3112010-08-16 07:51:42 +0000871 unsigned Count = C.getNodeBuilder().getCurrentBlockCount();
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000872 strLength = svalBuilder.getConjuredSymbolVal(NULL, CE, Count);
Jordy Rosee64f3112010-08-16 07:51:42 +0000873 }
874
875 // Set the return value.
876 state = state->BindExpr(CE, Result);
877 C.addTransition(state);
878}
879
Jordy Rosed325ffb2010-07-08 23:57:29 +0000880//===----------------------------------------------------------------------===//
Jordy Rosea5261542010-08-14 21:02:52 +0000881// The driver method, and other Checker callbacks.
Jordy Rosed325ffb2010-07-08 23:57:29 +0000882//===----------------------------------------------------------------------===//
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000883
Ted Kremenek9c149532010-12-01 21:57:22 +0000884bool CStringChecker::evalCallExpr(CheckerContext &C, const CallExpr *CE) {
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000885 // Get the callee. All the functions we care about are C functions
886 // with simple identifiers.
887 const GRState *state = C.getState();
888 const Expr *Callee = CE->getCallee();
889 const FunctionDecl *FD = state->getSVal(Callee).getAsFunctionDecl();
890
891 if (!FD)
892 return false;
893
894 // Get the name of the callee. If it's a builtin, strip off the prefix.
Douglas Gregor90d26a42010-11-01 23:16:05 +0000895 IdentifierInfo *II = FD->getIdentifier();
896 if (!II) // if no identifier, not a simple C function
897 return false;
898 llvm::StringRef Name = II->getName();
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000899 if (Name.startswith("__builtin_"))
900 Name = Name.substr(10);
901
Ted Kremenek9c149532010-12-01 21:57:22 +0000902 FnCheck evalFunction = llvm::StringSwitch<FnCheck>(Name)
903 .Cases("memcpy", "__memcpy_chk", &CStringChecker::evalMemcpy)
904 .Cases("memcmp", "bcmp", &CStringChecker::evalMemcmp)
905 .Cases("memmove", "__memmove_chk", &CStringChecker::evalMemmove)
906 .Cases("strcpy", "__strcpy_chk", &CStringChecker::evalStrcpy)
907 .Cases("stpcpy", "__stpcpy_chk", &CStringChecker::evalStpcpy)
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000908 .Case("strlen", &CStringChecker::evalstrLength)
Ted Kremenek9c149532010-12-01 21:57:22 +0000909 .Case("bcopy", &CStringChecker::evalBcopy)
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000910 .Default(NULL);
911
Jordy Rosed325ffb2010-07-08 23:57:29 +0000912 // If the callee isn't a string function, let another checker handle it.
Ted Kremenek9c149532010-12-01 21:57:22 +0000913 if (!evalFunction)
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000914 return false;
915
Jordy Rosed325ffb2010-07-08 23:57:29 +0000916 // Check and evaluate the call.
Ted Kremenek9c149532010-12-01 21:57:22 +0000917 (this->*evalFunction)(C, CE);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000918 return true;
919}
Jordy Rosea5261542010-08-14 21:02:52 +0000920
921void CStringChecker::PreVisitDeclStmt(CheckerContext &C, const DeclStmt *DS) {
922 // Record string length for char a[] = "abc";
923 const GRState *state = C.getState();
924
925 for (DeclStmt::const_decl_iterator I = DS->decl_begin(), E = DS->decl_end();
926 I != E; ++I) {
927 const VarDecl *D = dyn_cast<VarDecl>(*I);
928 if (!D)
929 continue;
930
931 // FIXME: Handle array fields of structs.
932 if (!D->getType()->isArrayType())
933 continue;
934
935 const Expr *Init = D->getInit();
936 if (!Init)
937 continue;
938 if (!isa<StringLiteral>(Init))
939 continue;
940
941 Loc VarLoc = state->getLValue(D, C.getPredecessor()->getLocationContext());
942 const MemRegion *MR = VarLoc.getAsRegion();
943 if (!MR)
944 continue;
945
946 SVal StrVal = state->getSVal(Init);
947 assert(StrVal.isValid() && "Initializer string is unknown or undefined");
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000948 DefinedOrUnknownSVal strLength
949 = cast<DefinedOrUnknownSVal>(getCStringLength(C, state, Init, StrVal));
Jordy Rosea5261542010-08-14 21:02:52 +0000950
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000951 state = state->set<CStringLength>(MR, strLength);
Jordy Rosea5261542010-08-14 21:02:52 +0000952 }
953
954 C.addTransition(state);
955}
956
957bool CStringChecker::WantsRegionChangeUpdate(const GRState *state) {
958 CStringLength::EntryMap Entries = state->get<CStringLength>();
959 return !Entries.isEmpty();
960}
961
962const GRState *CStringChecker::EvalRegionChanges(const GRState *state,
963 const MemRegion * const *Begin,
964 const MemRegion * const *End,
965 bool *) {
966 CStringLength::EntryMap Entries = state->get<CStringLength>();
967 if (Entries.isEmpty())
968 return state;
969
970 llvm::SmallPtrSet<const MemRegion *, 8> Invalidated;
971 llvm::SmallPtrSet<const MemRegion *, 32> SuperRegions;
972
973 // First build sets for the changed regions and their super-regions.
974 for ( ; Begin != End; ++Begin) {
975 const MemRegion *MR = *Begin;
976 Invalidated.insert(MR);
977
978 SuperRegions.insert(MR);
979 while (const SubRegion *SR = dyn_cast<SubRegion>(MR)) {
980 MR = SR->getSuperRegion();
981 SuperRegions.insert(MR);
982 }
983 }
984
985 CStringLength::EntryMap::Factory &F = state->get_context<CStringLength>();
986
987 // Then loop over the entries in the current state.
988 for (CStringLength::EntryMap::iterator I = Entries.begin(),
989 E = Entries.end(); I != E; ++I) {
990 const MemRegion *MR = I.getKey();
991
992 // Is this entry for a super-region of a changed region?
993 if (SuperRegions.count(MR)) {
Ted Kremenek3baf6722010-11-24 00:54:37 +0000994 Entries = F.remove(Entries, MR);
Jordy Rosea5261542010-08-14 21:02:52 +0000995 continue;
996 }
997
998 // Is this entry for a sub-region of a changed region?
999 const MemRegion *Super = MR;
1000 while (const SubRegion *SR = dyn_cast<SubRegion>(Super)) {
1001 Super = SR->getSuperRegion();
1002 if (Invalidated.count(Super)) {
Ted Kremenek3baf6722010-11-24 00:54:37 +00001003 Entries = F.remove(Entries, MR);
Jordy Rosea5261542010-08-14 21:02:52 +00001004 break;
1005 }
1006 }
1007 }
1008
1009 return state->set<CStringLength>(Entries);
1010}
1011
1012void CStringChecker::MarkLiveSymbols(const GRState *state, SymbolReaper &SR) {
1013 // Mark all symbols in our string length map as valid.
1014 CStringLength::EntryMap Entries = state->get<CStringLength>();
1015
1016 for (CStringLength::EntryMap::iterator I = Entries.begin(), E = Entries.end();
1017 I != E; ++I) {
1018 SVal Len = I.getData();
1019 if (SymbolRef Sym = Len.getAsSymbol())
1020 SR.markInUse(Sym);
1021 }
1022}
1023
Ted Kremenek9c149532010-12-01 21:57:22 +00001024void CStringChecker::evalDeadSymbols(CheckerContext &C, SymbolReaper &SR) {
Jordy Rosea5261542010-08-14 21:02:52 +00001025 if (!SR.hasDeadSymbols())
1026 return;
1027
1028 const GRState *state = C.getState();
1029 CStringLength::EntryMap Entries = state->get<CStringLength>();
1030 if (Entries.isEmpty())
1031 return;
1032
1033 CStringLength::EntryMap::Factory &F = state->get_context<CStringLength>();
1034 for (CStringLength::EntryMap::iterator I = Entries.begin(), E = Entries.end();
1035 I != E; ++I) {
1036 SVal Len = I.getData();
1037 if (SymbolRef Sym = Len.getAsSymbol()) {
1038 if (SR.isDead(Sym))
Ted Kremenek3baf6722010-11-24 00:54:37 +00001039 Entries = F.remove(Entries, I.getKey());
Jordy Rosea5261542010-08-14 21:02:52 +00001040 }
1041 }
1042
1043 state = state->set<CStringLength>(Entries);
Ted Kremenekd048c6e2010-12-20 21:19:09 +00001044 C.generateNode(state);
Jordy Rosea5261542010-08-14 21:02:52 +00001045}