blob: bd1a56a1aa05811f3f999e8f11ab19d8b2418376 [file] [log] [blame]
Anna Zaksc800f682011-10-11 16:49:54 +00001//= CStringChecker.cpp - Checks calls to C string functions --------*- C++ -*-//
Jordy Roseccbf7ee2010-07-06 23:11:01 +00002//
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"
Anna Zaksf0dfc9c2012-02-17 22:35:31 +000016#include "InterCheckerAPI.h"
Argyrios Kyrtzidisec8605f2011-03-01 01:16:21 +000017#include "clang/StaticAnalyzer/Core/Checker.h"
Argyrios Kyrtzidis695fb502011-02-17 21:39:17 +000018#include "clang/StaticAnalyzer/Core/CheckerManager.h"
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +000019#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
Ted Kremenek9b663712011-02-10 01:03:03 +000020#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
Ted Kremenek18c66fd2011-08-15 22:09:50 +000021#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
Benjamin Kramer8fe83e12012-02-04 13:45:25 +000022#include "llvm/ADT/SmallString.h"
Benjamin Kramer00bd44d2012-02-04 12:31:12 +000023#include "llvm/ADT/STLExtras.h"
Jordy Roseccbf7ee2010-07-06 23:11:01 +000024#include "llvm/ADT/StringSwitch.h"
25
26using namespace clang;
Ted Kremenek9ef65372010-12-23 07:20:52 +000027using namespace ento;
Jordy Roseccbf7ee2010-07-06 23:11:01 +000028
29namespace {
Argyrios Kyrtzidisec8605f2011-03-01 01:16:21 +000030class CStringChecker : public Checker< eval::Call,
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +000031 check::PreStmt<DeclStmt>,
32 check::LiveSymbols,
33 check::DeadSymbols,
34 check::RegionChanges
35 > {
Anna Zaks57300762012-02-07 00:56:14 +000036 mutable OwningPtr<BugType> BT_Null,
37 BT_Bounds,
38 BT_Overlap,
39 BT_NotCString,
40 BT_AdditionOverflow;
41
Jordy Rose9e49d9f2011-06-20 02:06:40 +000042 mutable const char *CurrentFunctionDescription;
43
Jordy Roseccbf7ee2010-07-06 23:11:01 +000044public:
Anna Zaks57300762012-02-07 00:56:14 +000045 /// The filter is used to filter out the diagnostics which are not enabled by
46 /// the user.
47 struct CStringChecksFilter {
48 DefaultBool CheckCStringNullArg;
49 DefaultBool CheckCStringOutOfBounds;
50 DefaultBool CheckCStringBufferOverlap;
51 DefaultBool CheckCStringNotNullTerm;
52 };
53
54 CStringChecksFilter Filter;
55
Jordy Roseccbf7ee2010-07-06 23:11:01 +000056 static void *getTag() { static int tag; return &tag; }
57
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +000058 bool evalCall(const CallExpr *CE, CheckerContext &C) const;
59 void checkPreStmt(const DeclStmt *DS, CheckerContext &C) const;
Ted Kremenek8bef8232012-01-26 21:29:00 +000060 void checkLiveSymbols(ProgramStateRef state, SymbolReaper &SR) const;
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +000061 void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
Ted Kremenek8bef8232012-01-26 21:29:00 +000062 bool wantsRegionChangeUpdate(ProgramStateRef state) const;
Jordy Rosea5261542010-08-14 21:02:52 +000063
Ted Kremenek8bef8232012-01-26 21:29:00 +000064 ProgramStateRef
65 checkRegionChanges(ProgramStateRef state,
Ted Kremenek18c66fd2011-08-15 22:09:50 +000066 const StoreManager::InvalidatedSymbols *,
Jordy Rose537716a2011-08-27 22:51:26 +000067 ArrayRef<const MemRegion *> ExplicitRegions,
Anna Zaks66c40402012-02-14 21:55:24 +000068 ArrayRef<const MemRegion *> Regions,
69 const CallOrObjCMessage *Call) const;
Jordy Roseccbf7ee2010-07-06 23:11:01 +000070
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +000071 typedef void (CStringChecker::*FnCheck)(CheckerContext &,
72 const CallExpr *) const;
Jordy Roseccbf7ee2010-07-06 23:11:01 +000073
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +000074 void evalMemcpy(CheckerContext &C, const CallExpr *CE) const;
Lenny Maioranib8b875b2011-03-31 21:36:53 +000075 void evalMempcpy(CheckerContext &C, const CallExpr *CE) const;
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +000076 void evalMemmove(CheckerContext &C, const CallExpr *CE) const;
77 void evalBcopy(CheckerContext &C, const CallExpr *CE) const;
Lenny Maioranib8b875b2011-03-31 21:36:53 +000078 void evalCopyCommon(CheckerContext &C, const CallExpr *CE,
Ted Kremenek8bef8232012-01-26 21:29:00 +000079 ProgramStateRef state,
Ted Kremenek18c66fd2011-08-15 22:09:50 +000080 const Expr *Size,
81 const Expr *Source,
82 const Expr *Dest,
Lenny Maioranib8b875b2011-03-31 21:36:53 +000083 bool Restricted = false,
84 bool IsMempcpy = false) const;
Jordy Rosed325ffb2010-07-08 23:57:29 +000085
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +000086 void evalMemcmp(CheckerContext &C, const CallExpr *CE) const;
Jordy Roseccbf7ee2010-07-06 23:11:01 +000087
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +000088 void evalstrLength(CheckerContext &C, const CallExpr *CE) const;
89 void evalstrnLength(CheckerContext &C, const CallExpr *CE) const;
Ted Kremenek18c66fd2011-08-15 22:09:50 +000090 void evalstrLengthCommon(CheckerContext &C,
91 const CallExpr *CE,
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +000092 bool IsStrnlen = false) const;
Jordy Rose19c5dd12010-07-27 01:37:31 +000093
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +000094 void evalStrcpy(CheckerContext &C, const CallExpr *CE) const;
95 void evalStrncpy(CheckerContext &C, const CallExpr *CE) const;
96 void evalStpcpy(CheckerContext &C, const CallExpr *CE) const;
Ted Kremenek18c66fd2011-08-15 22:09:50 +000097 void evalStrcpyCommon(CheckerContext &C,
98 const CallExpr *CE,
99 bool returnEnd,
100 bool isBounded,
101 bool isAppending) const;
Lenny Maiorani067bbd02011-04-09 15:12:58 +0000102
103 void evalStrcat(CheckerContext &C, const CallExpr *CE) const;
104 void evalStrncat(CheckerContext &C, const CallExpr *CE) const;
Jordy Rosee64f3112010-08-16 07:51:42 +0000105
Lenny Maiorani318dd922011-04-12 17:08:43 +0000106 void evalStrcmp(CheckerContext &C, const CallExpr *CE) const;
Lenny Maiorani357f6ee2011-04-25 22:21:00 +0000107 void evalStrncmp(CheckerContext &C, const CallExpr *CE) const;
Lenny Maioranibd1d16a2011-04-28 15:09:11 +0000108 void evalStrcasecmp(CheckerContext &C, const CallExpr *CE) const;
Lenny Maiorani454fd2d2011-05-02 19:05:49 +0000109 void evalStrncasecmp(CheckerContext &C, const CallExpr *CE) const;
Ted Kremenek18c66fd2011-08-15 22:09:50 +0000110 void evalStrcmpCommon(CheckerContext &C,
111 const CallExpr *CE,
112 bool isBounded = false,
113 bool ignoreCase = false) const;
Lenny Maiorani318dd922011-04-12 17:08:43 +0000114
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000115 // Utility methods
Ted Kremenek8bef8232012-01-26 21:29:00 +0000116 std::pair<ProgramStateRef , ProgramStateRef >
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +0000117 static assumeZero(CheckerContext &C,
Ted Kremenek8bef8232012-01-26 21:29:00 +0000118 ProgramStateRef state, SVal V, QualType Ty);
Jordy Rosed325ffb2010-07-08 23:57:29 +0000119
Ted Kremenek8bef8232012-01-26 21:29:00 +0000120 static ProgramStateRef setCStringLength(ProgramStateRef state,
Ted Kremenek18c66fd2011-08-15 22:09:50 +0000121 const MemRegion *MR,
122 SVal strLength);
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +0000123 static SVal getCStringLengthForRegion(CheckerContext &C,
Ted Kremenek8bef8232012-01-26 21:29:00 +0000124 ProgramStateRef &state,
Ted Kremenek18c66fd2011-08-15 22:09:50 +0000125 const Expr *Ex,
126 const MemRegion *MR,
Jordy Rosed5af0e12011-06-15 05:52:56 +0000127 bool hypothetical);
Ted Kremenek18c66fd2011-08-15 22:09:50 +0000128 SVal getCStringLength(CheckerContext &C,
Ted Kremenek8bef8232012-01-26 21:29:00 +0000129 ProgramStateRef &state,
Ted Kremenek18c66fd2011-08-15 22:09:50 +0000130 const Expr *Ex,
131 SVal Buf,
Jordy Rosed5af0e12011-06-15 05:52:56 +0000132 bool hypothetical = false) const;
Jordy Rose19c5dd12010-07-27 01:37:31 +0000133
Lenny Maiorani318dd922011-04-12 17:08:43 +0000134 const StringLiteral *getCStringLiteral(CheckerContext &C,
Ted Kremenek8bef8232012-01-26 21:29:00 +0000135 ProgramStateRef &state,
Lenny Maiorani318dd922011-04-12 17:08:43 +0000136 const Expr *expr,
137 SVal val) const;
138
Ted Kremenek8bef8232012-01-26 21:29:00 +0000139 static ProgramStateRef InvalidateBuffer(CheckerContext &C,
140 ProgramStateRef state,
Ted Kremenek18c66fd2011-08-15 22:09:50 +0000141 const Expr *Ex, SVal V);
Jordy Rosee64f3112010-08-16 07:51:42 +0000142
Ted Kremenek9c378f72011-08-12 23:37:29 +0000143 static bool SummarizeRegion(raw_ostream &os, ASTContext &Ctx,
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +0000144 const MemRegion *MR);
Jordy Rose19c5dd12010-07-27 01:37:31 +0000145
146 // Re-usable checks
Ted Kremenek8bef8232012-01-26 21:29:00 +0000147 ProgramStateRef checkNonNull(CheckerContext &C,
148 ProgramStateRef state,
Ted Kremenek18c66fd2011-08-15 22:09:50 +0000149 const Expr *S,
150 SVal l) const;
Ted Kremenek8bef8232012-01-26 21:29:00 +0000151 ProgramStateRef CheckLocation(CheckerContext &C,
152 ProgramStateRef state,
Ted Kremenek18c66fd2011-08-15 22:09:50 +0000153 const Expr *S,
154 SVal l,
155 const char *message = NULL) const;
Ted Kremenek8bef8232012-01-26 21:29:00 +0000156 ProgramStateRef CheckBufferAccess(CheckerContext &C,
157 ProgramStateRef state,
Ted Kremenek18c66fd2011-08-15 22:09:50 +0000158 const Expr *Size,
159 const Expr *FirstBuf,
160 const Expr *SecondBuf,
161 const char *firstMessage = NULL,
162 const char *secondMessage = NULL,
163 bool WarnAboutSize = false) const;
164
Ted Kremenek8bef8232012-01-26 21:29:00 +0000165 ProgramStateRef CheckBufferAccess(CheckerContext &C,
166 ProgramStateRef state,
Ted Kremenek18c66fd2011-08-15 22:09:50 +0000167 const Expr *Size,
168 const Expr *Buf,
169 const char *message = NULL,
170 bool WarnAboutSize = false) const {
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000171 // This is a convenience override.
Jordy Rose5e5f1502011-06-20 03:49:16 +0000172 return CheckBufferAccess(C, state, Size, Buf, NULL, message, NULL,
173 WarnAboutSize);
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000174 }
Ted Kremenek8bef8232012-01-26 21:29:00 +0000175 ProgramStateRef CheckOverlap(CheckerContext &C,
176 ProgramStateRef state,
Ted Kremenek18c66fd2011-08-15 22:09:50 +0000177 const Expr *Size,
178 const Expr *First,
179 const Expr *Second) const;
180 void emitOverlapBug(CheckerContext &C,
Ted Kremenek8bef8232012-01-26 21:29:00 +0000181 ProgramStateRef state,
Ted Kremenek18c66fd2011-08-15 22:09:50 +0000182 const Stmt *First,
183 const Stmt *Second) const;
184
Ted Kremenek8bef8232012-01-26 21:29:00 +0000185 ProgramStateRef checkAdditionOverflow(CheckerContext &C,
186 ProgramStateRef state,
Ted Kremenek18c66fd2011-08-15 22:09:50 +0000187 NonLoc left,
188 NonLoc right) const;
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000189};
Jordy Rosea5261542010-08-14 21:02:52 +0000190
191class CStringLength {
192public:
193 typedef llvm::ImmutableMap<const MemRegion *, SVal> EntryMap;
194};
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000195} //end anonymous namespace
196
Jordy Rosea5261542010-08-14 21:02:52 +0000197namespace clang {
Ted Kremenek9ef65372010-12-23 07:20:52 +0000198namespace ento {
Jordy Rosea5261542010-08-14 21:02:52 +0000199 template <>
Ted Kremenek18c66fd2011-08-15 22:09:50 +0000200 struct ProgramStateTrait<CStringLength>
201 : public ProgramStatePartialTrait<CStringLength::EntryMap> {
Jordy Rosea5261542010-08-14 21:02:52 +0000202 static void *GDMIndex() { return CStringChecker::getTag(); }
203 };
204}
Argyrios Kyrtzidis5a4f98f2010-12-22 18:53:20 +0000205}
Jordy Rosea5261542010-08-14 21:02:52 +0000206
Jordy Rosed325ffb2010-07-08 23:57:29 +0000207//===----------------------------------------------------------------------===//
208// Individual checks and utility methods.
209//===----------------------------------------------------------------------===//
210
Ted Kremenek8bef8232012-01-26 21:29:00 +0000211std::pair<ProgramStateRef , ProgramStateRef >
212CStringChecker::assumeZero(CheckerContext &C, ProgramStateRef state, SVal V,
Jordy Rosed325ffb2010-07-08 23:57:29 +0000213 QualType Ty) {
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000214 DefinedSVal *val = dyn_cast<DefinedSVal>(&V);
215 if (!val)
Ted Kremenek8bef8232012-01-26 21:29:00 +0000216 return std::pair<ProgramStateRef , ProgramStateRef >(state, state);
Jordy Rosea6b808c2010-07-07 07:48:06 +0000217
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000218 SValBuilder &svalBuilder = C.getSValBuilder();
219 DefinedOrUnknownSVal zero = svalBuilder.makeZeroVal(Ty);
220 return state->assume(svalBuilder.evalEQ(state, *val, zero));
Jordy Rosed325ffb2010-07-08 23:57:29 +0000221}
Jordy Rosea6b808c2010-07-07 07:48:06 +0000222
Ted Kremenek8bef8232012-01-26 21:29:00 +0000223ProgramStateRef CStringChecker::checkNonNull(CheckerContext &C,
224 ProgramStateRef state,
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +0000225 const Expr *S, SVal l) const {
Jordy Rosed325ffb2010-07-08 23:57:29 +0000226 // If a previous check has failed, propagate the failure.
227 if (!state)
228 return NULL;
229
Ted Kremenek8bef8232012-01-26 21:29:00 +0000230 ProgramStateRef stateNull, stateNonNull;
Ted Kremenek28f47b92010-12-01 22:16:56 +0000231 llvm::tie(stateNull, stateNonNull) = assumeZero(C, state, l, S->getType());
Jordy Rosed325ffb2010-07-08 23:57:29 +0000232
233 if (stateNull && !stateNonNull) {
Anna Zaks57300762012-02-07 00:56:14 +0000234 if (!Filter.CheckCStringNullArg)
235 return NULL;
236
Ted Kremenekd048c6e2010-12-20 21:19:09 +0000237 ExplodedNode *N = C.generateSink(stateNull);
Jordy Rosea6b808c2010-07-07 07:48:06 +0000238 if (!N)
239 return NULL;
240
Jordy Rosed325ffb2010-07-08 23:57:29 +0000241 if (!BT_Null)
Anna Zaks57300762012-02-07 00:56:14 +0000242 BT_Null.reset(new BuiltinBug("Unix API",
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +0000243 "Null pointer argument in call to byte string function"));
Jordy Rosea6b808c2010-07-07 07:48:06 +0000244
Dylan Noblesmithf7ccbad2012-02-05 02:13:05 +0000245 SmallString<80> buf;
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000246 llvm::raw_svector_ostream os(buf);
247 assert(CurrentFunctionDescription);
248 os << "Null pointer argument in call to " << CurrentFunctionDescription;
249
Jordy Rosea6b808c2010-07-07 07:48:06 +0000250 // Generate a report for this bug.
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +0000251 BuiltinBug *BT = static_cast<BuiltinBug*>(BT_Null.get());
Anna Zakse172e8b2011-08-17 23:00:25 +0000252 BugReport *report = new BugReport(*BT, os.str(), N);
Jordy Rosea6b808c2010-07-07 07:48:06 +0000253
254 report->addRange(S->getSourceRange());
Ted Kremenek76aadc32012-03-09 01:13:14 +0000255 report->addVisitor(bugreporter::getTrackNullOrUndefValueVisitor(N, S,
256 report));
Jordy Rosea6b808c2010-07-07 07:48:06 +0000257 C.EmitReport(report);
258 return NULL;
259 }
260
261 // From here on, assume that the value is non-null.
Jordy Rosed325ffb2010-07-08 23:57:29 +0000262 assert(stateNonNull);
263 return stateNonNull;
Jordy Rosea6b808c2010-07-07 07:48:06 +0000264}
265
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000266// FIXME: This was originally copied from ArrayBoundChecker.cpp. Refactor?
Ted Kremenek8bef8232012-01-26 21:29:00 +0000267ProgramStateRef CStringChecker::CheckLocation(CheckerContext &C,
268 ProgramStateRef state,
Jordy Rosee64f3112010-08-16 07:51:42 +0000269 const Expr *S, SVal l,
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000270 const char *warningMsg) const {
Jordy Rosed325ffb2010-07-08 23:57:29 +0000271 // If a previous check has failed, propagate the failure.
272 if (!state)
273 return NULL;
274
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000275 // Check for out of bound array element access.
276 const MemRegion *R = l.getAsRegion();
277 if (!R)
278 return state;
279
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000280 const ElementRegion *ER = dyn_cast<ElementRegion>(R);
281 if (!ER)
282 return state;
283
Zhongxing Xu018220c2010-08-11 06:10:55 +0000284 assert(ER->getValueType() == C.getASTContext().CharTy &&
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000285 "CheckLocation should only be called with char* ElementRegions");
286
287 // Get the size of the array.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000288 const SubRegion *superReg = cast<SubRegion>(ER->getSuperRegion());
289 SValBuilder &svalBuilder = C.getSValBuilder();
Jordy Rose1e022412011-06-16 05:51:02 +0000290 SVal Extent =
291 svalBuilder.convertToArrayIndex(superReg->getExtent(svalBuilder));
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000292 DefinedOrUnknownSVal Size = cast<DefinedOrUnknownSVal>(Extent);
293
294 // Get the index of the accessed element.
Gabor Greif89b06582010-09-09 10:51:37 +0000295 DefinedOrUnknownSVal Idx = cast<DefinedOrUnknownSVal>(ER->getIndex());
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000296
Ted Kremenek8bef8232012-01-26 21:29:00 +0000297 ProgramStateRef StInBound = state->assumeInBound(Idx, Size, true);
298 ProgramStateRef StOutBound = state->assumeInBound(Idx, Size, false);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000299 if (StOutBound && !StInBound) {
Ted Kremenekd048c6e2010-12-20 21:19:09 +0000300 ExplodedNode *N = C.generateSink(StOutBound);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000301 if (!N)
302 return NULL;
303
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000304 if (!BT_Bounds) {
305 BT_Bounds.reset(new BuiltinBug("Out-of-bound array access",
306 "Byte string function accesses out-of-bound array element"));
307 }
308 BuiltinBug *BT = static_cast<BuiltinBug*>(BT_Bounds.get());
309
310 // Generate a report for this bug.
Anna Zakse172e8b2011-08-17 23:00:25 +0000311 BugReport *report;
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000312 if (warningMsg) {
Anna Zakse172e8b2011-08-17 23:00:25 +0000313 report = new BugReport(*BT, warningMsg, N);
Jordy Rosee64f3112010-08-16 07:51:42 +0000314 } else {
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000315 assert(CurrentFunctionDescription);
316 assert(CurrentFunctionDescription[0] != '\0');
317
Dylan Noblesmithf7ccbad2012-02-05 02:13:05 +0000318 SmallString<80> buf;
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000319 llvm::raw_svector_ostream os(buf);
320 os << (char)toupper(CurrentFunctionDescription[0])
321 << &CurrentFunctionDescription[1]
322 << " accesses out-of-bound array element";
Anna Zakse172e8b2011-08-17 23:00:25 +0000323 report = new BugReport(*BT, os.str(), N);
Jordy Rosee64f3112010-08-16 07:51:42 +0000324 }
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000325
326 // FIXME: It would be nice to eventually make this diagnostic more clear,
327 // e.g., by referencing the original declaration or by saying *why* this
328 // reference is outside the range.
329
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000330 report->addRange(S->getSourceRange());
331 C.EmitReport(report);
332 return NULL;
333 }
334
335 // Array bound check succeeded. From this point forward the array bound
336 // should always succeed.
337 return StInBound;
338}
339
Ted Kremenek8bef8232012-01-26 21:29:00 +0000340ProgramStateRef CStringChecker::CheckBufferAccess(CheckerContext &C,
341 ProgramStateRef state,
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000342 const Expr *Size,
343 const Expr *FirstBuf,
Jordy Rosee64f3112010-08-16 07:51:42 +0000344 const Expr *SecondBuf,
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000345 const char *firstMessage,
Jordy Rose5e5f1502011-06-20 03:49:16 +0000346 const char *secondMessage,
347 bool WarnAboutSize) const {
Jordy Rosed325ffb2010-07-08 23:57:29 +0000348 // If a previous check has failed, propagate the failure.
349 if (!state)
350 return NULL;
351
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000352 SValBuilder &svalBuilder = C.getSValBuilder();
Jordy Rose1e022412011-06-16 05:51:02 +0000353 ASTContext &Ctx = svalBuilder.getContext();
Ted Kremenek5eca4822012-01-06 22:09:28 +0000354 const LocationContext *LCtx = C.getLocationContext();
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000355
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000356 QualType sizeTy = Size->getType();
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000357 QualType PtrTy = Ctx.getPointerType(Ctx.CharTy);
358
Jordy Rosea6b808c2010-07-07 07:48:06 +0000359 // Check that the first buffer is non-null.
Ted Kremenek5eca4822012-01-06 22:09:28 +0000360 SVal BufVal = state->getSVal(FirstBuf, LCtx);
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000361 state = checkNonNull(C, state, FirstBuf, BufVal);
Jordy Rosea6b808c2010-07-07 07:48:06 +0000362 if (!state)
363 return NULL;
364
Anna Zaks57300762012-02-07 00:56:14 +0000365 // If out-of-bounds checking is turned off, skip the rest.
366 if (!Filter.CheckCStringOutOfBounds)
367 return state;
368
Jordy Rosed325ffb2010-07-08 23:57:29 +0000369 // Get the access length and make sure it is known.
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000370 // FIXME: This assumes the caller has already checked that the access length
371 // is positive. And that it's unsigned.
Ted Kremenek5eca4822012-01-06 22:09:28 +0000372 SVal LengthVal = state->getSVal(Size, LCtx);
Jordy Rosed325ffb2010-07-08 23:57:29 +0000373 NonLoc *Length = dyn_cast<NonLoc>(&LengthVal);
374 if (!Length)
375 return state;
376
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000377 // Compute the offset of the last element to be accessed: size-1.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000378 NonLoc One = cast<NonLoc>(svalBuilder.makeIntVal(1, sizeTy));
379 NonLoc LastOffset = cast<NonLoc>(svalBuilder.evalBinOpNN(state, BO_Sub,
380 *Length, One, sizeTy));
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000381
Chris Lattnerfc8f0e12011-04-15 05:22:18 +0000382 // Check that the first buffer is sufficiently long.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000383 SVal BufStart = svalBuilder.evalCast(BufVal, PtrTy, FirstBuf->getType());
Jordy Roseb6a40262010-08-05 23:11:30 +0000384 if (Loc *BufLoc = dyn_cast<Loc>(&BufStart)) {
Jordy Rose5e5f1502011-06-20 03:49:16 +0000385 const Expr *warningExpr = (WarnAboutSize ? Size : FirstBuf);
386
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000387 SVal BufEnd = svalBuilder.evalBinOpLN(state, BO_Add, *BufLoc,
388 LastOffset, PtrTy);
Jordy Rose5e5f1502011-06-20 03:49:16 +0000389 state = CheckLocation(C, state, warningExpr, BufEnd, firstMessage);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000390
Jordy Roseb6a40262010-08-05 23:11:30 +0000391 // If the buffer isn't large enough, abort.
392 if (!state)
393 return NULL;
394 }
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000395
396 // If there's a second buffer, check it as well.
397 if (SecondBuf) {
Ted Kremenek5eca4822012-01-06 22:09:28 +0000398 BufVal = state->getSVal(SecondBuf, LCtx);
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000399 state = checkNonNull(C, state, SecondBuf, BufVal);
Jordy Rosea6b808c2010-07-07 07:48:06 +0000400 if (!state)
401 return NULL;
402
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000403 BufStart = svalBuilder.evalCast(BufVal, PtrTy, SecondBuf->getType());
Jordy Roseb6a40262010-08-05 23:11:30 +0000404 if (Loc *BufLoc = dyn_cast<Loc>(&BufStart)) {
Jordy Rose5e5f1502011-06-20 03:49:16 +0000405 const Expr *warningExpr = (WarnAboutSize ? Size : SecondBuf);
406
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000407 SVal BufEnd = svalBuilder.evalBinOpLN(state, BO_Add, *BufLoc,
408 LastOffset, PtrTy);
Jordy Rose5e5f1502011-06-20 03:49:16 +0000409 state = CheckLocation(C, state, warningExpr, BufEnd, secondMessage);
Jordy Roseb6a40262010-08-05 23:11:30 +0000410 }
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000411 }
412
413 // Large enough or not, return this state!
414 return state;
415}
416
Ted Kremenek8bef8232012-01-26 21:29:00 +0000417ProgramStateRef CStringChecker::CheckOverlap(CheckerContext &C,
418 ProgramStateRef state,
Jordy Rosed325ffb2010-07-08 23:57:29 +0000419 const Expr *Size,
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000420 const Expr *First,
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +0000421 const Expr *Second) const {
Anna Zaks57300762012-02-07 00:56:14 +0000422 if (!Filter.CheckCStringBufferOverlap)
423 return state;
424
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000425 // Do a simple check for overlap: if the two arguments are from the same
426 // buffer, see if the end of the first is greater than the start of the second
427 // or vice versa.
428
Jordy Rosed325ffb2010-07-08 23:57:29 +0000429 // If a previous check has failed, propagate the failure.
430 if (!state)
431 return NULL;
432
Ted Kremenek8bef8232012-01-26 21:29:00 +0000433 ProgramStateRef stateTrue, stateFalse;
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000434
435 // Get the buffer values and make sure they're known locations.
Ted Kremenek5eca4822012-01-06 22:09:28 +0000436 const LocationContext *LCtx = C.getLocationContext();
437 SVal firstVal = state->getSVal(First, LCtx);
438 SVal secondVal = state->getSVal(Second, LCtx);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000439
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000440 Loc *firstLoc = dyn_cast<Loc>(&firstVal);
441 if (!firstLoc)
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000442 return state;
443
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000444 Loc *secondLoc = dyn_cast<Loc>(&secondVal);
445 if (!secondLoc)
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000446 return state;
447
448 // Are the two values the same?
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000449 SValBuilder &svalBuilder = C.getSValBuilder();
450 llvm::tie(stateTrue, stateFalse) =
451 state->assume(svalBuilder.evalEQ(state, *firstLoc, *secondLoc));
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000452
453 if (stateTrue && !stateFalse) {
454 // If the values are known to be equal, that's automatically an overlap.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000455 emitOverlapBug(C, stateTrue, First, Second);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000456 return NULL;
457 }
458
Ted Kremenek28f47b92010-12-01 22:16:56 +0000459 // assume the two expressions are not equal.
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000460 assert(stateFalse);
461 state = stateFalse;
462
463 // Which value comes first?
Jordy Roseee2fde12011-06-16 05:56:50 +0000464 QualType cmpTy = svalBuilder.getConditionType();
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000465 SVal reverse = svalBuilder.evalBinOpLL(state, BO_GT,
466 *firstLoc, *secondLoc, cmpTy);
467 DefinedOrUnknownSVal *reverseTest = dyn_cast<DefinedOrUnknownSVal>(&reverse);
468 if (!reverseTest)
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000469 return state;
470
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000471 llvm::tie(stateTrue, stateFalse) = state->assume(*reverseTest);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000472 if (stateTrue) {
473 if (stateFalse) {
474 // If we don't know which one comes first, we can't perform this test.
475 return state;
476 } else {
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000477 // Switch the values so that firstVal is before secondVal.
478 Loc *tmpLoc = firstLoc;
479 firstLoc = secondLoc;
480 secondLoc = tmpLoc;
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000481
482 // Switch the Exprs as well, so that they still correspond.
483 const Expr *tmpExpr = First;
484 First = Second;
485 Second = tmpExpr;
486 }
487 }
488
489 // Get the length, and make sure it too is known.
Ted Kremenek5eca4822012-01-06 22:09:28 +0000490 SVal LengthVal = state->getSVal(Size, LCtx);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000491 NonLoc *Length = dyn_cast<NonLoc>(&LengthVal);
492 if (!Length)
493 return state;
494
495 // Convert the first buffer's start address to char*.
496 // Bail out if the cast fails.
Jordy Roseee2fde12011-06-16 05:56:50 +0000497 ASTContext &Ctx = svalBuilder.getContext();
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000498 QualType CharPtrTy = Ctx.getPointerType(Ctx.CharTy);
Jordy Rose1e022412011-06-16 05:51:02 +0000499 SVal FirstStart = svalBuilder.evalCast(*firstLoc, CharPtrTy,
500 First->getType());
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000501 Loc *FirstStartLoc = dyn_cast<Loc>(&FirstStart);
502 if (!FirstStartLoc)
503 return state;
504
505 // Compute the end of the first buffer. Bail out if THAT fails.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000506 SVal FirstEnd = svalBuilder.evalBinOpLN(state, BO_Add,
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000507 *FirstStartLoc, *Length, CharPtrTy);
508 Loc *FirstEndLoc = dyn_cast<Loc>(&FirstEnd);
509 if (!FirstEndLoc)
510 return state;
511
512 // Is the end of the first buffer past the start of the second buffer?
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000513 SVal Overlap = svalBuilder.evalBinOpLL(state, BO_GT,
514 *FirstEndLoc, *secondLoc, cmpTy);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000515 DefinedOrUnknownSVal *OverlapTest = dyn_cast<DefinedOrUnknownSVal>(&Overlap);
516 if (!OverlapTest)
517 return state;
518
Ted Kremenek28f47b92010-12-01 22:16:56 +0000519 llvm::tie(stateTrue, stateFalse) = state->assume(*OverlapTest);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000520
521 if (stateTrue && !stateFalse) {
522 // Overlap!
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000523 emitOverlapBug(C, stateTrue, First, Second);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000524 return NULL;
525 }
526
Ted Kremenek28f47b92010-12-01 22:16:56 +0000527 // assume the two expressions don't overlap.
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000528 assert(stateFalse);
529 return stateFalse;
530}
531
Ted Kremenek8bef8232012-01-26 21:29:00 +0000532void CStringChecker::emitOverlapBug(CheckerContext &C, ProgramStateRef state,
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +0000533 const Stmt *First, const Stmt *Second) const {
Ted Kremenekd048c6e2010-12-20 21:19:09 +0000534 ExplodedNode *N = C.generateSink(state);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000535 if (!N)
536 return;
537
538 if (!BT_Overlap)
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +0000539 BT_Overlap.reset(new BugType("Unix API", "Improper arguments"));
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000540
541 // Generate a report for this bug.
Anna Zakse172e8b2011-08-17 23:00:25 +0000542 BugReport *report =
543 new BugReport(*BT_Overlap,
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000544 "Arguments must not be overlapping buffers", N);
545 report->addRange(First->getSourceRange());
546 report->addRange(Second->getSourceRange());
547
548 C.EmitReport(report);
549}
550
Ted Kremenek8bef8232012-01-26 21:29:00 +0000551ProgramStateRef CStringChecker::checkAdditionOverflow(CheckerContext &C,
552 ProgramStateRef state,
Jordy Rosed5af0e12011-06-15 05:52:56 +0000553 NonLoc left,
554 NonLoc right) const {
Anna Zaks57300762012-02-07 00:56:14 +0000555 // If out-of-bounds checking is turned off, skip the rest.
556 if (!Filter.CheckCStringOutOfBounds)
557 return state;
558
Jordy Rosed5af0e12011-06-15 05:52:56 +0000559 // If a previous check has failed, propagate the failure.
560 if (!state)
561 return NULL;
562
563 SValBuilder &svalBuilder = C.getSValBuilder();
564 BasicValueFactory &BVF = svalBuilder.getBasicValueFactory();
565
566 QualType sizeTy = svalBuilder.getContext().getSizeType();
567 const llvm::APSInt &maxValInt = BVF.getMaxValue(sizeTy);
568 NonLoc maxVal = svalBuilder.makeIntVal(maxValInt);
569
Anna Zakse3d250e2011-12-11 18:43:40 +0000570 SVal maxMinusRight;
571 if (isa<nonloc::ConcreteInt>(right)) {
572 maxMinusRight = svalBuilder.evalBinOpNN(state, BO_Sub, maxVal, right,
573 sizeTy);
574 } else {
Jordy Rosed5af0e12011-06-15 05:52:56 +0000575 // Try switching the operands. (The order of these two assignments is
576 // important!)
577 maxMinusRight = svalBuilder.evalBinOpNN(state, BO_Sub, maxVal, left,
578 sizeTy);
579 left = right;
580 }
581
582 if (NonLoc *maxMinusRightNL = dyn_cast<NonLoc>(&maxMinusRight)) {
583 QualType cmpTy = svalBuilder.getConditionType();
584 // If left > max - right, we have an overflow.
585 SVal willOverflow = svalBuilder.evalBinOpNN(state, BO_GT, left,
586 *maxMinusRightNL, cmpTy);
587
Ted Kremenek8bef8232012-01-26 21:29:00 +0000588 ProgramStateRef stateOverflow, stateOkay;
Jordy Rosed5af0e12011-06-15 05:52:56 +0000589 llvm::tie(stateOverflow, stateOkay) =
590 state->assume(cast<DefinedOrUnknownSVal>(willOverflow));
591
592 if (stateOverflow && !stateOkay) {
593 // We have an overflow. Emit a bug report.
594 ExplodedNode *N = C.generateSink(stateOverflow);
595 if (!N)
596 return NULL;
597
598 if (!BT_AdditionOverflow)
599 BT_AdditionOverflow.reset(new BuiltinBug("API",
600 "Sum of expressions causes overflow"));
601
Jordy Rosed5af0e12011-06-15 05:52:56 +0000602 // This isn't a great error message, but this should never occur in real
603 // code anyway -- you'd have to create a buffer longer than a size_t can
604 // represent, which is sort of a contradiction.
Jordy Rose8cc24912011-06-20 03:51:53 +0000605 const char *warning =
606 "This expression will create a string whose length is too big to "
607 "be represented as a size_t";
Jordy Rosed5af0e12011-06-15 05:52:56 +0000608
609 // Generate a report for this bug.
Jordy Rose8cc24912011-06-20 03:51:53 +0000610 BugReport *report = new BugReport(*BT_AdditionOverflow, warning, N);
Jordy Rosed5af0e12011-06-15 05:52:56 +0000611 C.EmitReport(report);
612
613 return NULL;
614 }
615
616 // From now on, assume an overflow didn't occur.
617 assert(stateOkay);
618 state = stateOkay;
619 }
620
621 return state;
622}
623
Ted Kremenek8bef8232012-01-26 21:29:00 +0000624ProgramStateRef CStringChecker::setCStringLength(ProgramStateRef state,
Jordy Rosee64f3112010-08-16 07:51:42 +0000625 const MemRegion *MR,
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000626 SVal strLength) {
627 assert(!strLength.isUndef() && "Attempt to set an undefined string length");
Jordy Rosee64f3112010-08-16 07:51:42 +0000628
629 MR = MR->StripCasts();
630
631 switch (MR->getKind()) {
632 case MemRegion::StringRegionKind:
633 // FIXME: This can happen if we strcpy() into a string region. This is
634 // undefined [C99 6.4.5p6], but we should still warn about it.
635 return state;
636
637 case MemRegion::SymbolicRegionKind:
638 case MemRegion::AllocaRegionKind:
639 case MemRegion::VarRegionKind:
640 case MemRegion::FieldRegionKind:
641 case MemRegion::ObjCIvarRegionKind:
Jordy Rose210c05b2011-06-15 05:14:03 +0000642 // These are the types we can currently track string lengths for.
643 break;
Jordy Rosee64f3112010-08-16 07:51:42 +0000644
645 case MemRegion::ElementRegionKind:
646 // FIXME: Handle element regions by upper-bounding the parent region's
647 // string length.
648 return state;
649
650 default:
651 // Other regions (mostly non-data) can't have a reliable C string length.
652 // For now, just ignore the change.
653 // FIXME: These are rare but not impossible. We should output some kind of
654 // warning for things like strcpy((char[]){'a', 0}, "b");
655 return state;
656 }
Jordy Rose210c05b2011-06-15 05:14:03 +0000657
658 if (strLength.isUnknown())
659 return state->remove<CStringLength>(MR);
660
661 return state->set<CStringLength>(MR, strLength);
Jordy Rosee64f3112010-08-16 07:51:42 +0000662}
663
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000664SVal CStringChecker::getCStringLengthForRegion(CheckerContext &C,
Ted Kremenek8bef8232012-01-26 21:29:00 +0000665 ProgramStateRef &state,
Jordy Rosea5261542010-08-14 21:02:52 +0000666 const Expr *Ex,
Jordy Rosed5af0e12011-06-15 05:52:56 +0000667 const MemRegion *MR,
668 bool hypothetical) {
669 if (!hypothetical) {
670 // If there's a recorded length, go ahead and return it.
671 const SVal *Recorded = state->get<CStringLength>(MR);
672 if (Recorded)
673 return *Recorded;
674 }
Jordy Rosea5261542010-08-14 21:02:52 +0000675
676 // Otherwise, get a new symbol and update the state.
Anna Zaks5d0ea6d2011-10-04 20:43:05 +0000677 unsigned Count = C.getCurrentBlockCount();
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000678 SValBuilder &svalBuilder = C.getSValBuilder();
679 QualType sizeTy = svalBuilder.getContext().getSizeType();
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +0000680 SVal strLength = svalBuilder.getMetadataSymbolVal(CStringChecker::getTag(),
681 MR, Ex, sizeTy, Count);
Jordy Rosed5af0e12011-06-15 05:52:56 +0000682
683 if (!hypothetical)
684 state = state->set<CStringLength>(MR, strLength);
685
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000686 return strLength;
Jordy Rosea5261542010-08-14 21:02:52 +0000687}
688
Ted Kremenek8bef8232012-01-26 21:29:00 +0000689SVal CStringChecker::getCStringLength(CheckerContext &C, ProgramStateRef &state,
Jordy Rosed5af0e12011-06-15 05:52:56 +0000690 const Expr *Ex, SVal Buf,
691 bool hypothetical) const {
Jordy Rose19c5dd12010-07-27 01:37:31 +0000692 const MemRegion *MR = Buf.getAsRegion();
693 if (!MR) {
694 // If we can't get a region, see if it's something we /know/ isn't a
695 // C string. In the context of locations, the only time we can issue such
696 // a warning is for labels.
697 if (loc::GotoLabel *Label = dyn_cast<loc::GotoLabel>(&Buf)) {
Anna Zaks57300762012-02-07 00:56:14 +0000698 if (!Filter.CheckCStringNotNullTerm)
699 return UndefinedVal();
700
Anna Zaks0bd6b112011-10-26 21:06:34 +0000701 if (ExplodedNode *N = C.addTransition(state)) {
Jordy Rose19c5dd12010-07-27 01:37:31 +0000702 if (!BT_NotCString)
Anna Zaks57300762012-02-07 00:56:14 +0000703 BT_NotCString.reset(new BuiltinBug("Unix API",
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +0000704 "Argument is not a null-terminated string."));
Jordy Rose19c5dd12010-07-27 01:37:31 +0000705
Dylan Noblesmithf7ccbad2012-02-05 02:13:05 +0000706 SmallString<120> buf;
Jordy Rose19c5dd12010-07-27 01:37:31 +0000707 llvm::raw_svector_ostream os(buf);
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000708 assert(CurrentFunctionDescription);
709 os << "Argument to " << CurrentFunctionDescription
710 << " is the address of the label '" << Label->getLabel()->getName()
Jordy Rose19c5dd12010-07-27 01:37:31 +0000711 << "', which is not a null-terminated string";
712
713 // Generate a report for this bug.
Anna Zakse172e8b2011-08-17 23:00:25 +0000714 BugReport *report = new BugReport(*BT_NotCString,
Jordy Rose19c5dd12010-07-27 01:37:31 +0000715 os.str(), N);
716
717 report->addRange(Ex->getSourceRange());
718 C.EmitReport(report);
719 }
Jordy Rose19c5dd12010-07-27 01:37:31 +0000720 return UndefinedVal();
Anna Zaks57300762012-02-07 00:56:14 +0000721
Jordy Rose19c5dd12010-07-27 01:37:31 +0000722 }
723
Jordy Rosea5261542010-08-14 21:02:52 +0000724 // If it's not a region and not a label, give up.
725 return UnknownVal();
Jordy Rose19c5dd12010-07-27 01:37:31 +0000726 }
727
Jordy Rosea5261542010-08-14 21:02:52 +0000728 // If we have a region, strip casts from it and see if we can figure out
729 // its length. For anything we can't figure out, just return UnknownVal.
730 MR = MR->StripCasts();
731
732 switch (MR->getKind()) {
733 case MemRegion::StringRegionKind: {
734 // Modifying the contents of string regions is undefined [C99 6.4.5p6],
735 // so we can assume that the byte length is the correct C string length.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000736 SValBuilder &svalBuilder = C.getSValBuilder();
737 QualType sizeTy = svalBuilder.getContext().getSizeType();
738 const StringLiteral *strLit = cast<StringRegion>(MR)->getStringLiteral();
739 return svalBuilder.makeIntVal(strLit->getByteLength(), sizeTy);
Jordy Rosea5261542010-08-14 21:02:52 +0000740 }
741 case MemRegion::SymbolicRegionKind:
742 case MemRegion::AllocaRegionKind:
743 case MemRegion::VarRegionKind:
744 case MemRegion::FieldRegionKind:
745 case MemRegion::ObjCIvarRegionKind:
Jordy Rosed5af0e12011-06-15 05:52:56 +0000746 return getCStringLengthForRegion(C, state, Ex, MR, hypothetical);
Jordy Rosea5261542010-08-14 21:02:52 +0000747 case MemRegion::CompoundLiteralRegionKind:
748 // FIXME: Can we track this? Is it necessary?
749 return UnknownVal();
750 case MemRegion::ElementRegionKind:
751 // FIXME: How can we handle this? It's not good enough to subtract the
752 // offset from the base string length; consider "123\x00567" and &a[5].
753 return UnknownVal();
754 default:
755 // Other regions (mostly non-data) can't have a reliable C string length.
756 // In this case, an error is emitted and UndefinedVal is returned.
757 // The caller should always be prepared to handle this case.
Anna Zaks57300762012-02-07 00:56:14 +0000758 if (!Filter.CheckCStringNotNullTerm)
759 return UndefinedVal();
760
Anna Zaks0bd6b112011-10-26 21:06:34 +0000761 if (ExplodedNode *N = C.addTransition(state)) {
Jordy Rosea5261542010-08-14 21:02:52 +0000762 if (!BT_NotCString)
Anna Zaks57300762012-02-07 00:56:14 +0000763 BT_NotCString.reset(new BuiltinBug("Unix API",
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +0000764 "Argument is not a null-terminated string."));
Jordy Rosea5261542010-08-14 21:02:52 +0000765
Dylan Noblesmithf7ccbad2012-02-05 02:13:05 +0000766 SmallString<120> buf;
Jordy Rosea5261542010-08-14 21:02:52 +0000767 llvm::raw_svector_ostream os(buf);
768
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000769 assert(CurrentFunctionDescription);
770 os << "Argument to " << CurrentFunctionDescription << " is ";
Jordy Rosea5261542010-08-14 21:02:52 +0000771
772 if (SummarizeRegion(os, C.getASTContext(), MR))
773 os << ", which is not a null-terminated string";
774 else
775 os << "not a null-terminated string";
776
777 // Generate a report for this bug.
Anna Zakse172e8b2011-08-17 23:00:25 +0000778 BugReport *report = new BugReport(*BT_NotCString,
Jordy Rosea5261542010-08-14 21:02:52 +0000779 os.str(), N);
780
781 report->addRange(Ex->getSourceRange());
782 C.EmitReport(report);
783 }
784
785 return UndefinedVal();
786 }
Jordy Rose19c5dd12010-07-27 01:37:31 +0000787}
788
Lenny Maiorani318dd922011-04-12 17:08:43 +0000789const StringLiteral *CStringChecker::getCStringLiteral(CheckerContext &C,
Ted Kremenek8bef8232012-01-26 21:29:00 +0000790 ProgramStateRef &state, const Expr *expr, SVal val) const {
Lenny Maiorani318dd922011-04-12 17:08:43 +0000791
792 // Get the memory region pointed to by the val.
793 const MemRegion *bufRegion = val.getAsRegion();
794 if (!bufRegion)
795 return NULL;
796
797 // Strip casts off the memory region.
798 bufRegion = bufRegion->StripCasts();
799
800 // Cast the memory region to a string region.
801 const StringRegion *strRegion= dyn_cast<StringRegion>(bufRegion);
802 if (!strRegion)
803 return NULL;
804
805 // Return the actual string in the string region.
806 return strRegion->getStringLiteral();
807}
808
Ted Kremenek8bef8232012-01-26 21:29:00 +0000809ProgramStateRef CStringChecker::InvalidateBuffer(CheckerContext &C,
810 ProgramStateRef state,
Jordy Rosee64f3112010-08-16 07:51:42 +0000811 const Expr *E, SVal V) {
812 Loc *L = dyn_cast<Loc>(&V);
813 if (!L)
814 return state;
815
816 // FIXME: This is a simplified version of what's in CFRefCount.cpp -- it makes
817 // some assumptions about the value that CFRefCount can't. Even so, it should
818 // probably be refactored.
819 if (loc::MemRegionVal* MR = dyn_cast<loc::MemRegionVal>(L)) {
820 const MemRegion *R = MR->getRegion()->StripCasts();
821
822 // Are we dealing with an ElementRegion? If so, we should be invalidating
823 // the super-region.
824 if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
825 R = ER->getSuperRegion();
826 // FIXME: What about layers of ElementRegions?
827 }
828
829 // Invalidate this region.
Anna Zaks5d0ea6d2011-10-04 20:43:05 +0000830 unsigned Count = C.getCurrentBlockCount();
Ted Kremenek3133f792012-02-17 23:13:45 +0000831 const LocationContext *LCtx = C.getPredecessor()->getLocationContext();
832 return state->invalidateRegions(R, E, Count, LCtx);
Jordy Rosee64f3112010-08-16 07:51:42 +0000833 }
834
835 // If we have a non-region value by chance, just remove the binding.
836 // FIXME: is this necessary or correct? This handles the non-Region
837 // cases. Is it ever valid to store to these?
838 return state->unbindLoc(*L);
839}
840
Ted Kremenek9c378f72011-08-12 23:37:29 +0000841bool CStringChecker::SummarizeRegion(raw_ostream &os, ASTContext &Ctx,
Jordy Rose19c5dd12010-07-27 01:37:31 +0000842 const MemRegion *MR) {
Ted Kremenek96979342011-08-12 20:02:48 +0000843 const TypedValueRegion *TVR = dyn_cast<TypedValueRegion>(MR);
Jordy Rose19c5dd12010-07-27 01:37:31 +0000844
Jordy Rose096aef92011-08-12 21:41:07 +0000845 switch (MR->getKind()) {
Jordy Rose19c5dd12010-07-27 01:37:31 +0000846 case MemRegion::FunctionTextRegionKind: {
Jordy Rose096aef92011-08-12 21:41:07 +0000847 const FunctionDecl *FD = cast<FunctionTextRegion>(MR)->getDecl();
Jordy Rose19c5dd12010-07-27 01:37:31 +0000848 if (FD)
Benjamin Kramerb8989f22011-10-14 18:45:37 +0000849 os << "the address of the function '" << *FD << '\'';
Jordy Rose19c5dd12010-07-27 01:37:31 +0000850 else
851 os << "the address of a function";
852 return true;
853 }
854 case MemRegion::BlockTextRegionKind:
855 os << "block text";
856 return true;
857 case MemRegion::BlockDataRegionKind:
858 os << "a block";
859 return true;
860 case MemRegion::CXXThisRegionKind:
Zhongxing Xu02fe28c2010-11-26 08:52:48 +0000861 case MemRegion::CXXTempObjectRegionKind:
Ted Kremenek96979342011-08-12 20:02:48 +0000862 os << "a C++ temp object of type " << TVR->getValueType().getAsString();
Jordy Rose19c5dd12010-07-27 01:37:31 +0000863 return true;
864 case MemRegion::VarRegionKind:
Ted Kremenek96979342011-08-12 20:02:48 +0000865 os << "a variable of type" << TVR->getValueType().getAsString();
Jordy Rose19c5dd12010-07-27 01:37:31 +0000866 return true;
867 case MemRegion::FieldRegionKind:
Ted Kremenek96979342011-08-12 20:02:48 +0000868 os << "a field of type " << TVR->getValueType().getAsString();
Jordy Rose19c5dd12010-07-27 01:37:31 +0000869 return true;
870 case MemRegion::ObjCIvarRegionKind:
Ted Kremenek96979342011-08-12 20:02:48 +0000871 os << "an instance variable of type " << TVR->getValueType().getAsString();
Jordy Rose19c5dd12010-07-27 01:37:31 +0000872 return true;
873 default:
874 return false;
875 }
876}
877
Jordy Rosed325ffb2010-07-08 23:57:29 +0000878//===----------------------------------------------------------------------===//
Ted Kremenek9c149532010-12-01 21:57:22 +0000879// evaluation of individual function calls.
Jordy Rosed325ffb2010-07-08 23:57:29 +0000880//===----------------------------------------------------------------------===//
881
Lenny Maioranib8b875b2011-03-31 21:36:53 +0000882void CStringChecker::evalCopyCommon(CheckerContext &C,
883 const CallExpr *CE,
Ted Kremenek8bef8232012-01-26 21:29:00 +0000884 ProgramStateRef state,
Jordy Rosed325ffb2010-07-08 23:57:29 +0000885 const Expr *Size, const Expr *Dest,
Lenny Maioranib8b875b2011-03-31 21:36:53 +0000886 const Expr *Source, bool Restricted,
887 bool IsMempcpy) const {
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000888 CurrentFunctionDescription = "memory copy function";
889
Jordy Rosed325ffb2010-07-08 23:57:29 +0000890 // See if the size argument is zero.
Ted Kremenek5eca4822012-01-06 22:09:28 +0000891 const LocationContext *LCtx = C.getLocationContext();
892 SVal sizeVal = state->getSVal(Size, LCtx);
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000893 QualType sizeTy = Size->getType();
Jordy Rosed325ffb2010-07-08 23:57:29 +0000894
Ted Kremenek8bef8232012-01-26 21:29:00 +0000895 ProgramStateRef stateZeroSize, stateNonZeroSize;
Jordy Rose1e022412011-06-16 05:51:02 +0000896 llvm::tie(stateZeroSize, stateNonZeroSize) =
897 assumeZero(C, state, sizeVal, sizeTy);
Jordy Rosed325ffb2010-07-08 23:57:29 +0000898
Lenny Maioranib8b875b2011-03-31 21:36:53 +0000899 // Get the value of the Dest.
Ted Kremenek5eca4822012-01-06 22:09:28 +0000900 SVal destVal = state->getSVal(Dest, LCtx);
Lenny Maioranib8b875b2011-03-31 21:36:53 +0000901
902 // If the size is zero, there won't be any actual memory access, so
903 // just bind the return value to the destination buffer and return.
Anna Zaksdd160f32012-05-03 18:21:28 +0000904 if (stateZeroSize && !stateNonZeroSize) {
Ted Kremenek5eca4822012-01-06 22:09:28 +0000905 stateZeroSize = stateZeroSize->BindExpr(CE, LCtx, destVal);
Anna Zaks0bd6b112011-10-26 21:06:34 +0000906 C.addTransition(stateZeroSize);
Anna Zaksdd160f32012-05-03 18:21:28 +0000907 return;
Lenny Maioranib8b875b2011-03-31 21:36:53 +0000908 }
Jordy Rosed325ffb2010-07-08 23:57:29 +0000909
910 // If the size can be nonzero, we have to check the other arguments.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000911 if (stateNonZeroSize) {
Jordy Rose22d27172011-06-04 00:04:22 +0000912 state = stateNonZeroSize;
Lenny Maioranib8b875b2011-03-31 21:36:53 +0000913
914 // Ensure the destination is not null. If it is NULL there will be a
915 // NULL pointer dereference.
916 state = checkNonNull(C, state, Dest, destVal);
917 if (!state)
918 return;
919
920 // Get the value of the Src.
Ted Kremenek5eca4822012-01-06 22:09:28 +0000921 SVal srcVal = state->getSVal(Source, LCtx);
Lenny Maioranib8b875b2011-03-31 21:36:53 +0000922
923 // Ensure the source is not null. If it is NULL there will be a
924 // NULL pointer dereference.
925 state = checkNonNull(C, state, Source, srcVal);
926 if (!state)
927 return;
928
Jordy Rose7182b962011-06-04 01:50:25 +0000929 // Ensure the accesses are valid and that the buffers do not overlap.
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000930 const char * const writeWarning =
931 "Memory copy function overflows destination buffer";
Jordy Rosee64f3112010-08-16 07:51:42 +0000932 state = CheckBufferAccess(C, state, Size, Dest, Source,
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000933 writeWarning, /* sourceWarning = */ NULL);
Jordy Rosed325ffb2010-07-08 23:57:29 +0000934 if (Restricted)
935 state = CheckOverlap(C, state, Size, Dest, Source);
Jordy Rosee64f3112010-08-16 07:51:42 +0000936
Jordy Rose7182b962011-06-04 01:50:25 +0000937 if (!state)
938 return;
Lenny Maioranib8b875b2011-03-31 21:36:53 +0000939
Jordy Rose7182b962011-06-04 01:50:25 +0000940 // If this is mempcpy, get the byte after the last byte copied and
941 // bind the expr.
942 if (IsMempcpy) {
943 loc::MemRegionVal *destRegVal = dyn_cast<loc::MemRegionVal>(&destVal);
944 assert(destRegVal && "Destination should be a known MemRegionVal here");
945
946 // Get the length to copy.
947 NonLoc *lenValNonLoc = dyn_cast<NonLoc>(&sizeVal);
948
949 if (lenValNonLoc) {
950 // Get the byte after the last byte copied.
951 SVal lastElement = C.getSValBuilder().evalBinOpLN(state, BO_Add,
952 *destRegVal,
953 *lenValNonLoc,
954 Dest->getType());
955
956 // The byte after the last byte copied is the return value.
Ted Kremenek5eca4822012-01-06 22:09:28 +0000957 state = state->BindExpr(CE, LCtx, lastElement);
Jordy Rose3f8bb2f2011-06-04 01:47:27 +0000958 } else {
Jordy Rose7182b962011-06-04 01:50:25 +0000959 // If we don't know how much we copied, we can at least
960 // conjure a return value for later.
Anna Zaks5d0ea6d2011-10-04 20:43:05 +0000961 unsigned Count = C.getCurrentBlockCount();
Jordy Rose7182b962011-06-04 01:50:25 +0000962 SVal result =
Ted Kremenek3133f792012-02-17 23:13:45 +0000963 C.getSValBuilder().getConjuredSymbolVal(NULL, CE, LCtx, Count);
Ted Kremenek5eca4822012-01-06 22:09:28 +0000964 state = state->BindExpr(CE, LCtx, result);
Lenny Maioranib8b875b2011-03-31 21:36:53 +0000965 }
966
Jordy Rose7182b962011-06-04 01:50:25 +0000967 } else {
968 // All other copies return the destination buffer.
969 // (Well, bcopy() has a void return type, but this won't hurt.)
Ted Kremenek5eca4822012-01-06 22:09:28 +0000970 state = state->BindExpr(CE, LCtx, destVal);
Jordy Rosee64f3112010-08-16 07:51:42 +0000971 }
Jordy Rose7182b962011-06-04 01:50:25 +0000972
973 // Invalidate the destination.
974 // FIXME: Even if we can't perfectly model the copy, we should see if we
975 // can use LazyCompoundVals to copy the source values into the destination.
976 // This would probably remove any existing bindings past the end of the
977 // copied region, but that's still an improvement over blank invalidation.
Ted Kremenek5eca4822012-01-06 22:09:28 +0000978 state = InvalidateBuffer(C, state, Dest,
979 state->getSVal(Dest, C.getLocationContext()));
Anna Zaks0bd6b112011-10-26 21:06:34 +0000980 C.addTransition(state);
Jordy Rosed325ffb2010-07-08 23:57:29 +0000981 }
982}
983
984
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +0000985void CStringChecker::evalMemcpy(CheckerContext &C, const CallExpr *CE) const {
Anna Zaks259052d2012-04-10 23:41:11 +0000986 if (CE->getNumArgs() < 3)
987 return;
988
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000989 // void *memcpy(void *restrict dst, const void *restrict src, size_t n);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000990 // The return value is the address of the destination buffer.
Jordy Rosed325ffb2010-07-08 23:57:29 +0000991 const Expr *Dest = CE->getArg(0);
Ted Kremenek8bef8232012-01-26 21:29:00 +0000992 ProgramStateRef state = C.getState();
Jordy Rose3f8bb2f2011-06-04 01:47:27 +0000993
Lenny Maioranib8b875b2011-03-31 21:36:53 +0000994 evalCopyCommon(C, CE, state, CE->getArg(2), Dest, CE->getArg(1), true);
995}
996
997void CStringChecker::evalMempcpy(CheckerContext &C, const CallExpr *CE) const {
Anna Zaks259052d2012-04-10 23:41:11 +0000998 if (CE->getNumArgs() < 3)
999 return;
1000
Lenny Maioranib8b875b2011-03-31 21:36:53 +00001001 // void *mempcpy(void *restrict dst, const void *restrict src, size_t n);
1002 // The return value is a pointer to the byte following the last written byte.
1003 const Expr *Dest = CE->getArg(0);
Ted Kremenek8bef8232012-01-26 21:29:00 +00001004 ProgramStateRef state = C.getState();
Lenny Maioranib8b875b2011-03-31 21:36:53 +00001005
1006 evalCopyCommon(C, CE, state, CE->getArg(2), Dest, CE->getArg(1), true, true);
Jordy Roseccbf7ee2010-07-06 23:11:01 +00001007}
1008
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +00001009void CStringChecker::evalMemmove(CheckerContext &C, const CallExpr *CE) const {
Anna Zaks259052d2012-04-10 23:41:11 +00001010 if (CE->getNumArgs() < 3)
1011 return;
1012
Jordy Rosed325ffb2010-07-08 23:57:29 +00001013 // void *memmove(void *dst, const void *src, size_t n);
1014 // The return value is the address of the destination buffer.
1015 const Expr *Dest = CE->getArg(0);
Ted Kremenek8bef8232012-01-26 21:29:00 +00001016 ProgramStateRef state = C.getState();
Jordy Rose3f8bb2f2011-06-04 01:47:27 +00001017
Lenny Maioranib8b875b2011-03-31 21:36:53 +00001018 evalCopyCommon(C, CE, state, CE->getArg(2), Dest, CE->getArg(1));
Jordy Rosed325ffb2010-07-08 23:57:29 +00001019}
1020
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +00001021void CStringChecker::evalBcopy(CheckerContext &C, const CallExpr *CE) const {
Anna Zaks259052d2012-04-10 23:41:11 +00001022 if (CE->getNumArgs() < 3)
1023 return;
1024
Jordy Rosed325ffb2010-07-08 23:57:29 +00001025 // void bcopy(const void *src, void *dst, size_t n);
Lenny Maioranib8b875b2011-03-31 21:36:53 +00001026 evalCopyCommon(C, CE, C.getState(),
1027 CE->getArg(2), CE->getArg(1), CE->getArg(0));
Jordy Rosed325ffb2010-07-08 23:57:29 +00001028}
1029
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +00001030void CStringChecker::evalMemcmp(CheckerContext &C, const CallExpr *CE) const {
Anna Zaks259052d2012-04-10 23:41:11 +00001031 if (CE->getNumArgs() < 3)
1032 return;
1033
Jordy Rosebc56d1f2010-07-07 08:15:01 +00001034 // int memcmp(const void *s1, const void *s2, size_t n);
Jordy Rose9e49d9f2011-06-20 02:06:40 +00001035 CurrentFunctionDescription = "memory comparison function";
1036
Jordy Rosebc56d1f2010-07-07 08:15:01 +00001037 const Expr *Left = CE->getArg(0);
1038 const Expr *Right = CE->getArg(1);
1039 const Expr *Size = CE->getArg(2);
1040
Ted Kremenek8bef8232012-01-26 21:29:00 +00001041 ProgramStateRef state = C.getState();
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001042 SValBuilder &svalBuilder = C.getSValBuilder();
Jordy Rosebc56d1f2010-07-07 08:15:01 +00001043
Jordy Rosed325ffb2010-07-08 23:57:29 +00001044 // See if the size argument is zero.
Ted Kremenek5eca4822012-01-06 22:09:28 +00001045 const LocationContext *LCtx = C.getLocationContext();
1046 SVal sizeVal = state->getSVal(Size, LCtx);
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001047 QualType sizeTy = Size->getType();
Jordy Rosebc56d1f2010-07-07 08:15:01 +00001048
Ted Kremenek8bef8232012-01-26 21:29:00 +00001049 ProgramStateRef stateZeroSize, stateNonZeroSize;
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001050 llvm::tie(stateZeroSize, stateNonZeroSize) =
1051 assumeZero(C, state, sizeVal, sizeTy);
Jordy Rosebc56d1f2010-07-07 08:15:01 +00001052
Jordy Rosed325ffb2010-07-08 23:57:29 +00001053 // If the size can be zero, the result will be 0 in that case, and we don't
1054 // have to check either of the buffers.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001055 if (stateZeroSize) {
1056 state = stateZeroSize;
Ted Kremenek5eca4822012-01-06 22:09:28 +00001057 state = state->BindExpr(CE, LCtx,
1058 svalBuilder.makeZeroVal(CE->getType()));
Anna Zaks0bd6b112011-10-26 21:06:34 +00001059 C.addTransition(state);
Jordy Rosebc56d1f2010-07-07 08:15:01 +00001060 }
1061
Jordy Rosed325ffb2010-07-08 23:57:29 +00001062 // If the size can be nonzero, we have to check the other arguments.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001063 if (stateNonZeroSize) {
1064 state = stateNonZeroSize;
Jordy Rosed325ffb2010-07-08 23:57:29 +00001065 // If we know the two buffers are the same, we know the result is 0.
1066 // First, get the two buffers' addresses. Another checker will have already
1067 // made sure they're not undefined.
Ted Kremenek5eca4822012-01-06 22:09:28 +00001068 DefinedOrUnknownSVal LV =
1069 cast<DefinedOrUnknownSVal>(state->getSVal(Left, LCtx));
1070 DefinedOrUnknownSVal RV =
1071 cast<DefinedOrUnknownSVal>(state->getSVal(Right, LCtx));
Jordy Rosebc56d1f2010-07-07 08:15:01 +00001072
Jordy Rosed325ffb2010-07-08 23:57:29 +00001073 // See if they are the same.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001074 DefinedOrUnknownSVal SameBuf = svalBuilder.evalEQ(state, LV, RV);
Ted Kremenek8bef8232012-01-26 21:29:00 +00001075 ProgramStateRef StSameBuf, StNotSameBuf;
Ted Kremenek28f47b92010-12-01 22:16:56 +00001076 llvm::tie(StSameBuf, StNotSameBuf) = state->assume(SameBuf);
Jordy Rosed325ffb2010-07-08 23:57:29 +00001077
Jordy Rose1e022412011-06-16 05:51:02 +00001078 // If the two arguments might be the same buffer, we know the result is 0,
Jordy Rosed325ffb2010-07-08 23:57:29 +00001079 // and we only need to check one size.
1080 if (StSameBuf) {
1081 state = StSameBuf;
1082 state = CheckBufferAccess(C, state, Size, Left);
1083 if (state) {
Ted Kremenek5eca4822012-01-06 22:09:28 +00001084 state = StSameBuf->BindExpr(CE, LCtx,
1085 svalBuilder.makeZeroVal(CE->getType()));
Anna Zaks0bd6b112011-10-26 21:06:34 +00001086 C.addTransition(state);
Jordy Rosed325ffb2010-07-08 23:57:29 +00001087 }
1088 }
1089
1090 // If the two arguments might be different buffers, we have to check the
1091 // size of both of them.
1092 if (StNotSameBuf) {
1093 state = StNotSameBuf;
1094 state = CheckBufferAccess(C, state, Size, Left, Right);
1095 if (state) {
1096 // The return value is the comparison result, which we don't know.
Anna Zaks5d0ea6d2011-10-04 20:43:05 +00001097 unsigned Count = C.getCurrentBlockCount();
Ted Kremenek3133f792012-02-17 23:13:45 +00001098 SVal CmpV = svalBuilder.getConjuredSymbolVal(NULL, CE, LCtx, Count);
Ted Kremenek5eca4822012-01-06 22:09:28 +00001099 state = state->BindExpr(CE, LCtx, CmpV);
Anna Zaks0bd6b112011-10-26 21:06:34 +00001100 C.addTransition(state);
Jordy Rosed325ffb2010-07-08 23:57:29 +00001101 }
1102 }
1103 }
Jordy Rosebc56d1f2010-07-07 08:15:01 +00001104}
1105
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +00001106void CStringChecker::evalstrLength(CheckerContext &C,
1107 const CallExpr *CE) const {
Anna Zaks259052d2012-04-10 23:41:11 +00001108 if (CE->getNumArgs() < 1)
1109 return;
1110
Jordy Rose19c5dd12010-07-27 01:37:31 +00001111 // size_t strlen(const char *s);
Ted Kremenekbe4242c2011-02-22 04:55:05 +00001112 evalstrLengthCommon(C, CE, /* IsStrnlen = */ false);
1113}
1114
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +00001115void CStringChecker::evalstrnLength(CheckerContext &C,
1116 const CallExpr *CE) const {
Anna Zaks259052d2012-04-10 23:41:11 +00001117 if (CE->getNumArgs() < 2)
1118 return;
1119
Ted Kremenekbe4242c2011-02-22 04:55:05 +00001120 // size_t strnlen(const char *s, size_t maxlen);
1121 evalstrLengthCommon(C, CE, /* IsStrnlen = */ true);
1122}
1123
1124void CStringChecker::evalstrLengthCommon(CheckerContext &C, const CallExpr *CE,
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +00001125 bool IsStrnlen) const {
Jordy Rose9e49d9f2011-06-20 02:06:40 +00001126 CurrentFunctionDescription = "string length function";
Ted Kremenek8bef8232012-01-26 21:29:00 +00001127 ProgramStateRef state = C.getState();
Ted Kremenek5eca4822012-01-06 22:09:28 +00001128 const LocationContext *LCtx = C.getLocationContext();
Jordy Rose793bff32011-06-14 01:15:31 +00001129
1130 if (IsStrnlen) {
1131 const Expr *maxlenExpr = CE->getArg(1);
Ted Kremenek5eca4822012-01-06 22:09:28 +00001132 SVal maxlenVal = state->getSVal(maxlenExpr, LCtx);
Jordy Rose793bff32011-06-14 01:15:31 +00001133
Ted Kremenek8bef8232012-01-26 21:29:00 +00001134 ProgramStateRef stateZeroSize, stateNonZeroSize;
Jordy Rose793bff32011-06-14 01:15:31 +00001135 llvm::tie(stateZeroSize, stateNonZeroSize) =
1136 assumeZero(C, state, maxlenVal, maxlenExpr->getType());
1137
1138 // If the size can be zero, the result will be 0 in that case, and we don't
1139 // have to check the string itself.
1140 if (stateZeroSize) {
1141 SVal zero = C.getSValBuilder().makeZeroVal(CE->getType());
Ted Kremenek5eca4822012-01-06 22:09:28 +00001142 stateZeroSize = stateZeroSize->BindExpr(CE, LCtx, zero);
Anna Zaks0bd6b112011-10-26 21:06:34 +00001143 C.addTransition(stateZeroSize);
Jordy Rose793bff32011-06-14 01:15:31 +00001144 }
1145
1146 // If the size is GUARANTEED to be zero, we're done!
1147 if (!stateNonZeroSize)
1148 return;
1149
1150 // Otherwise, record the assumption that the size is nonzero.
1151 state = stateNonZeroSize;
1152 }
1153
1154 // Check that the string argument is non-null.
Jordy Rose19c5dd12010-07-27 01:37:31 +00001155 const Expr *Arg = CE->getArg(0);
Ted Kremenek5eca4822012-01-06 22:09:28 +00001156 SVal ArgVal = state->getSVal(Arg, LCtx);
Jordy Rose19c5dd12010-07-27 01:37:31 +00001157
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001158 state = checkNonNull(C, state, Arg, ArgVal);
Jordy Rose19c5dd12010-07-27 01:37:31 +00001159
Jordy Rosebd32bee2011-06-14 01:26:48 +00001160 if (!state)
1161 return;
Jordy Rosea5261542010-08-14 21:02:52 +00001162
Jordy Rosebd32bee2011-06-14 01:26:48 +00001163 SVal strLength = getCStringLength(C, state, Arg, ArgVal);
Jordy Rosea5261542010-08-14 21:02:52 +00001164
Jordy Rosebd32bee2011-06-14 01:26:48 +00001165 // If the argument isn't a valid C string, there's no valid state to
1166 // transition to.
1167 if (strLength.isUndef())
1168 return;
Jordy Rose793bff32011-06-14 01:15:31 +00001169
Jordy Rosebd32bee2011-06-14 01:26:48 +00001170 DefinedOrUnknownSVal result = UnknownVal();
Jordy Rose793bff32011-06-14 01:15:31 +00001171
Jordy Rosebd32bee2011-06-14 01:26:48 +00001172 // If the check is for strnlen() then bind the return value to no more than
1173 // the maxlen value.
1174 if (IsStrnlen) {
Jordy Roseee2fde12011-06-16 05:56:50 +00001175 QualType cmpTy = C.getSValBuilder().getConditionType();
Jordy Rose793bff32011-06-14 01:15:31 +00001176
Jordy Rosebd32bee2011-06-14 01:26:48 +00001177 // It's a little unfortunate to be getting this again,
1178 // but it's not that expensive...
1179 const Expr *maxlenExpr = CE->getArg(1);
Ted Kremenek5eca4822012-01-06 22:09:28 +00001180 SVal maxlenVal = state->getSVal(maxlenExpr, LCtx);
Ted Kremenekbe4242c2011-02-22 04:55:05 +00001181
Jordy Rosebd32bee2011-06-14 01:26:48 +00001182 NonLoc *strLengthNL = dyn_cast<NonLoc>(&strLength);
1183 NonLoc *maxlenValNL = dyn_cast<NonLoc>(&maxlenVal);
Ted Kremenekbe4242c2011-02-22 04:55:05 +00001184
Jordy Rosebd32bee2011-06-14 01:26:48 +00001185 if (strLengthNL && maxlenValNL) {
Ted Kremenek8bef8232012-01-26 21:29:00 +00001186 ProgramStateRef stateStringTooLong, stateStringNotTooLong;
Jordy Rose793bff32011-06-14 01:15:31 +00001187
Jordy Rosebd32bee2011-06-14 01:26:48 +00001188 // Check if the strLength is greater than the maxlen.
1189 llvm::tie(stateStringTooLong, stateStringNotTooLong) =
1190 state->assume(cast<DefinedOrUnknownSVal>
1191 (C.getSValBuilder().evalBinOpNN(state, BO_GT,
1192 *strLengthNL,
1193 *maxlenValNL,
1194 cmpTy)));
Jordy Rose793bff32011-06-14 01:15:31 +00001195
Jordy Rosebd32bee2011-06-14 01:26:48 +00001196 if (stateStringTooLong && !stateStringNotTooLong) {
1197 // If the string is longer than maxlen, return maxlen.
1198 result = *maxlenValNL;
1199 } else if (stateStringNotTooLong && !stateStringTooLong) {
1200 // If the string is shorter than maxlen, return its length.
1201 result = *strLengthNL;
Ted Kremenekbe4242c2011-02-22 04:55:05 +00001202 }
1203 }
1204
Jordy Rosebd32bee2011-06-14 01:26:48 +00001205 if (result.isUnknown()) {
1206 // If we don't have enough information for a comparison, there's
1207 // no guarantee the full string length will actually be returned.
1208 // All we know is the return value is the min of the string length
1209 // and the limit. This is better than nothing.
Anna Zaks5d0ea6d2011-10-04 20:43:05 +00001210 unsigned Count = C.getCurrentBlockCount();
Ted Kremenek3133f792012-02-17 23:13:45 +00001211 result = C.getSValBuilder().getConjuredSymbolVal(NULL, CE, LCtx, Count);
Jordy Rosebd32bee2011-06-14 01:26:48 +00001212 NonLoc *resultNL = cast<NonLoc>(&result);
1213
1214 if (strLengthNL) {
1215 state = state->assume(cast<DefinedOrUnknownSVal>
1216 (C.getSValBuilder().evalBinOpNN(state, BO_LE,
1217 *resultNL,
1218 *strLengthNL,
1219 cmpTy)), true);
1220 }
1221
1222 if (maxlenValNL) {
1223 state = state->assume(cast<DefinedOrUnknownSVal>
1224 (C.getSValBuilder().evalBinOpNN(state, BO_LE,
1225 *resultNL,
1226 *maxlenValNL,
1227 cmpTy)), true);
1228 }
1229 }
1230
1231 } else {
1232 // This is a plain strlen(), not strnlen().
1233 result = cast<DefinedOrUnknownSVal>(strLength);
1234
1235 // If we don't know the length of the string, conjure a return
1236 // value, so it can be used in constraints, at least.
1237 if (result.isUnknown()) {
Anna Zaks5d0ea6d2011-10-04 20:43:05 +00001238 unsigned Count = C.getCurrentBlockCount();
Ted Kremenek3133f792012-02-17 23:13:45 +00001239 result = C.getSValBuilder().getConjuredSymbolVal(NULL, CE, LCtx, Count);
Jordy Rosebd32bee2011-06-14 01:26:48 +00001240 }
Jordy Rose19c5dd12010-07-27 01:37:31 +00001241 }
Jordy Rosebd32bee2011-06-14 01:26:48 +00001242
1243 // Bind the return value.
1244 assert(!result.isUnknown() && "Should have conjured a value by now");
Ted Kremenek5eca4822012-01-06 22:09:28 +00001245 state = state->BindExpr(CE, LCtx, result);
Anna Zaks0bd6b112011-10-26 21:06:34 +00001246 C.addTransition(state);
Jordy Rose19c5dd12010-07-27 01:37:31 +00001247}
1248
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +00001249void CStringChecker::evalStrcpy(CheckerContext &C, const CallExpr *CE) const {
Anna Zaks259052d2012-04-10 23:41:11 +00001250 if (CE->getNumArgs() < 2)
1251 return;
1252
Jordy Rosee64f3112010-08-16 07:51:42 +00001253 // char *strcpy(char *restrict dst, const char *restrict src);
Lenny Maiorani067bbd02011-04-09 15:12:58 +00001254 evalStrcpyCommon(C, CE,
1255 /* returnEnd = */ false,
1256 /* isBounded = */ false,
1257 /* isAppending = */ false);
Ted Kremenek0ef473f2011-02-22 04:58:34 +00001258}
1259
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +00001260void CStringChecker::evalStrncpy(CheckerContext &C, const CallExpr *CE) const {
Anna Zaks259052d2012-04-10 23:41:11 +00001261 if (CE->getNumArgs() < 3)
1262 return;
1263
Jordy Rosec1525862011-06-04 00:05:23 +00001264 // char *strncpy(char *restrict dst, const char *restrict src, size_t n);
Lenny Maiorani067bbd02011-04-09 15:12:58 +00001265 evalStrcpyCommon(C, CE,
1266 /* returnEnd = */ false,
1267 /* isBounded = */ true,
1268 /* isAppending = */ false);
Jordy Rosee64f3112010-08-16 07:51:42 +00001269}
1270
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +00001271void CStringChecker::evalStpcpy(CheckerContext &C, const CallExpr *CE) const {
Anna Zaks259052d2012-04-10 23:41:11 +00001272 if (CE->getNumArgs() < 2)
1273 return;
1274
Jordy Rosee64f3112010-08-16 07:51:42 +00001275 // char *stpcpy(char *restrict dst, const char *restrict src);
Lenny Maiorani067bbd02011-04-09 15:12:58 +00001276 evalStrcpyCommon(C, CE,
1277 /* returnEnd = */ true,
1278 /* isBounded = */ false,
1279 /* isAppending = */ false);
1280}
1281
1282void CStringChecker::evalStrcat(CheckerContext &C, const CallExpr *CE) const {
Anna Zaks259052d2012-04-10 23:41:11 +00001283 if (CE->getNumArgs() < 2)
1284 return;
1285
Lenny Maiorani067bbd02011-04-09 15:12:58 +00001286 //char *strcat(char *restrict s1, const char *restrict s2);
1287 evalStrcpyCommon(C, CE,
1288 /* returnEnd = */ false,
1289 /* isBounded = */ false,
1290 /* isAppending = */ true);
1291}
1292
1293void CStringChecker::evalStrncat(CheckerContext &C, const CallExpr *CE) const {
Anna Zaks259052d2012-04-10 23:41:11 +00001294 if (CE->getNumArgs() < 3)
1295 return;
1296
Lenny Maiorani067bbd02011-04-09 15:12:58 +00001297 //char *strncat(char *restrict s1, const char *restrict s2, size_t n);
1298 evalStrcpyCommon(C, CE,
1299 /* returnEnd = */ false,
1300 /* isBounded = */ true,
1301 /* isAppending = */ true);
Jordy Rosee64f3112010-08-16 07:51:42 +00001302}
1303
Ted Kremenek9c149532010-12-01 21:57:22 +00001304void CStringChecker::evalStrcpyCommon(CheckerContext &C, const CallExpr *CE,
Lenny Maiorani067bbd02011-04-09 15:12:58 +00001305 bool returnEnd, bool isBounded,
1306 bool isAppending) const {
Jordy Rose9e49d9f2011-06-20 02:06:40 +00001307 CurrentFunctionDescription = "string copy function";
Ted Kremenek8bef8232012-01-26 21:29:00 +00001308 ProgramStateRef state = C.getState();
Ted Kremenek5eca4822012-01-06 22:09:28 +00001309 const LocationContext *LCtx = C.getLocationContext();
Jordy Rosee64f3112010-08-16 07:51:42 +00001310
Lenny Maiorani067bbd02011-04-09 15:12:58 +00001311 // Check that the destination is non-null.
Jordy Rosee64f3112010-08-16 07:51:42 +00001312 const Expr *Dst = CE->getArg(0);
Ted Kremenek5eca4822012-01-06 22:09:28 +00001313 SVal DstVal = state->getSVal(Dst, LCtx);
Jordy Rosee64f3112010-08-16 07:51:42 +00001314
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001315 state = checkNonNull(C, state, Dst, DstVal);
Jordy Rosee64f3112010-08-16 07:51:42 +00001316 if (!state)
1317 return;
1318
1319 // Check that the source is non-null.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001320 const Expr *srcExpr = CE->getArg(1);
Ted Kremenek5eca4822012-01-06 22:09:28 +00001321 SVal srcVal = state->getSVal(srcExpr, LCtx);
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001322 state = checkNonNull(C, state, srcExpr, srcVal);
Jordy Rosee64f3112010-08-16 07:51:42 +00001323 if (!state)
1324 return;
1325
1326 // Get the string length of the source.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001327 SVal strLength = getCStringLength(C, state, srcExpr, srcVal);
Jordy Rosee64f3112010-08-16 07:51:42 +00001328
1329 // If the source isn't a valid C string, give up.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001330 if (strLength.isUndef())
Jordy Rosee64f3112010-08-16 07:51:42 +00001331 return;
1332
Jordy Rosed5af0e12011-06-15 05:52:56 +00001333 SValBuilder &svalBuilder = C.getSValBuilder();
1334 QualType cmpTy = svalBuilder.getConditionType();
Jordy Rose8912aae2011-06-20 21:55:40 +00001335 QualType sizeTy = svalBuilder.getContext().getSizeType();
Jordy Rosed5af0e12011-06-15 05:52:56 +00001336
Jordy Rose8912aae2011-06-20 21:55:40 +00001337 // These two values allow checking two kinds of errors:
1338 // - actual overflows caused by a source that doesn't fit in the destination
1339 // - potential overflows caused by a bound that could exceed the destination
Jordy Rosed5af0e12011-06-15 05:52:56 +00001340 SVal amountCopied = UnknownVal();
Jordy Rose8912aae2011-06-20 21:55:40 +00001341 SVal maxLastElementIndex = UnknownVal();
1342 const char *boundWarning = NULL;
Jordy Rosed5af0e12011-06-15 05:52:56 +00001343
Lenny Maiorani067bbd02011-04-09 15:12:58 +00001344 // If the function is strncpy, strncat, etc... it is bounded.
1345 if (isBounded) {
1346 // Get the max number of characters to copy.
Ted Kremenek0ef473f2011-02-22 04:58:34 +00001347 const Expr *lenExpr = CE->getArg(2);
Ted Kremenek5eca4822012-01-06 22:09:28 +00001348 SVal lenVal = state->getSVal(lenExpr, LCtx);
Ted Kremenek0ef473f2011-02-22 04:58:34 +00001349
Jordy Rosed5af0e12011-06-15 05:52:56 +00001350 // Protect against misdeclared strncpy().
Jordy Rose8912aae2011-06-20 21:55:40 +00001351 lenVal = svalBuilder.evalCast(lenVal, sizeTy, lenExpr->getType());
Jordy Rosed5af0e12011-06-15 05:52:56 +00001352
Ted Kremenek0ef473f2011-02-22 04:58:34 +00001353 NonLoc *strLengthNL = dyn_cast<NonLoc>(&strLength);
1354 NonLoc *lenValNL = dyn_cast<NonLoc>(&lenVal);
1355
Jordy Rosed5af0e12011-06-15 05:52:56 +00001356 // If we know both values, we might be able to figure out how much
1357 // we're copying.
1358 if (strLengthNL && lenValNL) {
Ted Kremenek8bef8232012-01-26 21:29:00 +00001359 ProgramStateRef stateSourceTooLong, stateSourceNotTooLong;
Ted Kremenek0ef473f2011-02-22 04:58:34 +00001360
Jordy Rosed5af0e12011-06-15 05:52:56 +00001361 // Check if the max number to copy is less than the length of the src.
Jordy Rose8912aae2011-06-20 21:55:40 +00001362 // If the bound is equal to the source length, strncpy won't null-
1363 // terminate the result!
Jordy Rosed5af0e12011-06-15 05:52:56 +00001364 llvm::tie(stateSourceTooLong, stateSourceNotTooLong) =
1365 state->assume(cast<DefinedOrUnknownSVal>
Jordy Rose8912aae2011-06-20 21:55:40 +00001366 (svalBuilder.evalBinOpNN(state, BO_GE, *strLengthNL,
Jordy Rosed5af0e12011-06-15 05:52:56 +00001367 *lenValNL, cmpTy)));
1368
1369 if (stateSourceTooLong && !stateSourceNotTooLong) {
1370 // Max number to copy is less than the length of the src, so the actual
1371 // strLength copied is the max number arg.
1372 state = stateSourceTooLong;
1373 amountCopied = lenVal;
1374
1375 } else if (!stateSourceTooLong && stateSourceNotTooLong) {
1376 // The source buffer entirely fits in the bound.
1377 state = stateSourceNotTooLong;
1378 amountCopied = strLength;
1379 }
1380 }
1381
Jordy Rose5e5f1502011-06-20 03:49:16 +00001382 // We still want to know if the bound is known to be too large.
Jordy Rose8912aae2011-06-20 21:55:40 +00001383 if (lenValNL) {
1384 if (isAppending) {
1385 // For strncat, the check is strlen(dst) + lenVal < sizeof(dst)
1386
1387 // Get the string length of the destination. If the destination is
1388 // memory that can't have a string length, we shouldn't be copying
1389 // into it anyway.
1390 SVal dstStrLength = getCStringLength(C, state, Dst, DstVal);
1391 if (dstStrLength.isUndef())
1392 return;
1393
1394 if (NonLoc *dstStrLengthNL = dyn_cast<NonLoc>(&dstStrLength)) {
1395 maxLastElementIndex = svalBuilder.evalBinOpNN(state, BO_Add,
1396 *lenValNL,
1397 *dstStrLengthNL,
1398 sizeTy);
1399 boundWarning = "Size argument is greater than the free space in the "
1400 "destination buffer";
1401 }
1402
1403 } else {
1404 // For strncpy, this is just checking that lenVal <= sizeof(dst)
1405 // (Yes, strncpy and strncat differ in how they treat termination.
1406 // strncat ALWAYS terminates, but strncpy doesn't.)
1407 NonLoc one = cast<NonLoc>(svalBuilder.makeIntVal(1, sizeTy));
1408 maxLastElementIndex = svalBuilder.evalBinOpNN(state, BO_Sub, *lenValNL,
1409 one, sizeTy);
1410 boundWarning = "Size argument is greater than the length of the "
1411 "destination buffer";
1412 }
1413 }
Jordy Rose5e5f1502011-06-20 03:49:16 +00001414
Jordy Rosed5af0e12011-06-15 05:52:56 +00001415 // If we couldn't pin down the copy length, at least bound it.
Jordy Rose8912aae2011-06-20 21:55:40 +00001416 // FIXME: We should actually run this code path for append as well, but
1417 // right now it creates problems with constraints (since we can end up
1418 // trying to pass constraints from symbol to symbol).
1419 if (amountCopied.isUnknown() && !isAppending) {
Jordy Rosed5af0e12011-06-15 05:52:56 +00001420 // Try to get a "hypothetical" string length symbol, which we can later
1421 // set as a real value if that turns out to be the case.
1422 amountCopied = getCStringLength(C, state, lenExpr, srcVal, true);
1423 assert(!amountCopied.isUndef());
1424
1425 if (NonLoc *amountCopiedNL = dyn_cast<NonLoc>(&amountCopied)) {
1426 if (lenValNL) {
1427 // amountCopied <= lenVal
1428 SVal copiedLessThanBound = svalBuilder.evalBinOpNN(state, BO_LE,
1429 *amountCopiedNL,
1430 *lenValNL,
1431 cmpTy);
1432 state = state->assume(cast<DefinedOrUnknownSVal>(copiedLessThanBound),
1433 true);
1434 if (!state)
1435 return;
1436 }
1437
1438 if (strLengthNL) {
1439 // amountCopied <= strlen(source)
1440 SVal copiedLessThanSrc = svalBuilder.evalBinOpNN(state, BO_LE,
1441 *amountCopiedNL,
1442 *strLengthNL,
1443 cmpTy);
1444 state = state->assume(cast<DefinedOrUnknownSVal>(copiedLessThanSrc),
1445 true);
1446 if (!state)
1447 return;
1448 }
1449 }
1450 }
1451
1452 } else {
1453 // The function isn't bounded. The amount copied should match the length
1454 // of the source buffer.
1455 amountCopied = strLength;
Ted Kremenek0ef473f2011-02-22 04:58:34 +00001456 }
1457
Jordy Rosed5af0e12011-06-15 05:52:56 +00001458 assert(state);
1459
1460 // This represents the number of characters copied into the destination
1461 // buffer. (It may not actually be the strlen if the destination buffer
1462 // is not terminated.)
1463 SVal finalStrLength = UnknownVal();
1464
Lenny Maiorani067bbd02011-04-09 15:12:58 +00001465 // If this is an appending function (strcat, strncat...) then set the
1466 // string length to strlen(src) + strlen(dst) since the buffer will
1467 // ultimately contain both.
1468 if (isAppending) {
Jordy Rose1e022412011-06-16 05:51:02 +00001469 // Get the string length of the destination. If the destination is memory
1470 // that can't have a string length, we shouldn't be copying into it anyway.
Lenny Maiorani067bbd02011-04-09 15:12:58 +00001471 SVal dstStrLength = getCStringLength(C, state, Dst, DstVal);
1472 if (dstStrLength.isUndef())
1473 return;
1474
Jordy Rosed5af0e12011-06-15 05:52:56 +00001475 NonLoc *srcStrLengthNL = dyn_cast<NonLoc>(&amountCopied);
Lenny Maiorani067bbd02011-04-09 15:12:58 +00001476 NonLoc *dstStrLengthNL = dyn_cast<NonLoc>(&dstStrLength);
1477
Jordy Rosed5af0e12011-06-15 05:52:56 +00001478 // If we know both string lengths, we might know the final string length.
1479 if (srcStrLengthNL && dstStrLengthNL) {
1480 // Make sure the two lengths together don't overflow a size_t.
1481 state = checkAdditionOverflow(C, state, *srcStrLengthNL, *dstStrLengthNL);
1482 if (!state)
1483 return;
Lenny Maiorani067bbd02011-04-09 15:12:58 +00001484
Jordy Rosed5af0e12011-06-15 05:52:56 +00001485 finalStrLength = svalBuilder.evalBinOpNN(state, BO_Add, *srcStrLengthNL,
1486 *dstStrLengthNL, sizeTy);
1487 }
Lenny Maiorani067bbd02011-04-09 15:12:58 +00001488
Jordy Rosed5af0e12011-06-15 05:52:56 +00001489 // If we couldn't get a single value for the final string length,
1490 // we can at least bound it by the individual lengths.
1491 if (finalStrLength.isUnknown()) {
1492 // Try to get a "hypothetical" string length symbol, which we can later
1493 // set as a real value if that turns out to be the case.
1494 finalStrLength = getCStringLength(C, state, CE, DstVal, true);
1495 assert(!finalStrLength.isUndef());
1496
1497 if (NonLoc *finalStrLengthNL = dyn_cast<NonLoc>(&finalStrLength)) {
1498 if (srcStrLengthNL) {
1499 // finalStrLength >= srcStrLength
1500 SVal sourceInResult = svalBuilder.evalBinOpNN(state, BO_GE,
1501 *finalStrLengthNL,
1502 *srcStrLengthNL,
1503 cmpTy);
1504 state = state->assume(cast<DefinedOrUnknownSVal>(sourceInResult),
1505 true);
1506 if (!state)
1507 return;
1508 }
1509
1510 if (dstStrLengthNL) {
1511 // finalStrLength >= dstStrLength
1512 SVal destInResult = svalBuilder.evalBinOpNN(state, BO_GE,
1513 *finalStrLengthNL,
1514 *dstStrLengthNL,
1515 cmpTy);
1516 state = state->assume(cast<DefinedOrUnknownSVal>(destInResult),
1517 true);
1518 if (!state)
1519 return;
1520 }
1521 }
1522 }
1523
1524 } else {
1525 // Otherwise, this is a copy-over function (strcpy, strncpy, ...), and
1526 // the final string length will match the input string length.
1527 finalStrLength = amountCopied;
Lenny Maiorani067bbd02011-04-09 15:12:58 +00001528 }
1529
Jordy Rosed5af0e12011-06-15 05:52:56 +00001530 // The final result of the function will either be a pointer past the last
1531 // copied element, or a pointer to the start of the destination buffer.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001532 SVal Result = (returnEnd ? UnknownVal() : DstVal);
Jordy Rosee64f3112010-08-16 07:51:42 +00001533
Jordy Rosed5af0e12011-06-15 05:52:56 +00001534 assert(state);
1535
Jordy Rosee64f3112010-08-16 07:51:42 +00001536 // If the destination is a MemRegion, try to check for a buffer overflow and
1537 // record the new string length.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001538 if (loc::MemRegionVal *dstRegVal = dyn_cast<loc::MemRegionVal>(&DstVal)) {
Jordy Rose8912aae2011-06-20 21:55:40 +00001539 QualType ptrTy = Dst->getType();
1540
1541 // If we have an exact value on a bounded copy, use that to check for
1542 // overflows, rather than our estimate about how much is actually copied.
1543 if (boundWarning) {
1544 if (NonLoc *maxLastNL = dyn_cast<NonLoc>(&maxLastElementIndex)) {
1545 SVal maxLastElement = svalBuilder.evalBinOpLN(state, BO_Add, *dstRegVal,
1546 *maxLastNL, ptrTy);
1547 state = CheckLocation(C, state, CE->getArg(2), maxLastElement,
1548 boundWarning);
1549 if (!state)
1550 return;
1551 }
1552 }
1553
1554 // Then, if the final length is known...
Jordy Rosed5af0e12011-06-15 05:52:56 +00001555 if (NonLoc *knownStrLength = dyn_cast<NonLoc>(&finalStrLength)) {
1556 SVal lastElement = svalBuilder.evalBinOpLN(state, BO_Add, *dstRegVal,
Jordy Rose8912aae2011-06-20 21:55:40 +00001557 *knownStrLength, ptrTy);
Jordy Rosee64f3112010-08-16 07:51:42 +00001558
Jordy Rose8912aae2011-06-20 21:55:40 +00001559 // ...and we haven't checked the bound, we'll check the actual copy.
1560 if (!boundWarning) {
1561 const char * const warningMsg =
1562 "String copy function overflows destination buffer";
1563 state = CheckLocation(C, state, Dst, lastElement, warningMsg);
1564 if (!state)
1565 return;
1566 }
Jordy Rosee64f3112010-08-16 07:51:42 +00001567
1568 // If this is a stpcpy-style copy, the last element is the return value.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001569 if (returnEnd)
1570 Result = lastElement;
Jordy Rosee64f3112010-08-16 07:51:42 +00001571 }
1572
1573 // Invalidate the destination. This must happen before we set the C string
1574 // length because invalidation will clear the length.
1575 // FIXME: Even if we can't perfectly model the copy, we should see if we
1576 // can use LazyCompoundVals to copy the source values into the destination.
1577 // This would probably remove any existing bindings past the end of the
1578 // string, but that's still an improvement over blank invalidation.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001579 state = InvalidateBuffer(C, state, Dst, *dstRegVal);
Jordy Rosee64f3112010-08-16 07:51:42 +00001580
Jordy Rose5e5f1502011-06-20 03:49:16 +00001581 // Set the C string length of the destination, if we know it.
Jordy Rose8912aae2011-06-20 21:55:40 +00001582 if (isBounded && !isAppending) {
1583 // strncpy is annoying in that it doesn't guarantee to null-terminate
1584 // the result string. If the original string didn't fit entirely inside
1585 // the bound (including the null-terminator), we don't know how long the
1586 // result is.
1587 if (amountCopied != strLength)
1588 finalStrLength = UnknownVal();
1589 }
1590 state = setCStringLength(state, dstRegVal->getRegion(), finalStrLength);
Jordy Rosee64f3112010-08-16 07:51:42 +00001591 }
1592
Jordy Rosed5af0e12011-06-15 05:52:56 +00001593 assert(state);
1594
Jordy Rosee64f3112010-08-16 07:51:42 +00001595 // If this is a stpcpy-style copy, but we were unable to check for a buffer
1596 // overflow, we still need a result. Conjure a return value.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001597 if (returnEnd && Result.isUnknown()) {
Anna Zaks5d0ea6d2011-10-04 20:43:05 +00001598 unsigned Count = C.getCurrentBlockCount();
Ted Kremenek3133f792012-02-17 23:13:45 +00001599 Result = svalBuilder.getConjuredSymbolVal(NULL, CE, LCtx, Count);
Jordy Rosee64f3112010-08-16 07:51:42 +00001600 }
1601
1602 // Set the return value.
Ted Kremenek5eca4822012-01-06 22:09:28 +00001603 state = state->BindExpr(CE, LCtx, Result);
Anna Zaks0bd6b112011-10-26 21:06:34 +00001604 C.addTransition(state);
Jordy Rosee64f3112010-08-16 07:51:42 +00001605}
1606
Lenny Maiorani318dd922011-04-12 17:08:43 +00001607void CStringChecker::evalStrcmp(CheckerContext &C, const CallExpr *CE) const {
Anna Zaks259052d2012-04-10 23:41:11 +00001608 if (CE->getNumArgs() < 2)
1609 return;
1610
Jordy Roseadc42d42011-06-16 07:13:34 +00001611 //int strcmp(const char *s1, const char *s2);
Lenny Maioranibd1d16a2011-04-28 15:09:11 +00001612 evalStrcmpCommon(C, CE, /* isBounded = */ false, /* ignoreCase = */ false);
Lenny Maiorani357f6ee2011-04-25 22:21:00 +00001613}
Lenny Maiorani318dd922011-04-12 17:08:43 +00001614
Lenny Maiorani357f6ee2011-04-25 22:21:00 +00001615void CStringChecker::evalStrncmp(CheckerContext &C, const CallExpr *CE) const {
Anna Zaks259052d2012-04-10 23:41:11 +00001616 if (CE->getNumArgs() < 3)
1617 return;
1618
Jordy Roseadc42d42011-06-16 07:13:34 +00001619 //int strncmp(const char *s1, const char *s2, size_t n);
Lenny Maioranibd1d16a2011-04-28 15:09:11 +00001620 evalStrcmpCommon(C, CE, /* isBounded = */ true, /* ignoreCase = */ false);
1621}
1622
1623void CStringChecker::evalStrcasecmp(CheckerContext &C,
1624 const CallExpr *CE) const {
Anna Zaks259052d2012-04-10 23:41:11 +00001625 if (CE->getNumArgs() < 2)
1626 return;
1627
Jordy Roseadc42d42011-06-16 07:13:34 +00001628 //int strcasecmp(const char *s1, const char *s2);
Lenny Maioranibd1d16a2011-04-28 15:09:11 +00001629 evalStrcmpCommon(C, CE, /* isBounded = */ false, /* ignoreCase = */ true);
Lenny Maiorani357f6ee2011-04-25 22:21:00 +00001630}
1631
Lenny Maiorani454fd2d2011-05-02 19:05:49 +00001632void CStringChecker::evalStrncasecmp(CheckerContext &C,
1633 const CallExpr *CE) const {
Anna Zaks259052d2012-04-10 23:41:11 +00001634 if (CE->getNumArgs() < 3)
1635 return;
1636
Jordy Roseadc42d42011-06-16 07:13:34 +00001637 //int strncasecmp(const char *s1, const char *s2, size_t n);
Lenny Maiorani454fd2d2011-05-02 19:05:49 +00001638 evalStrcmpCommon(C, CE, /* isBounded = */ true, /* ignoreCase = */ true);
1639}
1640
Lenny Maiorani357f6ee2011-04-25 22:21:00 +00001641void CStringChecker::evalStrcmpCommon(CheckerContext &C, const CallExpr *CE,
Lenny Maioranibd1d16a2011-04-28 15:09:11 +00001642 bool isBounded, bool ignoreCase) const {
Jordy Rose9e49d9f2011-06-20 02:06:40 +00001643 CurrentFunctionDescription = "string comparison function";
Ted Kremenek8bef8232012-01-26 21:29:00 +00001644 ProgramStateRef state = C.getState();
Ted Kremenek5eca4822012-01-06 22:09:28 +00001645 const LocationContext *LCtx = C.getLocationContext();
Lenny Maiorani318dd922011-04-12 17:08:43 +00001646
1647 // Check that the first string is non-null
1648 const Expr *s1 = CE->getArg(0);
Ted Kremenek5eca4822012-01-06 22:09:28 +00001649 SVal s1Val = state->getSVal(s1, LCtx);
Lenny Maiorani318dd922011-04-12 17:08:43 +00001650 state = checkNonNull(C, state, s1, s1Val);
1651 if (!state)
1652 return;
1653
1654 // Check that the second string is non-null.
1655 const Expr *s2 = CE->getArg(1);
Ted Kremenek5eca4822012-01-06 22:09:28 +00001656 SVal s2Val = state->getSVal(s2, LCtx);
Lenny Maiorani318dd922011-04-12 17:08:43 +00001657 state = checkNonNull(C, state, s2, s2Val);
1658 if (!state)
1659 return;
1660
1661 // Get the string length of the first string or give up.
1662 SVal s1Length = getCStringLength(C, state, s1, s1Val);
1663 if (s1Length.isUndef())
1664 return;
1665
1666 // Get the string length of the second string or give up.
1667 SVal s2Length = getCStringLength(C, state, s2, s2Val);
1668 if (s2Length.isUndef())
1669 return;
1670
Jordy Roseadc42d42011-06-16 07:13:34 +00001671 // If we know the two buffers are the same, we know the result is 0.
1672 // First, get the two buffers' addresses. Another checker will have already
1673 // made sure they're not undefined.
1674 DefinedOrUnknownSVal LV = cast<DefinedOrUnknownSVal>(s1Val);
1675 DefinedOrUnknownSVal RV = cast<DefinedOrUnknownSVal>(s2Val);
Lenny Maiorani318dd922011-04-12 17:08:43 +00001676
Jordy Roseadc42d42011-06-16 07:13:34 +00001677 // See if they are the same.
Lenny Maiorani318dd922011-04-12 17:08:43 +00001678 SValBuilder &svalBuilder = C.getSValBuilder();
Jordy Roseadc42d42011-06-16 07:13:34 +00001679 DefinedOrUnknownSVal SameBuf = svalBuilder.evalEQ(state, LV, RV);
Ted Kremenek8bef8232012-01-26 21:29:00 +00001680 ProgramStateRef StSameBuf, StNotSameBuf;
Jordy Roseadc42d42011-06-16 07:13:34 +00001681 llvm::tie(StSameBuf, StNotSameBuf) = state->assume(SameBuf);
Lenny Maiorani318dd922011-04-12 17:08:43 +00001682
Jordy Roseadc42d42011-06-16 07:13:34 +00001683 // If the two arguments might be the same buffer, we know the result is 0,
1684 // and we only need to check one size.
1685 if (StSameBuf) {
Ted Kremenek5eca4822012-01-06 22:09:28 +00001686 StSameBuf = StSameBuf->BindExpr(CE, LCtx,
1687 svalBuilder.makeZeroVal(CE->getType()));
Anna Zaks0bd6b112011-10-26 21:06:34 +00001688 C.addTransition(StSameBuf);
Jordy Roseadc42d42011-06-16 07:13:34 +00001689
1690 // If the two arguments are GUARANTEED to be the same, we're done!
1691 if (!StNotSameBuf)
1692 return;
1693 }
1694
1695 assert(StNotSameBuf);
1696 state = StNotSameBuf;
1697
1698 // At this point we can go about comparing the two buffers.
1699 // For now, we only do this if they're both known string literals.
1700
1701 // Attempt to extract string literals from both expressions.
1702 const StringLiteral *s1StrLiteral = getCStringLiteral(C, state, s1, s1Val);
1703 const StringLiteral *s2StrLiteral = getCStringLiteral(C, state, s2, s2Val);
1704 bool canComputeResult = false;
1705
1706 if (s1StrLiteral && s2StrLiteral) {
Chris Lattner5f9e2722011-07-23 10:55:15 +00001707 StringRef s1StrRef = s1StrLiteral->getString();
1708 StringRef s2StrRef = s2StrLiteral->getString();
Jordy Roseadc42d42011-06-16 07:13:34 +00001709
1710 if (isBounded) {
1711 // Get the max number of characters to compare.
1712 const Expr *lenExpr = CE->getArg(2);
Ted Kremenek5eca4822012-01-06 22:09:28 +00001713 SVal lenVal = state->getSVal(lenExpr, LCtx);
Jordy Roseadc42d42011-06-16 07:13:34 +00001714
1715 // If the length is known, we can get the right substrings.
1716 if (const llvm::APSInt *len = svalBuilder.getKnownValue(state, lenVal)) {
1717 // Create substrings of each to compare the prefix.
1718 s1StrRef = s1StrRef.substr(0, (size_t)len->getZExtValue());
1719 s2StrRef = s2StrRef.substr(0, (size_t)len->getZExtValue());
1720 canComputeResult = true;
1721 }
1722 } else {
1723 // This is a normal, unbounded strcmp.
1724 canComputeResult = true;
1725 }
1726
1727 if (canComputeResult) {
1728 // Real strcmp stops at null characters.
1729 size_t s1Term = s1StrRef.find('\0');
Chris Lattner5f9e2722011-07-23 10:55:15 +00001730 if (s1Term != StringRef::npos)
Jordy Roseadc42d42011-06-16 07:13:34 +00001731 s1StrRef = s1StrRef.substr(0, s1Term);
1732
1733 size_t s2Term = s2StrRef.find('\0');
Chris Lattner5f9e2722011-07-23 10:55:15 +00001734 if (s2Term != StringRef::npos)
Jordy Roseadc42d42011-06-16 07:13:34 +00001735 s2StrRef = s2StrRef.substr(0, s2Term);
1736
1737 // Use StringRef's comparison methods to compute the actual result.
1738 int result;
1739
1740 if (ignoreCase) {
1741 // Compare string 1 to string 2 the same way strcasecmp() does.
1742 result = s1StrRef.compare_lower(s2StrRef);
1743 } else {
1744 // Compare string 1 to string 2 the same way strcmp() does.
1745 result = s1StrRef.compare(s2StrRef);
1746 }
1747
1748 // Build the SVal of the comparison and bind the return value.
1749 SVal resultVal = svalBuilder.makeIntVal(result, CE->getType());
Ted Kremenek5eca4822012-01-06 22:09:28 +00001750 state = state->BindExpr(CE, LCtx, resultVal);
Jordy Roseadc42d42011-06-16 07:13:34 +00001751 }
1752 }
1753
1754 if (!canComputeResult) {
1755 // Conjure a symbolic value. It's the best we can do.
Anna Zaks5d0ea6d2011-10-04 20:43:05 +00001756 unsigned Count = C.getCurrentBlockCount();
Ted Kremenek3133f792012-02-17 23:13:45 +00001757 SVal resultVal = svalBuilder.getConjuredSymbolVal(NULL, CE, LCtx, Count);
Ted Kremenek5eca4822012-01-06 22:09:28 +00001758 state = state->BindExpr(CE, LCtx, resultVal);
Jordy Roseadc42d42011-06-16 07:13:34 +00001759 }
1760
1761 // Record this as a possible path.
Anna Zaks0bd6b112011-10-26 21:06:34 +00001762 C.addTransition(state);
Lenny Maiorani318dd922011-04-12 17:08:43 +00001763}
1764
Jordy Rosed325ffb2010-07-08 23:57:29 +00001765//===----------------------------------------------------------------------===//
Jordy Rosea5261542010-08-14 21:02:52 +00001766// The driver method, and other Checker callbacks.
Jordy Rosed325ffb2010-07-08 23:57:29 +00001767//===----------------------------------------------------------------------===//
Jordy Roseccbf7ee2010-07-06 23:11:01 +00001768
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +00001769bool CStringChecker::evalCall(const CallExpr *CE, CheckerContext &C) const {
Anna Zaks998e2752012-02-17 22:35:26 +00001770 const FunctionDecl *FDecl = C.getCalleeDecl(CE);
1771
1772 if (!FDecl)
Jordy Roseccbf7ee2010-07-06 23:11:01 +00001773 return false;
Jordy Roseccbf7ee2010-07-06 23:11:01 +00001774
Anna Zaks998e2752012-02-17 22:35:26 +00001775 FnCheck evalFunction = 0;
1776 if (C.isCLibraryFunction(FDecl, "memcpy"))
1777 evalFunction = &CStringChecker::evalMemcpy;
1778 else if (C.isCLibraryFunction(FDecl, "mempcpy"))
1779 evalFunction = &CStringChecker::evalMempcpy;
1780 else if (C.isCLibraryFunction(FDecl, "memcmp"))
1781 evalFunction = &CStringChecker::evalMemcmp;
1782 else if (C.isCLibraryFunction(FDecl, "memmove"))
1783 evalFunction = &CStringChecker::evalMemmove;
1784 else if (C.isCLibraryFunction(FDecl, "strcpy"))
1785 evalFunction = &CStringChecker::evalStrcpy;
1786 else if (C.isCLibraryFunction(FDecl, "strncpy"))
1787 evalFunction = &CStringChecker::evalStrncpy;
1788 else if (C.isCLibraryFunction(FDecl, "stpcpy"))
1789 evalFunction = &CStringChecker::evalStpcpy;
1790 else if (C.isCLibraryFunction(FDecl, "strcat"))
1791 evalFunction = &CStringChecker::evalStrcat;
1792 else if (C.isCLibraryFunction(FDecl, "strncat"))
1793 evalFunction = &CStringChecker::evalStrncat;
1794 else if (C.isCLibraryFunction(FDecl, "strlen"))
1795 evalFunction = &CStringChecker::evalstrLength;
1796 else if (C.isCLibraryFunction(FDecl, "strnlen"))
1797 evalFunction = &CStringChecker::evalstrnLength;
1798 else if (C.isCLibraryFunction(FDecl, "strcmp"))
1799 evalFunction = &CStringChecker::evalStrcmp;
1800 else if (C.isCLibraryFunction(FDecl, "strncmp"))
1801 evalFunction = &CStringChecker::evalStrncmp;
1802 else if (C.isCLibraryFunction(FDecl, "strcasecmp"))
1803 evalFunction = &CStringChecker::evalStrcasecmp;
1804 else if (C.isCLibraryFunction(FDecl, "strncasecmp"))
1805 evalFunction = &CStringChecker::evalStrncasecmp;
1806 else if (C.isCLibraryFunction(FDecl, "bcopy"))
1807 evalFunction = &CStringChecker::evalBcopy;
1808 else if (C.isCLibraryFunction(FDecl, "bcmp"))
1809 evalFunction = &CStringChecker::evalMemcmp;
1810
Jordy Rosed325ffb2010-07-08 23:57:29 +00001811 // If the callee isn't a string function, let another checker handle it.
Ted Kremenek9c149532010-12-01 21:57:22 +00001812 if (!evalFunction)
Jordy Roseccbf7ee2010-07-06 23:11:01 +00001813 return false;
1814
Jordy Rose9e49d9f2011-06-20 02:06:40 +00001815 // Make sure each function sets its own description.
1816 // (But don't bother in a release build.)
1817 assert(!(CurrentFunctionDescription = NULL));
1818
Jordy Rosed325ffb2010-07-08 23:57:29 +00001819 // Check and evaluate the call.
Ted Kremenek9c149532010-12-01 21:57:22 +00001820 (this->*evalFunction)(C, CE);
Anna Zaks57300762012-02-07 00:56:14 +00001821
1822 // If the evaluate call resulted in no change, chain to the next eval call
1823 // handler.
1824 // Note, the custom CString evaluation calls assume that basic safety
1825 // properties are held. However, if the user chooses to turn off some of these
1826 // checks, we ignore the issues and leave the call evaluation to a generic
1827 // handler.
1828 if (!C.isDifferent())
1829 return false;
1830
Jordy Roseccbf7ee2010-07-06 23:11:01 +00001831 return true;
1832}
Jordy Rosea5261542010-08-14 21:02:52 +00001833
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +00001834void CStringChecker::checkPreStmt(const DeclStmt *DS, CheckerContext &C) const {
Jordy Rosea5261542010-08-14 21:02:52 +00001835 // Record string length for char a[] = "abc";
Ted Kremenek8bef8232012-01-26 21:29:00 +00001836 ProgramStateRef state = C.getState();
Jordy Rosea5261542010-08-14 21:02:52 +00001837
1838 for (DeclStmt::const_decl_iterator I = DS->decl_begin(), E = DS->decl_end();
1839 I != E; ++I) {
1840 const VarDecl *D = dyn_cast<VarDecl>(*I);
1841 if (!D)
1842 continue;
1843
1844 // FIXME: Handle array fields of structs.
1845 if (!D->getType()->isArrayType())
1846 continue;
1847
1848 const Expr *Init = D->getInit();
1849 if (!Init)
1850 continue;
1851 if (!isa<StringLiteral>(Init))
1852 continue;
1853
Anna Zaks39ac1872011-10-26 21:06:44 +00001854 Loc VarLoc = state->getLValue(D, C.getLocationContext());
Jordy Rosea5261542010-08-14 21:02:52 +00001855 const MemRegion *MR = VarLoc.getAsRegion();
1856 if (!MR)
1857 continue;
1858
Ted Kremenek5eca4822012-01-06 22:09:28 +00001859 SVal StrVal = state->getSVal(Init, C.getLocationContext());
Jordy Rosea5261542010-08-14 21:02:52 +00001860 assert(StrVal.isValid() && "Initializer string is unknown or undefined");
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001861 DefinedOrUnknownSVal strLength
1862 = cast<DefinedOrUnknownSVal>(getCStringLength(C, state, Init, StrVal));
Jordy Rosea5261542010-08-14 21:02:52 +00001863
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001864 state = state->set<CStringLength>(MR, strLength);
Jordy Rosea5261542010-08-14 21:02:52 +00001865 }
1866
Anna Zaks0bd6b112011-10-26 21:06:34 +00001867 C.addTransition(state);
Jordy Rosea5261542010-08-14 21:02:52 +00001868}
1869
Ted Kremenek8bef8232012-01-26 21:29:00 +00001870bool CStringChecker::wantsRegionChangeUpdate(ProgramStateRef state) const {
Jordy Rosea5261542010-08-14 21:02:52 +00001871 CStringLength::EntryMap Entries = state->get<CStringLength>();
1872 return !Entries.isEmpty();
1873}
1874
Ted Kremenek8bef8232012-01-26 21:29:00 +00001875ProgramStateRef
1876CStringChecker::checkRegionChanges(ProgramStateRef state,
Ted Kremenek35bdbf42011-05-02 19:42:42 +00001877 const StoreManager::InvalidatedSymbols *,
Jordy Rose537716a2011-08-27 22:51:26 +00001878 ArrayRef<const MemRegion *> ExplicitRegions,
Anna Zaks66c40402012-02-14 21:55:24 +00001879 ArrayRef<const MemRegion *> Regions,
1880 const CallOrObjCMessage *Call) const {
Jordy Rosea5261542010-08-14 21:02:52 +00001881 CStringLength::EntryMap Entries = state->get<CStringLength>();
1882 if (Entries.isEmpty())
1883 return state;
1884
1885 llvm::SmallPtrSet<const MemRegion *, 8> Invalidated;
1886 llvm::SmallPtrSet<const MemRegion *, 32> SuperRegions;
1887
1888 // First build sets for the changed regions and their super-regions.
Jordy Rose537716a2011-08-27 22:51:26 +00001889 for (ArrayRef<const MemRegion *>::iterator
1890 I = Regions.begin(), E = Regions.end(); I != E; ++I) {
1891 const MemRegion *MR = *I;
Jordy Rosea5261542010-08-14 21:02:52 +00001892 Invalidated.insert(MR);
1893
1894 SuperRegions.insert(MR);
1895 while (const SubRegion *SR = dyn_cast<SubRegion>(MR)) {
1896 MR = SR->getSuperRegion();
1897 SuperRegions.insert(MR);
1898 }
1899 }
1900
1901 CStringLength::EntryMap::Factory &F = state->get_context<CStringLength>();
1902
1903 // Then loop over the entries in the current state.
1904 for (CStringLength::EntryMap::iterator I = Entries.begin(),
1905 E = Entries.end(); I != E; ++I) {
1906 const MemRegion *MR = I.getKey();
1907
1908 // Is this entry for a super-region of a changed region?
1909 if (SuperRegions.count(MR)) {
Ted Kremenek3baf6722010-11-24 00:54:37 +00001910 Entries = F.remove(Entries, MR);
Jordy Rosea5261542010-08-14 21:02:52 +00001911 continue;
1912 }
1913
1914 // Is this entry for a sub-region of a changed region?
1915 const MemRegion *Super = MR;
1916 while (const SubRegion *SR = dyn_cast<SubRegion>(Super)) {
1917 Super = SR->getSuperRegion();
1918 if (Invalidated.count(Super)) {
Ted Kremenek3baf6722010-11-24 00:54:37 +00001919 Entries = F.remove(Entries, MR);
Jordy Rosea5261542010-08-14 21:02:52 +00001920 break;
1921 }
1922 }
1923 }
1924
1925 return state->set<CStringLength>(Entries);
1926}
1927
Ted Kremenek8bef8232012-01-26 21:29:00 +00001928void CStringChecker::checkLiveSymbols(ProgramStateRef state,
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +00001929 SymbolReaper &SR) const {
Jordy Rosea5261542010-08-14 21:02:52 +00001930 // Mark all symbols in our string length map as valid.
1931 CStringLength::EntryMap Entries = state->get<CStringLength>();
1932
1933 for (CStringLength::EntryMap::iterator I = Entries.begin(), E = Entries.end();
1934 I != E; ++I) {
1935 SVal Len = I.getData();
Jordy Rosed5af0e12011-06-15 05:52:56 +00001936
Anna Zaks1d1d5152011-12-06 23:12:33 +00001937 for (SymExpr::symbol_iterator si = Len.symbol_begin(),
1938 se = Len.symbol_end(); si != se; ++si)
Jordy Rosed5af0e12011-06-15 05:52:56 +00001939 SR.markInUse(*si);
Jordy Rosea5261542010-08-14 21:02:52 +00001940 }
1941}
1942
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +00001943void CStringChecker::checkDeadSymbols(SymbolReaper &SR,
1944 CheckerContext &C) const {
Jordy Rosea5261542010-08-14 21:02:52 +00001945 if (!SR.hasDeadSymbols())
1946 return;
1947
Ted Kremenek8bef8232012-01-26 21:29:00 +00001948 ProgramStateRef state = C.getState();
Jordy Rosea5261542010-08-14 21:02:52 +00001949 CStringLength::EntryMap Entries = state->get<CStringLength>();
1950 if (Entries.isEmpty())
1951 return;
1952
1953 CStringLength::EntryMap::Factory &F = state->get_context<CStringLength>();
1954 for (CStringLength::EntryMap::iterator I = Entries.begin(), E = Entries.end();
1955 I != E; ++I) {
1956 SVal Len = I.getData();
1957 if (SymbolRef Sym = Len.getAsSymbol()) {
1958 if (SR.isDead(Sym))
Ted Kremenek3baf6722010-11-24 00:54:37 +00001959 Entries = F.remove(Entries, I.getKey());
Jordy Rosea5261542010-08-14 21:02:52 +00001960 }
1961 }
1962
1963 state = state->set<CStringLength>(Entries);
Anna Zaks0bd6b112011-10-26 21:06:34 +00001964 C.addTransition(state);
Jordy Rosea5261542010-08-14 21:02:52 +00001965}
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +00001966
Anna Zaks57300762012-02-07 00:56:14 +00001967#define REGISTER_CHECKER(name) \
1968void ento::register##name(CheckerManager &mgr) {\
1969 static CStringChecker *TheChecker = 0; \
1970 if (TheChecker == 0) \
1971 TheChecker = mgr.registerChecker<CStringChecker>(); \
1972 TheChecker->Filter.Check##name = true; \
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +00001973}
Anna Zaks57300762012-02-07 00:56:14 +00001974
1975REGISTER_CHECKER(CStringNullArg)
1976REGISTER_CHECKER(CStringOutOfBounds)
1977REGISTER_CHECKER(CStringBufferOverlap)
1978REGISTER_CHECKER(CStringNotNullTerm)
Anna Zaksf0dfc9c2012-02-17 22:35:31 +00001979
1980void ento::registerCStringCheckerBasic(CheckerManager &Mgr) {
1981 registerCStringNullArg(Mgr);
1982}