blob: 71c4ee68ef25a0d99e964c6b29bf45a132e58f22 [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
Argyrios Kyrtzidisa0decc92011-02-15 21:25:03 +000015#include "ClangSACheckers.h"
Argyrios Kyrtzidisec8605f2011-03-01 01:16:21 +000016#include "clang/StaticAnalyzer/Core/Checker.h"
Argyrios Kyrtzidis695fb502011-02-17 21:39:17 +000017#include "clang/StaticAnalyzer/Core/CheckerManager.h"
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +000018#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
Ted Kremenek9b663712011-02-10 01:03:03 +000019#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
Ted Kremenek9b663712011-02-10 01:03:03 +000020#include "clang/StaticAnalyzer/Core/PathSensitive/GRStateTrait.h"
Jordy Roseccbf7ee2010-07-06 23:11:01 +000021#include "llvm/ADT/StringSwitch.h"
22
23using namespace clang;
Ted Kremenek9ef65372010-12-23 07:20:52 +000024using namespace ento;
Jordy Roseccbf7ee2010-07-06 23:11:01 +000025
26namespace {
Argyrios Kyrtzidisec8605f2011-03-01 01:16:21 +000027class CStringChecker : public Checker< eval::Call,
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +000028 check::PreStmt<DeclStmt>,
29 check::LiveSymbols,
30 check::DeadSymbols,
31 check::RegionChanges
32 > {
Jordy Rose9e49d9f2011-06-20 02:06:40 +000033 mutable llvm::OwningPtr<BugType> BT_Null, BT_Bounds,
Jordy Rosed5af0e12011-06-15 05:52:56 +000034 BT_Overlap, BT_NotCString,
35 BT_AdditionOverflow;
Jordy Rose9e49d9f2011-06-20 02:06:40 +000036 mutable const char *CurrentFunctionDescription;
37
Jordy Roseccbf7ee2010-07-06 23:11:01 +000038public:
Jordy Roseccbf7ee2010-07-06 23:11:01 +000039 static void *getTag() { static int tag; return &tag; }
40
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +000041 bool evalCall(const CallExpr *CE, CheckerContext &C) const;
42 void checkPreStmt(const DeclStmt *DS, CheckerContext &C) const;
43 void checkLiveSymbols(const GRState *state, SymbolReaper &SR) const;
44 void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
45 bool wantsRegionChangeUpdate(const GRState *state) const;
Jordy Rosea5261542010-08-14 21:02:52 +000046
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +000047 const GRState *checkRegionChanges(const GRState *state,
Ted Kremenek35bdbf42011-05-02 19:42:42 +000048 const StoreManager::InvalidatedSymbols *,
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +000049 const MemRegion * const *Begin,
50 const MemRegion * const *End) const;
Jordy Roseccbf7ee2010-07-06 23:11:01 +000051
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +000052 typedef void (CStringChecker::*FnCheck)(CheckerContext &,
53 const CallExpr *) const;
Jordy Roseccbf7ee2010-07-06 23:11:01 +000054
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +000055 void evalMemcpy(CheckerContext &C, const CallExpr *CE) const;
Lenny Maioranib8b875b2011-03-31 21:36:53 +000056 void evalMempcpy(CheckerContext &C, const CallExpr *CE) const;
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +000057 void evalMemmove(CheckerContext &C, const CallExpr *CE) const;
58 void evalBcopy(CheckerContext &C, const CallExpr *CE) const;
Lenny Maioranib8b875b2011-03-31 21:36:53 +000059 void evalCopyCommon(CheckerContext &C, const CallExpr *CE,
60 const GRState *state,
Jordy Rosed325ffb2010-07-08 23:57:29 +000061 const Expr *Size, const Expr *Source, const Expr *Dest,
Lenny Maioranib8b875b2011-03-31 21:36:53 +000062 bool Restricted = false,
63 bool IsMempcpy = false) const;
Jordy Rosed325ffb2010-07-08 23:57:29 +000064
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +000065 void evalMemcmp(CheckerContext &C, const CallExpr *CE) const;
Jordy Roseccbf7ee2010-07-06 23:11:01 +000066
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +000067 void evalstrLength(CheckerContext &C, const CallExpr *CE) const;
68 void evalstrnLength(CheckerContext &C, const CallExpr *CE) const;
Ted Kremenekbe4242c2011-02-22 04:55:05 +000069 void evalstrLengthCommon(CheckerContext &C, const CallExpr *CE,
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +000070 bool IsStrnlen = false) const;
Jordy Rose19c5dd12010-07-27 01:37:31 +000071
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +000072 void evalStrcpy(CheckerContext &C, const CallExpr *CE) const;
73 void evalStrncpy(CheckerContext &C, const CallExpr *CE) const;
74 void evalStpcpy(CheckerContext &C, const CallExpr *CE) const;
Ted Kremenek0ef473f2011-02-22 04:58:34 +000075 void evalStrcpyCommon(CheckerContext &C, const CallExpr *CE, bool returnEnd,
Lenny Maiorani067bbd02011-04-09 15:12:58 +000076 bool isBounded, bool isAppending) const;
77
78 void evalStrcat(CheckerContext &C, const CallExpr *CE) const;
79 void evalStrncat(CheckerContext &C, const CallExpr *CE) const;
Jordy Rosee64f3112010-08-16 07:51:42 +000080
Lenny Maiorani318dd922011-04-12 17:08:43 +000081 void evalStrcmp(CheckerContext &C, const CallExpr *CE) const;
Lenny Maiorani357f6ee2011-04-25 22:21:00 +000082 void evalStrncmp(CheckerContext &C, const CallExpr *CE) const;
Lenny Maioranibd1d16a2011-04-28 15:09:11 +000083 void evalStrcasecmp(CheckerContext &C, const CallExpr *CE) const;
Lenny Maiorani454fd2d2011-05-02 19:05:49 +000084 void evalStrncasecmp(CheckerContext &C, const CallExpr *CE) const;
Lenny Maiorani357f6ee2011-04-25 22:21:00 +000085 void evalStrcmpCommon(CheckerContext &C, const CallExpr *CE,
Lenny Maioranibd1d16a2011-04-28 15:09:11 +000086 bool isBounded = false, bool ignoreCase = false) const;
Lenny Maiorani318dd922011-04-12 17:08:43 +000087
Jordy Roseccbf7ee2010-07-06 23:11:01 +000088 // Utility methods
Jordy Rosed325ffb2010-07-08 23:57:29 +000089 std::pair<const GRState*, const GRState*>
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +000090 static assumeZero(CheckerContext &C,
91 const GRState *state, SVal V, QualType Ty);
Jordy Rosed325ffb2010-07-08 23:57:29 +000092
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +000093 static const GRState *setCStringLength(const GRState *state,
94 const MemRegion *MR, SVal strLength);
95 static SVal getCStringLengthForRegion(CheckerContext &C,
96 const GRState *&state,
Jordy Rosed5af0e12011-06-15 05:52:56 +000097 const Expr *Ex, const MemRegion *MR,
98 bool hypothetical);
Ted Kremenekc8413fd2010-12-02 07:49:45 +000099 SVal getCStringLength(CheckerContext &C, const GRState *&state,
Jordy Rosed5af0e12011-06-15 05:52:56 +0000100 const Expr *Ex, SVal Buf,
101 bool hypothetical = false) const;
Jordy Rose19c5dd12010-07-27 01:37:31 +0000102
Lenny Maiorani318dd922011-04-12 17:08:43 +0000103 const StringLiteral *getCStringLiteral(CheckerContext &C,
104 const GRState *&state,
105 const Expr *expr,
106 SVal val) const;
107
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +0000108 static const GRState *InvalidateBuffer(CheckerContext &C,
109 const GRState *state,
110 const Expr *Ex, SVal V);
Jordy Rosee64f3112010-08-16 07:51:42 +0000111
Chris Lattner5f9e2722011-07-23 10:55:15 +0000112 static bool SummarizeRegion(raw_ostream& os, ASTContext& Ctx,
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +0000113 const MemRegion *MR);
Jordy Rose19c5dd12010-07-27 01:37:31 +0000114
115 // Re-usable checks
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000116 const GRState *checkNonNull(CheckerContext &C, const GRState *state,
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +0000117 const Expr *S, SVal l) const;
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000118 const GRState *CheckLocation(CheckerContext &C, const GRState *state,
Jordy Rosee64f3112010-08-16 07:51:42 +0000119 const Expr *S, SVal l,
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000120 const char *message = NULL) const;
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000121 const GRState *CheckBufferAccess(CheckerContext &C, const GRState *state,
122 const Expr *Size,
123 const Expr *FirstBuf,
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000124 const Expr *SecondBuf,
125 const char *firstMessage = NULL,
Jordy Rose5e5f1502011-06-20 03:49:16 +0000126 const char *secondMessage = NULL,
127 bool WarnAboutSize = false) const;
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000128 const GRState *CheckBufferAccess(CheckerContext &C, const GRState *state,
129 const Expr *Size, const Expr *Buf,
Jordy Rose5e5f1502011-06-20 03:49:16 +0000130 const char *message = NULL,
131 bool WarnAboutSize = false) const {
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000132 // This is a convenience override.
Jordy Rose5e5f1502011-06-20 03:49:16 +0000133 return CheckBufferAccess(C, state, Size, Buf, NULL, message, NULL,
134 WarnAboutSize);
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000135 }
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000136 const GRState *CheckOverlap(CheckerContext &C, const GRState *state,
Jordy Rosed325ffb2010-07-08 23:57:29 +0000137 const Expr *Size, const Expr *First,
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +0000138 const Expr *Second) const;
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000139 void emitOverlapBug(CheckerContext &C, const GRState *state,
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +0000140 const Stmt *First, const Stmt *Second) const;
Jordy Rosed5af0e12011-06-15 05:52:56 +0000141 const GRState *checkAdditionOverflow(CheckerContext &C, const GRState *state,
142 NonLoc left, NonLoc right) const;
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000143};
Jordy Rosea5261542010-08-14 21:02:52 +0000144
145class CStringLength {
146public:
147 typedef llvm::ImmutableMap<const MemRegion *, SVal> EntryMap;
148};
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000149} //end anonymous namespace
150
Jordy Rosea5261542010-08-14 21:02:52 +0000151namespace clang {
Ted Kremenek9ef65372010-12-23 07:20:52 +0000152namespace ento {
Jordy Rosea5261542010-08-14 21:02:52 +0000153 template <>
154 struct GRStateTrait<CStringLength>
155 : public GRStatePartialTrait<CStringLength::EntryMap> {
156 static void *GDMIndex() { return CStringChecker::getTag(); }
157 };
158}
Argyrios Kyrtzidis5a4f98f2010-12-22 18:53:20 +0000159}
Jordy Rosea5261542010-08-14 21:02:52 +0000160
Jordy Rosed325ffb2010-07-08 23:57:29 +0000161//===----------------------------------------------------------------------===//
162// Individual checks and utility methods.
163//===----------------------------------------------------------------------===//
164
165std::pair<const GRState*, const GRState*>
Ted Kremenek28f47b92010-12-01 22:16:56 +0000166CStringChecker::assumeZero(CheckerContext &C, const GRState *state, SVal V,
Jordy Rosed325ffb2010-07-08 23:57:29 +0000167 QualType Ty) {
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000168 DefinedSVal *val = dyn_cast<DefinedSVal>(&V);
169 if (!val)
Jordy Rosed325ffb2010-07-08 23:57:29 +0000170 return std::pair<const GRState*, const GRState *>(state, state);
Jordy Rosea6b808c2010-07-07 07:48:06 +0000171
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000172 SValBuilder &svalBuilder = C.getSValBuilder();
173 DefinedOrUnknownSVal zero = svalBuilder.makeZeroVal(Ty);
174 return state->assume(svalBuilder.evalEQ(state, *val, zero));
Jordy Rosed325ffb2010-07-08 23:57:29 +0000175}
Jordy Rosea6b808c2010-07-07 07:48:06 +0000176
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000177const GRState *CStringChecker::checkNonNull(CheckerContext &C,
Jordy Rosed325ffb2010-07-08 23:57:29 +0000178 const GRState *state,
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +0000179 const Expr *S, SVal l) const {
Jordy Rosed325ffb2010-07-08 23:57:29 +0000180 // If a previous check has failed, propagate the failure.
181 if (!state)
182 return NULL;
183
184 const GRState *stateNull, *stateNonNull;
Ted Kremenek28f47b92010-12-01 22:16:56 +0000185 llvm::tie(stateNull, stateNonNull) = assumeZero(C, state, l, S->getType());
Jordy Rosed325ffb2010-07-08 23:57:29 +0000186
187 if (stateNull && !stateNonNull) {
Ted Kremenekd048c6e2010-12-20 21:19:09 +0000188 ExplodedNode *N = C.generateSink(stateNull);
Jordy Rosea6b808c2010-07-07 07:48:06 +0000189 if (!N)
190 return NULL;
191
Jordy Rosed325ffb2010-07-08 23:57:29 +0000192 if (!BT_Null)
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +0000193 BT_Null.reset(new BuiltinBug("API",
194 "Null pointer argument in call to byte string function"));
Jordy Rosea6b808c2010-07-07 07:48:06 +0000195
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000196 llvm::SmallString<80> buf;
197 llvm::raw_svector_ostream os(buf);
198 assert(CurrentFunctionDescription);
199 os << "Null pointer argument in call to " << CurrentFunctionDescription;
200
Jordy Rosea6b808c2010-07-07 07:48:06 +0000201 // Generate a report for this bug.
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +0000202 BuiltinBug *BT = static_cast<BuiltinBug*>(BT_Null.get());
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000203 EnhancedBugReport *report = new EnhancedBugReport(*BT, os.str(), N);
Jordy Rosea6b808c2010-07-07 07:48:06 +0000204
205 report->addRange(S->getSourceRange());
206 report->addVisitorCreator(bugreporter::registerTrackNullOrUndefValue, S);
207 C.EmitReport(report);
208 return NULL;
209 }
210
211 // From here on, assume that the value is non-null.
Jordy Rosed325ffb2010-07-08 23:57:29 +0000212 assert(stateNonNull);
213 return stateNonNull;
Jordy Rosea6b808c2010-07-07 07:48:06 +0000214}
215
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000216// FIXME: This was originally copied from ArrayBoundChecker.cpp. Refactor?
217const GRState *CStringChecker::CheckLocation(CheckerContext &C,
218 const GRState *state,
Jordy Rosee64f3112010-08-16 07:51:42 +0000219 const Expr *S, SVal l,
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000220 const char *warningMsg) const {
Jordy Rosed325ffb2010-07-08 23:57:29 +0000221 // If a previous check has failed, propagate the failure.
222 if (!state)
223 return NULL;
224
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000225 // Check for out of bound array element access.
226 const MemRegion *R = l.getAsRegion();
227 if (!R)
228 return state;
229
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000230 const ElementRegion *ER = dyn_cast<ElementRegion>(R);
231 if (!ER)
232 return state;
233
Zhongxing Xu018220c2010-08-11 06:10:55 +0000234 assert(ER->getValueType() == C.getASTContext().CharTy &&
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000235 "CheckLocation should only be called with char* ElementRegions");
236
237 // Get the size of the array.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000238 const SubRegion *superReg = cast<SubRegion>(ER->getSuperRegion());
239 SValBuilder &svalBuilder = C.getSValBuilder();
Jordy Rose1e022412011-06-16 05:51:02 +0000240 SVal Extent =
241 svalBuilder.convertToArrayIndex(superReg->getExtent(svalBuilder));
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000242 DefinedOrUnknownSVal Size = cast<DefinedOrUnknownSVal>(Extent);
243
244 // Get the index of the accessed element.
Gabor Greif89b06582010-09-09 10:51:37 +0000245 DefinedOrUnknownSVal Idx = cast<DefinedOrUnknownSVal>(ER->getIndex());
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000246
Ted Kremenek28f47b92010-12-01 22:16:56 +0000247 const GRState *StInBound = state->assumeInBound(Idx, Size, true);
248 const GRState *StOutBound = state->assumeInBound(Idx, Size, false);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000249 if (StOutBound && !StInBound) {
Ted Kremenekd048c6e2010-12-20 21:19:09 +0000250 ExplodedNode *N = C.generateSink(StOutBound);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000251 if (!N)
252 return NULL;
253
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000254 if (!BT_Bounds) {
255 BT_Bounds.reset(new BuiltinBug("Out-of-bound array access",
256 "Byte string function accesses out-of-bound array element"));
257 }
258 BuiltinBug *BT = static_cast<BuiltinBug*>(BT_Bounds.get());
259
260 // Generate a report for this bug.
261 RangedBugReport *report;
262 if (warningMsg) {
263 report = new RangedBugReport(*BT, warningMsg, N);
Jordy Rosee64f3112010-08-16 07:51:42 +0000264 } else {
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000265 assert(CurrentFunctionDescription);
266 assert(CurrentFunctionDescription[0] != '\0');
267
268 llvm::SmallString<80> buf;
269 llvm::raw_svector_ostream os(buf);
270 os << (char)toupper(CurrentFunctionDescription[0])
271 << &CurrentFunctionDescription[1]
272 << " accesses out-of-bound array element";
273 report = new RangedBugReport(*BT, os.str(), N);
Jordy Rosee64f3112010-08-16 07:51:42 +0000274 }
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000275
276 // FIXME: It would be nice to eventually make this diagnostic more clear,
277 // e.g., by referencing the original declaration or by saying *why* this
278 // reference is outside the range.
279
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000280 report->addRange(S->getSourceRange());
281 C.EmitReport(report);
282 return NULL;
283 }
284
285 // Array bound check succeeded. From this point forward the array bound
286 // should always succeed.
287 return StInBound;
288}
289
290const GRState *CStringChecker::CheckBufferAccess(CheckerContext &C,
291 const GRState *state,
292 const Expr *Size,
293 const Expr *FirstBuf,
Jordy Rosee64f3112010-08-16 07:51:42 +0000294 const Expr *SecondBuf,
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000295 const char *firstMessage,
Jordy Rose5e5f1502011-06-20 03:49:16 +0000296 const char *secondMessage,
297 bool WarnAboutSize) const {
Jordy Rosed325ffb2010-07-08 23:57:29 +0000298 // If a previous check has failed, propagate the failure.
299 if (!state)
300 return NULL;
301
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000302 SValBuilder &svalBuilder = C.getSValBuilder();
Jordy Rose1e022412011-06-16 05:51:02 +0000303 ASTContext &Ctx = svalBuilder.getContext();
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000304
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000305 QualType sizeTy = Size->getType();
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000306 QualType PtrTy = Ctx.getPointerType(Ctx.CharTy);
307
Jordy Rosea6b808c2010-07-07 07:48:06 +0000308 // Check that the first buffer is non-null.
309 SVal BufVal = state->getSVal(FirstBuf);
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000310 state = checkNonNull(C, state, FirstBuf, BufVal);
Jordy Rosea6b808c2010-07-07 07:48:06 +0000311 if (!state)
312 return NULL;
313
Jordy Rosed325ffb2010-07-08 23:57:29 +0000314 // Get the access length and make sure it is known.
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000315 // FIXME: This assumes the caller has already checked that the access length
316 // is positive. And that it's unsigned.
Jordy Rosed325ffb2010-07-08 23:57:29 +0000317 SVal LengthVal = state->getSVal(Size);
318 NonLoc *Length = dyn_cast<NonLoc>(&LengthVal);
319 if (!Length)
320 return state;
321
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000322 // Compute the offset of the last element to be accessed: size-1.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000323 NonLoc One = cast<NonLoc>(svalBuilder.makeIntVal(1, sizeTy));
324 NonLoc LastOffset = cast<NonLoc>(svalBuilder.evalBinOpNN(state, BO_Sub,
325 *Length, One, sizeTy));
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000326
Chris Lattnerfc8f0e12011-04-15 05:22:18 +0000327 // Check that the first buffer is sufficiently long.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000328 SVal BufStart = svalBuilder.evalCast(BufVal, PtrTy, FirstBuf->getType());
Jordy Roseb6a40262010-08-05 23:11:30 +0000329 if (Loc *BufLoc = dyn_cast<Loc>(&BufStart)) {
Jordy Rose5e5f1502011-06-20 03:49:16 +0000330 const Expr *warningExpr = (WarnAboutSize ? Size : FirstBuf);
331
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000332 SVal BufEnd = svalBuilder.evalBinOpLN(state, BO_Add, *BufLoc,
333 LastOffset, PtrTy);
Jordy Rose5e5f1502011-06-20 03:49:16 +0000334 state = CheckLocation(C, state, warningExpr, BufEnd, firstMessage);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000335
Jordy Roseb6a40262010-08-05 23:11:30 +0000336 // If the buffer isn't large enough, abort.
337 if (!state)
338 return NULL;
339 }
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000340
341 // If there's a second buffer, check it as well.
342 if (SecondBuf) {
343 BufVal = state->getSVal(SecondBuf);
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000344 state = checkNonNull(C, state, SecondBuf, BufVal);
Jordy Rosea6b808c2010-07-07 07:48:06 +0000345 if (!state)
346 return NULL;
347
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000348 BufStart = svalBuilder.evalCast(BufVal, PtrTy, SecondBuf->getType());
Jordy Roseb6a40262010-08-05 23:11:30 +0000349 if (Loc *BufLoc = dyn_cast<Loc>(&BufStart)) {
Jordy Rose5e5f1502011-06-20 03:49:16 +0000350 const Expr *warningExpr = (WarnAboutSize ? Size : SecondBuf);
351
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000352 SVal BufEnd = svalBuilder.evalBinOpLN(state, BO_Add, *BufLoc,
353 LastOffset, PtrTy);
Jordy Rose5e5f1502011-06-20 03:49:16 +0000354 state = CheckLocation(C, state, warningExpr, BufEnd, secondMessage);
Jordy Roseb6a40262010-08-05 23:11:30 +0000355 }
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000356 }
357
358 // Large enough or not, return this state!
359 return state;
360}
361
362const GRState *CStringChecker::CheckOverlap(CheckerContext &C,
363 const GRState *state,
Jordy Rosed325ffb2010-07-08 23:57:29 +0000364 const Expr *Size,
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000365 const Expr *First,
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +0000366 const Expr *Second) const {
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000367 // Do a simple check for overlap: if the two arguments are from the same
368 // buffer, see if the end of the first is greater than the start of the second
369 // or vice versa.
370
Jordy Rosed325ffb2010-07-08 23:57:29 +0000371 // If a previous check has failed, propagate the failure.
372 if (!state)
373 return NULL;
374
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000375 const GRState *stateTrue, *stateFalse;
376
377 // Get the buffer values and make sure they're known locations.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000378 SVal firstVal = state->getSVal(First);
379 SVal secondVal = state->getSVal(Second);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000380
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000381 Loc *firstLoc = dyn_cast<Loc>(&firstVal);
382 if (!firstLoc)
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000383 return state;
384
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000385 Loc *secondLoc = dyn_cast<Loc>(&secondVal);
386 if (!secondLoc)
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000387 return state;
388
389 // Are the two values the same?
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000390 SValBuilder &svalBuilder = C.getSValBuilder();
391 llvm::tie(stateTrue, stateFalse) =
392 state->assume(svalBuilder.evalEQ(state, *firstLoc, *secondLoc));
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000393
394 if (stateTrue && !stateFalse) {
395 // If the values are known to be equal, that's automatically an overlap.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000396 emitOverlapBug(C, stateTrue, First, Second);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000397 return NULL;
398 }
399
Ted Kremenek28f47b92010-12-01 22:16:56 +0000400 // assume the two expressions are not equal.
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000401 assert(stateFalse);
402 state = stateFalse;
403
404 // Which value comes first?
Jordy Roseee2fde12011-06-16 05:56:50 +0000405 QualType cmpTy = svalBuilder.getConditionType();
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000406 SVal reverse = svalBuilder.evalBinOpLL(state, BO_GT,
407 *firstLoc, *secondLoc, cmpTy);
408 DefinedOrUnknownSVal *reverseTest = dyn_cast<DefinedOrUnknownSVal>(&reverse);
409 if (!reverseTest)
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000410 return state;
411
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000412 llvm::tie(stateTrue, stateFalse) = state->assume(*reverseTest);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000413 if (stateTrue) {
414 if (stateFalse) {
415 // If we don't know which one comes first, we can't perform this test.
416 return state;
417 } else {
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000418 // Switch the values so that firstVal is before secondVal.
419 Loc *tmpLoc = firstLoc;
420 firstLoc = secondLoc;
421 secondLoc = tmpLoc;
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000422
423 // Switch the Exprs as well, so that they still correspond.
424 const Expr *tmpExpr = First;
425 First = Second;
426 Second = tmpExpr;
427 }
428 }
429
430 // Get the length, and make sure it too is known.
431 SVal LengthVal = state->getSVal(Size);
432 NonLoc *Length = dyn_cast<NonLoc>(&LengthVal);
433 if (!Length)
434 return state;
435
436 // Convert the first buffer's start address to char*.
437 // Bail out if the cast fails.
Jordy Roseee2fde12011-06-16 05:56:50 +0000438 ASTContext &Ctx = svalBuilder.getContext();
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000439 QualType CharPtrTy = Ctx.getPointerType(Ctx.CharTy);
Jordy Rose1e022412011-06-16 05:51:02 +0000440 SVal FirstStart = svalBuilder.evalCast(*firstLoc, CharPtrTy,
441 First->getType());
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000442 Loc *FirstStartLoc = dyn_cast<Loc>(&FirstStart);
443 if (!FirstStartLoc)
444 return state;
445
446 // Compute the end of the first buffer. Bail out if THAT fails.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000447 SVal FirstEnd = svalBuilder.evalBinOpLN(state, BO_Add,
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000448 *FirstStartLoc, *Length, CharPtrTy);
449 Loc *FirstEndLoc = dyn_cast<Loc>(&FirstEnd);
450 if (!FirstEndLoc)
451 return state;
452
453 // Is the end of the first buffer past the start of the second buffer?
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000454 SVal Overlap = svalBuilder.evalBinOpLL(state, BO_GT,
455 *FirstEndLoc, *secondLoc, cmpTy);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000456 DefinedOrUnknownSVal *OverlapTest = dyn_cast<DefinedOrUnknownSVal>(&Overlap);
457 if (!OverlapTest)
458 return state;
459
Ted Kremenek28f47b92010-12-01 22:16:56 +0000460 llvm::tie(stateTrue, stateFalse) = state->assume(*OverlapTest);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000461
462 if (stateTrue && !stateFalse) {
463 // Overlap!
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000464 emitOverlapBug(C, stateTrue, First, Second);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000465 return NULL;
466 }
467
Ted Kremenek28f47b92010-12-01 22:16:56 +0000468 // assume the two expressions don't overlap.
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000469 assert(stateFalse);
470 return stateFalse;
471}
472
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000473void CStringChecker::emitOverlapBug(CheckerContext &C, const GRState *state,
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +0000474 const Stmt *First, const Stmt *Second) const {
Ted Kremenekd048c6e2010-12-20 21:19:09 +0000475 ExplodedNode *N = C.generateSink(state);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000476 if (!N)
477 return;
478
479 if (!BT_Overlap)
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +0000480 BT_Overlap.reset(new BugType("Unix API", "Improper arguments"));
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000481
482 // Generate a report for this bug.
483 RangedBugReport *report =
484 new RangedBugReport(*BT_Overlap,
485 "Arguments must not be overlapping buffers", N);
486 report->addRange(First->getSourceRange());
487 report->addRange(Second->getSourceRange());
488
489 C.EmitReport(report);
490}
491
Jordy Rosed5af0e12011-06-15 05:52:56 +0000492const GRState *CStringChecker::checkAdditionOverflow(CheckerContext &C,
493 const GRState *state,
494 NonLoc left,
495 NonLoc right) const {
496 // If a previous check has failed, propagate the failure.
497 if (!state)
498 return NULL;
499
500 SValBuilder &svalBuilder = C.getSValBuilder();
501 BasicValueFactory &BVF = svalBuilder.getBasicValueFactory();
502
503 QualType sizeTy = svalBuilder.getContext().getSizeType();
504 const llvm::APSInt &maxValInt = BVF.getMaxValue(sizeTy);
505 NonLoc maxVal = svalBuilder.makeIntVal(maxValInt);
506
507 SVal maxMinusRight = svalBuilder.evalBinOpNN(state, BO_Sub, maxVal, right,
508 sizeTy);
509
510 if (maxMinusRight.isUnknownOrUndef()) {
511 // Try switching the operands. (The order of these two assignments is
512 // important!)
513 maxMinusRight = svalBuilder.evalBinOpNN(state, BO_Sub, maxVal, left,
514 sizeTy);
515 left = right;
516 }
517
518 if (NonLoc *maxMinusRightNL = dyn_cast<NonLoc>(&maxMinusRight)) {
519 QualType cmpTy = svalBuilder.getConditionType();
520 // If left > max - right, we have an overflow.
521 SVal willOverflow = svalBuilder.evalBinOpNN(state, BO_GT, left,
522 *maxMinusRightNL, cmpTy);
523
524 const GRState *stateOverflow, *stateOkay;
525 llvm::tie(stateOverflow, stateOkay) =
526 state->assume(cast<DefinedOrUnknownSVal>(willOverflow));
527
528 if (stateOverflow && !stateOkay) {
529 // We have an overflow. Emit a bug report.
530 ExplodedNode *N = C.generateSink(stateOverflow);
531 if (!N)
532 return NULL;
533
534 if (!BT_AdditionOverflow)
535 BT_AdditionOverflow.reset(new BuiltinBug("API",
536 "Sum of expressions causes overflow"));
537
Jordy Rosed5af0e12011-06-15 05:52:56 +0000538 // This isn't a great error message, but this should never occur in real
539 // code anyway -- you'd have to create a buffer longer than a size_t can
540 // represent, which is sort of a contradiction.
Jordy Rose8cc24912011-06-20 03:51:53 +0000541 const char *warning =
542 "This expression will create a string whose length is too big to "
543 "be represented as a size_t";
Jordy Rosed5af0e12011-06-15 05:52:56 +0000544
545 // Generate a report for this bug.
Jordy Rose8cc24912011-06-20 03:51:53 +0000546 BugReport *report = new BugReport(*BT_AdditionOverflow, warning, N);
Jordy Rosed5af0e12011-06-15 05:52:56 +0000547 C.EmitReport(report);
548
549 return NULL;
550 }
551
552 // From now on, assume an overflow didn't occur.
553 assert(stateOkay);
554 state = stateOkay;
555 }
556
557 return state;
558}
559
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000560const GRState *CStringChecker::setCStringLength(const GRState *state,
Jordy Rosee64f3112010-08-16 07:51:42 +0000561 const MemRegion *MR,
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000562 SVal strLength) {
563 assert(!strLength.isUndef() && "Attempt to set an undefined string length");
Jordy Rosee64f3112010-08-16 07:51:42 +0000564
565 MR = MR->StripCasts();
566
567 switch (MR->getKind()) {
568 case MemRegion::StringRegionKind:
569 // FIXME: This can happen if we strcpy() into a string region. This is
570 // undefined [C99 6.4.5p6], but we should still warn about it.
571 return state;
572
573 case MemRegion::SymbolicRegionKind:
574 case MemRegion::AllocaRegionKind:
575 case MemRegion::VarRegionKind:
576 case MemRegion::FieldRegionKind:
577 case MemRegion::ObjCIvarRegionKind:
Jordy Rose210c05b2011-06-15 05:14:03 +0000578 // These are the types we can currently track string lengths for.
579 break;
Jordy Rosee64f3112010-08-16 07:51:42 +0000580
581 case MemRegion::ElementRegionKind:
582 // FIXME: Handle element regions by upper-bounding the parent region's
583 // string length.
584 return state;
585
586 default:
587 // Other regions (mostly non-data) can't have a reliable C string length.
588 // For now, just ignore the change.
589 // FIXME: These are rare but not impossible. We should output some kind of
590 // warning for things like strcpy((char[]){'a', 0}, "b");
591 return state;
592 }
Jordy Rose210c05b2011-06-15 05:14:03 +0000593
594 if (strLength.isUnknown())
595 return state->remove<CStringLength>(MR);
596
597 return state->set<CStringLength>(MR, strLength);
Jordy Rosee64f3112010-08-16 07:51:42 +0000598}
599
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000600SVal CStringChecker::getCStringLengthForRegion(CheckerContext &C,
Jordy Rosea5261542010-08-14 21:02:52 +0000601 const GRState *&state,
602 const Expr *Ex,
Jordy Rosed5af0e12011-06-15 05:52:56 +0000603 const MemRegion *MR,
604 bool hypothetical) {
605 if (!hypothetical) {
606 // If there's a recorded length, go ahead and return it.
607 const SVal *Recorded = state->get<CStringLength>(MR);
608 if (Recorded)
609 return *Recorded;
610 }
Jordy Rosea5261542010-08-14 21:02:52 +0000611
612 // Otherwise, get a new symbol and update the state.
613 unsigned Count = C.getNodeBuilder().getCurrentBlockCount();
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000614 SValBuilder &svalBuilder = C.getSValBuilder();
615 QualType sizeTy = svalBuilder.getContext().getSizeType();
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +0000616 SVal strLength = svalBuilder.getMetadataSymbolVal(CStringChecker::getTag(),
617 MR, Ex, sizeTy, Count);
Jordy Rosed5af0e12011-06-15 05:52:56 +0000618
619 if (!hypothetical)
620 state = state->set<CStringLength>(MR, strLength);
621
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000622 return strLength;
Jordy Rosea5261542010-08-14 21:02:52 +0000623}
624
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000625SVal CStringChecker::getCStringLength(CheckerContext &C, const GRState *&state,
Jordy Rosed5af0e12011-06-15 05:52:56 +0000626 const Expr *Ex, SVal Buf,
627 bool hypothetical) const {
Jordy Rose19c5dd12010-07-27 01:37:31 +0000628 const MemRegion *MR = Buf.getAsRegion();
629 if (!MR) {
630 // If we can't get a region, see if it's something we /know/ isn't a
631 // C string. In the context of locations, the only time we can issue such
632 // a warning is for labels.
633 if (loc::GotoLabel *Label = dyn_cast<loc::GotoLabel>(&Buf)) {
Ted Kremenekd048c6e2010-12-20 21:19:09 +0000634 if (ExplodedNode *N = C.generateNode(state)) {
Jordy Rose19c5dd12010-07-27 01:37:31 +0000635 if (!BT_NotCString)
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +0000636 BT_NotCString.reset(new BuiltinBug("API",
637 "Argument is not a null-terminated string."));
Jordy Rose19c5dd12010-07-27 01:37:31 +0000638
639 llvm::SmallString<120> buf;
640 llvm::raw_svector_ostream os(buf);
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000641 assert(CurrentFunctionDescription);
642 os << "Argument to " << CurrentFunctionDescription
643 << " is the address of the label '" << Label->getLabel()->getName()
Jordy Rose19c5dd12010-07-27 01:37:31 +0000644 << "', which is not a null-terminated string";
645
646 // Generate a report for this bug.
647 EnhancedBugReport *report = new EnhancedBugReport(*BT_NotCString,
648 os.str(), N);
649
650 report->addRange(Ex->getSourceRange());
651 C.EmitReport(report);
652 }
653
654 return UndefinedVal();
655 }
656
Jordy Rosea5261542010-08-14 21:02:52 +0000657 // If it's not a region and not a label, give up.
658 return UnknownVal();
Jordy Rose19c5dd12010-07-27 01:37:31 +0000659 }
660
Jordy Rosea5261542010-08-14 21:02:52 +0000661 // If we have a region, strip casts from it and see if we can figure out
662 // its length. For anything we can't figure out, just return UnknownVal.
663 MR = MR->StripCasts();
664
665 switch (MR->getKind()) {
666 case MemRegion::StringRegionKind: {
667 // Modifying the contents of string regions is undefined [C99 6.4.5p6],
668 // so we can assume that the byte length is the correct C string length.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000669 SValBuilder &svalBuilder = C.getSValBuilder();
670 QualType sizeTy = svalBuilder.getContext().getSizeType();
671 const StringLiteral *strLit = cast<StringRegion>(MR)->getStringLiteral();
672 return svalBuilder.makeIntVal(strLit->getByteLength(), sizeTy);
Jordy Rosea5261542010-08-14 21:02:52 +0000673 }
674 case MemRegion::SymbolicRegionKind:
675 case MemRegion::AllocaRegionKind:
676 case MemRegion::VarRegionKind:
677 case MemRegion::FieldRegionKind:
678 case MemRegion::ObjCIvarRegionKind:
Jordy Rosed5af0e12011-06-15 05:52:56 +0000679 return getCStringLengthForRegion(C, state, Ex, MR, hypothetical);
Jordy Rosea5261542010-08-14 21:02:52 +0000680 case MemRegion::CompoundLiteralRegionKind:
681 // FIXME: Can we track this? Is it necessary?
682 return UnknownVal();
683 case MemRegion::ElementRegionKind:
684 // FIXME: How can we handle this? It's not good enough to subtract the
685 // offset from the base string length; consider "123\x00567" and &a[5].
686 return UnknownVal();
687 default:
688 // Other regions (mostly non-data) can't have a reliable C string length.
689 // In this case, an error is emitted and UndefinedVal is returned.
690 // The caller should always be prepared to handle this case.
Ted Kremenekd048c6e2010-12-20 21:19:09 +0000691 if (ExplodedNode *N = C.generateNode(state)) {
Jordy Rosea5261542010-08-14 21:02:52 +0000692 if (!BT_NotCString)
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +0000693 BT_NotCString.reset(new BuiltinBug("API",
694 "Argument is not a null-terminated string."));
Jordy Rosea5261542010-08-14 21:02:52 +0000695
696 llvm::SmallString<120> buf;
697 llvm::raw_svector_ostream os(buf);
698
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000699 assert(CurrentFunctionDescription);
700 os << "Argument to " << CurrentFunctionDescription << " is ";
Jordy Rosea5261542010-08-14 21:02:52 +0000701
702 if (SummarizeRegion(os, C.getASTContext(), MR))
703 os << ", which is not a null-terminated string";
704 else
705 os << "not a null-terminated string";
706
707 // Generate a report for this bug.
708 EnhancedBugReport *report = new EnhancedBugReport(*BT_NotCString,
709 os.str(), N);
710
711 report->addRange(Ex->getSourceRange());
712 C.EmitReport(report);
713 }
714
715 return UndefinedVal();
716 }
Jordy Rose19c5dd12010-07-27 01:37:31 +0000717}
718
Lenny Maiorani318dd922011-04-12 17:08:43 +0000719const StringLiteral *CStringChecker::getCStringLiteral(CheckerContext &C,
720 const GRState *&state, const Expr *expr, SVal val) const {
721
722 // Get the memory region pointed to by the val.
723 const MemRegion *bufRegion = val.getAsRegion();
724 if (!bufRegion)
725 return NULL;
726
727 // Strip casts off the memory region.
728 bufRegion = bufRegion->StripCasts();
729
730 // Cast the memory region to a string region.
731 const StringRegion *strRegion= dyn_cast<StringRegion>(bufRegion);
732 if (!strRegion)
733 return NULL;
734
735 // Return the actual string in the string region.
736 return strRegion->getStringLiteral();
737}
738
Jordy Rosee64f3112010-08-16 07:51:42 +0000739const GRState *CStringChecker::InvalidateBuffer(CheckerContext &C,
740 const GRState *state,
741 const Expr *E, SVal V) {
742 Loc *L = dyn_cast<Loc>(&V);
743 if (!L)
744 return state;
745
746 // FIXME: This is a simplified version of what's in CFRefCount.cpp -- it makes
747 // some assumptions about the value that CFRefCount can't. Even so, it should
748 // probably be refactored.
749 if (loc::MemRegionVal* MR = dyn_cast<loc::MemRegionVal>(L)) {
750 const MemRegion *R = MR->getRegion()->StripCasts();
751
752 // Are we dealing with an ElementRegion? If so, we should be invalidating
753 // the super-region.
754 if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
755 R = ER->getSuperRegion();
756 // FIXME: What about layers of ElementRegions?
757 }
758
759 // Invalidate this region.
760 unsigned Count = C.getNodeBuilder().getCurrentBlockCount();
Ted Kremenek25345282011-02-11 19:48:15 +0000761 return state->invalidateRegion(R, E, Count, NULL);
Jordy Rosee64f3112010-08-16 07:51:42 +0000762 }
763
764 // If we have a non-region value by chance, just remove the binding.
765 // FIXME: is this necessary or correct? This handles the non-Region
766 // cases. Is it ever valid to store to these?
767 return state->unbindLoc(*L);
768}
769
Chris Lattner5f9e2722011-07-23 10:55:15 +0000770bool CStringChecker::SummarizeRegion(raw_ostream& os, ASTContext& Ctx,
Jordy Rose19c5dd12010-07-27 01:37:31 +0000771 const MemRegion *MR) {
772 const TypedRegion *TR = dyn_cast<TypedRegion>(MR);
Ted Kremenek96979342011-08-12 20:02:48 +0000773 const TypedValueRegion *TVR = dyn_cast<TypedValueRegion>(MR);
Jordy Rose19c5dd12010-07-27 01:37:31 +0000774
775 switch (TR->getKind()) {
776 case MemRegion::FunctionTextRegionKind: {
777 const FunctionDecl *FD = cast<FunctionTextRegion>(TR)->getDecl();
778 if (FD)
779 os << "the address of the function '" << FD << "'";
780 else
781 os << "the address of a function";
782 return true;
783 }
784 case MemRegion::BlockTextRegionKind:
785 os << "block text";
786 return true;
787 case MemRegion::BlockDataRegionKind:
788 os << "a block";
789 return true;
790 case MemRegion::CXXThisRegionKind:
Zhongxing Xu02fe28c2010-11-26 08:52:48 +0000791 case MemRegion::CXXTempObjectRegionKind:
Ted Kremenek96979342011-08-12 20:02:48 +0000792 os << "a C++ temp object of type " << TVR->getValueType().getAsString();
Jordy Rose19c5dd12010-07-27 01:37:31 +0000793 return true;
794 case MemRegion::VarRegionKind:
Ted Kremenek96979342011-08-12 20:02:48 +0000795 os << "a variable of type" << TVR->getValueType().getAsString();
Jordy Rose19c5dd12010-07-27 01:37:31 +0000796 return true;
797 case MemRegion::FieldRegionKind:
Ted Kremenek96979342011-08-12 20:02:48 +0000798 os << "a field of type " << TVR->getValueType().getAsString();
Jordy Rose19c5dd12010-07-27 01:37:31 +0000799 return true;
800 case MemRegion::ObjCIvarRegionKind:
Ted Kremenek96979342011-08-12 20:02:48 +0000801 os << "an instance variable of type " << TVR->getValueType().getAsString();
Jordy Rose19c5dd12010-07-27 01:37:31 +0000802 return true;
803 default:
804 return false;
805 }
806}
807
Jordy Rosed325ffb2010-07-08 23:57:29 +0000808//===----------------------------------------------------------------------===//
Ted Kremenek9c149532010-12-01 21:57:22 +0000809// evaluation of individual function calls.
Jordy Rosed325ffb2010-07-08 23:57:29 +0000810//===----------------------------------------------------------------------===//
811
Lenny Maioranib8b875b2011-03-31 21:36:53 +0000812void CStringChecker::evalCopyCommon(CheckerContext &C,
813 const CallExpr *CE,
814 const GRState *state,
Jordy Rosed325ffb2010-07-08 23:57:29 +0000815 const Expr *Size, const Expr *Dest,
Lenny Maioranib8b875b2011-03-31 21:36:53 +0000816 const Expr *Source, bool Restricted,
817 bool IsMempcpy) const {
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000818 CurrentFunctionDescription = "memory copy function";
819
Jordy Rosed325ffb2010-07-08 23:57:29 +0000820 // See if the size argument is zero.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000821 SVal sizeVal = state->getSVal(Size);
822 QualType sizeTy = Size->getType();
Jordy Rosed325ffb2010-07-08 23:57:29 +0000823
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000824 const GRState *stateZeroSize, *stateNonZeroSize;
Jordy Rose1e022412011-06-16 05:51:02 +0000825 llvm::tie(stateZeroSize, stateNonZeroSize) =
826 assumeZero(C, state, sizeVal, sizeTy);
Jordy Rosed325ffb2010-07-08 23:57:29 +0000827
Lenny Maioranib8b875b2011-03-31 21:36:53 +0000828 // Get the value of the Dest.
829 SVal destVal = state->getSVal(Dest);
830
831 // If the size is zero, there won't be any actual memory access, so
832 // just bind the return value to the destination buffer and return.
833 if (stateZeroSize) {
Jordy Rose22d27172011-06-04 00:04:22 +0000834 stateZeroSize = stateZeroSize->BindExpr(CE, destVal);
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000835 C.addTransition(stateZeroSize);
Lenny Maioranib8b875b2011-03-31 21:36:53 +0000836 }
Jordy Rosed325ffb2010-07-08 23:57:29 +0000837
838 // If the size can be nonzero, we have to check the other arguments.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000839 if (stateNonZeroSize) {
Jordy Rose22d27172011-06-04 00:04:22 +0000840 state = stateNonZeroSize;
Lenny Maioranib8b875b2011-03-31 21:36:53 +0000841
842 // Ensure the destination is not null. If it is NULL there will be a
843 // NULL pointer dereference.
844 state = checkNonNull(C, state, Dest, destVal);
845 if (!state)
846 return;
847
848 // Get the value of the Src.
849 SVal srcVal = state->getSVal(Source);
850
851 // Ensure the source is not null. If it is NULL there will be a
852 // NULL pointer dereference.
853 state = checkNonNull(C, state, Source, srcVal);
854 if (!state)
855 return;
856
Jordy Rose7182b962011-06-04 01:50:25 +0000857 // Ensure the accesses are valid and that the buffers do not overlap.
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000858 const char * const writeWarning =
859 "Memory copy function overflows destination buffer";
Jordy Rosee64f3112010-08-16 07:51:42 +0000860 state = CheckBufferAccess(C, state, Size, Dest, Source,
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000861 writeWarning, /* sourceWarning = */ NULL);
Jordy Rosed325ffb2010-07-08 23:57:29 +0000862 if (Restricted)
863 state = CheckOverlap(C, state, Size, Dest, Source);
Jordy Rosee64f3112010-08-16 07:51:42 +0000864
Jordy Rose7182b962011-06-04 01:50:25 +0000865 if (!state)
866 return;
Lenny Maioranib8b875b2011-03-31 21:36:53 +0000867
Jordy Rose7182b962011-06-04 01:50:25 +0000868 // If this is mempcpy, get the byte after the last byte copied and
869 // bind the expr.
870 if (IsMempcpy) {
871 loc::MemRegionVal *destRegVal = dyn_cast<loc::MemRegionVal>(&destVal);
872 assert(destRegVal && "Destination should be a known MemRegionVal here");
873
874 // Get the length to copy.
875 NonLoc *lenValNonLoc = dyn_cast<NonLoc>(&sizeVal);
876
877 if (lenValNonLoc) {
878 // Get the byte after the last byte copied.
879 SVal lastElement = C.getSValBuilder().evalBinOpLN(state, BO_Add,
880 *destRegVal,
881 *lenValNonLoc,
882 Dest->getType());
883
884 // The byte after the last byte copied is the return value.
885 state = state->BindExpr(CE, lastElement);
Jordy Rose3f8bb2f2011-06-04 01:47:27 +0000886 } else {
Jordy Rose7182b962011-06-04 01:50:25 +0000887 // If we don't know how much we copied, we can at least
888 // conjure a return value for later.
889 unsigned Count = C.getNodeBuilder().getCurrentBlockCount();
890 SVal result =
891 C.getSValBuilder().getConjuredSymbolVal(NULL, CE, Count);
892 state = state->BindExpr(CE, result);
Lenny Maioranib8b875b2011-03-31 21:36:53 +0000893 }
894
Jordy Rose7182b962011-06-04 01:50:25 +0000895 } else {
896 // All other copies return the destination buffer.
897 // (Well, bcopy() has a void return type, but this won't hurt.)
898 state = state->BindExpr(CE, destVal);
Jordy Rosee64f3112010-08-16 07:51:42 +0000899 }
Jordy Rose7182b962011-06-04 01:50:25 +0000900
901 // Invalidate the destination.
902 // FIXME: Even if we can't perfectly model the copy, we should see if we
903 // can use LazyCompoundVals to copy the source values into the destination.
904 // This would probably remove any existing bindings past the end of the
905 // copied region, but that's still an improvement over blank invalidation.
906 state = InvalidateBuffer(C, state, Dest, state->getSVal(Dest));
907 C.addTransition(state);
Jordy Rosed325ffb2010-07-08 23:57:29 +0000908 }
909}
910
911
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +0000912void CStringChecker::evalMemcpy(CheckerContext &C, const CallExpr *CE) const {
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000913 // void *memcpy(void *restrict dst, const void *restrict src, size_t n);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000914 // The return value is the address of the destination buffer.
Jordy Rosed325ffb2010-07-08 23:57:29 +0000915 const Expr *Dest = CE->getArg(0);
916 const GRState *state = C.getState();
Jordy Rose3f8bb2f2011-06-04 01:47:27 +0000917
Lenny Maioranib8b875b2011-03-31 21:36:53 +0000918 evalCopyCommon(C, CE, state, CE->getArg(2), Dest, CE->getArg(1), true);
919}
920
921void CStringChecker::evalMempcpy(CheckerContext &C, const CallExpr *CE) const {
922 // void *mempcpy(void *restrict dst, const void *restrict src, size_t n);
923 // The return value is a pointer to the byte following the last written byte.
924 const Expr *Dest = CE->getArg(0);
925 const GRState *state = C.getState();
926
927 evalCopyCommon(C, CE, state, CE->getArg(2), Dest, CE->getArg(1), true, true);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000928}
929
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +0000930void CStringChecker::evalMemmove(CheckerContext &C, const CallExpr *CE) const {
Jordy Rosed325ffb2010-07-08 23:57:29 +0000931 // void *memmove(void *dst, const void *src, size_t n);
932 // The return value is the address of the destination buffer.
933 const Expr *Dest = CE->getArg(0);
934 const GRState *state = C.getState();
Jordy Rose3f8bb2f2011-06-04 01:47:27 +0000935
Lenny Maioranib8b875b2011-03-31 21:36:53 +0000936 evalCopyCommon(C, CE, state, CE->getArg(2), Dest, CE->getArg(1));
Jordy Rosed325ffb2010-07-08 23:57:29 +0000937}
938
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +0000939void CStringChecker::evalBcopy(CheckerContext &C, const CallExpr *CE) const {
Jordy Rosed325ffb2010-07-08 23:57:29 +0000940 // void bcopy(const void *src, void *dst, size_t n);
Lenny Maioranib8b875b2011-03-31 21:36:53 +0000941 evalCopyCommon(C, CE, C.getState(),
942 CE->getArg(2), CE->getArg(1), CE->getArg(0));
Jordy Rosed325ffb2010-07-08 23:57:29 +0000943}
944
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +0000945void CStringChecker::evalMemcmp(CheckerContext &C, const CallExpr *CE) const {
Jordy Rosebc56d1f2010-07-07 08:15:01 +0000946 // int memcmp(const void *s1, const void *s2, size_t n);
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000947 CurrentFunctionDescription = "memory comparison function";
948
Jordy Rosebc56d1f2010-07-07 08:15:01 +0000949 const Expr *Left = CE->getArg(0);
950 const Expr *Right = CE->getArg(1);
951 const Expr *Size = CE->getArg(2);
952
953 const GRState *state = C.getState();
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000954 SValBuilder &svalBuilder = C.getSValBuilder();
Jordy Rosebc56d1f2010-07-07 08:15:01 +0000955
Jordy Rosed325ffb2010-07-08 23:57:29 +0000956 // See if the size argument is zero.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000957 SVal sizeVal = state->getSVal(Size);
958 QualType sizeTy = Size->getType();
Jordy Rosebc56d1f2010-07-07 08:15:01 +0000959
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000960 const GRState *stateZeroSize, *stateNonZeroSize;
961 llvm::tie(stateZeroSize, stateNonZeroSize) =
962 assumeZero(C, state, sizeVal, sizeTy);
Jordy Rosebc56d1f2010-07-07 08:15:01 +0000963
Jordy Rosed325ffb2010-07-08 23:57:29 +0000964 // If the size can be zero, the result will be 0 in that case, and we don't
965 // have to check either of the buffers.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000966 if (stateZeroSize) {
967 state = stateZeroSize;
968 state = state->BindExpr(CE, svalBuilder.makeZeroVal(CE->getType()));
Jordy Rosed325ffb2010-07-08 23:57:29 +0000969 C.addTransition(state);
Jordy Rosebc56d1f2010-07-07 08:15:01 +0000970 }
971
Jordy Rosed325ffb2010-07-08 23:57:29 +0000972 // If the size can be nonzero, we have to check the other arguments.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000973 if (stateNonZeroSize) {
974 state = stateNonZeroSize;
Jordy Rosed325ffb2010-07-08 23:57:29 +0000975 // If we know the two buffers are the same, we know the result is 0.
976 // First, get the two buffers' addresses. Another checker will have already
977 // made sure they're not undefined.
978 DefinedOrUnknownSVal LV = cast<DefinedOrUnknownSVal>(state->getSVal(Left));
979 DefinedOrUnknownSVal RV = cast<DefinedOrUnknownSVal>(state->getSVal(Right));
Jordy Rosebc56d1f2010-07-07 08:15:01 +0000980
Jordy Rosed325ffb2010-07-08 23:57:29 +0000981 // See if they are the same.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000982 DefinedOrUnknownSVal SameBuf = svalBuilder.evalEQ(state, LV, RV);
Jordy Rosed325ffb2010-07-08 23:57:29 +0000983 const GRState *StSameBuf, *StNotSameBuf;
Ted Kremenek28f47b92010-12-01 22:16:56 +0000984 llvm::tie(StSameBuf, StNotSameBuf) = state->assume(SameBuf);
Jordy Rosed325ffb2010-07-08 23:57:29 +0000985
Jordy Rose1e022412011-06-16 05:51:02 +0000986 // If the two arguments might be the same buffer, we know the result is 0,
Jordy Rosed325ffb2010-07-08 23:57:29 +0000987 // and we only need to check one size.
988 if (StSameBuf) {
989 state = StSameBuf;
990 state = CheckBufferAccess(C, state, Size, Left);
991 if (state) {
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000992 state = StSameBuf->BindExpr(CE, svalBuilder.makeZeroVal(CE->getType()));
Jordy Rosed325ffb2010-07-08 23:57:29 +0000993 C.addTransition(state);
994 }
995 }
996
997 // If the two arguments might be different buffers, we have to check the
998 // size of both of them.
999 if (StNotSameBuf) {
1000 state = StNotSameBuf;
1001 state = CheckBufferAccess(C, state, Size, Left, Right);
1002 if (state) {
1003 // The return value is the comparison result, which we don't know.
1004 unsigned Count = C.getNodeBuilder().getCurrentBlockCount();
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001005 SVal CmpV = svalBuilder.getConjuredSymbolVal(NULL, CE, Count);
Jordy Rosed325ffb2010-07-08 23:57:29 +00001006 state = state->BindExpr(CE, CmpV);
1007 C.addTransition(state);
1008 }
1009 }
1010 }
Jordy Rosebc56d1f2010-07-07 08:15:01 +00001011}
1012
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +00001013void CStringChecker::evalstrLength(CheckerContext &C,
1014 const CallExpr *CE) const {
Jordy Rose19c5dd12010-07-27 01:37:31 +00001015 // size_t strlen(const char *s);
Ted Kremenekbe4242c2011-02-22 04:55:05 +00001016 evalstrLengthCommon(C, CE, /* IsStrnlen = */ false);
1017}
1018
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +00001019void CStringChecker::evalstrnLength(CheckerContext &C,
1020 const CallExpr *CE) const {
Ted Kremenekbe4242c2011-02-22 04:55:05 +00001021 // size_t strnlen(const char *s, size_t maxlen);
1022 evalstrLengthCommon(C, CE, /* IsStrnlen = */ true);
1023}
1024
1025void CStringChecker::evalstrLengthCommon(CheckerContext &C, const CallExpr *CE,
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +00001026 bool IsStrnlen) const {
Jordy Rose9e49d9f2011-06-20 02:06:40 +00001027 CurrentFunctionDescription = "string length function";
Jordy Rose19c5dd12010-07-27 01:37:31 +00001028 const GRState *state = C.getState();
Jordy Rose793bff32011-06-14 01:15:31 +00001029
1030 if (IsStrnlen) {
1031 const Expr *maxlenExpr = CE->getArg(1);
1032 SVal maxlenVal = state->getSVal(maxlenExpr);
1033
1034 const GRState *stateZeroSize, *stateNonZeroSize;
1035 llvm::tie(stateZeroSize, stateNonZeroSize) =
1036 assumeZero(C, state, maxlenVal, maxlenExpr->getType());
1037
1038 // If the size can be zero, the result will be 0 in that case, and we don't
1039 // have to check the string itself.
1040 if (stateZeroSize) {
1041 SVal zero = C.getSValBuilder().makeZeroVal(CE->getType());
1042 stateZeroSize = stateZeroSize->BindExpr(CE, zero);
1043 C.addTransition(stateZeroSize);
1044 }
1045
1046 // If the size is GUARANTEED to be zero, we're done!
1047 if (!stateNonZeroSize)
1048 return;
1049
1050 // Otherwise, record the assumption that the size is nonzero.
1051 state = stateNonZeroSize;
1052 }
1053
1054 // Check that the string argument is non-null.
Jordy Rose19c5dd12010-07-27 01:37:31 +00001055 const Expr *Arg = CE->getArg(0);
1056 SVal ArgVal = state->getSVal(Arg);
1057
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001058 state = checkNonNull(C, state, Arg, ArgVal);
Jordy Rose19c5dd12010-07-27 01:37:31 +00001059
Jordy Rosebd32bee2011-06-14 01:26:48 +00001060 if (!state)
1061 return;
Jordy Rosea5261542010-08-14 21:02:52 +00001062
Jordy Rosebd32bee2011-06-14 01:26:48 +00001063 SVal strLength = getCStringLength(C, state, Arg, ArgVal);
Jordy Rosea5261542010-08-14 21:02:52 +00001064
Jordy Rosebd32bee2011-06-14 01:26:48 +00001065 // If the argument isn't a valid C string, there's no valid state to
1066 // transition to.
1067 if (strLength.isUndef())
1068 return;
Jordy Rose793bff32011-06-14 01:15:31 +00001069
Jordy Rosebd32bee2011-06-14 01:26:48 +00001070 DefinedOrUnknownSVal result = UnknownVal();
Jordy Rose793bff32011-06-14 01:15:31 +00001071
Jordy Rosebd32bee2011-06-14 01:26:48 +00001072 // If the check is for strnlen() then bind the return value to no more than
1073 // the maxlen value.
1074 if (IsStrnlen) {
Jordy Roseee2fde12011-06-16 05:56:50 +00001075 QualType cmpTy = C.getSValBuilder().getConditionType();
Jordy Rose793bff32011-06-14 01:15:31 +00001076
Jordy Rosebd32bee2011-06-14 01:26:48 +00001077 // It's a little unfortunate to be getting this again,
1078 // but it's not that expensive...
1079 const Expr *maxlenExpr = CE->getArg(1);
1080 SVal maxlenVal = state->getSVal(maxlenExpr);
Ted Kremenekbe4242c2011-02-22 04:55:05 +00001081
Jordy Rosebd32bee2011-06-14 01:26:48 +00001082 NonLoc *strLengthNL = dyn_cast<NonLoc>(&strLength);
1083 NonLoc *maxlenValNL = dyn_cast<NonLoc>(&maxlenVal);
Ted Kremenekbe4242c2011-02-22 04:55:05 +00001084
Jordy Rosebd32bee2011-06-14 01:26:48 +00001085 if (strLengthNL && maxlenValNL) {
1086 const GRState *stateStringTooLong, *stateStringNotTooLong;
Jordy Rose793bff32011-06-14 01:15:31 +00001087
Jordy Rosebd32bee2011-06-14 01:26:48 +00001088 // Check if the strLength is greater than the maxlen.
1089 llvm::tie(stateStringTooLong, stateStringNotTooLong) =
1090 state->assume(cast<DefinedOrUnknownSVal>
1091 (C.getSValBuilder().evalBinOpNN(state, BO_GT,
1092 *strLengthNL,
1093 *maxlenValNL,
1094 cmpTy)));
Jordy Rose793bff32011-06-14 01:15:31 +00001095
Jordy Rosebd32bee2011-06-14 01:26:48 +00001096 if (stateStringTooLong && !stateStringNotTooLong) {
1097 // If the string is longer than maxlen, return maxlen.
1098 result = *maxlenValNL;
1099 } else if (stateStringNotTooLong && !stateStringTooLong) {
1100 // If the string is shorter than maxlen, return its length.
1101 result = *strLengthNL;
Ted Kremenekbe4242c2011-02-22 04:55:05 +00001102 }
1103 }
1104
Jordy Rosebd32bee2011-06-14 01:26:48 +00001105 if (result.isUnknown()) {
1106 // If we don't have enough information for a comparison, there's
1107 // no guarantee the full string length will actually be returned.
1108 // All we know is the return value is the min of the string length
1109 // and the limit. This is better than nothing.
1110 unsigned Count = C.getNodeBuilder().getCurrentBlockCount();
1111 result = C.getSValBuilder().getConjuredSymbolVal(NULL, CE, Count);
1112 NonLoc *resultNL = cast<NonLoc>(&result);
1113
1114 if (strLengthNL) {
1115 state = state->assume(cast<DefinedOrUnknownSVal>
1116 (C.getSValBuilder().evalBinOpNN(state, BO_LE,
1117 *resultNL,
1118 *strLengthNL,
1119 cmpTy)), true);
1120 }
1121
1122 if (maxlenValNL) {
1123 state = state->assume(cast<DefinedOrUnknownSVal>
1124 (C.getSValBuilder().evalBinOpNN(state, BO_LE,
1125 *resultNL,
1126 *maxlenValNL,
1127 cmpTy)), true);
1128 }
1129 }
1130
1131 } else {
1132 // This is a plain strlen(), not strnlen().
1133 result = cast<DefinedOrUnknownSVal>(strLength);
1134
1135 // If we don't know the length of the string, conjure a return
1136 // value, so it can be used in constraints, at least.
1137 if (result.isUnknown()) {
1138 unsigned Count = C.getNodeBuilder().getCurrentBlockCount();
1139 result = C.getSValBuilder().getConjuredSymbolVal(NULL, CE, Count);
1140 }
Jordy Rose19c5dd12010-07-27 01:37:31 +00001141 }
Jordy Rosebd32bee2011-06-14 01:26:48 +00001142
1143 // Bind the return value.
1144 assert(!result.isUnknown() && "Should have conjured a value by now");
1145 state = state->BindExpr(CE, result);
1146 C.addTransition(state);
Jordy Rose19c5dd12010-07-27 01:37:31 +00001147}
1148
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +00001149void CStringChecker::evalStrcpy(CheckerContext &C, const CallExpr *CE) const {
Jordy Rosee64f3112010-08-16 07:51:42 +00001150 // char *strcpy(char *restrict dst, const char *restrict src);
Lenny Maiorani067bbd02011-04-09 15:12:58 +00001151 evalStrcpyCommon(C, CE,
1152 /* returnEnd = */ false,
1153 /* isBounded = */ false,
1154 /* isAppending = */ false);
Ted Kremenek0ef473f2011-02-22 04:58:34 +00001155}
1156
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +00001157void CStringChecker::evalStrncpy(CheckerContext &C, const CallExpr *CE) const {
Jordy Rosec1525862011-06-04 00:05:23 +00001158 // char *strncpy(char *restrict dst, const char *restrict src, size_t n);
Lenny Maiorani067bbd02011-04-09 15:12:58 +00001159 evalStrcpyCommon(C, CE,
1160 /* returnEnd = */ false,
1161 /* isBounded = */ true,
1162 /* isAppending = */ false);
Jordy Rosee64f3112010-08-16 07:51:42 +00001163}
1164
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +00001165void CStringChecker::evalStpcpy(CheckerContext &C, const CallExpr *CE) const {
Jordy Rosee64f3112010-08-16 07:51:42 +00001166 // char *stpcpy(char *restrict dst, const char *restrict src);
Lenny Maiorani067bbd02011-04-09 15:12:58 +00001167 evalStrcpyCommon(C, CE,
1168 /* returnEnd = */ true,
1169 /* isBounded = */ false,
1170 /* isAppending = */ false);
1171}
1172
1173void CStringChecker::evalStrcat(CheckerContext &C, const CallExpr *CE) const {
1174 //char *strcat(char *restrict s1, const char *restrict s2);
1175 evalStrcpyCommon(C, CE,
1176 /* returnEnd = */ false,
1177 /* isBounded = */ false,
1178 /* isAppending = */ true);
1179}
1180
1181void CStringChecker::evalStrncat(CheckerContext &C, const CallExpr *CE) const {
1182 //char *strncat(char *restrict s1, const char *restrict s2, size_t n);
1183 evalStrcpyCommon(C, CE,
1184 /* returnEnd = */ false,
1185 /* isBounded = */ true,
1186 /* isAppending = */ true);
Jordy Rosee64f3112010-08-16 07:51:42 +00001187}
1188
Ted Kremenek9c149532010-12-01 21:57:22 +00001189void CStringChecker::evalStrcpyCommon(CheckerContext &C, const CallExpr *CE,
Lenny Maiorani067bbd02011-04-09 15:12:58 +00001190 bool returnEnd, bool isBounded,
1191 bool isAppending) const {
Jordy Rose9e49d9f2011-06-20 02:06:40 +00001192 CurrentFunctionDescription = "string copy function";
Jordy Rosee64f3112010-08-16 07:51:42 +00001193 const GRState *state = C.getState();
1194
Lenny Maiorani067bbd02011-04-09 15:12:58 +00001195 // Check that the destination is non-null.
Jordy Rosee64f3112010-08-16 07:51:42 +00001196 const Expr *Dst = CE->getArg(0);
1197 SVal DstVal = state->getSVal(Dst);
1198
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001199 state = checkNonNull(C, state, Dst, DstVal);
Jordy Rosee64f3112010-08-16 07:51:42 +00001200 if (!state)
1201 return;
1202
1203 // Check that the source is non-null.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001204 const Expr *srcExpr = CE->getArg(1);
1205 SVal srcVal = state->getSVal(srcExpr);
1206 state = checkNonNull(C, state, srcExpr, srcVal);
Jordy Rosee64f3112010-08-16 07:51:42 +00001207 if (!state)
1208 return;
1209
1210 // Get the string length of the source.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001211 SVal strLength = getCStringLength(C, state, srcExpr, srcVal);
Jordy Rosee64f3112010-08-16 07:51:42 +00001212
1213 // If the source isn't a valid C string, give up.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001214 if (strLength.isUndef())
Jordy Rosee64f3112010-08-16 07:51:42 +00001215 return;
1216
Jordy Rosed5af0e12011-06-15 05:52:56 +00001217 SValBuilder &svalBuilder = C.getSValBuilder();
1218 QualType cmpTy = svalBuilder.getConditionType();
Jordy Rose8912aae2011-06-20 21:55:40 +00001219 QualType sizeTy = svalBuilder.getContext().getSizeType();
Jordy Rosed5af0e12011-06-15 05:52:56 +00001220
Jordy Rose8912aae2011-06-20 21:55:40 +00001221 // These two values allow checking two kinds of errors:
1222 // - actual overflows caused by a source that doesn't fit in the destination
1223 // - potential overflows caused by a bound that could exceed the destination
Jordy Rosed5af0e12011-06-15 05:52:56 +00001224 SVal amountCopied = UnknownVal();
Jordy Rose8912aae2011-06-20 21:55:40 +00001225 SVal maxLastElementIndex = UnknownVal();
1226 const char *boundWarning = NULL;
Jordy Rosed5af0e12011-06-15 05:52:56 +00001227
Lenny Maiorani067bbd02011-04-09 15:12:58 +00001228 // If the function is strncpy, strncat, etc... it is bounded.
1229 if (isBounded) {
1230 // Get the max number of characters to copy.
Ted Kremenek0ef473f2011-02-22 04:58:34 +00001231 const Expr *lenExpr = CE->getArg(2);
1232 SVal lenVal = state->getSVal(lenExpr);
1233
Jordy Rosed5af0e12011-06-15 05:52:56 +00001234 // Protect against misdeclared strncpy().
Jordy Rose8912aae2011-06-20 21:55:40 +00001235 lenVal = svalBuilder.evalCast(lenVal, sizeTy, lenExpr->getType());
Jordy Rosed5af0e12011-06-15 05:52:56 +00001236
Ted Kremenek0ef473f2011-02-22 04:58:34 +00001237 NonLoc *strLengthNL = dyn_cast<NonLoc>(&strLength);
1238 NonLoc *lenValNL = dyn_cast<NonLoc>(&lenVal);
1239
Jordy Rosed5af0e12011-06-15 05:52:56 +00001240 // If we know both values, we might be able to figure out how much
1241 // we're copying.
1242 if (strLengthNL && lenValNL) {
1243 const GRState *stateSourceTooLong, *stateSourceNotTooLong;
Ted Kremenek0ef473f2011-02-22 04:58:34 +00001244
Jordy Rosed5af0e12011-06-15 05:52:56 +00001245 // Check if the max number to copy is less than the length of the src.
Jordy Rose8912aae2011-06-20 21:55:40 +00001246 // If the bound is equal to the source length, strncpy won't null-
1247 // terminate the result!
Jordy Rosed5af0e12011-06-15 05:52:56 +00001248 llvm::tie(stateSourceTooLong, stateSourceNotTooLong) =
1249 state->assume(cast<DefinedOrUnknownSVal>
Jordy Rose8912aae2011-06-20 21:55:40 +00001250 (svalBuilder.evalBinOpNN(state, BO_GE, *strLengthNL,
Jordy Rosed5af0e12011-06-15 05:52:56 +00001251 *lenValNL, cmpTy)));
1252
1253 if (stateSourceTooLong && !stateSourceNotTooLong) {
1254 // Max number to copy is less than the length of the src, so the actual
1255 // strLength copied is the max number arg.
1256 state = stateSourceTooLong;
1257 amountCopied = lenVal;
1258
1259 } else if (!stateSourceTooLong && stateSourceNotTooLong) {
1260 // The source buffer entirely fits in the bound.
1261 state = stateSourceNotTooLong;
1262 amountCopied = strLength;
1263 }
1264 }
1265
Jordy Rose5e5f1502011-06-20 03:49:16 +00001266 // We still want to know if the bound is known to be too large.
Jordy Rose8912aae2011-06-20 21:55:40 +00001267 if (lenValNL) {
1268 if (isAppending) {
1269 // For strncat, the check is strlen(dst) + lenVal < sizeof(dst)
1270
1271 // Get the string length of the destination. If the destination is
1272 // memory that can't have a string length, we shouldn't be copying
1273 // into it anyway.
1274 SVal dstStrLength = getCStringLength(C, state, Dst, DstVal);
1275 if (dstStrLength.isUndef())
1276 return;
1277
1278 if (NonLoc *dstStrLengthNL = dyn_cast<NonLoc>(&dstStrLength)) {
1279 maxLastElementIndex = svalBuilder.evalBinOpNN(state, BO_Add,
1280 *lenValNL,
1281 *dstStrLengthNL,
1282 sizeTy);
1283 boundWarning = "Size argument is greater than the free space in the "
1284 "destination buffer";
1285 }
1286
1287 } else {
1288 // For strncpy, this is just checking that lenVal <= sizeof(dst)
1289 // (Yes, strncpy and strncat differ in how they treat termination.
1290 // strncat ALWAYS terminates, but strncpy doesn't.)
1291 NonLoc one = cast<NonLoc>(svalBuilder.makeIntVal(1, sizeTy));
1292 maxLastElementIndex = svalBuilder.evalBinOpNN(state, BO_Sub, *lenValNL,
1293 one, sizeTy);
1294 boundWarning = "Size argument is greater than the length of the "
1295 "destination buffer";
1296 }
1297 }
Jordy Rose5e5f1502011-06-20 03:49:16 +00001298
Jordy Rosed5af0e12011-06-15 05:52:56 +00001299 // If we couldn't pin down the copy length, at least bound it.
Jordy Rose8912aae2011-06-20 21:55:40 +00001300 // FIXME: We should actually run this code path for append as well, but
1301 // right now it creates problems with constraints (since we can end up
1302 // trying to pass constraints from symbol to symbol).
1303 if (amountCopied.isUnknown() && !isAppending) {
Jordy Rosed5af0e12011-06-15 05:52:56 +00001304 // Try to get a "hypothetical" string length symbol, which we can later
1305 // set as a real value if that turns out to be the case.
1306 amountCopied = getCStringLength(C, state, lenExpr, srcVal, true);
1307 assert(!amountCopied.isUndef());
1308
1309 if (NonLoc *amountCopiedNL = dyn_cast<NonLoc>(&amountCopied)) {
1310 if (lenValNL) {
1311 // amountCopied <= lenVal
1312 SVal copiedLessThanBound = svalBuilder.evalBinOpNN(state, BO_LE,
1313 *amountCopiedNL,
1314 *lenValNL,
1315 cmpTy);
1316 state = state->assume(cast<DefinedOrUnknownSVal>(copiedLessThanBound),
1317 true);
1318 if (!state)
1319 return;
1320 }
1321
1322 if (strLengthNL) {
1323 // amountCopied <= strlen(source)
1324 SVal copiedLessThanSrc = svalBuilder.evalBinOpNN(state, BO_LE,
1325 *amountCopiedNL,
1326 *strLengthNL,
1327 cmpTy);
1328 state = state->assume(cast<DefinedOrUnknownSVal>(copiedLessThanSrc),
1329 true);
1330 if (!state)
1331 return;
1332 }
1333 }
1334 }
1335
1336 } else {
1337 // The function isn't bounded. The amount copied should match the length
1338 // of the source buffer.
1339 amountCopied = strLength;
Ted Kremenek0ef473f2011-02-22 04:58:34 +00001340 }
1341
Jordy Rosed5af0e12011-06-15 05:52:56 +00001342 assert(state);
1343
1344 // This represents the number of characters copied into the destination
1345 // buffer. (It may not actually be the strlen if the destination buffer
1346 // is not terminated.)
1347 SVal finalStrLength = UnknownVal();
1348
Lenny Maiorani067bbd02011-04-09 15:12:58 +00001349 // If this is an appending function (strcat, strncat...) then set the
1350 // string length to strlen(src) + strlen(dst) since the buffer will
1351 // ultimately contain both.
1352 if (isAppending) {
Jordy Rose1e022412011-06-16 05:51:02 +00001353 // Get the string length of the destination. If the destination is memory
1354 // that can't have a string length, we shouldn't be copying into it anyway.
Lenny Maiorani067bbd02011-04-09 15:12:58 +00001355 SVal dstStrLength = getCStringLength(C, state, Dst, DstVal);
1356 if (dstStrLength.isUndef())
1357 return;
1358
Jordy Rosed5af0e12011-06-15 05:52:56 +00001359 NonLoc *srcStrLengthNL = dyn_cast<NonLoc>(&amountCopied);
Lenny Maiorani067bbd02011-04-09 15:12:58 +00001360 NonLoc *dstStrLengthNL = dyn_cast<NonLoc>(&dstStrLength);
1361
Jordy Rosed5af0e12011-06-15 05:52:56 +00001362 // If we know both string lengths, we might know the final string length.
1363 if (srcStrLengthNL && dstStrLengthNL) {
1364 // Make sure the two lengths together don't overflow a size_t.
1365 state = checkAdditionOverflow(C, state, *srcStrLengthNL, *dstStrLengthNL);
1366 if (!state)
1367 return;
Lenny Maiorani067bbd02011-04-09 15:12:58 +00001368
Jordy Rosed5af0e12011-06-15 05:52:56 +00001369 finalStrLength = svalBuilder.evalBinOpNN(state, BO_Add, *srcStrLengthNL,
1370 *dstStrLengthNL, sizeTy);
1371 }
Lenny Maiorani067bbd02011-04-09 15:12:58 +00001372
Jordy Rosed5af0e12011-06-15 05:52:56 +00001373 // If we couldn't get a single value for the final string length,
1374 // we can at least bound it by the individual lengths.
1375 if (finalStrLength.isUnknown()) {
1376 // Try to get a "hypothetical" string length symbol, which we can later
1377 // set as a real value if that turns out to be the case.
1378 finalStrLength = getCStringLength(C, state, CE, DstVal, true);
1379 assert(!finalStrLength.isUndef());
1380
1381 if (NonLoc *finalStrLengthNL = dyn_cast<NonLoc>(&finalStrLength)) {
1382 if (srcStrLengthNL) {
1383 // finalStrLength >= srcStrLength
1384 SVal sourceInResult = svalBuilder.evalBinOpNN(state, BO_GE,
1385 *finalStrLengthNL,
1386 *srcStrLengthNL,
1387 cmpTy);
1388 state = state->assume(cast<DefinedOrUnknownSVal>(sourceInResult),
1389 true);
1390 if (!state)
1391 return;
1392 }
1393
1394 if (dstStrLengthNL) {
1395 // finalStrLength >= dstStrLength
1396 SVal destInResult = svalBuilder.evalBinOpNN(state, BO_GE,
1397 *finalStrLengthNL,
1398 *dstStrLengthNL,
1399 cmpTy);
1400 state = state->assume(cast<DefinedOrUnknownSVal>(destInResult),
1401 true);
1402 if (!state)
1403 return;
1404 }
1405 }
1406 }
1407
1408 } else {
1409 // Otherwise, this is a copy-over function (strcpy, strncpy, ...), and
1410 // the final string length will match the input string length.
1411 finalStrLength = amountCopied;
Lenny Maiorani067bbd02011-04-09 15:12:58 +00001412 }
1413
Jordy Rosed5af0e12011-06-15 05:52:56 +00001414 // The final result of the function will either be a pointer past the last
1415 // copied element, or a pointer to the start of the destination buffer.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001416 SVal Result = (returnEnd ? UnknownVal() : DstVal);
Jordy Rosee64f3112010-08-16 07:51:42 +00001417
Jordy Rosed5af0e12011-06-15 05:52:56 +00001418 assert(state);
1419
Jordy Rosee64f3112010-08-16 07:51:42 +00001420 // If the destination is a MemRegion, try to check for a buffer overflow and
1421 // record the new string length.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001422 if (loc::MemRegionVal *dstRegVal = dyn_cast<loc::MemRegionVal>(&DstVal)) {
Jordy Rose8912aae2011-06-20 21:55:40 +00001423 QualType ptrTy = Dst->getType();
1424
1425 // If we have an exact value on a bounded copy, use that to check for
1426 // overflows, rather than our estimate about how much is actually copied.
1427 if (boundWarning) {
1428 if (NonLoc *maxLastNL = dyn_cast<NonLoc>(&maxLastElementIndex)) {
1429 SVal maxLastElement = svalBuilder.evalBinOpLN(state, BO_Add, *dstRegVal,
1430 *maxLastNL, ptrTy);
1431 state = CheckLocation(C, state, CE->getArg(2), maxLastElement,
1432 boundWarning);
1433 if (!state)
1434 return;
1435 }
1436 }
1437
1438 // Then, if the final length is known...
Jordy Rosed5af0e12011-06-15 05:52:56 +00001439 if (NonLoc *knownStrLength = dyn_cast<NonLoc>(&finalStrLength)) {
1440 SVal lastElement = svalBuilder.evalBinOpLN(state, BO_Add, *dstRegVal,
Jordy Rose8912aae2011-06-20 21:55:40 +00001441 *knownStrLength, ptrTy);
Jordy Rosee64f3112010-08-16 07:51:42 +00001442
Jordy Rose8912aae2011-06-20 21:55:40 +00001443 // ...and we haven't checked the bound, we'll check the actual copy.
1444 if (!boundWarning) {
1445 const char * const warningMsg =
1446 "String copy function overflows destination buffer";
1447 state = CheckLocation(C, state, Dst, lastElement, warningMsg);
1448 if (!state)
1449 return;
1450 }
Jordy Rosee64f3112010-08-16 07:51:42 +00001451
1452 // If this is a stpcpy-style copy, the last element is the return value.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001453 if (returnEnd)
1454 Result = lastElement;
Jordy Rosee64f3112010-08-16 07:51:42 +00001455 }
1456
1457 // Invalidate the destination. This must happen before we set the C string
1458 // length because invalidation will clear the length.
1459 // FIXME: Even if we can't perfectly model the copy, we should see if we
1460 // can use LazyCompoundVals to copy the source values into the destination.
1461 // This would probably remove any existing bindings past the end of the
1462 // string, but that's still an improvement over blank invalidation.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001463 state = InvalidateBuffer(C, state, Dst, *dstRegVal);
Jordy Rosee64f3112010-08-16 07:51:42 +00001464
Jordy Rose5e5f1502011-06-20 03:49:16 +00001465 // Set the C string length of the destination, if we know it.
Jordy Rose8912aae2011-06-20 21:55:40 +00001466 if (isBounded && !isAppending) {
1467 // strncpy is annoying in that it doesn't guarantee to null-terminate
1468 // the result string. If the original string didn't fit entirely inside
1469 // the bound (including the null-terminator), we don't know how long the
1470 // result is.
1471 if (amountCopied != strLength)
1472 finalStrLength = UnknownVal();
1473 }
1474 state = setCStringLength(state, dstRegVal->getRegion(), finalStrLength);
Jordy Rosee64f3112010-08-16 07:51:42 +00001475 }
1476
Jordy Rosed5af0e12011-06-15 05:52:56 +00001477 assert(state);
1478
Jordy Rosee64f3112010-08-16 07:51:42 +00001479 // If this is a stpcpy-style copy, but we were unable to check for a buffer
1480 // overflow, we still need a result. Conjure a return value.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001481 if (returnEnd && Result.isUnknown()) {
Jordy Rosee64f3112010-08-16 07:51:42 +00001482 unsigned Count = C.getNodeBuilder().getCurrentBlockCount();
Jordy Rosed5af0e12011-06-15 05:52:56 +00001483 Result = svalBuilder.getConjuredSymbolVal(NULL, CE, Count);
Jordy Rosee64f3112010-08-16 07:51:42 +00001484 }
1485
1486 // Set the return value.
1487 state = state->BindExpr(CE, Result);
1488 C.addTransition(state);
1489}
1490
Lenny Maiorani318dd922011-04-12 17:08:43 +00001491void CStringChecker::evalStrcmp(CheckerContext &C, const CallExpr *CE) const {
Jordy Roseadc42d42011-06-16 07:13:34 +00001492 //int strcmp(const char *s1, const char *s2);
Lenny Maioranibd1d16a2011-04-28 15:09:11 +00001493 evalStrcmpCommon(C, CE, /* isBounded = */ false, /* ignoreCase = */ false);
Lenny Maiorani357f6ee2011-04-25 22:21:00 +00001494}
Lenny Maiorani318dd922011-04-12 17:08:43 +00001495
Lenny Maiorani357f6ee2011-04-25 22:21:00 +00001496void CStringChecker::evalStrncmp(CheckerContext &C, const CallExpr *CE) const {
Jordy Roseadc42d42011-06-16 07:13:34 +00001497 //int strncmp(const char *s1, const char *s2, size_t n);
Lenny Maioranibd1d16a2011-04-28 15:09:11 +00001498 evalStrcmpCommon(C, CE, /* isBounded = */ true, /* ignoreCase = */ false);
1499}
1500
1501void CStringChecker::evalStrcasecmp(CheckerContext &C,
1502 const CallExpr *CE) const {
Jordy Roseadc42d42011-06-16 07:13:34 +00001503 //int strcasecmp(const char *s1, const char *s2);
Lenny Maioranibd1d16a2011-04-28 15:09:11 +00001504 evalStrcmpCommon(C, CE, /* isBounded = */ false, /* ignoreCase = */ true);
Lenny Maiorani357f6ee2011-04-25 22:21:00 +00001505}
1506
Lenny Maiorani454fd2d2011-05-02 19:05:49 +00001507void CStringChecker::evalStrncasecmp(CheckerContext &C,
1508 const CallExpr *CE) const {
Jordy Roseadc42d42011-06-16 07:13:34 +00001509 //int strncasecmp(const char *s1, const char *s2, size_t n);
Lenny Maiorani454fd2d2011-05-02 19:05:49 +00001510 evalStrcmpCommon(C, CE, /* isBounded = */ true, /* ignoreCase = */ true);
1511}
1512
Lenny Maiorani357f6ee2011-04-25 22:21:00 +00001513void CStringChecker::evalStrcmpCommon(CheckerContext &C, const CallExpr *CE,
Lenny Maioranibd1d16a2011-04-28 15:09:11 +00001514 bool isBounded, bool ignoreCase) const {
Jordy Rose9e49d9f2011-06-20 02:06:40 +00001515 CurrentFunctionDescription = "string comparison function";
Lenny Maiorani318dd922011-04-12 17:08:43 +00001516 const GRState *state = C.getState();
1517
1518 // Check that the first string is non-null
1519 const Expr *s1 = CE->getArg(0);
1520 SVal s1Val = state->getSVal(s1);
1521 state = checkNonNull(C, state, s1, s1Val);
1522 if (!state)
1523 return;
1524
1525 // Check that the second string is non-null.
1526 const Expr *s2 = CE->getArg(1);
1527 SVal s2Val = state->getSVal(s2);
1528 state = checkNonNull(C, state, s2, s2Val);
1529 if (!state)
1530 return;
1531
1532 // Get the string length of the first string or give up.
1533 SVal s1Length = getCStringLength(C, state, s1, s1Val);
1534 if (s1Length.isUndef())
1535 return;
1536
1537 // Get the string length of the second string or give up.
1538 SVal s2Length = getCStringLength(C, state, s2, s2Val);
1539 if (s2Length.isUndef())
1540 return;
1541
Jordy Roseadc42d42011-06-16 07:13:34 +00001542 // If we know the two buffers are the same, we know the result is 0.
1543 // First, get the two buffers' addresses. Another checker will have already
1544 // made sure they're not undefined.
1545 DefinedOrUnknownSVal LV = cast<DefinedOrUnknownSVal>(s1Val);
1546 DefinedOrUnknownSVal RV = cast<DefinedOrUnknownSVal>(s2Val);
Lenny Maiorani318dd922011-04-12 17:08:43 +00001547
Jordy Roseadc42d42011-06-16 07:13:34 +00001548 // See if they are the same.
Lenny Maiorani318dd922011-04-12 17:08:43 +00001549 SValBuilder &svalBuilder = C.getSValBuilder();
Jordy Roseadc42d42011-06-16 07:13:34 +00001550 DefinedOrUnknownSVal SameBuf = svalBuilder.evalEQ(state, LV, RV);
1551 const GRState *StSameBuf, *StNotSameBuf;
1552 llvm::tie(StSameBuf, StNotSameBuf) = state->assume(SameBuf);
Lenny Maiorani318dd922011-04-12 17:08:43 +00001553
Jordy Roseadc42d42011-06-16 07:13:34 +00001554 // If the two arguments might be the same buffer, we know the result is 0,
1555 // and we only need to check one size.
1556 if (StSameBuf) {
1557 StSameBuf = StSameBuf->BindExpr(CE, svalBuilder.makeZeroVal(CE->getType()));
1558 C.addTransition(StSameBuf);
1559
1560 // If the two arguments are GUARANTEED to be the same, we're done!
1561 if (!StNotSameBuf)
1562 return;
1563 }
1564
1565 assert(StNotSameBuf);
1566 state = StNotSameBuf;
1567
1568 // At this point we can go about comparing the two buffers.
1569 // For now, we only do this if they're both known string literals.
1570
1571 // Attempt to extract string literals from both expressions.
1572 const StringLiteral *s1StrLiteral = getCStringLiteral(C, state, s1, s1Val);
1573 const StringLiteral *s2StrLiteral = getCStringLiteral(C, state, s2, s2Val);
1574 bool canComputeResult = false;
1575
1576 if (s1StrLiteral && s2StrLiteral) {
Chris Lattner5f9e2722011-07-23 10:55:15 +00001577 StringRef s1StrRef = s1StrLiteral->getString();
1578 StringRef s2StrRef = s2StrLiteral->getString();
Jordy Roseadc42d42011-06-16 07:13:34 +00001579
1580 if (isBounded) {
1581 // Get the max number of characters to compare.
1582 const Expr *lenExpr = CE->getArg(2);
1583 SVal lenVal = state->getSVal(lenExpr);
1584
1585 // If the length is known, we can get the right substrings.
1586 if (const llvm::APSInt *len = svalBuilder.getKnownValue(state, lenVal)) {
1587 // Create substrings of each to compare the prefix.
1588 s1StrRef = s1StrRef.substr(0, (size_t)len->getZExtValue());
1589 s2StrRef = s2StrRef.substr(0, (size_t)len->getZExtValue());
1590 canComputeResult = true;
1591 }
1592 } else {
1593 // This is a normal, unbounded strcmp.
1594 canComputeResult = true;
1595 }
1596
1597 if (canComputeResult) {
1598 // Real strcmp stops at null characters.
1599 size_t s1Term = s1StrRef.find('\0');
Chris Lattner5f9e2722011-07-23 10:55:15 +00001600 if (s1Term != StringRef::npos)
Jordy Roseadc42d42011-06-16 07:13:34 +00001601 s1StrRef = s1StrRef.substr(0, s1Term);
1602
1603 size_t s2Term = s2StrRef.find('\0');
Chris Lattner5f9e2722011-07-23 10:55:15 +00001604 if (s2Term != StringRef::npos)
Jordy Roseadc42d42011-06-16 07:13:34 +00001605 s2StrRef = s2StrRef.substr(0, s2Term);
1606
1607 // Use StringRef's comparison methods to compute the actual result.
1608 int result;
1609
1610 if (ignoreCase) {
1611 // Compare string 1 to string 2 the same way strcasecmp() does.
1612 result = s1StrRef.compare_lower(s2StrRef);
1613 } else {
1614 // Compare string 1 to string 2 the same way strcmp() does.
1615 result = s1StrRef.compare(s2StrRef);
1616 }
1617
1618 // Build the SVal of the comparison and bind the return value.
1619 SVal resultVal = svalBuilder.makeIntVal(result, CE->getType());
1620 state = state->BindExpr(CE, resultVal);
1621 }
1622 }
1623
1624 if (!canComputeResult) {
1625 // Conjure a symbolic value. It's the best we can do.
1626 unsigned Count = C.getNodeBuilder().getCurrentBlockCount();
1627 SVal resultVal = svalBuilder.getConjuredSymbolVal(NULL, CE, Count);
1628 state = state->BindExpr(CE, resultVal);
1629 }
1630
1631 // Record this as a possible path.
Lenny Maiorani318dd922011-04-12 17:08:43 +00001632 C.addTransition(state);
1633}
1634
Jordy Rosed325ffb2010-07-08 23:57:29 +00001635//===----------------------------------------------------------------------===//
Jordy Rosea5261542010-08-14 21:02:52 +00001636// The driver method, and other Checker callbacks.
Jordy Rosed325ffb2010-07-08 23:57:29 +00001637//===----------------------------------------------------------------------===//
Jordy Roseccbf7ee2010-07-06 23:11:01 +00001638
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +00001639bool CStringChecker::evalCall(const CallExpr *CE, CheckerContext &C) const {
Jordy Roseccbf7ee2010-07-06 23:11:01 +00001640 // Get the callee. All the functions we care about are C functions
1641 // with simple identifiers.
1642 const GRState *state = C.getState();
1643 const Expr *Callee = CE->getCallee();
1644 const FunctionDecl *FD = state->getSVal(Callee).getAsFunctionDecl();
1645
1646 if (!FD)
1647 return false;
1648
1649 // Get the name of the callee. If it's a builtin, strip off the prefix.
Douglas Gregor90d26a42010-11-01 23:16:05 +00001650 IdentifierInfo *II = FD->getIdentifier();
1651 if (!II) // if no identifier, not a simple C function
1652 return false;
Chris Lattner5f9e2722011-07-23 10:55:15 +00001653 StringRef Name = II->getName();
Jordy Roseccbf7ee2010-07-06 23:11:01 +00001654 if (Name.startswith("__builtin_"))
1655 Name = Name.substr(10);
1656
Ted Kremenek9c149532010-12-01 21:57:22 +00001657 FnCheck evalFunction = llvm::StringSwitch<FnCheck>(Name)
1658 .Cases("memcpy", "__memcpy_chk", &CStringChecker::evalMemcpy)
Jordy Rosebe460d82011-06-03 23:42:56 +00001659 .Cases("mempcpy", "__mempcpy_chk", &CStringChecker::evalMempcpy)
Ted Kremenek9c149532010-12-01 21:57:22 +00001660 .Cases("memcmp", "bcmp", &CStringChecker::evalMemcmp)
1661 .Cases("memmove", "__memmove_chk", &CStringChecker::evalMemmove)
1662 .Cases("strcpy", "__strcpy_chk", &CStringChecker::evalStrcpy)
Jordy Rose5e5f1502011-06-20 03:49:16 +00001663 .Cases("strncpy", "__strncpy_chk", &CStringChecker::evalStrncpy)
Ted Kremenek9c149532010-12-01 21:57:22 +00001664 .Cases("stpcpy", "__stpcpy_chk", &CStringChecker::evalStpcpy)
Lenny Maiorani067bbd02011-04-09 15:12:58 +00001665 .Cases("strcat", "__strcat_chk", &CStringChecker::evalStrcat)
1666 .Cases("strncat", "__strncat_chk", &CStringChecker::evalStrncat)
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001667 .Case("strlen", &CStringChecker::evalstrLength)
Ted Kremenekbe4242c2011-02-22 04:55:05 +00001668 .Case("strnlen", &CStringChecker::evalstrnLength)
Lenny Maiorani318dd922011-04-12 17:08:43 +00001669 .Case("strcmp", &CStringChecker::evalStrcmp)
Lenny Maiorani357f6ee2011-04-25 22:21:00 +00001670 .Case("strncmp", &CStringChecker::evalStrncmp)
Lenny Maioranibd1d16a2011-04-28 15:09:11 +00001671 .Case("strcasecmp", &CStringChecker::evalStrcasecmp)
Lenny Maiorani454fd2d2011-05-02 19:05:49 +00001672 .Case("strncasecmp", &CStringChecker::evalStrncasecmp)
Ted Kremenek9c149532010-12-01 21:57:22 +00001673 .Case("bcopy", &CStringChecker::evalBcopy)
Jordy Roseccbf7ee2010-07-06 23:11:01 +00001674 .Default(NULL);
1675
Jordy Rosed325ffb2010-07-08 23:57:29 +00001676 // If the callee isn't a string function, let another checker handle it.
Ted Kremenek9c149532010-12-01 21:57:22 +00001677 if (!evalFunction)
Jordy Roseccbf7ee2010-07-06 23:11:01 +00001678 return false;
1679
Jordy Rose9e49d9f2011-06-20 02:06:40 +00001680 // Make sure each function sets its own description.
1681 // (But don't bother in a release build.)
1682 assert(!(CurrentFunctionDescription = NULL));
1683
Jordy Rosed325ffb2010-07-08 23:57:29 +00001684 // Check and evaluate the call.
Ted Kremenek9c149532010-12-01 21:57:22 +00001685 (this->*evalFunction)(C, CE);
Jordy Roseccbf7ee2010-07-06 23:11:01 +00001686 return true;
1687}
Jordy Rosea5261542010-08-14 21:02:52 +00001688
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +00001689void CStringChecker::checkPreStmt(const DeclStmt *DS, CheckerContext &C) const {
Jordy Rosea5261542010-08-14 21:02:52 +00001690 // Record string length for char a[] = "abc";
1691 const GRState *state = C.getState();
1692
1693 for (DeclStmt::const_decl_iterator I = DS->decl_begin(), E = DS->decl_end();
1694 I != E; ++I) {
1695 const VarDecl *D = dyn_cast<VarDecl>(*I);
1696 if (!D)
1697 continue;
1698
1699 // FIXME: Handle array fields of structs.
1700 if (!D->getType()->isArrayType())
1701 continue;
1702
1703 const Expr *Init = D->getInit();
1704 if (!Init)
1705 continue;
1706 if (!isa<StringLiteral>(Init))
1707 continue;
1708
1709 Loc VarLoc = state->getLValue(D, C.getPredecessor()->getLocationContext());
1710 const MemRegion *MR = VarLoc.getAsRegion();
1711 if (!MR)
1712 continue;
1713
1714 SVal StrVal = state->getSVal(Init);
1715 assert(StrVal.isValid() && "Initializer string is unknown or undefined");
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001716 DefinedOrUnknownSVal strLength
1717 = cast<DefinedOrUnknownSVal>(getCStringLength(C, state, Init, StrVal));
Jordy Rosea5261542010-08-14 21:02:52 +00001718
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001719 state = state->set<CStringLength>(MR, strLength);
Jordy Rosea5261542010-08-14 21:02:52 +00001720 }
1721
1722 C.addTransition(state);
1723}
1724
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +00001725bool CStringChecker::wantsRegionChangeUpdate(const GRState *state) const {
Jordy Rosea5261542010-08-14 21:02:52 +00001726 CStringLength::EntryMap Entries = state->get<CStringLength>();
1727 return !Entries.isEmpty();
1728}
1729
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +00001730const GRState *
1731CStringChecker::checkRegionChanges(const GRState *state,
Ted Kremenek35bdbf42011-05-02 19:42:42 +00001732 const StoreManager::InvalidatedSymbols *,
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +00001733 const MemRegion * const *Begin,
1734 const MemRegion * const *End) const {
Jordy Rosea5261542010-08-14 21:02:52 +00001735 CStringLength::EntryMap Entries = state->get<CStringLength>();
1736 if (Entries.isEmpty())
1737 return state;
1738
1739 llvm::SmallPtrSet<const MemRegion *, 8> Invalidated;
1740 llvm::SmallPtrSet<const MemRegion *, 32> SuperRegions;
1741
1742 // First build sets for the changed regions and their super-regions.
1743 for ( ; Begin != End; ++Begin) {
1744 const MemRegion *MR = *Begin;
1745 Invalidated.insert(MR);
1746
1747 SuperRegions.insert(MR);
1748 while (const SubRegion *SR = dyn_cast<SubRegion>(MR)) {
1749 MR = SR->getSuperRegion();
1750 SuperRegions.insert(MR);
1751 }
1752 }
1753
1754 CStringLength::EntryMap::Factory &F = state->get_context<CStringLength>();
1755
1756 // Then loop over the entries in the current state.
1757 for (CStringLength::EntryMap::iterator I = Entries.begin(),
1758 E = Entries.end(); I != E; ++I) {
1759 const MemRegion *MR = I.getKey();
1760
1761 // Is this entry for a super-region of a changed region?
1762 if (SuperRegions.count(MR)) {
Ted Kremenek3baf6722010-11-24 00:54:37 +00001763 Entries = F.remove(Entries, MR);
Jordy Rosea5261542010-08-14 21:02:52 +00001764 continue;
1765 }
1766
1767 // Is this entry for a sub-region of a changed region?
1768 const MemRegion *Super = MR;
1769 while (const SubRegion *SR = dyn_cast<SubRegion>(Super)) {
1770 Super = SR->getSuperRegion();
1771 if (Invalidated.count(Super)) {
Ted Kremenek3baf6722010-11-24 00:54:37 +00001772 Entries = F.remove(Entries, MR);
Jordy Rosea5261542010-08-14 21:02:52 +00001773 break;
1774 }
1775 }
1776 }
1777
1778 return state->set<CStringLength>(Entries);
1779}
1780
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +00001781void CStringChecker::checkLiveSymbols(const GRState *state,
1782 SymbolReaper &SR) const {
Jordy Rosea5261542010-08-14 21:02:52 +00001783 // Mark all symbols in our string length map as valid.
1784 CStringLength::EntryMap Entries = state->get<CStringLength>();
1785
1786 for (CStringLength::EntryMap::iterator I = Entries.begin(), E = Entries.end();
1787 I != E; ++I) {
1788 SVal Len = I.getData();
Jordy Rosed5af0e12011-06-15 05:52:56 +00001789
1790 for (SVal::symbol_iterator si = Len.symbol_begin(), se = Len.symbol_end();
1791 si != se; ++si)
1792 SR.markInUse(*si);
Jordy Rosea5261542010-08-14 21:02:52 +00001793 }
1794}
1795
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +00001796void CStringChecker::checkDeadSymbols(SymbolReaper &SR,
1797 CheckerContext &C) const {
Jordy Rosea5261542010-08-14 21:02:52 +00001798 if (!SR.hasDeadSymbols())
1799 return;
1800
1801 const GRState *state = C.getState();
1802 CStringLength::EntryMap Entries = state->get<CStringLength>();
1803 if (Entries.isEmpty())
1804 return;
1805
1806 CStringLength::EntryMap::Factory &F = state->get_context<CStringLength>();
1807 for (CStringLength::EntryMap::iterator I = Entries.begin(), E = Entries.end();
1808 I != E; ++I) {
1809 SVal Len = I.getData();
1810 if (SymbolRef Sym = Len.getAsSymbol()) {
1811 if (SR.isDead(Sym))
Ted Kremenek3baf6722010-11-24 00:54:37 +00001812 Entries = F.remove(Entries, I.getKey());
Jordy Rosea5261542010-08-14 21:02:52 +00001813 }
1814 }
1815
1816 state = state->set<CStringLength>(Entries);
Ted Kremenekd048c6e2010-12-20 21:19:09 +00001817 C.generateNode(state);
Jordy Rosea5261542010-08-14 21:02:52 +00001818}
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +00001819
1820void ento::registerCStringChecker(CheckerManager &mgr) {
1821 mgr.registerChecker<CStringChecker>();
1822}