blob: 5ca813bcfd6923f4f7e0513e4a61f84b2b745f9d [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"
Argyrios Kyrtzidisec8605f2011-03-01 01:16:21 +000016#include "clang/StaticAnalyzer/Core/Checker.h"
Argyrios Kyrtzidis695fb502011-02-17 21:39:17 +000017#include "clang/StaticAnalyzer/Core/CheckerManager.h"
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +000018#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
Ted Kremenek9b663712011-02-10 01:03:03 +000019#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
Ted Kremenek18c66fd2011-08-15 22:09:50 +000020#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
Benjamin Kramer8fe83e12012-02-04 13:45:25 +000021#include "llvm/ADT/SmallString.h"
Benjamin Kramer00bd44d2012-02-04 12:31:12 +000022#include "llvm/ADT/STLExtras.h"
Jordy Roseccbf7ee2010-07-06 23:11:01 +000023#include "llvm/ADT/StringSwitch.h"
24
25using namespace clang;
Ted Kremenek9ef65372010-12-23 07:20:52 +000026using namespace ento;
Jordy Roseccbf7ee2010-07-06 23:11:01 +000027
28namespace {
Argyrios Kyrtzidisec8605f2011-03-01 01:16:21 +000029class CStringChecker : public Checker< eval::Call,
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +000030 check::PreStmt<DeclStmt>,
31 check::LiveSymbols,
32 check::DeadSymbols,
33 check::RegionChanges
34 > {
Anna Zaks57300762012-02-07 00:56:14 +000035 mutable OwningPtr<BugType> BT_Null,
36 BT_Bounds,
37 BT_Overlap,
38 BT_NotCString,
39 BT_AdditionOverflow;
40
Jordy Rose9e49d9f2011-06-20 02:06:40 +000041 mutable const char *CurrentFunctionDescription;
42
Jordy Roseccbf7ee2010-07-06 23:11:01 +000043public:
Anna Zaks57300762012-02-07 00:56:14 +000044 /// The filter is used to filter out the diagnostics which are not enabled by
45 /// the user.
46 struct CStringChecksFilter {
47 DefaultBool CheckCStringNullArg;
48 DefaultBool CheckCStringOutOfBounds;
49 DefaultBool CheckCStringBufferOverlap;
50 DefaultBool CheckCStringNotNullTerm;
51 };
52
53 CStringChecksFilter Filter;
54
Jordy Roseccbf7ee2010-07-06 23:11:01 +000055 static void *getTag() { static int tag; return &tag; }
56
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +000057 bool evalCall(const CallExpr *CE, CheckerContext &C) const;
58 void checkPreStmt(const DeclStmt *DS, CheckerContext &C) const;
Ted Kremenek8bef8232012-01-26 21:29:00 +000059 void checkLiveSymbols(ProgramStateRef state, SymbolReaper &SR) const;
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +000060 void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
Ted Kremenek8bef8232012-01-26 21:29:00 +000061 bool wantsRegionChangeUpdate(ProgramStateRef state) const;
Jordy Rosea5261542010-08-14 21:02:52 +000062
Ted Kremenek8bef8232012-01-26 21:29:00 +000063 ProgramStateRef
64 checkRegionChanges(ProgramStateRef state,
Ted Kremenek18c66fd2011-08-15 22:09:50 +000065 const StoreManager::InvalidatedSymbols *,
Jordy Rose537716a2011-08-27 22:51:26 +000066 ArrayRef<const MemRegion *> ExplicitRegions,
Anna Zaks66c40402012-02-14 21:55:24 +000067 ArrayRef<const MemRegion *> Regions,
68 const CallOrObjCMessage *Call) const;
Jordy Roseccbf7ee2010-07-06 23:11:01 +000069
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +000070 typedef void (CStringChecker::*FnCheck)(CheckerContext &,
71 const CallExpr *) const;
Jordy Roseccbf7ee2010-07-06 23:11:01 +000072
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +000073 void evalMemcpy(CheckerContext &C, const CallExpr *CE) const;
Lenny Maioranib8b875b2011-03-31 21:36:53 +000074 void evalMempcpy(CheckerContext &C, const CallExpr *CE) const;
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +000075 void evalMemmove(CheckerContext &C, const CallExpr *CE) const;
76 void evalBcopy(CheckerContext &C, const CallExpr *CE) const;
Lenny Maioranib8b875b2011-03-31 21:36:53 +000077 void evalCopyCommon(CheckerContext &C, const CallExpr *CE,
Ted Kremenek8bef8232012-01-26 21:29:00 +000078 ProgramStateRef state,
Ted Kremenek18c66fd2011-08-15 22:09:50 +000079 const Expr *Size,
80 const Expr *Source,
81 const Expr *Dest,
Lenny Maioranib8b875b2011-03-31 21:36:53 +000082 bool Restricted = false,
83 bool IsMempcpy = false) const;
Jordy Rosed325ffb2010-07-08 23:57:29 +000084
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +000085 void evalMemcmp(CheckerContext &C, const CallExpr *CE) const;
Jordy Roseccbf7ee2010-07-06 23:11:01 +000086
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +000087 void evalstrLength(CheckerContext &C, const CallExpr *CE) const;
88 void evalstrnLength(CheckerContext &C, const CallExpr *CE) const;
Ted Kremenek18c66fd2011-08-15 22:09:50 +000089 void evalstrLengthCommon(CheckerContext &C,
90 const CallExpr *CE,
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +000091 bool IsStrnlen = false) const;
Jordy Rose19c5dd12010-07-27 01:37:31 +000092
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +000093 void evalStrcpy(CheckerContext &C, const CallExpr *CE) const;
94 void evalStrncpy(CheckerContext &C, const CallExpr *CE) const;
95 void evalStpcpy(CheckerContext &C, const CallExpr *CE) const;
Ted Kremenek18c66fd2011-08-15 22:09:50 +000096 void evalStrcpyCommon(CheckerContext &C,
97 const CallExpr *CE,
98 bool returnEnd,
99 bool isBounded,
100 bool isAppending) const;
Lenny Maiorani067bbd02011-04-09 15:12:58 +0000101
102 void evalStrcat(CheckerContext &C, const CallExpr *CE) const;
103 void evalStrncat(CheckerContext &C, const CallExpr *CE) const;
Jordy Rosee64f3112010-08-16 07:51:42 +0000104
Lenny Maiorani318dd922011-04-12 17:08:43 +0000105 void evalStrcmp(CheckerContext &C, const CallExpr *CE) const;
Lenny Maiorani357f6ee2011-04-25 22:21:00 +0000106 void evalStrncmp(CheckerContext &C, const CallExpr *CE) const;
Lenny Maioranibd1d16a2011-04-28 15:09:11 +0000107 void evalStrcasecmp(CheckerContext &C, const CallExpr *CE) const;
Lenny Maiorani454fd2d2011-05-02 19:05:49 +0000108 void evalStrncasecmp(CheckerContext &C, const CallExpr *CE) const;
Ted Kremenek18c66fd2011-08-15 22:09:50 +0000109 void evalStrcmpCommon(CheckerContext &C,
110 const CallExpr *CE,
111 bool isBounded = false,
112 bool ignoreCase = false) const;
Lenny Maiorani318dd922011-04-12 17:08:43 +0000113
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000114 // Utility methods
Ted Kremenek8bef8232012-01-26 21:29:00 +0000115 std::pair<ProgramStateRef , ProgramStateRef >
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +0000116 static assumeZero(CheckerContext &C,
Ted Kremenek8bef8232012-01-26 21:29:00 +0000117 ProgramStateRef state, SVal V, QualType Ty);
Jordy Rosed325ffb2010-07-08 23:57:29 +0000118
Ted Kremenek8bef8232012-01-26 21:29:00 +0000119 static ProgramStateRef setCStringLength(ProgramStateRef state,
Ted Kremenek18c66fd2011-08-15 22:09:50 +0000120 const MemRegion *MR,
121 SVal strLength);
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +0000122 static SVal getCStringLengthForRegion(CheckerContext &C,
Ted Kremenek8bef8232012-01-26 21:29:00 +0000123 ProgramStateRef &state,
Ted Kremenek18c66fd2011-08-15 22:09:50 +0000124 const Expr *Ex,
125 const MemRegion *MR,
Jordy Rosed5af0e12011-06-15 05:52:56 +0000126 bool hypothetical);
Ted Kremenek18c66fd2011-08-15 22:09:50 +0000127 SVal getCStringLength(CheckerContext &C,
Ted Kremenek8bef8232012-01-26 21:29:00 +0000128 ProgramStateRef &state,
Ted Kremenek18c66fd2011-08-15 22:09:50 +0000129 const Expr *Ex,
130 SVal Buf,
Jordy Rosed5af0e12011-06-15 05:52:56 +0000131 bool hypothetical = false) const;
Jordy Rose19c5dd12010-07-27 01:37:31 +0000132
Lenny Maiorani318dd922011-04-12 17:08:43 +0000133 const StringLiteral *getCStringLiteral(CheckerContext &C,
Ted Kremenek8bef8232012-01-26 21:29:00 +0000134 ProgramStateRef &state,
Lenny Maiorani318dd922011-04-12 17:08:43 +0000135 const Expr *expr,
136 SVal val) const;
137
Ted Kremenek8bef8232012-01-26 21:29:00 +0000138 static ProgramStateRef InvalidateBuffer(CheckerContext &C,
139 ProgramStateRef state,
Ted Kremenek18c66fd2011-08-15 22:09:50 +0000140 const Expr *Ex, SVal V);
Jordy Rosee64f3112010-08-16 07:51:42 +0000141
Ted Kremenek9c378f72011-08-12 23:37:29 +0000142 static bool SummarizeRegion(raw_ostream &os, ASTContext &Ctx,
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +0000143 const MemRegion *MR);
Jordy Rose19c5dd12010-07-27 01:37:31 +0000144
145 // Re-usable checks
Ted Kremenek8bef8232012-01-26 21:29:00 +0000146 ProgramStateRef checkNonNull(CheckerContext &C,
147 ProgramStateRef state,
Ted Kremenek18c66fd2011-08-15 22:09:50 +0000148 const Expr *S,
149 SVal l) const;
Ted Kremenek8bef8232012-01-26 21:29:00 +0000150 ProgramStateRef CheckLocation(CheckerContext &C,
151 ProgramStateRef state,
Ted Kremenek18c66fd2011-08-15 22:09:50 +0000152 const Expr *S,
153 SVal l,
154 const char *message = NULL) const;
Ted Kremenek8bef8232012-01-26 21:29:00 +0000155 ProgramStateRef CheckBufferAccess(CheckerContext &C,
156 ProgramStateRef state,
Ted Kremenek18c66fd2011-08-15 22:09:50 +0000157 const Expr *Size,
158 const Expr *FirstBuf,
159 const Expr *SecondBuf,
160 const char *firstMessage = NULL,
161 const char *secondMessage = NULL,
162 bool WarnAboutSize = false) const;
163
Ted Kremenek8bef8232012-01-26 21:29:00 +0000164 ProgramStateRef CheckBufferAccess(CheckerContext &C,
165 ProgramStateRef state,
Ted Kremenek18c66fd2011-08-15 22:09:50 +0000166 const Expr *Size,
167 const Expr *Buf,
168 const char *message = NULL,
169 bool WarnAboutSize = false) const {
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000170 // This is a convenience override.
Jordy Rose5e5f1502011-06-20 03:49:16 +0000171 return CheckBufferAccess(C, state, Size, Buf, NULL, message, NULL,
172 WarnAboutSize);
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000173 }
Ted Kremenek8bef8232012-01-26 21:29:00 +0000174 ProgramStateRef CheckOverlap(CheckerContext &C,
175 ProgramStateRef state,
Ted Kremenek18c66fd2011-08-15 22:09:50 +0000176 const Expr *Size,
177 const Expr *First,
178 const Expr *Second) const;
179 void emitOverlapBug(CheckerContext &C,
Ted Kremenek8bef8232012-01-26 21:29:00 +0000180 ProgramStateRef state,
Ted Kremenek18c66fd2011-08-15 22:09:50 +0000181 const Stmt *First,
182 const Stmt *Second) const;
183
Ted Kremenek8bef8232012-01-26 21:29:00 +0000184 ProgramStateRef checkAdditionOverflow(CheckerContext &C,
185 ProgramStateRef state,
Ted Kremenek18c66fd2011-08-15 22:09:50 +0000186 NonLoc left,
187 NonLoc right) const;
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000188};
Jordy Rosea5261542010-08-14 21:02:52 +0000189
190class CStringLength {
191public:
192 typedef llvm::ImmutableMap<const MemRegion *, SVal> EntryMap;
193};
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000194} //end anonymous namespace
195
Jordy Rosea5261542010-08-14 21:02:52 +0000196namespace clang {
Ted Kremenek9ef65372010-12-23 07:20:52 +0000197namespace ento {
Jordy Rosea5261542010-08-14 21:02:52 +0000198 template <>
Ted Kremenek18c66fd2011-08-15 22:09:50 +0000199 struct ProgramStateTrait<CStringLength>
200 : public ProgramStatePartialTrait<CStringLength::EntryMap> {
Jordy Rosea5261542010-08-14 21:02:52 +0000201 static void *GDMIndex() { return CStringChecker::getTag(); }
202 };
203}
Argyrios Kyrtzidis5a4f98f2010-12-22 18:53:20 +0000204}
Jordy Rosea5261542010-08-14 21:02:52 +0000205
Jordy Rosed325ffb2010-07-08 23:57:29 +0000206//===----------------------------------------------------------------------===//
207// Individual checks and utility methods.
208//===----------------------------------------------------------------------===//
209
Ted Kremenek8bef8232012-01-26 21:29:00 +0000210std::pair<ProgramStateRef , ProgramStateRef >
211CStringChecker::assumeZero(CheckerContext &C, ProgramStateRef state, SVal V,
Jordy Rosed325ffb2010-07-08 23:57:29 +0000212 QualType Ty) {
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000213 DefinedSVal *val = dyn_cast<DefinedSVal>(&V);
214 if (!val)
Ted Kremenek8bef8232012-01-26 21:29:00 +0000215 return std::pair<ProgramStateRef , ProgramStateRef >(state, state);
Jordy Rosea6b808c2010-07-07 07:48:06 +0000216
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000217 SValBuilder &svalBuilder = C.getSValBuilder();
218 DefinedOrUnknownSVal zero = svalBuilder.makeZeroVal(Ty);
219 return state->assume(svalBuilder.evalEQ(state, *val, zero));
Jordy Rosed325ffb2010-07-08 23:57:29 +0000220}
Jordy Rosea6b808c2010-07-07 07:48:06 +0000221
Ted Kremenek8bef8232012-01-26 21:29:00 +0000222ProgramStateRef CStringChecker::checkNonNull(CheckerContext &C,
223 ProgramStateRef state,
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +0000224 const Expr *S, SVal l) const {
Jordy Rosed325ffb2010-07-08 23:57:29 +0000225 // If a previous check has failed, propagate the failure.
226 if (!state)
227 return NULL;
228
Ted Kremenek8bef8232012-01-26 21:29:00 +0000229 ProgramStateRef stateNull, stateNonNull;
Ted Kremenek28f47b92010-12-01 22:16:56 +0000230 llvm::tie(stateNull, stateNonNull) = assumeZero(C, state, l, S->getType());
Jordy Rosed325ffb2010-07-08 23:57:29 +0000231
232 if (stateNull && !stateNonNull) {
Anna Zaks57300762012-02-07 00:56:14 +0000233 if (!Filter.CheckCStringNullArg)
234 return NULL;
235
Ted Kremenekd048c6e2010-12-20 21:19:09 +0000236 ExplodedNode *N = C.generateSink(stateNull);
Jordy Rosea6b808c2010-07-07 07:48:06 +0000237 if (!N)
238 return NULL;
239
Jordy Rosed325ffb2010-07-08 23:57:29 +0000240 if (!BT_Null)
Anna Zaks57300762012-02-07 00:56:14 +0000241 BT_Null.reset(new BuiltinBug("Unix API",
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +0000242 "Null pointer argument in call to byte string function"));
Jordy Rosea6b808c2010-07-07 07:48:06 +0000243
Dylan Noblesmithf7ccbad2012-02-05 02:13:05 +0000244 SmallString<80> buf;
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000245 llvm::raw_svector_ostream os(buf);
246 assert(CurrentFunctionDescription);
247 os << "Null pointer argument in call to " << CurrentFunctionDescription;
248
Jordy Rosea6b808c2010-07-07 07:48:06 +0000249 // Generate a report for this bug.
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +0000250 BuiltinBug *BT = static_cast<BuiltinBug*>(BT_Null.get());
Anna Zakse172e8b2011-08-17 23:00:25 +0000251 BugReport *report = new BugReport(*BT, os.str(), N);
Jordy Rosea6b808c2010-07-07 07:48:06 +0000252
253 report->addRange(S->getSourceRange());
Anna Zaks50bbc162011-08-19 22:33:38 +0000254 report->addVisitor(bugreporter::getTrackNullOrUndefValueVisitor(N, S));
Jordy Rosea6b808c2010-07-07 07:48:06 +0000255 C.EmitReport(report);
256 return NULL;
257 }
258
259 // From here on, assume that the value is non-null.
Jordy Rosed325ffb2010-07-08 23:57:29 +0000260 assert(stateNonNull);
261 return stateNonNull;
Jordy Rosea6b808c2010-07-07 07:48:06 +0000262}
263
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000264// FIXME: This was originally copied from ArrayBoundChecker.cpp. Refactor?
Ted Kremenek8bef8232012-01-26 21:29:00 +0000265ProgramStateRef CStringChecker::CheckLocation(CheckerContext &C,
266 ProgramStateRef state,
Jordy Rosee64f3112010-08-16 07:51:42 +0000267 const Expr *S, SVal l,
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000268 const char *warningMsg) const {
Jordy Rosed325ffb2010-07-08 23:57:29 +0000269 // If a previous check has failed, propagate the failure.
270 if (!state)
271 return NULL;
272
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000273 // Check for out of bound array element access.
274 const MemRegion *R = l.getAsRegion();
275 if (!R)
276 return state;
277
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000278 const ElementRegion *ER = dyn_cast<ElementRegion>(R);
279 if (!ER)
280 return state;
281
Zhongxing Xu018220c2010-08-11 06:10:55 +0000282 assert(ER->getValueType() == C.getASTContext().CharTy &&
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000283 "CheckLocation should only be called with char* ElementRegions");
284
285 // Get the size of the array.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000286 const SubRegion *superReg = cast<SubRegion>(ER->getSuperRegion());
287 SValBuilder &svalBuilder = C.getSValBuilder();
Jordy Rose1e022412011-06-16 05:51:02 +0000288 SVal Extent =
289 svalBuilder.convertToArrayIndex(superReg->getExtent(svalBuilder));
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000290 DefinedOrUnknownSVal Size = cast<DefinedOrUnknownSVal>(Extent);
291
292 // Get the index of the accessed element.
Gabor Greif89b06582010-09-09 10:51:37 +0000293 DefinedOrUnknownSVal Idx = cast<DefinedOrUnknownSVal>(ER->getIndex());
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000294
Ted Kremenek8bef8232012-01-26 21:29:00 +0000295 ProgramStateRef StInBound = state->assumeInBound(Idx, Size, true);
296 ProgramStateRef StOutBound = state->assumeInBound(Idx, Size, false);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000297 if (StOutBound && !StInBound) {
Ted Kremenekd048c6e2010-12-20 21:19:09 +0000298 ExplodedNode *N = C.generateSink(StOutBound);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000299 if (!N)
300 return NULL;
301
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000302 if (!BT_Bounds) {
303 BT_Bounds.reset(new BuiltinBug("Out-of-bound array access",
304 "Byte string function accesses out-of-bound array element"));
305 }
306 BuiltinBug *BT = static_cast<BuiltinBug*>(BT_Bounds.get());
307
308 // Generate a report for this bug.
Anna Zakse172e8b2011-08-17 23:00:25 +0000309 BugReport *report;
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000310 if (warningMsg) {
Anna Zakse172e8b2011-08-17 23:00:25 +0000311 report = new BugReport(*BT, warningMsg, N);
Jordy Rosee64f3112010-08-16 07:51:42 +0000312 } else {
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000313 assert(CurrentFunctionDescription);
314 assert(CurrentFunctionDescription[0] != '\0');
315
Dylan Noblesmithf7ccbad2012-02-05 02:13:05 +0000316 SmallString<80> buf;
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000317 llvm::raw_svector_ostream os(buf);
318 os << (char)toupper(CurrentFunctionDescription[0])
319 << &CurrentFunctionDescription[1]
320 << " accesses out-of-bound array element";
Anna Zakse172e8b2011-08-17 23:00:25 +0000321 report = new BugReport(*BT, os.str(), N);
Jordy Rosee64f3112010-08-16 07:51:42 +0000322 }
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000323
324 // FIXME: It would be nice to eventually make this diagnostic more clear,
325 // e.g., by referencing the original declaration or by saying *why* this
326 // reference is outside the range.
327
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000328 report->addRange(S->getSourceRange());
329 C.EmitReport(report);
330 return NULL;
331 }
332
333 // Array bound check succeeded. From this point forward the array bound
334 // should always succeed.
335 return StInBound;
336}
337
Ted Kremenek8bef8232012-01-26 21:29:00 +0000338ProgramStateRef CStringChecker::CheckBufferAccess(CheckerContext &C,
339 ProgramStateRef state,
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000340 const Expr *Size,
341 const Expr *FirstBuf,
Jordy Rosee64f3112010-08-16 07:51:42 +0000342 const Expr *SecondBuf,
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000343 const char *firstMessage,
Jordy Rose5e5f1502011-06-20 03:49:16 +0000344 const char *secondMessage,
345 bool WarnAboutSize) const {
Jordy Rosed325ffb2010-07-08 23:57:29 +0000346 // If a previous check has failed, propagate the failure.
347 if (!state)
348 return NULL;
349
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000350 SValBuilder &svalBuilder = C.getSValBuilder();
Jordy Rose1e022412011-06-16 05:51:02 +0000351 ASTContext &Ctx = svalBuilder.getContext();
Ted Kremenek5eca4822012-01-06 22:09:28 +0000352 const LocationContext *LCtx = C.getLocationContext();
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000353
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000354 QualType sizeTy = Size->getType();
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000355 QualType PtrTy = Ctx.getPointerType(Ctx.CharTy);
356
Jordy Rosea6b808c2010-07-07 07:48:06 +0000357 // Check that the first buffer is non-null.
Ted Kremenek5eca4822012-01-06 22:09:28 +0000358 SVal BufVal = state->getSVal(FirstBuf, LCtx);
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000359 state = checkNonNull(C, state, FirstBuf, BufVal);
Jordy Rosea6b808c2010-07-07 07:48:06 +0000360 if (!state)
361 return NULL;
362
Anna Zaks57300762012-02-07 00:56:14 +0000363 // If out-of-bounds checking is turned off, skip the rest.
364 if (!Filter.CheckCStringOutOfBounds)
365 return state;
366
Jordy Rosed325ffb2010-07-08 23:57:29 +0000367 // Get the access length and make sure it is known.
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000368 // FIXME: This assumes the caller has already checked that the access length
369 // is positive. And that it's unsigned.
Ted Kremenek5eca4822012-01-06 22:09:28 +0000370 SVal LengthVal = state->getSVal(Size, LCtx);
Jordy Rosed325ffb2010-07-08 23:57:29 +0000371 NonLoc *Length = dyn_cast<NonLoc>(&LengthVal);
372 if (!Length)
373 return state;
374
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000375 // Compute the offset of the last element to be accessed: size-1.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000376 NonLoc One = cast<NonLoc>(svalBuilder.makeIntVal(1, sizeTy));
377 NonLoc LastOffset = cast<NonLoc>(svalBuilder.evalBinOpNN(state, BO_Sub,
378 *Length, One, sizeTy));
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000379
Chris Lattnerfc8f0e12011-04-15 05:22:18 +0000380 // Check that the first buffer is sufficiently long.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000381 SVal BufStart = svalBuilder.evalCast(BufVal, PtrTy, FirstBuf->getType());
Jordy Roseb6a40262010-08-05 23:11:30 +0000382 if (Loc *BufLoc = dyn_cast<Loc>(&BufStart)) {
Jordy Rose5e5f1502011-06-20 03:49:16 +0000383 const Expr *warningExpr = (WarnAboutSize ? Size : FirstBuf);
384
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000385 SVal BufEnd = svalBuilder.evalBinOpLN(state, BO_Add, *BufLoc,
386 LastOffset, PtrTy);
Jordy Rose5e5f1502011-06-20 03:49:16 +0000387 state = CheckLocation(C, state, warningExpr, BufEnd, firstMessage);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000388
Jordy Roseb6a40262010-08-05 23:11:30 +0000389 // If the buffer isn't large enough, abort.
390 if (!state)
391 return NULL;
392 }
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000393
394 // If there's a second buffer, check it as well.
395 if (SecondBuf) {
Ted Kremenek5eca4822012-01-06 22:09:28 +0000396 BufVal = state->getSVal(SecondBuf, LCtx);
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000397 state = checkNonNull(C, state, SecondBuf, BufVal);
Jordy Rosea6b808c2010-07-07 07:48:06 +0000398 if (!state)
399 return NULL;
400
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000401 BufStart = svalBuilder.evalCast(BufVal, PtrTy, SecondBuf->getType());
Jordy Roseb6a40262010-08-05 23:11:30 +0000402 if (Loc *BufLoc = dyn_cast<Loc>(&BufStart)) {
Jordy Rose5e5f1502011-06-20 03:49:16 +0000403 const Expr *warningExpr = (WarnAboutSize ? Size : SecondBuf);
404
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000405 SVal BufEnd = svalBuilder.evalBinOpLN(state, BO_Add, *BufLoc,
406 LastOffset, PtrTy);
Jordy Rose5e5f1502011-06-20 03:49:16 +0000407 state = CheckLocation(C, state, warningExpr, BufEnd, secondMessage);
Jordy Roseb6a40262010-08-05 23:11:30 +0000408 }
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000409 }
410
411 // Large enough or not, return this state!
412 return state;
413}
414
Ted Kremenek8bef8232012-01-26 21:29:00 +0000415ProgramStateRef CStringChecker::CheckOverlap(CheckerContext &C,
416 ProgramStateRef state,
Jordy Rosed325ffb2010-07-08 23:57:29 +0000417 const Expr *Size,
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000418 const Expr *First,
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +0000419 const Expr *Second) const {
Anna Zaks57300762012-02-07 00:56:14 +0000420 if (!Filter.CheckCStringBufferOverlap)
421 return state;
422
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000423 // Do a simple check for overlap: if the two arguments are from the same
424 // buffer, see if the end of the first is greater than the start of the second
425 // or vice versa.
426
Jordy Rosed325ffb2010-07-08 23:57:29 +0000427 // If a previous check has failed, propagate the failure.
428 if (!state)
429 return NULL;
430
Ted Kremenek8bef8232012-01-26 21:29:00 +0000431 ProgramStateRef stateTrue, stateFalse;
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000432
433 // Get the buffer values and make sure they're known locations.
Ted Kremenek5eca4822012-01-06 22:09:28 +0000434 const LocationContext *LCtx = C.getLocationContext();
435 SVal firstVal = state->getSVal(First, LCtx);
436 SVal secondVal = state->getSVal(Second, LCtx);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000437
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000438 Loc *firstLoc = dyn_cast<Loc>(&firstVal);
439 if (!firstLoc)
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000440 return state;
441
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000442 Loc *secondLoc = dyn_cast<Loc>(&secondVal);
443 if (!secondLoc)
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000444 return state;
445
446 // Are the two values the same?
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000447 SValBuilder &svalBuilder = C.getSValBuilder();
448 llvm::tie(stateTrue, stateFalse) =
449 state->assume(svalBuilder.evalEQ(state, *firstLoc, *secondLoc));
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000450
451 if (stateTrue && !stateFalse) {
452 // If the values are known to be equal, that's automatically an overlap.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000453 emitOverlapBug(C, stateTrue, First, Second);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000454 return NULL;
455 }
456
Ted Kremenek28f47b92010-12-01 22:16:56 +0000457 // assume the two expressions are not equal.
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000458 assert(stateFalse);
459 state = stateFalse;
460
461 // Which value comes first?
Jordy Roseee2fde12011-06-16 05:56:50 +0000462 QualType cmpTy = svalBuilder.getConditionType();
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000463 SVal reverse = svalBuilder.evalBinOpLL(state, BO_GT,
464 *firstLoc, *secondLoc, cmpTy);
465 DefinedOrUnknownSVal *reverseTest = dyn_cast<DefinedOrUnknownSVal>(&reverse);
466 if (!reverseTest)
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000467 return state;
468
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000469 llvm::tie(stateTrue, stateFalse) = state->assume(*reverseTest);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000470 if (stateTrue) {
471 if (stateFalse) {
472 // If we don't know which one comes first, we can't perform this test.
473 return state;
474 } else {
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000475 // Switch the values so that firstVal is before secondVal.
476 Loc *tmpLoc = firstLoc;
477 firstLoc = secondLoc;
478 secondLoc = tmpLoc;
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000479
480 // Switch the Exprs as well, so that they still correspond.
481 const Expr *tmpExpr = First;
482 First = Second;
483 Second = tmpExpr;
484 }
485 }
486
487 // Get the length, and make sure it too is known.
Ted Kremenek5eca4822012-01-06 22:09:28 +0000488 SVal LengthVal = state->getSVal(Size, LCtx);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000489 NonLoc *Length = dyn_cast<NonLoc>(&LengthVal);
490 if (!Length)
491 return state;
492
493 // Convert the first buffer's start address to char*.
494 // Bail out if the cast fails.
Jordy Roseee2fde12011-06-16 05:56:50 +0000495 ASTContext &Ctx = svalBuilder.getContext();
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000496 QualType CharPtrTy = Ctx.getPointerType(Ctx.CharTy);
Jordy Rose1e022412011-06-16 05:51:02 +0000497 SVal FirstStart = svalBuilder.evalCast(*firstLoc, CharPtrTy,
498 First->getType());
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000499 Loc *FirstStartLoc = dyn_cast<Loc>(&FirstStart);
500 if (!FirstStartLoc)
501 return state;
502
503 // Compute the end of the first buffer. Bail out if THAT fails.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000504 SVal FirstEnd = svalBuilder.evalBinOpLN(state, BO_Add,
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000505 *FirstStartLoc, *Length, CharPtrTy);
506 Loc *FirstEndLoc = dyn_cast<Loc>(&FirstEnd);
507 if (!FirstEndLoc)
508 return state;
509
510 // Is the end of the first buffer past the start of the second buffer?
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000511 SVal Overlap = svalBuilder.evalBinOpLL(state, BO_GT,
512 *FirstEndLoc, *secondLoc, cmpTy);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000513 DefinedOrUnknownSVal *OverlapTest = dyn_cast<DefinedOrUnknownSVal>(&Overlap);
514 if (!OverlapTest)
515 return state;
516
Ted Kremenek28f47b92010-12-01 22:16:56 +0000517 llvm::tie(stateTrue, stateFalse) = state->assume(*OverlapTest);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000518
519 if (stateTrue && !stateFalse) {
520 // Overlap!
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000521 emitOverlapBug(C, stateTrue, First, Second);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000522 return NULL;
523 }
524
Ted Kremenek28f47b92010-12-01 22:16:56 +0000525 // assume the two expressions don't overlap.
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000526 assert(stateFalse);
527 return stateFalse;
528}
529
Ted Kremenek8bef8232012-01-26 21:29:00 +0000530void CStringChecker::emitOverlapBug(CheckerContext &C, ProgramStateRef state,
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +0000531 const Stmt *First, const Stmt *Second) const {
Ted Kremenekd048c6e2010-12-20 21:19:09 +0000532 ExplodedNode *N = C.generateSink(state);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000533 if (!N)
534 return;
535
536 if (!BT_Overlap)
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +0000537 BT_Overlap.reset(new BugType("Unix API", "Improper arguments"));
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000538
539 // Generate a report for this bug.
Anna Zakse172e8b2011-08-17 23:00:25 +0000540 BugReport *report =
541 new BugReport(*BT_Overlap,
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000542 "Arguments must not be overlapping buffers", N);
543 report->addRange(First->getSourceRange());
544 report->addRange(Second->getSourceRange());
545
546 C.EmitReport(report);
547}
548
Ted Kremenek8bef8232012-01-26 21:29:00 +0000549ProgramStateRef CStringChecker::checkAdditionOverflow(CheckerContext &C,
550 ProgramStateRef state,
Jordy Rosed5af0e12011-06-15 05:52:56 +0000551 NonLoc left,
552 NonLoc right) const {
Anna Zaks57300762012-02-07 00:56:14 +0000553 // If out-of-bounds checking is turned off, skip the rest.
554 if (!Filter.CheckCStringOutOfBounds)
555 return state;
556
Jordy Rosed5af0e12011-06-15 05:52:56 +0000557 // If a previous check has failed, propagate the failure.
558 if (!state)
559 return NULL;
560
561 SValBuilder &svalBuilder = C.getSValBuilder();
562 BasicValueFactory &BVF = svalBuilder.getBasicValueFactory();
563
564 QualType sizeTy = svalBuilder.getContext().getSizeType();
565 const llvm::APSInt &maxValInt = BVF.getMaxValue(sizeTy);
566 NonLoc maxVal = svalBuilder.makeIntVal(maxValInt);
567
Anna Zakse3d250e2011-12-11 18:43:40 +0000568 SVal maxMinusRight;
569 if (isa<nonloc::ConcreteInt>(right)) {
570 maxMinusRight = svalBuilder.evalBinOpNN(state, BO_Sub, maxVal, right,
571 sizeTy);
572 } else {
Jordy Rosed5af0e12011-06-15 05:52:56 +0000573 // Try switching the operands. (The order of these two assignments is
574 // important!)
575 maxMinusRight = svalBuilder.evalBinOpNN(state, BO_Sub, maxVal, left,
576 sizeTy);
577 left = right;
578 }
579
580 if (NonLoc *maxMinusRightNL = dyn_cast<NonLoc>(&maxMinusRight)) {
581 QualType cmpTy = svalBuilder.getConditionType();
582 // If left > max - right, we have an overflow.
583 SVal willOverflow = svalBuilder.evalBinOpNN(state, BO_GT, left,
584 *maxMinusRightNL, cmpTy);
585
Ted Kremenek8bef8232012-01-26 21:29:00 +0000586 ProgramStateRef stateOverflow, stateOkay;
Jordy Rosed5af0e12011-06-15 05:52:56 +0000587 llvm::tie(stateOverflow, stateOkay) =
588 state->assume(cast<DefinedOrUnknownSVal>(willOverflow));
589
590 if (stateOverflow && !stateOkay) {
591 // We have an overflow. Emit a bug report.
592 ExplodedNode *N = C.generateSink(stateOverflow);
593 if (!N)
594 return NULL;
595
596 if (!BT_AdditionOverflow)
597 BT_AdditionOverflow.reset(new BuiltinBug("API",
598 "Sum of expressions causes overflow"));
599
Jordy Rosed5af0e12011-06-15 05:52:56 +0000600 // This isn't a great error message, but this should never occur in real
601 // code anyway -- you'd have to create a buffer longer than a size_t can
602 // represent, which is sort of a contradiction.
Jordy Rose8cc24912011-06-20 03:51:53 +0000603 const char *warning =
604 "This expression will create a string whose length is too big to "
605 "be represented as a size_t";
Jordy Rosed5af0e12011-06-15 05:52:56 +0000606
607 // Generate a report for this bug.
Jordy Rose8cc24912011-06-20 03:51:53 +0000608 BugReport *report = new BugReport(*BT_AdditionOverflow, warning, N);
Jordy Rosed5af0e12011-06-15 05:52:56 +0000609 C.EmitReport(report);
610
611 return NULL;
612 }
613
614 // From now on, assume an overflow didn't occur.
615 assert(stateOkay);
616 state = stateOkay;
617 }
618
619 return state;
620}
621
Ted Kremenek8bef8232012-01-26 21:29:00 +0000622ProgramStateRef CStringChecker::setCStringLength(ProgramStateRef state,
Jordy Rosee64f3112010-08-16 07:51:42 +0000623 const MemRegion *MR,
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000624 SVal strLength) {
625 assert(!strLength.isUndef() && "Attempt to set an undefined string length");
Jordy Rosee64f3112010-08-16 07:51:42 +0000626
627 MR = MR->StripCasts();
628
629 switch (MR->getKind()) {
630 case MemRegion::StringRegionKind:
631 // FIXME: This can happen if we strcpy() into a string region. This is
632 // undefined [C99 6.4.5p6], but we should still warn about it.
633 return state;
634
635 case MemRegion::SymbolicRegionKind:
636 case MemRegion::AllocaRegionKind:
637 case MemRegion::VarRegionKind:
638 case MemRegion::FieldRegionKind:
639 case MemRegion::ObjCIvarRegionKind:
Jordy Rose210c05b2011-06-15 05:14:03 +0000640 // These are the types we can currently track string lengths for.
641 break;
Jordy Rosee64f3112010-08-16 07:51:42 +0000642
643 case MemRegion::ElementRegionKind:
644 // FIXME: Handle element regions by upper-bounding the parent region's
645 // string length.
646 return state;
647
648 default:
649 // Other regions (mostly non-data) can't have a reliable C string length.
650 // For now, just ignore the change.
651 // FIXME: These are rare but not impossible. We should output some kind of
652 // warning for things like strcpy((char[]){'a', 0}, "b");
653 return state;
654 }
Jordy Rose210c05b2011-06-15 05:14:03 +0000655
656 if (strLength.isUnknown())
657 return state->remove<CStringLength>(MR);
658
659 return state->set<CStringLength>(MR, strLength);
Jordy Rosee64f3112010-08-16 07:51:42 +0000660}
661
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000662SVal CStringChecker::getCStringLengthForRegion(CheckerContext &C,
Ted Kremenek8bef8232012-01-26 21:29:00 +0000663 ProgramStateRef &state,
Jordy Rosea5261542010-08-14 21:02:52 +0000664 const Expr *Ex,
Jordy Rosed5af0e12011-06-15 05:52:56 +0000665 const MemRegion *MR,
666 bool hypothetical) {
667 if (!hypothetical) {
668 // If there's a recorded length, go ahead and return it.
669 const SVal *Recorded = state->get<CStringLength>(MR);
670 if (Recorded)
671 return *Recorded;
672 }
Jordy Rosea5261542010-08-14 21:02:52 +0000673
674 // Otherwise, get a new symbol and update the state.
Anna Zaks5d0ea6d2011-10-04 20:43:05 +0000675 unsigned Count = C.getCurrentBlockCount();
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000676 SValBuilder &svalBuilder = C.getSValBuilder();
677 QualType sizeTy = svalBuilder.getContext().getSizeType();
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +0000678 SVal strLength = svalBuilder.getMetadataSymbolVal(CStringChecker::getTag(),
679 MR, Ex, sizeTy, Count);
Jordy Rosed5af0e12011-06-15 05:52:56 +0000680
681 if (!hypothetical)
682 state = state->set<CStringLength>(MR, strLength);
683
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000684 return strLength;
Jordy Rosea5261542010-08-14 21:02:52 +0000685}
686
Ted Kremenek8bef8232012-01-26 21:29:00 +0000687SVal CStringChecker::getCStringLength(CheckerContext &C, ProgramStateRef &state,
Jordy Rosed5af0e12011-06-15 05:52:56 +0000688 const Expr *Ex, SVal Buf,
689 bool hypothetical) const {
Jordy Rose19c5dd12010-07-27 01:37:31 +0000690 const MemRegion *MR = Buf.getAsRegion();
691 if (!MR) {
692 // If we can't get a region, see if it's something we /know/ isn't a
693 // C string. In the context of locations, the only time we can issue such
694 // a warning is for labels.
695 if (loc::GotoLabel *Label = dyn_cast<loc::GotoLabel>(&Buf)) {
Anna Zaks57300762012-02-07 00:56:14 +0000696 if (!Filter.CheckCStringNotNullTerm)
697 return UndefinedVal();
698
Anna Zaks0bd6b112011-10-26 21:06:34 +0000699 if (ExplodedNode *N = C.addTransition(state)) {
Jordy Rose19c5dd12010-07-27 01:37:31 +0000700 if (!BT_NotCString)
Anna Zaks57300762012-02-07 00:56:14 +0000701 BT_NotCString.reset(new BuiltinBug("Unix API",
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +0000702 "Argument is not a null-terminated string."));
Jordy Rose19c5dd12010-07-27 01:37:31 +0000703
Dylan Noblesmithf7ccbad2012-02-05 02:13:05 +0000704 SmallString<120> buf;
Jordy Rose19c5dd12010-07-27 01:37:31 +0000705 llvm::raw_svector_ostream os(buf);
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000706 assert(CurrentFunctionDescription);
707 os << "Argument to " << CurrentFunctionDescription
708 << " is the address of the label '" << Label->getLabel()->getName()
Jordy Rose19c5dd12010-07-27 01:37:31 +0000709 << "', which is not a null-terminated string";
710
711 // Generate a report for this bug.
Anna Zakse172e8b2011-08-17 23:00:25 +0000712 BugReport *report = new BugReport(*BT_NotCString,
Jordy Rose19c5dd12010-07-27 01:37:31 +0000713 os.str(), N);
714
715 report->addRange(Ex->getSourceRange());
716 C.EmitReport(report);
717 }
Jordy Rose19c5dd12010-07-27 01:37:31 +0000718 return UndefinedVal();
Anna Zaks57300762012-02-07 00:56:14 +0000719
Jordy Rose19c5dd12010-07-27 01:37:31 +0000720 }
721
Jordy Rosea5261542010-08-14 21:02:52 +0000722 // If it's not a region and not a label, give up.
723 return UnknownVal();
Jordy Rose19c5dd12010-07-27 01:37:31 +0000724 }
725
Jordy Rosea5261542010-08-14 21:02:52 +0000726 // If we have a region, strip casts from it and see if we can figure out
727 // its length. For anything we can't figure out, just return UnknownVal.
728 MR = MR->StripCasts();
729
730 switch (MR->getKind()) {
731 case MemRegion::StringRegionKind: {
732 // Modifying the contents of string regions is undefined [C99 6.4.5p6],
733 // so we can assume that the byte length is the correct C string length.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000734 SValBuilder &svalBuilder = C.getSValBuilder();
735 QualType sizeTy = svalBuilder.getContext().getSizeType();
736 const StringLiteral *strLit = cast<StringRegion>(MR)->getStringLiteral();
737 return svalBuilder.makeIntVal(strLit->getByteLength(), sizeTy);
Jordy Rosea5261542010-08-14 21:02:52 +0000738 }
739 case MemRegion::SymbolicRegionKind:
740 case MemRegion::AllocaRegionKind:
741 case MemRegion::VarRegionKind:
742 case MemRegion::FieldRegionKind:
743 case MemRegion::ObjCIvarRegionKind:
Jordy Rosed5af0e12011-06-15 05:52:56 +0000744 return getCStringLengthForRegion(C, state, Ex, MR, hypothetical);
Jordy Rosea5261542010-08-14 21:02:52 +0000745 case MemRegion::CompoundLiteralRegionKind:
746 // FIXME: Can we track this? Is it necessary?
747 return UnknownVal();
748 case MemRegion::ElementRegionKind:
749 // FIXME: How can we handle this? It's not good enough to subtract the
750 // offset from the base string length; consider "123\x00567" and &a[5].
751 return UnknownVal();
752 default:
753 // Other regions (mostly non-data) can't have a reliable C string length.
754 // In this case, an error is emitted and UndefinedVal is returned.
755 // The caller should always be prepared to handle this case.
Anna Zaks57300762012-02-07 00:56:14 +0000756 if (!Filter.CheckCStringNotNullTerm)
757 return UndefinedVal();
758
Anna Zaks0bd6b112011-10-26 21:06:34 +0000759 if (ExplodedNode *N = C.addTransition(state)) {
Jordy Rosea5261542010-08-14 21:02:52 +0000760 if (!BT_NotCString)
Anna Zaks57300762012-02-07 00:56:14 +0000761 BT_NotCString.reset(new BuiltinBug("Unix API",
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +0000762 "Argument is not a null-terminated string."));
Jordy Rosea5261542010-08-14 21:02:52 +0000763
Dylan Noblesmithf7ccbad2012-02-05 02:13:05 +0000764 SmallString<120> buf;
Jordy Rosea5261542010-08-14 21:02:52 +0000765 llvm::raw_svector_ostream os(buf);
766
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000767 assert(CurrentFunctionDescription);
768 os << "Argument to " << CurrentFunctionDescription << " is ";
Jordy Rosea5261542010-08-14 21:02:52 +0000769
770 if (SummarizeRegion(os, C.getASTContext(), MR))
771 os << ", which is not a null-terminated string";
772 else
773 os << "not a null-terminated string";
774
775 // Generate a report for this bug.
Anna Zakse172e8b2011-08-17 23:00:25 +0000776 BugReport *report = new BugReport(*BT_NotCString,
Jordy Rosea5261542010-08-14 21:02:52 +0000777 os.str(), N);
778
779 report->addRange(Ex->getSourceRange());
780 C.EmitReport(report);
781 }
782
783 return UndefinedVal();
784 }
Jordy Rose19c5dd12010-07-27 01:37:31 +0000785}
786
Lenny Maiorani318dd922011-04-12 17:08:43 +0000787const StringLiteral *CStringChecker::getCStringLiteral(CheckerContext &C,
Ted Kremenek8bef8232012-01-26 21:29:00 +0000788 ProgramStateRef &state, const Expr *expr, SVal val) const {
Lenny Maiorani318dd922011-04-12 17:08:43 +0000789
790 // Get the memory region pointed to by the val.
791 const MemRegion *bufRegion = val.getAsRegion();
792 if (!bufRegion)
793 return NULL;
794
795 // Strip casts off the memory region.
796 bufRegion = bufRegion->StripCasts();
797
798 // Cast the memory region to a string region.
799 const StringRegion *strRegion= dyn_cast<StringRegion>(bufRegion);
800 if (!strRegion)
801 return NULL;
802
803 // Return the actual string in the string region.
804 return strRegion->getStringLiteral();
805}
806
Ted Kremenek8bef8232012-01-26 21:29:00 +0000807ProgramStateRef CStringChecker::InvalidateBuffer(CheckerContext &C,
808 ProgramStateRef state,
Jordy Rosee64f3112010-08-16 07:51:42 +0000809 const Expr *E, SVal V) {
810 Loc *L = dyn_cast<Loc>(&V);
811 if (!L)
812 return state;
813
814 // FIXME: This is a simplified version of what's in CFRefCount.cpp -- it makes
815 // some assumptions about the value that CFRefCount can't. Even so, it should
816 // probably be refactored.
817 if (loc::MemRegionVal* MR = dyn_cast<loc::MemRegionVal>(L)) {
818 const MemRegion *R = MR->getRegion()->StripCasts();
819
820 // Are we dealing with an ElementRegion? If so, we should be invalidating
821 // the super-region.
822 if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
823 R = ER->getSuperRegion();
824 // FIXME: What about layers of ElementRegions?
825 }
826
827 // Invalidate this region.
Anna Zaks5d0ea6d2011-10-04 20:43:05 +0000828 unsigned Count = C.getCurrentBlockCount();
Jordy Rose537716a2011-08-27 22:51:26 +0000829 return state->invalidateRegions(R, E, Count);
Jordy Rosee64f3112010-08-16 07:51:42 +0000830 }
831
832 // If we have a non-region value by chance, just remove the binding.
833 // FIXME: is this necessary or correct? This handles the non-Region
834 // cases. Is it ever valid to store to these?
835 return state->unbindLoc(*L);
836}
837
Ted Kremenek9c378f72011-08-12 23:37:29 +0000838bool CStringChecker::SummarizeRegion(raw_ostream &os, ASTContext &Ctx,
Jordy Rose19c5dd12010-07-27 01:37:31 +0000839 const MemRegion *MR) {
Ted Kremenek96979342011-08-12 20:02:48 +0000840 const TypedValueRegion *TVR = dyn_cast<TypedValueRegion>(MR);
Jordy Rose19c5dd12010-07-27 01:37:31 +0000841
Jordy Rose096aef92011-08-12 21:41:07 +0000842 switch (MR->getKind()) {
Jordy Rose19c5dd12010-07-27 01:37:31 +0000843 case MemRegion::FunctionTextRegionKind: {
Jordy Rose096aef92011-08-12 21:41:07 +0000844 const FunctionDecl *FD = cast<FunctionTextRegion>(MR)->getDecl();
Jordy Rose19c5dd12010-07-27 01:37:31 +0000845 if (FD)
Benjamin Kramerb8989f22011-10-14 18:45:37 +0000846 os << "the address of the function '" << *FD << '\'';
Jordy Rose19c5dd12010-07-27 01:37:31 +0000847 else
848 os << "the address of a function";
849 return true;
850 }
851 case MemRegion::BlockTextRegionKind:
852 os << "block text";
853 return true;
854 case MemRegion::BlockDataRegionKind:
855 os << "a block";
856 return true;
857 case MemRegion::CXXThisRegionKind:
Zhongxing Xu02fe28c2010-11-26 08:52:48 +0000858 case MemRegion::CXXTempObjectRegionKind:
Ted Kremenek96979342011-08-12 20:02:48 +0000859 os << "a C++ temp object of type " << TVR->getValueType().getAsString();
Jordy Rose19c5dd12010-07-27 01:37:31 +0000860 return true;
861 case MemRegion::VarRegionKind:
Ted Kremenek96979342011-08-12 20:02:48 +0000862 os << "a variable of type" << TVR->getValueType().getAsString();
Jordy Rose19c5dd12010-07-27 01:37:31 +0000863 return true;
864 case MemRegion::FieldRegionKind:
Ted Kremenek96979342011-08-12 20:02:48 +0000865 os << "a field of type " << TVR->getValueType().getAsString();
Jordy Rose19c5dd12010-07-27 01:37:31 +0000866 return true;
867 case MemRegion::ObjCIvarRegionKind:
Ted Kremenek96979342011-08-12 20:02:48 +0000868 os << "an instance variable of type " << TVR->getValueType().getAsString();
Jordy Rose19c5dd12010-07-27 01:37:31 +0000869 return true;
870 default:
871 return false;
872 }
873}
874
Jordy Rosed325ffb2010-07-08 23:57:29 +0000875//===----------------------------------------------------------------------===//
Ted Kremenek9c149532010-12-01 21:57:22 +0000876// evaluation of individual function calls.
Jordy Rosed325ffb2010-07-08 23:57:29 +0000877//===----------------------------------------------------------------------===//
878
Lenny Maioranib8b875b2011-03-31 21:36:53 +0000879void CStringChecker::evalCopyCommon(CheckerContext &C,
880 const CallExpr *CE,
Ted Kremenek8bef8232012-01-26 21:29:00 +0000881 ProgramStateRef state,
Jordy Rosed325ffb2010-07-08 23:57:29 +0000882 const Expr *Size, const Expr *Dest,
Lenny Maioranib8b875b2011-03-31 21:36:53 +0000883 const Expr *Source, bool Restricted,
884 bool IsMempcpy) const {
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000885 CurrentFunctionDescription = "memory copy function";
886
Jordy Rosed325ffb2010-07-08 23:57:29 +0000887 // See if the size argument is zero.
Ted Kremenek5eca4822012-01-06 22:09:28 +0000888 const LocationContext *LCtx = C.getLocationContext();
889 SVal sizeVal = state->getSVal(Size, LCtx);
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000890 QualType sizeTy = Size->getType();
Jordy Rosed325ffb2010-07-08 23:57:29 +0000891
Ted Kremenek8bef8232012-01-26 21:29:00 +0000892 ProgramStateRef stateZeroSize, stateNonZeroSize;
Jordy Rose1e022412011-06-16 05:51:02 +0000893 llvm::tie(stateZeroSize, stateNonZeroSize) =
894 assumeZero(C, state, sizeVal, sizeTy);
Jordy Rosed325ffb2010-07-08 23:57:29 +0000895
Lenny Maioranib8b875b2011-03-31 21:36:53 +0000896 // Get the value of the Dest.
Ted Kremenek5eca4822012-01-06 22:09:28 +0000897 SVal destVal = state->getSVal(Dest, LCtx);
Lenny Maioranib8b875b2011-03-31 21:36:53 +0000898
899 // If the size is zero, there won't be any actual memory access, so
900 // just bind the return value to the destination buffer and return.
901 if (stateZeroSize) {
Ted Kremenek5eca4822012-01-06 22:09:28 +0000902 stateZeroSize = stateZeroSize->BindExpr(CE, LCtx, destVal);
Anna Zaks0bd6b112011-10-26 21:06:34 +0000903 C.addTransition(stateZeroSize);
Lenny Maioranib8b875b2011-03-31 21:36:53 +0000904 }
Jordy Rosed325ffb2010-07-08 23:57:29 +0000905
906 // If the size can be nonzero, we have to check the other arguments.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000907 if (stateNonZeroSize) {
Jordy Rose22d27172011-06-04 00:04:22 +0000908 state = stateNonZeroSize;
Lenny Maioranib8b875b2011-03-31 21:36:53 +0000909
910 // Ensure the destination is not null. If it is NULL there will be a
911 // NULL pointer dereference.
912 state = checkNonNull(C, state, Dest, destVal);
913 if (!state)
914 return;
915
916 // Get the value of the Src.
Ted Kremenek5eca4822012-01-06 22:09:28 +0000917 SVal srcVal = state->getSVal(Source, LCtx);
Lenny Maioranib8b875b2011-03-31 21:36:53 +0000918
919 // Ensure the source is not null. If it is NULL there will be a
920 // NULL pointer dereference.
921 state = checkNonNull(C, state, Source, srcVal);
922 if (!state)
923 return;
924
Jordy Rose7182b962011-06-04 01:50:25 +0000925 // Ensure the accesses are valid and that the buffers do not overlap.
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000926 const char * const writeWarning =
927 "Memory copy function overflows destination buffer";
Jordy Rosee64f3112010-08-16 07:51:42 +0000928 state = CheckBufferAccess(C, state, Size, Dest, Source,
Jordy Rose9e49d9f2011-06-20 02:06:40 +0000929 writeWarning, /* sourceWarning = */ NULL);
Jordy Rosed325ffb2010-07-08 23:57:29 +0000930 if (Restricted)
931 state = CheckOverlap(C, state, Size, Dest, Source);
Jordy Rosee64f3112010-08-16 07:51:42 +0000932
Jordy Rose7182b962011-06-04 01:50:25 +0000933 if (!state)
934 return;
Lenny Maioranib8b875b2011-03-31 21:36:53 +0000935
Jordy Rose7182b962011-06-04 01:50:25 +0000936 // If this is mempcpy, get the byte after the last byte copied and
937 // bind the expr.
938 if (IsMempcpy) {
939 loc::MemRegionVal *destRegVal = dyn_cast<loc::MemRegionVal>(&destVal);
940 assert(destRegVal && "Destination should be a known MemRegionVal here");
941
942 // Get the length to copy.
943 NonLoc *lenValNonLoc = dyn_cast<NonLoc>(&sizeVal);
944
945 if (lenValNonLoc) {
946 // Get the byte after the last byte copied.
947 SVal lastElement = C.getSValBuilder().evalBinOpLN(state, BO_Add,
948 *destRegVal,
949 *lenValNonLoc,
950 Dest->getType());
951
952 // The byte after the last byte copied is the return value.
Ted Kremenek5eca4822012-01-06 22:09:28 +0000953 state = state->BindExpr(CE, LCtx, lastElement);
Jordy Rose3f8bb2f2011-06-04 01:47:27 +0000954 } else {
Jordy Rose7182b962011-06-04 01:50:25 +0000955 // If we don't know how much we copied, we can at least
956 // conjure a return value for later.
Anna Zaks5d0ea6d2011-10-04 20:43:05 +0000957 unsigned Count = C.getCurrentBlockCount();
Jordy Rose7182b962011-06-04 01:50:25 +0000958 SVal result =
959 C.getSValBuilder().getConjuredSymbolVal(NULL, CE, Count);
Ted Kremenek5eca4822012-01-06 22:09:28 +0000960 state = state->BindExpr(CE, LCtx, result);
Lenny Maioranib8b875b2011-03-31 21:36:53 +0000961 }
962
Jordy Rose7182b962011-06-04 01:50:25 +0000963 } else {
964 // All other copies return the destination buffer.
965 // (Well, bcopy() has a void return type, but this won't hurt.)
Ted Kremenek5eca4822012-01-06 22:09:28 +0000966 state = state->BindExpr(CE, LCtx, destVal);
Jordy Rosee64f3112010-08-16 07:51:42 +0000967 }
Jordy Rose7182b962011-06-04 01:50:25 +0000968
969 // Invalidate the destination.
970 // FIXME: Even if we can't perfectly model the copy, we should see if we
971 // can use LazyCompoundVals to copy the source values into the destination.
972 // This would probably remove any existing bindings past the end of the
973 // copied region, but that's still an improvement over blank invalidation.
Ted Kremenek5eca4822012-01-06 22:09:28 +0000974 state = InvalidateBuffer(C, state, Dest,
975 state->getSVal(Dest, C.getLocationContext()));
Anna Zaks0bd6b112011-10-26 21:06:34 +0000976 C.addTransition(state);
Jordy Rosed325ffb2010-07-08 23:57:29 +0000977 }
978}
979
980
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +0000981void CStringChecker::evalMemcpy(CheckerContext &C, const CallExpr *CE) const {
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000982 // void *memcpy(void *restrict dst, const void *restrict src, size_t n);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000983 // The return value is the address of the destination buffer.
Jordy Rosed325ffb2010-07-08 23:57:29 +0000984 const Expr *Dest = CE->getArg(0);
Ted Kremenek8bef8232012-01-26 21:29:00 +0000985 ProgramStateRef state = C.getState();
Jordy Rose3f8bb2f2011-06-04 01:47:27 +0000986
Lenny Maioranib8b875b2011-03-31 21:36:53 +0000987 evalCopyCommon(C, CE, state, CE->getArg(2), Dest, CE->getArg(1), true);
988}
989
990void CStringChecker::evalMempcpy(CheckerContext &C, const CallExpr *CE) const {
991 // void *mempcpy(void *restrict dst, const void *restrict src, size_t n);
992 // The return value is a pointer to the byte following the last written byte.
993 const Expr *Dest = CE->getArg(0);
Ted Kremenek8bef8232012-01-26 21:29:00 +0000994 ProgramStateRef state = C.getState();
Lenny Maioranib8b875b2011-03-31 21:36:53 +0000995
996 evalCopyCommon(C, CE, state, CE->getArg(2), Dest, CE->getArg(1), true, true);
Jordy Roseccbf7ee2010-07-06 23:11:01 +0000997}
998
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +0000999void CStringChecker::evalMemmove(CheckerContext &C, const CallExpr *CE) const {
Jordy Rosed325ffb2010-07-08 23:57:29 +00001000 // void *memmove(void *dst, const void *src, size_t n);
1001 // The return value is the address of the destination buffer.
1002 const Expr *Dest = CE->getArg(0);
Ted Kremenek8bef8232012-01-26 21:29:00 +00001003 ProgramStateRef state = C.getState();
Jordy Rose3f8bb2f2011-06-04 01:47:27 +00001004
Lenny Maioranib8b875b2011-03-31 21:36:53 +00001005 evalCopyCommon(C, CE, state, CE->getArg(2), Dest, CE->getArg(1));
Jordy Rosed325ffb2010-07-08 23:57:29 +00001006}
1007
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +00001008void CStringChecker::evalBcopy(CheckerContext &C, const CallExpr *CE) const {
Jordy Rosed325ffb2010-07-08 23:57:29 +00001009 // void bcopy(const void *src, void *dst, size_t n);
Lenny Maioranib8b875b2011-03-31 21:36:53 +00001010 evalCopyCommon(C, CE, C.getState(),
1011 CE->getArg(2), CE->getArg(1), CE->getArg(0));
Jordy Rosed325ffb2010-07-08 23:57:29 +00001012}
1013
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +00001014void CStringChecker::evalMemcmp(CheckerContext &C, const CallExpr *CE) const {
Jordy Rosebc56d1f2010-07-07 08:15:01 +00001015 // int memcmp(const void *s1, const void *s2, size_t n);
Jordy Rose9e49d9f2011-06-20 02:06:40 +00001016 CurrentFunctionDescription = "memory comparison function";
1017
Jordy Rosebc56d1f2010-07-07 08:15:01 +00001018 const Expr *Left = CE->getArg(0);
1019 const Expr *Right = CE->getArg(1);
1020 const Expr *Size = CE->getArg(2);
1021
Ted Kremenek8bef8232012-01-26 21:29:00 +00001022 ProgramStateRef state = C.getState();
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001023 SValBuilder &svalBuilder = C.getSValBuilder();
Jordy Rosebc56d1f2010-07-07 08:15:01 +00001024
Jordy Rosed325ffb2010-07-08 23:57:29 +00001025 // See if the size argument is zero.
Ted Kremenek5eca4822012-01-06 22:09:28 +00001026 const LocationContext *LCtx = C.getLocationContext();
1027 SVal sizeVal = state->getSVal(Size, LCtx);
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001028 QualType sizeTy = Size->getType();
Jordy Rosebc56d1f2010-07-07 08:15:01 +00001029
Ted Kremenek8bef8232012-01-26 21:29:00 +00001030 ProgramStateRef stateZeroSize, stateNonZeroSize;
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001031 llvm::tie(stateZeroSize, stateNonZeroSize) =
1032 assumeZero(C, state, sizeVal, sizeTy);
Jordy Rosebc56d1f2010-07-07 08:15:01 +00001033
Jordy Rosed325ffb2010-07-08 23:57:29 +00001034 // If the size can be zero, the result will be 0 in that case, and we don't
1035 // have to check either of the buffers.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001036 if (stateZeroSize) {
1037 state = stateZeroSize;
Ted Kremenek5eca4822012-01-06 22:09:28 +00001038 state = state->BindExpr(CE, LCtx,
1039 svalBuilder.makeZeroVal(CE->getType()));
Anna Zaks0bd6b112011-10-26 21:06:34 +00001040 C.addTransition(state);
Jordy Rosebc56d1f2010-07-07 08:15:01 +00001041 }
1042
Jordy Rosed325ffb2010-07-08 23:57:29 +00001043 // If the size can be nonzero, we have to check the other arguments.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001044 if (stateNonZeroSize) {
1045 state = stateNonZeroSize;
Jordy Rosed325ffb2010-07-08 23:57:29 +00001046 // If we know the two buffers are the same, we know the result is 0.
1047 // First, get the two buffers' addresses. Another checker will have already
1048 // made sure they're not undefined.
Ted Kremenek5eca4822012-01-06 22:09:28 +00001049 DefinedOrUnknownSVal LV =
1050 cast<DefinedOrUnknownSVal>(state->getSVal(Left, LCtx));
1051 DefinedOrUnknownSVal RV =
1052 cast<DefinedOrUnknownSVal>(state->getSVal(Right, LCtx));
Jordy Rosebc56d1f2010-07-07 08:15:01 +00001053
Jordy Rosed325ffb2010-07-08 23:57:29 +00001054 // See if they are the same.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001055 DefinedOrUnknownSVal SameBuf = svalBuilder.evalEQ(state, LV, RV);
Ted Kremenek8bef8232012-01-26 21:29:00 +00001056 ProgramStateRef StSameBuf, StNotSameBuf;
Ted Kremenek28f47b92010-12-01 22:16:56 +00001057 llvm::tie(StSameBuf, StNotSameBuf) = state->assume(SameBuf);
Jordy Rosed325ffb2010-07-08 23:57:29 +00001058
Jordy Rose1e022412011-06-16 05:51:02 +00001059 // If the two arguments might be the same buffer, we know the result is 0,
Jordy Rosed325ffb2010-07-08 23:57:29 +00001060 // and we only need to check one size.
1061 if (StSameBuf) {
1062 state = StSameBuf;
1063 state = CheckBufferAccess(C, state, Size, Left);
1064 if (state) {
Ted Kremenek5eca4822012-01-06 22:09:28 +00001065 state = StSameBuf->BindExpr(CE, LCtx,
1066 svalBuilder.makeZeroVal(CE->getType()));
Anna Zaks0bd6b112011-10-26 21:06:34 +00001067 C.addTransition(state);
Jordy Rosed325ffb2010-07-08 23:57:29 +00001068 }
1069 }
1070
1071 // If the two arguments might be different buffers, we have to check the
1072 // size of both of them.
1073 if (StNotSameBuf) {
1074 state = StNotSameBuf;
1075 state = CheckBufferAccess(C, state, Size, Left, Right);
1076 if (state) {
1077 // The return value is the comparison result, which we don't know.
Anna Zaks5d0ea6d2011-10-04 20:43:05 +00001078 unsigned Count = C.getCurrentBlockCount();
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001079 SVal CmpV = svalBuilder.getConjuredSymbolVal(NULL, CE, Count);
Ted Kremenek5eca4822012-01-06 22:09:28 +00001080 state = state->BindExpr(CE, LCtx, CmpV);
Anna Zaks0bd6b112011-10-26 21:06:34 +00001081 C.addTransition(state);
Jordy Rosed325ffb2010-07-08 23:57:29 +00001082 }
1083 }
1084 }
Jordy Rosebc56d1f2010-07-07 08:15:01 +00001085}
1086
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +00001087void CStringChecker::evalstrLength(CheckerContext &C,
1088 const CallExpr *CE) const {
Jordy Rose19c5dd12010-07-27 01:37:31 +00001089 // size_t strlen(const char *s);
Ted Kremenekbe4242c2011-02-22 04:55:05 +00001090 evalstrLengthCommon(C, CE, /* IsStrnlen = */ false);
1091}
1092
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +00001093void CStringChecker::evalstrnLength(CheckerContext &C,
1094 const CallExpr *CE) const {
Ted Kremenekbe4242c2011-02-22 04:55:05 +00001095 // size_t strnlen(const char *s, size_t maxlen);
1096 evalstrLengthCommon(C, CE, /* IsStrnlen = */ true);
1097}
1098
1099void CStringChecker::evalstrLengthCommon(CheckerContext &C, const CallExpr *CE,
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +00001100 bool IsStrnlen) const {
Jordy Rose9e49d9f2011-06-20 02:06:40 +00001101 CurrentFunctionDescription = "string length function";
Ted Kremenek8bef8232012-01-26 21:29:00 +00001102 ProgramStateRef state = C.getState();
Ted Kremenek5eca4822012-01-06 22:09:28 +00001103 const LocationContext *LCtx = C.getLocationContext();
Jordy Rose793bff32011-06-14 01:15:31 +00001104
1105 if (IsStrnlen) {
1106 const Expr *maxlenExpr = CE->getArg(1);
Ted Kremenek5eca4822012-01-06 22:09:28 +00001107 SVal maxlenVal = state->getSVal(maxlenExpr, LCtx);
Jordy Rose793bff32011-06-14 01:15:31 +00001108
Ted Kremenek8bef8232012-01-26 21:29:00 +00001109 ProgramStateRef stateZeroSize, stateNonZeroSize;
Jordy Rose793bff32011-06-14 01:15:31 +00001110 llvm::tie(stateZeroSize, stateNonZeroSize) =
1111 assumeZero(C, state, maxlenVal, maxlenExpr->getType());
1112
1113 // If the size can be zero, the result will be 0 in that case, and we don't
1114 // have to check the string itself.
1115 if (stateZeroSize) {
1116 SVal zero = C.getSValBuilder().makeZeroVal(CE->getType());
Ted Kremenek5eca4822012-01-06 22:09:28 +00001117 stateZeroSize = stateZeroSize->BindExpr(CE, LCtx, zero);
Anna Zaks0bd6b112011-10-26 21:06:34 +00001118 C.addTransition(stateZeroSize);
Jordy Rose793bff32011-06-14 01:15:31 +00001119 }
1120
1121 // If the size is GUARANTEED to be zero, we're done!
1122 if (!stateNonZeroSize)
1123 return;
1124
1125 // Otherwise, record the assumption that the size is nonzero.
1126 state = stateNonZeroSize;
1127 }
1128
1129 // Check that the string argument is non-null.
Jordy Rose19c5dd12010-07-27 01:37:31 +00001130 const Expr *Arg = CE->getArg(0);
Ted Kremenek5eca4822012-01-06 22:09:28 +00001131 SVal ArgVal = state->getSVal(Arg, LCtx);
Jordy Rose19c5dd12010-07-27 01:37:31 +00001132
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001133 state = checkNonNull(C, state, Arg, ArgVal);
Jordy Rose19c5dd12010-07-27 01:37:31 +00001134
Jordy Rosebd32bee2011-06-14 01:26:48 +00001135 if (!state)
1136 return;
Jordy Rosea5261542010-08-14 21:02:52 +00001137
Jordy Rosebd32bee2011-06-14 01:26:48 +00001138 SVal strLength = getCStringLength(C, state, Arg, ArgVal);
Jordy Rosea5261542010-08-14 21:02:52 +00001139
Jordy Rosebd32bee2011-06-14 01:26:48 +00001140 // If the argument isn't a valid C string, there's no valid state to
1141 // transition to.
1142 if (strLength.isUndef())
1143 return;
Jordy Rose793bff32011-06-14 01:15:31 +00001144
Jordy Rosebd32bee2011-06-14 01:26:48 +00001145 DefinedOrUnknownSVal result = UnknownVal();
Jordy Rose793bff32011-06-14 01:15:31 +00001146
Jordy Rosebd32bee2011-06-14 01:26:48 +00001147 // If the check is for strnlen() then bind the return value to no more than
1148 // the maxlen value.
1149 if (IsStrnlen) {
Jordy Roseee2fde12011-06-16 05:56:50 +00001150 QualType cmpTy = C.getSValBuilder().getConditionType();
Jordy Rose793bff32011-06-14 01:15:31 +00001151
Jordy Rosebd32bee2011-06-14 01:26:48 +00001152 // It's a little unfortunate to be getting this again,
1153 // but it's not that expensive...
1154 const Expr *maxlenExpr = CE->getArg(1);
Ted Kremenek5eca4822012-01-06 22:09:28 +00001155 SVal maxlenVal = state->getSVal(maxlenExpr, LCtx);
Ted Kremenekbe4242c2011-02-22 04:55:05 +00001156
Jordy Rosebd32bee2011-06-14 01:26:48 +00001157 NonLoc *strLengthNL = dyn_cast<NonLoc>(&strLength);
1158 NonLoc *maxlenValNL = dyn_cast<NonLoc>(&maxlenVal);
Ted Kremenekbe4242c2011-02-22 04:55:05 +00001159
Jordy Rosebd32bee2011-06-14 01:26:48 +00001160 if (strLengthNL && maxlenValNL) {
Ted Kremenek8bef8232012-01-26 21:29:00 +00001161 ProgramStateRef stateStringTooLong, stateStringNotTooLong;
Jordy Rose793bff32011-06-14 01:15:31 +00001162
Jordy Rosebd32bee2011-06-14 01:26:48 +00001163 // Check if the strLength is greater than the maxlen.
1164 llvm::tie(stateStringTooLong, stateStringNotTooLong) =
1165 state->assume(cast<DefinedOrUnknownSVal>
1166 (C.getSValBuilder().evalBinOpNN(state, BO_GT,
1167 *strLengthNL,
1168 *maxlenValNL,
1169 cmpTy)));
Jordy Rose793bff32011-06-14 01:15:31 +00001170
Jordy Rosebd32bee2011-06-14 01:26:48 +00001171 if (stateStringTooLong && !stateStringNotTooLong) {
1172 // If the string is longer than maxlen, return maxlen.
1173 result = *maxlenValNL;
1174 } else if (stateStringNotTooLong && !stateStringTooLong) {
1175 // If the string is shorter than maxlen, return its length.
1176 result = *strLengthNL;
Ted Kremenekbe4242c2011-02-22 04:55:05 +00001177 }
1178 }
1179
Jordy Rosebd32bee2011-06-14 01:26:48 +00001180 if (result.isUnknown()) {
1181 // If we don't have enough information for a comparison, there's
1182 // no guarantee the full string length will actually be returned.
1183 // All we know is the return value is the min of the string length
1184 // and the limit. This is better than nothing.
Anna Zaks5d0ea6d2011-10-04 20:43:05 +00001185 unsigned Count = C.getCurrentBlockCount();
Jordy Rosebd32bee2011-06-14 01:26:48 +00001186 result = C.getSValBuilder().getConjuredSymbolVal(NULL, CE, Count);
1187 NonLoc *resultNL = cast<NonLoc>(&result);
1188
1189 if (strLengthNL) {
1190 state = state->assume(cast<DefinedOrUnknownSVal>
1191 (C.getSValBuilder().evalBinOpNN(state, BO_LE,
1192 *resultNL,
1193 *strLengthNL,
1194 cmpTy)), true);
1195 }
1196
1197 if (maxlenValNL) {
1198 state = state->assume(cast<DefinedOrUnknownSVal>
1199 (C.getSValBuilder().evalBinOpNN(state, BO_LE,
1200 *resultNL,
1201 *maxlenValNL,
1202 cmpTy)), true);
1203 }
1204 }
1205
1206 } else {
1207 // This is a plain strlen(), not strnlen().
1208 result = cast<DefinedOrUnknownSVal>(strLength);
1209
1210 // If we don't know the length of the string, conjure a return
1211 // value, so it can be used in constraints, at least.
1212 if (result.isUnknown()) {
Anna Zaks5d0ea6d2011-10-04 20:43:05 +00001213 unsigned Count = C.getCurrentBlockCount();
Jordy Rosebd32bee2011-06-14 01:26:48 +00001214 result = C.getSValBuilder().getConjuredSymbolVal(NULL, CE, Count);
1215 }
Jordy Rose19c5dd12010-07-27 01:37:31 +00001216 }
Jordy Rosebd32bee2011-06-14 01:26:48 +00001217
1218 // Bind the return value.
1219 assert(!result.isUnknown() && "Should have conjured a value by now");
Ted Kremenek5eca4822012-01-06 22:09:28 +00001220 state = state->BindExpr(CE, LCtx, result);
Anna Zaks0bd6b112011-10-26 21:06:34 +00001221 C.addTransition(state);
Jordy Rose19c5dd12010-07-27 01:37:31 +00001222}
1223
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +00001224void CStringChecker::evalStrcpy(CheckerContext &C, const CallExpr *CE) const {
Jordy Rosee64f3112010-08-16 07:51:42 +00001225 // char *strcpy(char *restrict dst, const char *restrict src);
Lenny Maiorani067bbd02011-04-09 15:12:58 +00001226 evalStrcpyCommon(C, CE,
1227 /* returnEnd = */ false,
1228 /* isBounded = */ false,
1229 /* isAppending = */ false);
Ted Kremenek0ef473f2011-02-22 04:58:34 +00001230}
1231
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +00001232void CStringChecker::evalStrncpy(CheckerContext &C, const CallExpr *CE) const {
Jordy Rosec1525862011-06-04 00:05:23 +00001233 // char *strncpy(char *restrict dst, const char *restrict src, size_t n);
Lenny Maiorani067bbd02011-04-09 15:12:58 +00001234 evalStrcpyCommon(C, CE,
1235 /* returnEnd = */ false,
1236 /* isBounded = */ true,
1237 /* isAppending = */ false);
Jordy Rosee64f3112010-08-16 07:51:42 +00001238}
1239
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +00001240void CStringChecker::evalStpcpy(CheckerContext &C, const CallExpr *CE) const {
Jordy Rosee64f3112010-08-16 07:51:42 +00001241 // char *stpcpy(char *restrict dst, const char *restrict src);
Lenny Maiorani067bbd02011-04-09 15:12:58 +00001242 evalStrcpyCommon(C, CE,
1243 /* returnEnd = */ true,
1244 /* isBounded = */ false,
1245 /* isAppending = */ false);
1246}
1247
1248void CStringChecker::evalStrcat(CheckerContext &C, const CallExpr *CE) const {
1249 //char *strcat(char *restrict s1, const char *restrict s2);
1250 evalStrcpyCommon(C, CE,
1251 /* returnEnd = */ false,
1252 /* isBounded = */ false,
1253 /* isAppending = */ true);
1254}
1255
1256void CStringChecker::evalStrncat(CheckerContext &C, const CallExpr *CE) const {
1257 //char *strncat(char *restrict s1, const char *restrict s2, size_t n);
1258 evalStrcpyCommon(C, CE,
1259 /* returnEnd = */ false,
1260 /* isBounded = */ true,
1261 /* isAppending = */ true);
Jordy Rosee64f3112010-08-16 07:51:42 +00001262}
1263
Ted Kremenek9c149532010-12-01 21:57:22 +00001264void CStringChecker::evalStrcpyCommon(CheckerContext &C, const CallExpr *CE,
Lenny Maiorani067bbd02011-04-09 15:12:58 +00001265 bool returnEnd, bool isBounded,
1266 bool isAppending) const {
Jordy Rose9e49d9f2011-06-20 02:06:40 +00001267 CurrentFunctionDescription = "string copy function";
Ted Kremenek8bef8232012-01-26 21:29:00 +00001268 ProgramStateRef state = C.getState();
Ted Kremenek5eca4822012-01-06 22:09:28 +00001269 const LocationContext *LCtx = C.getLocationContext();
Jordy Rosee64f3112010-08-16 07:51:42 +00001270
Lenny Maiorani067bbd02011-04-09 15:12:58 +00001271 // Check that the destination is non-null.
Jordy Rosee64f3112010-08-16 07:51:42 +00001272 const Expr *Dst = CE->getArg(0);
Ted Kremenek5eca4822012-01-06 22:09:28 +00001273 SVal DstVal = state->getSVal(Dst, LCtx);
Jordy Rosee64f3112010-08-16 07:51:42 +00001274
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001275 state = checkNonNull(C, state, Dst, DstVal);
Jordy Rosee64f3112010-08-16 07:51:42 +00001276 if (!state)
1277 return;
1278
1279 // Check that the source is non-null.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001280 const Expr *srcExpr = CE->getArg(1);
Ted Kremenek5eca4822012-01-06 22:09:28 +00001281 SVal srcVal = state->getSVal(srcExpr, LCtx);
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001282 state = checkNonNull(C, state, srcExpr, srcVal);
Jordy Rosee64f3112010-08-16 07:51:42 +00001283 if (!state)
1284 return;
1285
1286 // Get the string length of the source.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001287 SVal strLength = getCStringLength(C, state, srcExpr, srcVal);
Jordy Rosee64f3112010-08-16 07:51:42 +00001288
1289 // If the source isn't a valid C string, give up.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001290 if (strLength.isUndef())
Jordy Rosee64f3112010-08-16 07:51:42 +00001291 return;
1292
Jordy Rosed5af0e12011-06-15 05:52:56 +00001293 SValBuilder &svalBuilder = C.getSValBuilder();
1294 QualType cmpTy = svalBuilder.getConditionType();
Jordy Rose8912aae2011-06-20 21:55:40 +00001295 QualType sizeTy = svalBuilder.getContext().getSizeType();
Jordy Rosed5af0e12011-06-15 05:52:56 +00001296
Jordy Rose8912aae2011-06-20 21:55:40 +00001297 // These two values allow checking two kinds of errors:
1298 // - actual overflows caused by a source that doesn't fit in the destination
1299 // - potential overflows caused by a bound that could exceed the destination
Jordy Rosed5af0e12011-06-15 05:52:56 +00001300 SVal amountCopied = UnknownVal();
Jordy Rose8912aae2011-06-20 21:55:40 +00001301 SVal maxLastElementIndex = UnknownVal();
1302 const char *boundWarning = NULL;
Jordy Rosed5af0e12011-06-15 05:52:56 +00001303
Lenny Maiorani067bbd02011-04-09 15:12:58 +00001304 // If the function is strncpy, strncat, etc... it is bounded.
1305 if (isBounded) {
1306 // Get the max number of characters to copy.
Ted Kremenek0ef473f2011-02-22 04:58:34 +00001307 const Expr *lenExpr = CE->getArg(2);
Ted Kremenek5eca4822012-01-06 22:09:28 +00001308 SVal lenVal = state->getSVal(lenExpr, LCtx);
Ted Kremenek0ef473f2011-02-22 04:58:34 +00001309
Jordy Rosed5af0e12011-06-15 05:52:56 +00001310 // Protect against misdeclared strncpy().
Jordy Rose8912aae2011-06-20 21:55:40 +00001311 lenVal = svalBuilder.evalCast(lenVal, sizeTy, lenExpr->getType());
Jordy Rosed5af0e12011-06-15 05:52:56 +00001312
Ted Kremenek0ef473f2011-02-22 04:58:34 +00001313 NonLoc *strLengthNL = dyn_cast<NonLoc>(&strLength);
1314 NonLoc *lenValNL = dyn_cast<NonLoc>(&lenVal);
1315
Jordy Rosed5af0e12011-06-15 05:52:56 +00001316 // If we know both values, we might be able to figure out how much
1317 // we're copying.
1318 if (strLengthNL && lenValNL) {
Ted Kremenek8bef8232012-01-26 21:29:00 +00001319 ProgramStateRef stateSourceTooLong, stateSourceNotTooLong;
Ted Kremenek0ef473f2011-02-22 04:58:34 +00001320
Jordy Rosed5af0e12011-06-15 05:52:56 +00001321 // Check if the max number to copy is less than the length of the src.
Jordy Rose8912aae2011-06-20 21:55:40 +00001322 // If the bound is equal to the source length, strncpy won't null-
1323 // terminate the result!
Jordy Rosed5af0e12011-06-15 05:52:56 +00001324 llvm::tie(stateSourceTooLong, stateSourceNotTooLong) =
1325 state->assume(cast<DefinedOrUnknownSVal>
Jordy Rose8912aae2011-06-20 21:55:40 +00001326 (svalBuilder.evalBinOpNN(state, BO_GE, *strLengthNL,
Jordy Rosed5af0e12011-06-15 05:52:56 +00001327 *lenValNL, cmpTy)));
1328
1329 if (stateSourceTooLong && !stateSourceNotTooLong) {
1330 // Max number to copy is less than the length of the src, so the actual
1331 // strLength copied is the max number arg.
1332 state = stateSourceTooLong;
1333 amountCopied = lenVal;
1334
1335 } else if (!stateSourceTooLong && stateSourceNotTooLong) {
1336 // The source buffer entirely fits in the bound.
1337 state = stateSourceNotTooLong;
1338 amountCopied = strLength;
1339 }
1340 }
1341
Jordy Rose5e5f1502011-06-20 03:49:16 +00001342 // We still want to know if the bound is known to be too large.
Jordy Rose8912aae2011-06-20 21:55:40 +00001343 if (lenValNL) {
1344 if (isAppending) {
1345 // For strncat, the check is strlen(dst) + lenVal < sizeof(dst)
1346
1347 // Get the string length of the destination. If the destination is
1348 // memory that can't have a string length, we shouldn't be copying
1349 // into it anyway.
1350 SVal dstStrLength = getCStringLength(C, state, Dst, DstVal);
1351 if (dstStrLength.isUndef())
1352 return;
1353
1354 if (NonLoc *dstStrLengthNL = dyn_cast<NonLoc>(&dstStrLength)) {
1355 maxLastElementIndex = svalBuilder.evalBinOpNN(state, BO_Add,
1356 *lenValNL,
1357 *dstStrLengthNL,
1358 sizeTy);
1359 boundWarning = "Size argument is greater than the free space in the "
1360 "destination buffer";
1361 }
1362
1363 } else {
1364 // For strncpy, this is just checking that lenVal <= sizeof(dst)
1365 // (Yes, strncpy and strncat differ in how they treat termination.
1366 // strncat ALWAYS terminates, but strncpy doesn't.)
1367 NonLoc one = cast<NonLoc>(svalBuilder.makeIntVal(1, sizeTy));
1368 maxLastElementIndex = svalBuilder.evalBinOpNN(state, BO_Sub, *lenValNL,
1369 one, sizeTy);
1370 boundWarning = "Size argument is greater than the length of the "
1371 "destination buffer";
1372 }
1373 }
Jordy Rose5e5f1502011-06-20 03:49:16 +00001374
Jordy Rosed5af0e12011-06-15 05:52:56 +00001375 // If we couldn't pin down the copy length, at least bound it.
Jordy Rose8912aae2011-06-20 21:55:40 +00001376 // FIXME: We should actually run this code path for append as well, but
1377 // right now it creates problems with constraints (since we can end up
1378 // trying to pass constraints from symbol to symbol).
1379 if (amountCopied.isUnknown() && !isAppending) {
Jordy Rosed5af0e12011-06-15 05:52:56 +00001380 // Try to get a "hypothetical" string length symbol, which we can later
1381 // set as a real value if that turns out to be the case.
1382 amountCopied = getCStringLength(C, state, lenExpr, srcVal, true);
1383 assert(!amountCopied.isUndef());
1384
1385 if (NonLoc *amountCopiedNL = dyn_cast<NonLoc>(&amountCopied)) {
1386 if (lenValNL) {
1387 // amountCopied <= lenVal
1388 SVal copiedLessThanBound = svalBuilder.evalBinOpNN(state, BO_LE,
1389 *amountCopiedNL,
1390 *lenValNL,
1391 cmpTy);
1392 state = state->assume(cast<DefinedOrUnknownSVal>(copiedLessThanBound),
1393 true);
1394 if (!state)
1395 return;
1396 }
1397
1398 if (strLengthNL) {
1399 // amountCopied <= strlen(source)
1400 SVal copiedLessThanSrc = svalBuilder.evalBinOpNN(state, BO_LE,
1401 *amountCopiedNL,
1402 *strLengthNL,
1403 cmpTy);
1404 state = state->assume(cast<DefinedOrUnknownSVal>(copiedLessThanSrc),
1405 true);
1406 if (!state)
1407 return;
1408 }
1409 }
1410 }
1411
1412 } else {
1413 // The function isn't bounded. The amount copied should match the length
1414 // of the source buffer.
1415 amountCopied = strLength;
Ted Kremenek0ef473f2011-02-22 04:58:34 +00001416 }
1417
Jordy Rosed5af0e12011-06-15 05:52:56 +00001418 assert(state);
1419
1420 // This represents the number of characters copied into the destination
1421 // buffer. (It may not actually be the strlen if the destination buffer
1422 // is not terminated.)
1423 SVal finalStrLength = UnknownVal();
1424
Lenny Maiorani067bbd02011-04-09 15:12:58 +00001425 // If this is an appending function (strcat, strncat...) then set the
1426 // string length to strlen(src) + strlen(dst) since the buffer will
1427 // ultimately contain both.
1428 if (isAppending) {
Jordy Rose1e022412011-06-16 05:51:02 +00001429 // Get the string length of the destination. If the destination is memory
1430 // that can't have a string length, we shouldn't be copying into it anyway.
Lenny Maiorani067bbd02011-04-09 15:12:58 +00001431 SVal dstStrLength = getCStringLength(C, state, Dst, DstVal);
1432 if (dstStrLength.isUndef())
1433 return;
1434
Jordy Rosed5af0e12011-06-15 05:52:56 +00001435 NonLoc *srcStrLengthNL = dyn_cast<NonLoc>(&amountCopied);
Lenny Maiorani067bbd02011-04-09 15:12:58 +00001436 NonLoc *dstStrLengthNL = dyn_cast<NonLoc>(&dstStrLength);
1437
Jordy Rosed5af0e12011-06-15 05:52:56 +00001438 // If we know both string lengths, we might know the final string length.
1439 if (srcStrLengthNL && dstStrLengthNL) {
1440 // Make sure the two lengths together don't overflow a size_t.
1441 state = checkAdditionOverflow(C, state, *srcStrLengthNL, *dstStrLengthNL);
1442 if (!state)
1443 return;
Lenny Maiorani067bbd02011-04-09 15:12:58 +00001444
Jordy Rosed5af0e12011-06-15 05:52:56 +00001445 finalStrLength = svalBuilder.evalBinOpNN(state, BO_Add, *srcStrLengthNL,
1446 *dstStrLengthNL, sizeTy);
1447 }
Lenny Maiorani067bbd02011-04-09 15:12:58 +00001448
Jordy Rosed5af0e12011-06-15 05:52:56 +00001449 // If we couldn't get a single value for the final string length,
1450 // we can at least bound it by the individual lengths.
1451 if (finalStrLength.isUnknown()) {
1452 // Try to get a "hypothetical" string length symbol, which we can later
1453 // set as a real value if that turns out to be the case.
1454 finalStrLength = getCStringLength(C, state, CE, DstVal, true);
1455 assert(!finalStrLength.isUndef());
1456
1457 if (NonLoc *finalStrLengthNL = dyn_cast<NonLoc>(&finalStrLength)) {
1458 if (srcStrLengthNL) {
1459 // finalStrLength >= srcStrLength
1460 SVal sourceInResult = svalBuilder.evalBinOpNN(state, BO_GE,
1461 *finalStrLengthNL,
1462 *srcStrLengthNL,
1463 cmpTy);
1464 state = state->assume(cast<DefinedOrUnknownSVal>(sourceInResult),
1465 true);
1466 if (!state)
1467 return;
1468 }
1469
1470 if (dstStrLengthNL) {
1471 // finalStrLength >= dstStrLength
1472 SVal destInResult = svalBuilder.evalBinOpNN(state, BO_GE,
1473 *finalStrLengthNL,
1474 *dstStrLengthNL,
1475 cmpTy);
1476 state = state->assume(cast<DefinedOrUnknownSVal>(destInResult),
1477 true);
1478 if (!state)
1479 return;
1480 }
1481 }
1482 }
1483
1484 } else {
1485 // Otherwise, this is a copy-over function (strcpy, strncpy, ...), and
1486 // the final string length will match the input string length.
1487 finalStrLength = amountCopied;
Lenny Maiorani067bbd02011-04-09 15:12:58 +00001488 }
1489
Jordy Rosed5af0e12011-06-15 05:52:56 +00001490 // The final result of the function will either be a pointer past the last
1491 // copied element, or a pointer to the start of the destination buffer.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001492 SVal Result = (returnEnd ? UnknownVal() : DstVal);
Jordy Rosee64f3112010-08-16 07:51:42 +00001493
Jordy Rosed5af0e12011-06-15 05:52:56 +00001494 assert(state);
1495
Jordy Rosee64f3112010-08-16 07:51:42 +00001496 // If the destination is a MemRegion, try to check for a buffer overflow and
1497 // record the new string length.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001498 if (loc::MemRegionVal *dstRegVal = dyn_cast<loc::MemRegionVal>(&DstVal)) {
Jordy Rose8912aae2011-06-20 21:55:40 +00001499 QualType ptrTy = Dst->getType();
1500
1501 // If we have an exact value on a bounded copy, use that to check for
1502 // overflows, rather than our estimate about how much is actually copied.
1503 if (boundWarning) {
1504 if (NonLoc *maxLastNL = dyn_cast<NonLoc>(&maxLastElementIndex)) {
1505 SVal maxLastElement = svalBuilder.evalBinOpLN(state, BO_Add, *dstRegVal,
1506 *maxLastNL, ptrTy);
1507 state = CheckLocation(C, state, CE->getArg(2), maxLastElement,
1508 boundWarning);
1509 if (!state)
1510 return;
1511 }
1512 }
1513
1514 // Then, if the final length is known...
Jordy Rosed5af0e12011-06-15 05:52:56 +00001515 if (NonLoc *knownStrLength = dyn_cast<NonLoc>(&finalStrLength)) {
1516 SVal lastElement = svalBuilder.evalBinOpLN(state, BO_Add, *dstRegVal,
Jordy Rose8912aae2011-06-20 21:55:40 +00001517 *knownStrLength, ptrTy);
Jordy Rosee64f3112010-08-16 07:51:42 +00001518
Jordy Rose8912aae2011-06-20 21:55:40 +00001519 // ...and we haven't checked the bound, we'll check the actual copy.
1520 if (!boundWarning) {
1521 const char * const warningMsg =
1522 "String copy function overflows destination buffer";
1523 state = CheckLocation(C, state, Dst, lastElement, warningMsg);
1524 if (!state)
1525 return;
1526 }
Jordy Rosee64f3112010-08-16 07:51:42 +00001527
1528 // If this is a stpcpy-style copy, the last element is the return value.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001529 if (returnEnd)
1530 Result = lastElement;
Jordy Rosee64f3112010-08-16 07:51:42 +00001531 }
1532
1533 // Invalidate the destination. This must happen before we set the C string
1534 // length because invalidation will clear the length.
1535 // FIXME: Even if we can't perfectly model the copy, we should see if we
1536 // can use LazyCompoundVals to copy the source values into the destination.
1537 // This would probably remove any existing bindings past the end of the
1538 // string, but that's still an improvement over blank invalidation.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001539 state = InvalidateBuffer(C, state, Dst, *dstRegVal);
Jordy Rosee64f3112010-08-16 07:51:42 +00001540
Jordy Rose5e5f1502011-06-20 03:49:16 +00001541 // Set the C string length of the destination, if we know it.
Jordy Rose8912aae2011-06-20 21:55:40 +00001542 if (isBounded && !isAppending) {
1543 // strncpy is annoying in that it doesn't guarantee to null-terminate
1544 // the result string. If the original string didn't fit entirely inside
1545 // the bound (including the null-terminator), we don't know how long the
1546 // result is.
1547 if (amountCopied != strLength)
1548 finalStrLength = UnknownVal();
1549 }
1550 state = setCStringLength(state, dstRegVal->getRegion(), finalStrLength);
Jordy Rosee64f3112010-08-16 07:51:42 +00001551 }
1552
Jordy Rosed5af0e12011-06-15 05:52:56 +00001553 assert(state);
1554
Jordy Rosee64f3112010-08-16 07:51:42 +00001555 // If this is a stpcpy-style copy, but we were unable to check for a buffer
1556 // overflow, we still need a result. Conjure a return value.
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001557 if (returnEnd && Result.isUnknown()) {
Anna Zaks5d0ea6d2011-10-04 20:43:05 +00001558 unsigned Count = C.getCurrentBlockCount();
Jordy Rosed5af0e12011-06-15 05:52:56 +00001559 Result = svalBuilder.getConjuredSymbolVal(NULL, CE, Count);
Jordy Rosee64f3112010-08-16 07:51:42 +00001560 }
1561
1562 // Set the return value.
Ted Kremenek5eca4822012-01-06 22:09:28 +00001563 state = state->BindExpr(CE, LCtx, Result);
Anna Zaks0bd6b112011-10-26 21:06:34 +00001564 C.addTransition(state);
Jordy Rosee64f3112010-08-16 07:51:42 +00001565}
1566
Lenny Maiorani318dd922011-04-12 17:08:43 +00001567void CStringChecker::evalStrcmp(CheckerContext &C, const CallExpr *CE) const {
Jordy Roseadc42d42011-06-16 07:13:34 +00001568 //int strcmp(const char *s1, const char *s2);
Lenny Maioranibd1d16a2011-04-28 15:09:11 +00001569 evalStrcmpCommon(C, CE, /* isBounded = */ false, /* ignoreCase = */ false);
Lenny Maiorani357f6ee2011-04-25 22:21:00 +00001570}
Lenny Maiorani318dd922011-04-12 17:08:43 +00001571
Lenny Maiorani357f6ee2011-04-25 22:21:00 +00001572void CStringChecker::evalStrncmp(CheckerContext &C, const CallExpr *CE) const {
Jordy Roseadc42d42011-06-16 07:13:34 +00001573 //int strncmp(const char *s1, const char *s2, size_t n);
Lenny Maioranibd1d16a2011-04-28 15:09:11 +00001574 evalStrcmpCommon(C, CE, /* isBounded = */ true, /* ignoreCase = */ false);
1575}
1576
1577void CStringChecker::evalStrcasecmp(CheckerContext &C,
1578 const CallExpr *CE) const {
Jordy Roseadc42d42011-06-16 07:13:34 +00001579 //int strcasecmp(const char *s1, const char *s2);
Lenny Maioranibd1d16a2011-04-28 15:09:11 +00001580 evalStrcmpCommon(C, CE, /* isBounded = */ false, /* ignoreCase = */ true);
Lenny Maiorani357f6ee2011-04-25 22:21:00 +00001581}
1582
Lenny Maiorani454fd2d2011-05-02 19:05:49 +00001583void CStringChecker::evalStrncasecmp(CheckerContext &C,
1584 const CallExpr *CE) const {
Jordy Roseadc42d42011-06-16 07:13:34 +00001585 //int strncasecmp(const char *s1, const char *s2, size_t n);
Lenny Maiorani454fd2d2011-05-02 19:05:49 +00001586 evalStrcmpCommon(C, CE, /* isBounded = */ true, /* ignoreCase = */ true);
1587}
1588
Lenny Maiorani357f6ee2011-04-25 22:21:00 +00001589void CStringChecker::evalStrcmpCommon(CheckerContext &C, const CallExpr *CE,
Lenny Maioranibd1d16a2011-04-28 15:09:11 +00001590 bool isBounded, bool ignoreCase) const {
Jordy Rose9e49d9f2011-06-20 02:06:40 +00001591 CurrentFunctionDescription = "string comparison function";
Ted Kremenek8bef8232012-01-26 21:29:00 +00001592 ProgramStateRef state = C.getState();
Ted Kremenek5eca4822012-01-06 22:09:28 +00001593 const LocationContext *LCtx = C.getLocationContext();
Lenny Maiorani318dd922011-04-12 17:08:43 +00001594
1595 // Check that the first string is non-null
1596 const Expr *s1 = CE->getArg(0);
Ted Kremenek5eca4822012-01-06 22:09:28 +00001597 SVal s1Val = state->getSVal(s1, LCtx);
Lenny Maiorani318dd922011-04-12 17:08:43 +00001598 state = checkNonNull(C, state, s1, s1Val);
1599 if (!state)
1600 return;
1601
1602 // Check that the second string is non-null.
1603 const Expr *s2 = CE->getArg(1);
Ted Kremenek5eca4822012-01-06 22:09:28 +00001604 SVal s2Val = state->getSVal(s2, LCtx);
Lenny Maiorani318dd922011-04-12 17:08:43 +00001605 state = checkNonNull(C, state, s2, s2Val);
1606 if (!state)
1607 return;
1608
1609 // Get the string length of the first string or give up.
1610 SVal s1Length = getCStringLength(C, state, s1, s1Val);
1611 if (s1Length.isUndef())
1612 return;
1613
1614 // Get the string length of the second string or give up.
1615 SVal s2Length = getCStringLength(C, state, s2, s2Val);
1616 if (s2Length.isUndef())
1617 return;
1618
Jordy Roseadc42d42011-06-16 07:13:34 +00001619 // If we know the two buffers are the same, we know the result is 0.
1620 // First, get the two buffers' addresses. Another checker will have already
1621 // made sure they're not undefined.
1622 DefinedOrUnknownSVal LV = cast<DefinedOrUnknownSVal>(s1Val);
1623 DefinedOrUnknownSVal RV = cast<DefinedOrUnknownSVal>(s2Val);
Lenny Maiorani318dd922011-04-12 17:08:43 +00001624
Jordy Roseadc42d42011-06-16 07:13:34 +00001625 // See if they are the same.
Lenny Maiorani318dd922011-04-12 17:08:43 +00001626 SValBuilder &svalBuilder = C.getSValBuilder();
Jordy Roseadc42d42011-06-16 07:13:34 +00001627 DefinedOrUnknownSVal SameBuf = svalBuilder.evalEQ(state, LV, RV);
Ted Kremenek8bef8232012-01-26 21:29:00 +00001628 ProgramStateRef StSameBuf, StNotSameBuf;
Jordy Roseadc42d42011-06-16 07:13:34 +00001629 llvm::tie(StSameBuf, StNotSameBuf) = state->assume(SameBuf);
Lenny Maiorani318dd922011-04-12 17:08:43 +00001630
Jordy Roseadc42d42011-06-16 07:13:34 +00001631 // If the two arguments might be the same buffer, we know the result is 0,
1632 // and we only need to check one size.
1633 if (StSameBuf) {
Ted Kremenek5eca4822012-01-06 22:09:28 +00001634 StSameBuf = StSameBuf->BindExpr(CE, LCtx,
1635 svalBuilder.makeZeroVal(CE->getType()));
Anna Zaks0bd6b112011-10-26 21:06:34 +00001636 C.addTransition(StSameBuf);
Jordy Roseadc42d42011-06-16 07:13:34 +00001637
1638 // If the two arguments are GUARANTEED to be the same, we're done!
1639 if (!StNotSameBuf)
1640 return;
1641 }
1642
1643 assert(StNotSameBuf);
1644 state = StNotSameBuf;
1645
1646 // At this point we can go about comparing the two buffers.
1647 // For now, we only do this if they're both known string literals.
1648
1649 // Attempt to extract string literals from both expressions.
1650 const StringLiteral *s1StrLiteral = getCStringLiteral(C, state, s1, s1Val);
1651 const StringLiteral *s2StrLiteral = getCStringLiteral(C, state, s2, s2Val);
1652 bool canComputeResult = false;
1653
1654 if (s1StrLiteral && s2StrLiteral) {
Chris Lattner5f9e2722011-07-23 10:55:15 +00001655 StringRef s1StrRef = s1StrLiteral->getString();
1656 StringRef s2StrRef = s2StrLiteral->getString();
Jordy Roseadc42d42011-06-16 07:13:34 +00001657
1658 if (isBounded) {
1659 // Get the max number of characters to compare.
1660 const Expr *lenExpr = CE->getArg(2);
Ted Kremenek5eca4822012-01-06 22:09:28 +00001661 SVal lenVal = state->getSVal(lenExpr, LCtx);
Jordy Roseadc42d42011-06-16 07:13:34 +00001662
1663 // If the length is known, we can get the right substrings.
1664 if (const llvm::APSInt *len = svalBuilder.getKnownValue(state, lenVal)) {
1665 // Create substrings of each to compare the prefix.
1666 s1StrRef = s1StrRef.substr(0, (size_t)len->getZExtValue());
1667 s2StrRef = s2StrRef.substr(0, (size_t)len->getZExtValue());
1668 canComputeResult = true;
1669 }
1670 } else {
1671 // This is a normal, unbounded strcmp.
1672 canComputeResult = true;
1673 }
1674
1675 if (canComputeResult) {
1676 // Real strcmp stops at null characters.
1677 size_t s1Term = s1StrRef.find('\0');
Chris Lattner5f9e2722011-07-23 10:55:15 +00001678 if (s1Term != StringRef::npos)
Jordy Roseadc42d42011-06-16 07:13:34 +00001679 s1StrRef = s1StrRef.substr(0, s1Term);
1680
1681 size_t s2Term = s2StrRef.find('\0');
Chris Lattner5f9e2722011-07-23 10:55:15 +00001682 if (s2Term != StringRef::npos)
Jordy Roseadc42d42011-06-16 07:13:34 +00001683 s2StrRef = s2StrRef.substr(0, s2Term);
1684
1685 // Use StringRef's comparison methods to compute the actual result.
1686 int result;
1687
1688 if (ignoreCase) {
1689 // Compare string 1 to string 2 the same way strcasecmp() does.
1690 result = s1StrRef.compare_lower(s2StrRef);
1691 } else {
1692 // Compare string 1 to string 2 the same way strcmp() does.
1693 result = s1StrRef.compare(s2StrRef);
1694 }
1695
1696 // Build the SVal of the comparison and bind the return value.
1697 SVal resultVal = svalBuilder.makeIntVal(result, CE->getType());
Ted Kremenek5eca4822012-01-06 22:09:28 +00001698 state = state->BindExpr(CE, LCtx, resultVal);
Jordy Roseadc42d42011-06-16 07:13:34 +00001699 }
1700 }
1701
1702 if (!canComputeResult) {
1703 // Conjure a symbolic value. It's the best we can do.
Anna Zaks5d0ea6d2011-10-04 20:43:05 +00001704 unsigned Count = C.getCurrentBlockCount();
Jordy Roseadc42d42011-06-16 07:13:34 +00001705 SVal resultVal = svalBuilder.getConjuredSymbolVal(NULL, CE, Count);
Ted Kremenek5eca4822012-01-06 22:09:28 +00001706 state = state->BindExpr(CE, LCtx, resultVal);
Jordy Roseadc42d42011-06-16 07:13:34 +00001707 }
1708
1709 // Record this as a possible path.
Anna Zaks0bd6b112011-10-26 21:06:34 +00001710 C.addTransition(state);
Lenny Maiorani318dd922011-04-12 17:08:43 +00001711}
1712
Jordy Rosed325ffb2010-07-08 23:57:29 +00001713//===----------------------------------------------------------------------===//
Jordy Rosea5261542010-08-14 21:02:52 +00001714// The driver method, and other Checker callbacks.
Jordy Rosed325ffb2010-07-08 23:57:29 +00001715//===----------------------------------------------------------------------===//
Jordy Roseccbf7ee2010-07-06 23:11:01 +00001716
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +00001717bool CStringChecker::evalCall(const CallExpr *CE, CheckerContext &C) const {
Anna Zaks998e2752012-02-17 22:35:26 +00001718 const FunctionDecl *FDecl = C.getCalleeDecl(CE);
1719
1720 if (!FDecl)
Jordy Roseccbf7ee2010-07-06 23:11:01 +00001721 return false;
Jordy Roseccbf7ee2010-07-06 23:11:01 +00001722
Anna Zaks998e2752012-02-17 22:35:26 +00001723 FnCheck evalFunction = 0;
1724 if (C.isCLibraryFunction(FDecl, "memcpy"))
1725 evalFunction = &CStringChecker::evalMemcpy;
1726 else if (C.isCLibraryFunction(FDecl, "mempcpy"))
1727 evalFunction = &CStringChecker::evalMempcpy;
1728 else if (C.isCLibraryFunction(FDecl, "memcmp"))
1729 evalFunction = &CStringChecker::evalMemcmp;
1730 else if (C.isCLibraryFunction(FDecl, "memmove"))
1731 evalFunction = &CStringChecker::evalMemmove;
1732 else if (C.isCLibraryFunction(FDecl, "strcpy"))
1733 evalFunction = &CStringChecker::evalStrcpy;
1734 else if (C.isCLibraryFunction(FDecl, "strncpy"))
1735 evalFunction = &CStringChecker::evalStrncpy;
1736 else if (C.isCLibraryFunction(FDecl, "stpcpy"))
1737 evalFunction = &CStringChecker::evalStpcpy;
1738 else if (C.isCLibraryFunction(FDecl, "strcat"))
1739 evalFunction = &CStringChecker::evalStrcat;
1740 else if (C.isCLibraryFunction(FDecl, "strncat"))
1741 evalFunction = &CStringChecker::evalStrncat;
1742 else if (C.isCLibraryFunction(FDecl, "strlen"))
1743 evalFunction = &CStringChecker::evalstrLength;
1744 else if (C.isCLibraryFunction(FDecl, "strnlen"))
1745 evalFunction = &CStringChecker::evalstrnLength;
1746 else if (C.isCLibraryFunction(FDecl, "strcmp"))
1747 evalFunction = &CStringChecker::evalStrcmp;
1748 else if (C.isCLibraryFunction(FDecl, "strncmp"))
1749 evalFunction = &CStringChecker::evalStrncmp;
1750 else if (C.isCLibraryFunction(FDecl, "strcasecmp"))
1751 evalFunction = &CStringChecker::evalStrcasecmp;
1752 else if (C.isCLibraryFunction(FDecl, "strncasecmp"))
1753 evalFunction = &CStringChecker::evalStrncasecmp;
1754 else if (C.isCLibraryFunction(FDecl, "bcopy"))
1755 evalFunction = &CStringChecker::evalBcopy;
1756 else if (C.isCLibraryFunction(FDecl, "bcmp"))
1757 evalFunction = &CStringChecker::evalMemcmp;
1758
Jordy Rosed325ffb2010-07-08 23:57:29 +00001759 // If the callee isn't a string function, let another checker handle it.
Ted Kremenek9c149532010-12-01 21:57:22 +00001760 if (!evalFunction)
Jordy Roseccbf7ee2010-07-06 23:11:01 +00001761 return false;
1762
Jordy Rose9e49d9f2011-06-20 02:06:40 +00001763 // Make sure each function sets its own description.
1764 // (But don't bother in a release build.)
1765 assert(!(CurrentFunctionDescription = NULL));
1766
Jordy Rosed325ffb2010-07-08 23:57:29 +00001767 // Check and evaluate the call.
Ted Kremenek9c149532010-12-01 21:57:22 +00001768 (this->*evalFunction)(C, CE);
Anna Zaks57300762012-02-07 00:56:14 +00001769
1770 // If the evaluate call resulted in no change, chain to the next eval call
1771 // handler.
1772 // Note, the custom CString evaluation calls assume that basic safety
1773 // properties are held. However, if the user chooses to turn off some of these
1774 // checks, we ignore the issues and leave the call evaluation to a generic
1775 // handler.
1776 if (!C.isDifferent())
1777 return false;
1778
Jordy Roseccbf7ee2010-07-06 23:11:01 +00001779 return true;
1780}
Jordy Rosea5261542010-08-14 21:02:52 +00001781
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +00001782void CStringChecker::checkPreStmt(const DeclStmt *DS, CheckerContext &C) const {
Jordy Rosea5261542010-08-14 21:02:52 +00001783 // Record string length for char a[] = "abc";
Ted Kremenek8bef8232012-01-26 21:29:00 +00001784 ProgramStateRef state = C.getState();
Jordy Rosea5261542010-08-14 21:02:52 +00001785
1786 for (DeclStmt::const_decl_iterator I = DS->decl_begin(), E = DS->decl_end();
1787 I != E; ++I) {
1788 const VarDecl *D = dyn_cast<VarDecl>(*I);
1789 if (!D)
1790 continue;
1791
1792 // FIXME: Handle array fields of structs.
1793 if (!D->getType()->isArrayType())
1794 continue;
1795
1796 const Expr *Init = D->getInit();
1797 if (!Init)
1798 continue;
1799 if (!isa<StringLiteral>(Init))
1800 continue;
1801
Anna Zaks39ac1872011-10-26 21:06:44 +00001802 Loc VarLoc = state->getLValue(D, C.getLocationContext());
Jordy Rosea5261542010-08-14 21:02:52 +00001803 const MemRegion *MR = VarLoc.getAsRegion();
1804 if (!MR)
1805 continue;
1806
Ted Kremenek5eca4822012-01-06 22:09:28 +00001807 SVal StrVal = state->getSVal(Init, C.getLocationContext());
Jordy Rosea5261542010-08-14 21:02:52 +00001808 assert(StrVal.isValid() && "Initializer string is unknown or undefined");
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001809 DefinedOrUnknownSVal strLength
1810 = cast<DefinedOrUnknownSVal>(getCStringLength(C, state, Init, StrVal));
Jordy Rosea5261542010-08-14 21:02:52 +00001811
Ted Kremenekc8413fd2010-12-02 07:49:45 +00001812 state = state->set<CStringLength>(MR, strLength);
Jordy Rosea5261542010-08-14 21:02:52 +00001813 }
1814
Anna Zaks0bd6b112011-10-26 21:06:34 +00001815 C.addTransition(state);
Jordy Rosea5261542010-08-14 21:02:52 +00001816}
1817
Ted Kremenek8bef8232012-01-26 21:29:00 +00001818bool CStringChecker::wantsRegionChangeUpdate(ProgramStateRef state) const {
Jordy Rosea5261542010-08-14 21:02:52 +00001819 CStringLength::EntryMap Entries = state->get<CStringLength>();
1820 return !Entries.isEmpty();
1821}
1822
Ted Kremenek8bef8232012-01-26 21:29:00 +00001823ProgramStateRef
1824CStringChecker::checkRegionChanges(ProgramStateRef state,
Ted Kremenek35bdbf42011-05-02 19:42:42 +00001825 const StoreManager::InvalidatedSymbols *,
Jordy Rose537716a2011-08-27 22:51:26 +00001826 ArrayRef<const MemRegion *> ExplicitRegions,
Anna Zaks66c40402012-02-14 21:55:24 +00001827 ArrayRef<const MemRegion *> Regions,
1828 const CallOrObjCMessage *Call) const {
Jordy Rosea5261542010-08-14 21:02:52 +00001829 CStringLength::EntryMap Entries = state->get<CStringLength>();
1830 if (Entries.isEmpty())
1831 return state;
1832
1833 llvm::SmallPtrSet<const MemRegion *, 8> Invalidated;
1834 llvm::SmallPtrSet<const MemRegion *, 32> SuperRegions;
1835
1836 // First build sets for the changed regions and their super-regions.
Jordy Rose537716a2011-08-27 22:51:26 +00001837 for (ArrayRef<const MemRegion *>::iterator
1838 I = Regions.begin(), E = Regions.end(); I != E; ++I) {
1839 const MemRegion *MR = *I;
Jordy Rosea5261542010-08-14 21:02:52 +00001840 Invalidated.insert(MR);
1841
1842 SuperRegions.insert(MR);
1843 while (const SubRegion *SR = dyn_cast<SubRegion>(MR)) {
1844 MR = SR->getSuperRegion();
1845 SuperRegions.insert(MR);
1846 }
1847 }
1848
1849 CStringLength::EntryMap::Factory &F = state->get_context<CStringLength>();
1850
1851 // Then loop over the entries in the current state.
1852 for (CStringLength::EntryMap::iterator I = Entries.begin(),
1853 E = Entries.end(); I != E; ++I) {
1854 const MemRegion *MR = I.getKey();
1855
1856 // Is this entry for a super-region of a changed region?
1857 if (SuperRegions.count(MR)) {
Ted Kremenek3baf6722010-11-24 00:54:37 +00001858 Entries = F.remove(Entries, MR);
Jordy Rosea5261542010-08-14 21:02:52 +00001859 continue;
1860 }
1861
1862 // Is this entry for a sub-region of a changed region?
1863 const MemRegion *Super = MR;
1864 while (const SubRegion *SR = dyn_cast<SubRegion>(Super)) {
1865 Super = SR->getSuperRegion();
1866 if (Invalidated.count(Super)) {
Ted Kremenek3baf6722010-11-24 00:54:37 +00001867 Entries = F.remove(Entries, MR);
Jordy Rosea5261542010-08-14 21:02:52 +00001868 break;
1869 }
1870 }
1871 }
1872
1873 return state->set<CStringLength>(Entries);
1874}
1875
Ted Kremenek8bef8232012-01-26 21:29:00 +00001876void CStringChecker::checkLiveSymbols(ProgramStateRef state,
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +00001877 SymbolReaper &SR) const {
Jordy Rosea5261542010-08-14 21:02:52 +00001878 // Mark all symbols in our string length map as valid.
1879 CStringLength::EntryMap Entries = state->get<CStringLength>();
1880
1881 for (CStringLength::EntryMap::iterator I = Entries.begin(), E = Entries.end();
1882 I != E; ++I) {
1883 SVal Len = I.getData();
Jordy Rosed5af0e12011-06-15 05:52:56 +00001884
Anna Zaks1d1d5152011-12-06 23:12:33 +00001885 for (SymExpr::symbol_iterator si = Len.symbol_begin(),
1886 se = Len.symbol_end(); si != se; ++si)
Jordy Rosed5af0e12011-06-15 05:52:56 +00001887 SR.markInUse(*si);
Jordy Rosea5261542010-08-14 21:02:52 +00001888 }
1889}
1890
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +00001891void CStringChecker::checkDeadSymbols(SymbolReaper &SR,
1892 CheckerContext &C) const {
Jordy Rosea5261542010-08-14 21:02:52 +00001893 if (!SR.hasDeadSymbols())
1894 return;
1895
Ted Kremenek8bef8232012-01-26 21:29:00 +00001896 ProgramStateRef state = C.getState();
Jordy Rosea5261542010-08-14 21:02:52 +00001897 CStringLength::EntryMap Entries = state->get<CStringLength>();
1898 if (Entries.isEmpty())
1899 return;
1900
1901 CStringLength::EntryMap::Factory &F = state->get_context<CStringLength>();
1902 for (CStringLength::EntryMap::iterator I = Entries.begin(), E = Entries.end();
1903 I != E; ++I) {
1904 SVal Len = I.getData();
1905 if (SymbolRef Sym = Len.getAsSymbol()) {
1906 if (SR.isDead(Sym))
Ted Kremenek3baf6722010-11-24 00:54:37 +00001907 Entries = F.remove(Entries, I.getKey());
Jordy Rosea5261542010-08-14 21:02:52 +00001908 }
1909 }
1910
1911 state = state->set<CStringLength>(Entries);
Anna Zaks0bd6b112011-10-26 21:06:34 +00001912 C.addTransition(state);
Jordy Rosea5261542010-08-14 21:02:52 +00001913}
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +00001914
Anna Zaks57300762012-02-07 00:56:14 +00001915#define REGISTER_CHECKER(name) \
1916void ento::register##name(CheckerManager &mgr) {\
1917 static CStringChecker *TheChecker = 0; \
1918 if (TheChecker == 0) \
1919 TheChecker = mgr.registerChecker<CStringChecker>(); \
1920 TheChecker->Filter.Check##name = true; \
Argyrios Kyrtzidis183ff982011-02-24 01:05:30 +00001921}
Anna Zaks57300762012-02-07 00:56:14 +00001922
1923REGISTER_CHECKER(CStringNullArg)
1924REGISTER_CHECKER(CStringOutOfBounds)
1925REGISTER_CHECKER(CStringBufferOverlap)
1926REGISTER_CHECKER(CStringNotNullTerm)