Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/clang/lib/StaticAnalyzer/Checkers/CStringChecker.cpp
Line
Count
Source (jump to first uncovered line)
1
//= CStringChecker.cpp - Checks calls to C string functions --------*- C++ -*-//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
//
9
// This defines CStringChecker, which is an assortment of checks on calls
10
// to functions in <string.h>.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
15
#include "InterCheckerAPI.h"
16
#include "clang/Basic/CharInfo.h"
17
#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
18
#include "clang/StaticAnalyzer/Core/Checker.h"
19
#include "clang/StaticAnalyzer/Core/CheckerManager.h"
20
#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
21
#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
22
#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
23
#include "llvm/ADT/STLExtras.h"
24
#include "llvm/ADT/SmallString.h"
25
#include "llvm/Support/raw_ostream.h"
26
27
using namespace clang;
28
using namespace ento;
29
30
namespace {
31
class CStringChecker : public Checker< eval::Call,
32
                                         check::PreStmt<DeclStmt>,
33
                                         check::LiveSymbols,
34
                                         check::DeadSymbols,
35
                                         check::RegionChanges
36
                                         > {
37
  mutable std::unique_ptr<BugType> BT_Null, BT_Bounds, BT_Overlap,
38
      BT_NotCString, BT_AdditionOverflow;
39
40
  mutable const char *CurrentFunctionDescription;
41
42
public:
43
  /// The filter is used to filter out the diagnostics which are not enabled by
44
  /// the user.
45
  struct CStringChecksFilter {
46
    DefaultBool CheckCStringNullArg;
47
    DefaultBool CheckCStringOutOfBounds;
48
    DefaultBool CheckCStringBufferOverlap;
49
    DefaultBool CheckCStringNotNullTerm;
50
51
    CheckName CheckNameCStringNullArg;
52
    CheckName CheckNameCStringOutOfBounds;
53
    CheckName CheckNameCStringBufferOverlap;
54
    CheckName CheckNameCStringNotNullTerm;
55
  };
56
57
  CStringChecksFilter Filter;
58
59
500
  static void *getTag() { static int tag; return &tag; }
60
61
  bool evalCall(const CallEvent &Call, CheckerContext &C) const;
62
  void checkPreStmt(const DeclStmt *DS, CheckerContext &C) const;
63
  void checkLiveSymbols(ProgramStateRef state, SymbolReaper &SR) const;
64
  void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
65
66
  ProgramStateRef
67
    checkRegionChanges(ProgramStateRef state,
68
                       const InvalidatedSymbols *,
69
                       ArrayRef<const MemRegion *> ExplicitRegions,
70
                       ArrayRef<const MemRegion *> Regions,
71
                       const LocationContext *LCtx,
72
                       const CallEvent *Call) const;
73
74
  typedef void (CStringChecker::*FnCheck)(CheckerContext &,
75
                                          const CallExpr *) const;
76
  CallDescriptionMap<FnCheck> Callbacks = {
77
      {{CDF_MaybeBuiltin, "memcpy", 3}, &CStringChecker::evalMemcpy},
78
      {{CDF_MaybeBuiltin, "mempcpy", 3}, &CStringChecker::evalMempcpy},
79
      {{CDF_MaybeBuiltin, "memcmp", 3}, &CStringChecker::evalMemcmp},
80
      {{CDF_MaybeBuiltin, "memmove", 3}, &CStringChecker::evalMemmove},
81
      {{CDF_MaybeBuiltin, "memset", 3}, &CStringChecker::evalMemset},
82
      {{CDF_MaybeBuiltin, "explicit_memset", 3}, &CStringChecker::evalMemset},
83
      {{CDF_MaybeBuiltin, "strcpy", 2}, &CStringChecker::evalStrcpy},
84
      {{CDF_MaybeBuiltin, "strncpy", 3}, &CStringChecker::evalStrncpy},
85
      {{CDF_MaybeBuiltin, "stpcpy", 2}, &CStringChecker::evalStpcpy},
86
      {{CDF_MaybeBuiltin, "strlcpy", 3}, &CStringChecker::evalStrlcpy},
87
      {{CDF_MaybeBuiltin, "strcat", 2}, &CStringChecker::evalStrcat},
88
      {{CDF_MaybeBuiltin, "strncat", 3}, &CStringChecker::evalStrncat},
89
      {{CDF_MaybeBuiltin, "strlcat", 3}, &CStringChecker::evalStrlcat},
90
      {{CDF_MaybeBuiltin, "strlen", 1}, &CStringChecker::evalstrLength},
91
      {{CDF_MaybeBuiltin, "strnlen", 2}, &CStringChecker::evalstrnLength},
92
      {{CDF_MaybeBuiltin, "strcmp", 2}, &CStringChecker::evalStrcmp},
93
      {{CDF_MaybeBuiltin, "strncmp", 3}, &CStringChecker::evalStrncmp},
94
      {{CDF_MaybeBuiltin, "strcasecmp", 2}, &CStringChecker::evalStrcasecmp},
95
      {{CDF_MaybeBuiltin, "strncasecmp", 3}, &CStringChecker::evalStrncasecmp},
96
      {{CDF_MaybeBuiltin, "strsep", 2}, &CStringChecker::evalStrsep},
97
      {{CDF_MaybeBuiltin, "bcopy", 3}, &CStringChecker::evalBcopy},
98
      {{CDF_MaybeBuiltin, "bcmp", 3}, &CStringChecker::evalMemcmp},
99
      {{CDF_MaybeBuiltin, "bzero", 2}, &CStringChecker::evalBzero},
100
      {{CDF_MaybeBuiltin, "explicit_bzero", 2}, &CStringChecker::evalBzero},
101
  };
102
103
  // These require a bit of special handling.
104
  CallDescription StdCopy{{"std", "copy"}, 3},
105
      StdCopyBackward{{"std", "copy_backward"}, 3};
106
107
  FnCheck identifyCall(const CallEvent &Call, CheckerContext &C) const;
108
  void evalMemcpy(CheckerContext &C, const CallExpr *CE) const;
109
  void evalMempcpy(CheckerContext &C, const CallExpr *CE) const;
110
  void evalMemmove(CheckerContext &C, const CallExpr *CE) const;
111
  void evalBcopy(CheckerContext &C, const CallExpr *CE) const;
112
  void evalCopyCommon(CheckerContext &C, const CallExpr *CE,
113
                      ProgramStateRef state,
114
                      const Expr *Size,
115
                      const Expr *Source,
116
                      const Expr *Dest,
117
                      bool Restricted = false,
118
                      bool IsMempcpy = false) const;
119
120
  void evalMemcmp(CheckerContext &C, const CallExpr *CE) const;
121
122
  void evalstrLength(CheckerContext &C, const CallExpr *CE) const;
123
  void evalstrnLength(CheckerContext &C, const CallExpr *CE) const;
124
  void evalstrLengthCommon(CheckerContext &C,
125
                           const CallExpr *CE,
126
                           bool IsStrnlen = false) const;
127
128
  void evalStrcpy(CheckerContext &C, const CallExpr *CE) const;
129
  void evalStrncpy(CheckerContext &C, const CallExpr *CE) const;
130
  void evalStpcpy(CheckerContext &C, const CallExpr *CE) const;
131
  void evalStrlcpy(CheckerContext &C, const CallExpr *CE) const;
132
  void evalStrcpyCommon(CheckerContext &C,
133
                        const CallExpr *CE,
134
                        bool returnEnd,
135
                        bool isBounded,
136
                        bool isAppending,
137
                        bool returnPtr = true) const;
138
139
  void evalStrcat(CheckerContext &C, const CallExpr *CE) const;
140
  void evalStrncat(CheckerContext &C, const CallExpr *CE) const;
141
  void evalStrlcat(CheckerContext &C, const CallExpr *CE) const;
142
143
  void evalStrcmp(CheckerContext &C, const CallExpr *CE) const;
144
  void evalStrncmp(CheckerContext &C, const CallExpr *CE) const;
145
  void evalStrcasecmp(CheckerContext &C, const CallExpr *CE) const;
146
  void evalStrncasecmp(CheckerContext &C, const CallExpr *CE) const;
147
  void evalStrcmpCommon(CheckerContext &C,
148
                        const CallExpr *CE,
149
                        bool isBounded = false,
150
                        bool ignoreCase = false) const;
151
152
  void evalStrsep(CheckerContext &C, const CallExpr *CE) const;
153
154
  void evalStdCopy(CheckerContext &C, const CallExpr *CE) const;
155
  void evalStdCopyBackward(CheckerContext &C, const CallExpr *CE) const;
156
  void evalStdCopyCommon(CheckerContext &C, const CallExpr *CE) const;
157
  void evalMemset(CheckerContext &C, const CallExpr *CE) const;
158
  void evalBzero(CheckerContext &C, const CallExpr *CE) const;
159
160
  // Utility methods
161
  std::pair<ProgramStateRef , ProgramStateRef >
162
  static assumeZero(CheckerContext &C,
163
                    ProgramStateRef state, SVal V, QualType Ty);
164
165
  static ProgramStateRef setCStringLength(ProgramStateRef state,
166
                                              const MemRegion *MR,
167
                                              SVal strLength);
168
  static SVal getCStringLengthForRegion(CheckerContext &C,
169
                                        ProgramStateRef &state,
170
                                        const Expr *Ex,
171
                                        const MemRegion *MR,
172
                                        bool hypothetical);
173
  SVal getCStringLength(CheckerContext &C,
174
                        ProgramStateRef &state,
175
                        const Expr *Ex,
176
                        SVal Buf,
177
                        bool hypothetical = false) const;
178
179
  const StringLiteral *getCStringLiteral(CheckerContext &C,
180
                                         ProgramStateRef &state,
181
                                         const Expr *expr,
182
                                         SVal val) const;
183
184
  static ProgramStateRef InvalidateBuffer(CheckerContext &C,
185
                                          ProgramStateRef state,
186
                                          const Expr *Ex, SVal V,
187
                                          bool IsSourceBuffer,
188
                                          const Expr *Size);
189
190
  static bool SummarizeRegion(raw_ostream &os, ASTContext &Ctx,
191
                              const MemRegion *MR);
192
193
  static bool memsetAux(const Expr *DstBuffer, SVal CharE,
194
                        const Expr *Size, CheckerContext &C,
195
                        ProgramStateRef &State);
196
197
  // Re-usable checks
198
  ProgramStateRef checkNonNull(CheckerContext &C,
199
                                   ProgramStateRef state,
200
                                   const Expr *S,
201
                                   SVal l) const;
202
  ProgramStateRef CheckLocation(CheckerContext &C,
203
                                    ProgramStateRef state,
204
                                    const Expr *S,
205
                                    SVal l,
206
                                    const char *message = nullptr) const;
207
  ProgramStateRef CheckBufferAccess(CheckerContext &C,
208
                                        ProgramStateRef state,
209
                                        const Expr *Size,
210
                                        const Expr *FirstBuf,
211
                                        const Expr *SecondBuf,
212
                                        const char *firstMessage = nullptr,
213
                                        const char *secondMessage = nullptr,
214
                                        bool WarnAboutSize = false) const;
215
216
  ProgramStateRef CheckBufferAccess(CheckerContext &C,
217
                                        ProgramStateRef state,
218
                                        const Expr *Size,
219
                                        const Expr *Buf,
220
                                        const char *message = nullptr,
221
200
                                        bool WarnAboutSize = false) const {
222
200
    // This is a convenience overload.
223
200
    return CheckBufferAccess(C, state, Size, Buf, nullptr, message, nullptr,
224
200
                             WarnAboutSize);
225
200
  }
226
  ProgramStateRef CheckOverlap(CheckerContext &C,
227
                                   ProgramStateRef state,
228
                                   const Expr *Size,
229
                                   const Expr *First,
230
                                   const Expr *Second) const;
231
  void emitOverlapBug(CheckerContext &C,
232
                      ProgramStateRef state,
233
                      const Stmt *First,
234
                      const Stmt *Second) const;
235
236
  void emitNullArgBug(CheckerContext &C, ProgramStateRef State, const Stmt *S,
237
                      StringRef WarningMsg) const;
238
  void emitOutOfBoundsBug(CheckerContext &C, ProgramStateRef State,
239
                          const Stmt *S, StringRef WarningMsg) const;
240
  void emitNotCStringBug(CheckerContext &C, ProgramStateRef State,
241
                         const Stmt *S, StringRef WarningMsg) const;
242
  void emitAdditionOverflowBug(CheckerContext &C, ProgramStateRef State) const;
243
244
  ProgramStateRef checkAdditionOverflow(CheckerContext &C,
245
                                            ProgramStateRef state,
246
                                            NonLoc left,
247
                                            NonLoc right) const;
248
249
  // Return true if the destination buffer of the copy function may be in bound.
250
  // Expects SVal of Size to be positive and unsigned.
251
  // Expects SVal of FirstBuf to be a FieldRegion.
252
  static bool IsFirstBufInBound(CheckerContext &C,
253
                                ProgramStateRef state,
254
                                const Expr *FirstBuf,
255
                                const Expr *Size);
256
};
257
258
} //end anonymous namespace
259
260
REGISTER_MAP_WITH_PROGRAMSTATE(CStringLength, const MemRegion *, SVal)
261
262
//===----------------------------------------------------------------------===//
263
// Individual checks and utility methods.
264
//===----------------------------------------------------------------------===//
265
266
std::pair<ProgramStateRef , ProgramStateRef >
267
CStringChecker::assumeZero(CheckerContext &C, ProgramStateRef state, SVal V,
268
4.41k
                           QualType Ty) {
269
4.41k
  Optional<DefinedSVal> val = V.getAs<DefinedSVal>();
270
4.41k
  if (!val)
271
10
    return std::pair<ProgramStateRef , ProgramStateRef >(state, state);
272
4.40k
273
4.40k
  SValBuilder &svalBuilder = C.getSValBuilder();
274
4.40k
  DefinedOrUnknownSVal zero = svalBuilder.makeZeroVal(Ty);
275
4.40k
  return state->assume(svalBuilder.evalEQ(state, *val, zero));
276
4.40k
}
277
278
ProgramStateRef CStringChecker::checkNonNull(CheckerContext &C,
279
                                            ProgramStateRef state,
280
3.55k
                                            const Expr *S, SVal l) const {
281
3.55k
  // If a previous check has failed, propagate the failure.
282
3.55k
  if (!state)
283
0
    return nullptr;
284
3.55k
285
3.55k
  ProgramStateRef stateNull, stateNonNull;
286
3.55k
  std::tie(stateNull, stateNonNull) = assumeZero(C, state, l, S->getType());
287
3.55k
288
3.55k
  if (stateNull && 
!stateNonNull537
) {
289
144
    if (Filter.CheckCStringNullArg) {
290
144
      SmallString<80> buf;
291
144
      llvm::raw_svector_ostream os(buf);
292
144
      assert(CurrentFunctionDescription);
293
144
      os << "Null pointer argument in call to " << CurrentFunctionDescription;
294
144
295
144
      emitNullArgBug(C, stateNull, S, os.str());
296
144
    }
297
144
    return nullptr;
298
144
  }
299
3.40k
300
3.40k
  // From here on, assume that the value is non-null.
301
3.40k
  assert(stateNonNull);
302
3.40k
  return stateNonNull;
303
3.40k
}
304
305
// FIXME: This was originally copied from ArrayBoundChecker.cpp. Refactor?
306
ProgramStateRef CStringChecker::CheckLocation(CheckerContext &C,
307
                                             ProgramStateRef state,
308
                                             const Expr *S, SVal l,
309
791
                                             const char *warningMsg) const {
310
791
  // If a previous check has failed, propagate the failure.
311
791
  if (!state)
312
0
    return nullptr;
313
791
314
791
  // Check for out of bound array element access.
315
791
  const MemRegion *R = l.getAsRegion();
316
791
  if (!R)
317
0
    return state;
318
791
319
791
  const ElementRegion *ER = dyn_cast<ElementRegion>(R);
320
791
  if (!ER)
321
0
    return state;
322
791
323
791
  if (ER->getValueType() != C.getASTContext().CharTy)
324
1
    return state;
325
790
326
790
  // Get the size of the array.
327
790
  const SubRegion *superReg = cast<SubRegion>(ER->getSuperRegion());
328
790
  SValBuilder &svalBuilder = C.getSValBuilder();
329
790
  SVal Extent =
330
790
    svalBuilder.convertToArrayIndex(superReg->getExtent(svalBuilder));
331
790
  DefinedOrUnknownSVal Size = Extent.castAs<DefinedOrUnknownSVal>();
332
790
333
790
  // Get the index of the accessed element.
334
790
  DefinedOrUnknownSVal Idx = ER->getIndex().castAs<DefinedOrUnknownSVal>();
335
790
336
790
  ProgramStateRef StInBound = state->assumeInBound(Idx, Size, true);
337
790
  ProgramStateRef StOutBound = state->assumeInBound(Idx, Size, false);
338
790
  if (StOutBound && 
!StInBound301
) {
339
161
    // These checks are either enabled by the CString out-of-bounds checker
340
161
    // explicitly or implicitly by the Malloc checker.
341
161
    // In the latter case we only do modeling but do not emit warning.
342
161
    if (!Filter.CheckCStringOutOfBounds)
343
37
      return nullptr;
344
124
    // Emit a bug report.
345
124
    if (warningMsg) {
346
86
      emitOutOfBoundsBug(C, StOutBound, S, warningMsg);
347
86
    } else {
348
38
      assert(CurrentFunctionDescription);
349
38
      assert(CurrentFunctionDescription[0] != '\0');
350
38
351
38
      SmallString<80> buf;
352
38
      llvm::raw_svector_ostream os(buf);
353
38
      os << toUppercase(CurrentFunctionDescription[0])
354
38
         << &CurrentFunctionDescription[1]
355
38
         << " accesses out-of-bound array element";
356
38
      emitOutOfBoundsBug(C, StOutBound, S, os.str());
357
38
    }
358
124
    return nullptr;
359
124
  }
360
629
361
629
  // Array bound check succeeded.  From this point forward the array bound
362
629
  // should always succeed.
363
629
  return StInBound;
364
629
}
365
366
ProgramStateRef CStringChecker::CheckBufferAccess(CheckerContext &C,
367
                                                 ProgramStateRef state,
368
                                                 const Expr *Size,
369
                                                 const Expr *FirstBuf,
370
                                                 const Expr *SecondBuf,
371
                                                 const char *firstMessage,
372
                                                 const char *secondMessage,
373
442
                                                 bool WarnAboutSize) const {
374
442
  // If a previous check has failed, propagate the failure.
375
442
  if (!state)
376
0
    return nullptr;
377
442
378
442
  SValBuilder &svalBuilder = C.getSValBuilder();
379
442
  ASTContext &Ctx = svalBuilder.getContext();
380
442
  const LocationContext *LCtx = C.getLocationContext();
381
442
382
442
  QualType sizeTy = Size->getType();
383
442
  QualType PtrTy = Ctx.getPointerType(Ctx.CharTy);
384
442
385
442
  // Check that the first buffer is non-null.
386
442
  SVal BufVal = C.getSVal(FirstBuf);
387
442
  state = checkNonNull(C, state, FirstBuf, BufVal);
388
442
  if (!state)
389
0
    return nullptr;
390
442
391
442
  // If out-of-bounds checking is turned off, skip the rest.
392
442
  if (!Filter.CheckCStringOutOfBounds)
393
102
    return state;
394
340
395
340
  // Get the access length and make sure it is known.
396
340
  // FIXME: This assumes the caller has already checked that the access length
397
340
  // is positive. And that it's unsigned.
398
340
  SVal LengthVal = C.getSVal(Size);
399
340
  Optional<NonLoc> Length = LengthVal.getAs<NonLoc>();
400
340
  if (!Length)
401
4
    return state;
402
336
403
336
  // Compute the offset of the last element to be accessed: size-1.
404
336
  NonLoc One = svalBuilder.makeIntVal(1, sizeTy).castAs<NonLoc>();
405
336
  SVal Offset = svalBuilder.evalBinOpNN(state, BO_Sub, *Length, One, sizeTy);
406
336
  if (Offset.isUnknown())
407
4
    return nullptr;
408
332
  NonLoc LastOffset = Offset.castAs<NonLoc>();
409
332
410
332
  // Check that the first buffer is sufficiently long.
411
332
  SVal BufStart = svalBuilder.evalCast(BufVal, PtrTy, FirstBuf->getType());
412
332
  if (Optional<Loc> BufLoc = BufStart.getAs<Loc>()) {
413
328
    const Expr *warningExpr = (WarnAboutSize ? 
Size0
: FirstBuf);
414
328
415
328
    SVal BufEnd = svalBuilder.evalBinOpLN(state, BO_Add, *BufLoc,
416
328
                                          LastOffset, PtrTy);
417
328
    state = CheckLocation(C, state, warningExpr, BufEnd, firstMessage);
418
328
419
328
    // If the buffer isn't large enough, abort.
420
328
    if (!state)
421
34
      return nullptr;
422
298
  }
423
298
424
298
  // If there's a second buffer, check it as well.
425
298
  if (SecondBuf) {
426
152
    BufVal = state->getSVal(SecondBuf, LCtx);
427
152
    state = checkNonNull(C, state, SecondBuf, BufVal);
428
152
    if (!state)
429
0
      return nullptr;
430
152
431
152
    BufStart = svalBuilder.evalCast(BufVal, PtrTy, SecondBuf->getType());
432
152
    if (Optional<Loc> BufLoc = BufStart.getAs<Loc>()) {
433
152
      const Expr *warningExpr = (WarnAboutSize ? 
Size0
: SecondBuf);
434
152
435
152
      SVal BufEnd = svalBuilder.evalBinOpLN(state, BO_Add, *BufLoc,
436
152
                                            LastOffset, PtrTy);
437
152
      state = CheckLocation(C, state, warningExpr, BufEnd, secondMessage);
438
152
    }
439
152
  }
440
298
441
298
  // Large enough or not, return this state!
442
298
  return state;
443
298
}
444
445
ProgramStateRef CStringChecker::CheckOverlap(CheckerContext &C,
446
                                            ProgramStateRef state,
447
                                            const Expr *Size,
448
                                            const Expr *First,
449
504
                                            const Expr *Second) const {
450
504
  if (!Filter.CheckCStringBufferOverlap)
451
169
    return state;
452
335
453
335
  // Do a simple check for overlap: if the two arguments are from the same
454
335
  // buffer, see if the end of the first is greater than the start of the second
455
335
  // or vice versa.
456
335
457
335
  // If a previous check has failed, propagate the failure.
458
335
  if (!state)
459
36
    return nullptr;
460
299
461
299
  ProgramStateRef stateTrue, stateFalse;
462
299
463
299
  // Get the buffer values and make sure they're known locations.
464
299
  const LocationContext *LCtx = C.getLocationContext();
465
299
  SVal firstVal = state->getSVal(First, LCtx);
466
299
  SVal secondVal = state->getSVal(Second, LCtx);
467
299
468
299
  Optional<Loc> firstLoc = firstVal.getAs<Loc>();
469
299
  if (!firstLoc)
470
0
    return state;
471
299
472
299
  Optional<Loc> secondLoc = secondVal.getAs<Loc>();
473
299
  if (!secondLoc)
474
0
    return state;
475
299
476
299
  // Are the two values the same?
477
299
  SValBuilder &svalBuilder = C.getSValBuilder();
478
299
  std::tie(stateTrue, stateFalse) =
479
299
    state->assume(svalBuilder.evalEQ(state, *firstLoc, *secondLoc));
480
299
481
299
  if (stateTrue && 
!stateFalse47
) {
482
8
    // If the values are known to be equal, that's automatically an overlap.
483
8
    emitOverlapBug(C, stateTrue, First, Second);
484
8
    return nullptr;
485
8
  }
486
291
487
291
  // assume the two expressions are not equal.
488
291
  assert(stateFalse);
489
291
  state = stateFalse;
490
291
491
291
  // Which value comes first?
492
291
  QualType cmpTy = svalBuilder.getConditionType();
493
291
  SVal reverse = svalBuilder.evalBinOpLL(state, BO_GT,
494
291
                                         *firstLoc, *secondLoc, cmpTy);
495
291
  Optional<DefinedOrUnknownSVal> reverseTest =
496
291
      reverse.getAs<DefinedOrUnknownSVal>();
497
291
  if (!reverseTest)
498
0
    return state;
499
291
500
291
  std::tie(stateTrue, stateFalse) = state->assume(*reverseTest);
501
291
  if (stateTrue) {
502
274
    if (stateFalse) {
503
258
      // If we don't know which one comes first, we can't perform this test.
504
258
      return state;
505
258
    } else {
506
16
      // Switch the values so that firstVal is before secondVal.
507
16
      std::swap(firstLoc, secondLoc);
508
16
509
16
      // Switch the Exprs as well, so that they still correspond.
510
16
      std::swap(First, Second);
511
16
    }
512
274
  }
513
291
514
291
  // Get the length, and make sure it too is known.
515
291
  SVal LengthVal = state->getSVal(Size, LCtx);
516
33
  Optional<NonLoc> Length = LengthVal.getAs<NonLoc>();
517
33
  if (!Length)
518
0
    return state;
519
33
520
33
  // Convert the first buffer's start address to char*.
521
33
  // Bail out if the cast fails.
522
33
  ASTContext &Ctx = svalBuilder.getContext();
523
33
  QualType CharPtrTy = Ctx.getPointerType(Ctx.CharTy);
524
33
  SVal FirstStart = svalBuilder.evalCast(*firstLoc, CharPtrTy,
525
33
                                         First->getType());
526
33
  Optional<Loc> FirstStartLoc = FirstStart.getAs<Loc>();
527
33
  if (!FirstStartLoc)
528
0
    return state;
529
33
530
33
  // Compute the end of the first buffer. Bail out if THAT fails.
531
33
  SVal FirstEnd = svalBuilder.evalBinOpLN(state, BO_Add,
532
33
                                 *FirstStartLoc, *Length, CharPtrTy);
533
33
  Optional<Loc> FirstEndLoc = FirstEnd.getAs<Loc>();
534
33
  if (!FirstEndLoc)
535
0
    return state;
536
33
537
33
  // Is the end of the first buffer past the start of the second buffer?
538
33
  SVal Overlap = svalBuilder.evalBinOpLL(state, BO_GT,
539
33
                                *FirstEndLoc, *secondLoc, cmpTy);
540
33
  Optional<DefinedOrUnknownSVal> OverlapTest =
541
33
      Overlap.getAs<DefinedOrUnknownSVal>();
542
33
  if (!OverlapTest)
543
0
    return state;
544
33
545
33
  std::tie(stateTrue, stateFalse) = state->assume(*OverlapTest);
546
33
547
33
  if (stateTrue && 
!stateFalse17
) {
548
17
    // Overlap!
549
17
    emitOverlapBug(C, stateTrue, First, Second);
550
17
    return nullptr;
551
17
  }
552
16
553
16
  // assume the two expressions don't overlap.
554
16
  assert(stateFalse);
555
16
  return stateFalse;
556
16
}
557
558
void CStringChecker::emitOverlapBug(CheckerContext &C, ProgramStateRef state,
559
25
                                  const Stmt *First, const Stmt *Second) const {
560
25
  ExplodedNode *N = C.generateErrorNode(state);
561
25
  if (!N)
562
0
    return;
563
25
564
25
  if (!BT_Overlap)
565
5
    BT_Overlap.reset(new BugType(Filter.CheckNameCStringBufferOverlap,
566
5
                                 categories::UnixAPI, "Improper arguments"));
567
25
568
25
  // Generate a report for this bug.
569
25
  auto report = llvm::make_unique<BugReport>(
570
25
      *BT_Overlap, "Arguments must not be overlapping buffers", N);
571
25
  report->addRange(First->getSourceRange());
572
25
  report->addRange(Second->getSourceRange());
573
25
574
25
  C.emitReport(std::move(report));
575
25
}
576
577
void CStringChecker::emitNullArgBug(CheckerContext &C, ProgramStateRef State,
578
144
                                    const Stmt *S, StringRef WarningMsg) const {
579
144
  if (ExplodedNode *N = C.generateErrorNode(State)) {
580
144
    if (!BT_Null)
581
13
      BT_Null.reset(new BuiltinBug(
582
13
          Filter.CheckNameCStringNullArg, categories::UnixAPI,
583
13
          "Null pointer argument in call to byte string function"));
584
144
585
144
    BuiltinBug *BT = static_cast<BuiltinBug *>(BT_Null.get());
586
144
    auto Report = llvm::make_unique<BugReport>(*BT, WarningMsg, N);
587
144
    Report->addRange(S->getSourceRange());
588
144
    if (const auto *Ex = dyn_cast<Expr>(S))
589
144
      bugreporter::trackExpressionValue(N, Ex, *Report);
590
144
    C.emitReport(std::move(Report));
591
144
  }
592
144
}
593
594
void CStringChecker::emitOutOfBoundsBug(CheckerContext &C,
595
                                        ProgramStateRef State, const Stmt *S,
596
124
                                        StringRef WarningMsg) const {
597
124
  if (ExplodedNode *N = C.generateErrorNode(State)) {
598
124
    if (!BT_Bounds)
599
10
      BT_Bounds.reset(new BuiltinBug(
600
10
          Filter.CheckCStringOutOfBounds ? Filter.CheckNameCStringOutOfBounds
601
10
                                         : 
Filter.CheckNameCStringNullArg0
,
602
10
          "Out-of-bound array access",
603
10
          "Byte string function accesses out-of-bound array element"));
604
124
605
124
    BuiltinBug *BT = static_cast<BuiltinBug *>(BT_Bounds.get());
606
124
607
124
    // FIXME: It would be nice to eventually make this diagnostic more clear,
608
124
    // e.g., by referencing the original declaration or by saying *why* this
609
124
    // reference is outside the range.
610
124
    auto Report = llvm::make_unique<BugReport>(*BT, WarningMsg, N);
611
124
    Report->addRange(S->getSourceRange());
612
124
    C.emitReport(std::move(Report));
613
124
  }
614
124
}
615
616
void CStringChecker::emitNotCStringBug(CheckerContext &C, ProgramStateRef State,
617
                                       const Stmt *S,
618
46
                                       StringRef WarningMsg) const {
619
46
  if (ExplodedNode *N = C.generateNonFatalErrorNode(State)) {
620
46
    if (!BT_NotCString)
621
6
      BT_NotCString.reset(new BuiltinBug(
622
6
          Filter.CheckNameCStringNotNullTerm, categories::UnixAPI,
623
6
          "Argument is not a null-terminated string."));
624
46
625
46
    auto Report = llvm::make_unique<BugReport>(*BT_NotCString, WarningMsg, N);
626
46
627
46
    Report->addRange(S->getSourceRange());
628
46
    C.emitReport(std::move(Report));
629
46
  }
630
46
}
631
632
void CStringChecker::emitAdditionOverflowBug(CheckerContext &C,
633
0
                                             ProgramStateRef State) const {
634
0
  if (ExplodedNode *N = C.generateErrorNode(State)) {
635
0
    if (!BT_NotCString)
636
0
      BT_NotCString.reset(
637
0
          new BuiltinBug(Filter.CheckNameCStringOutOfBounds, "API",
638
0
                         "Sum of expressions causes overflow."));
639
0
640
0
    // This isn't a great error message, but this should never occur in real
641
0
    // code anyway -- you'd have to create a buffer longer than a size_t can
642
0
    // represent, which is sort of a contradiction.
643
0
    const char *WarningMsg =
644
0
        "This expression will create a string whose length is too big to "
645
0
        "be represented as a size_t";
646
0
647
0
    auto Report = llvm::make_unique<BugReport>(*BT_NotCString, WarningMsg, N);
648
0
    C.emitReport(std::move(Report));
649
0
  }
650
0
}
651
652
ProgramStateRef CStringChecker::checkAdditionOverflow(CheckerContext &C,
653
                                                     ProgramStateRef state,
654
                                                     NonLoc left,
655
117
                                                     NonLoc right) const {
656
117
  // If out-of-bounds checking is turned off, skip the rest.
657
117
  if (!Filter.CheckCStringOutOfBounds)
658
43
    return state;
659
74
660
74
  // If a previous check has failed, propagate the failure.
661
74
  if (!state)
662
0
    return nullptr;
663
74
664
74
  SValBuilder &svalBuilder = C.getSValBuilder();
665
74
  BasicValueFactory &BVF = svalBuilder.getBasicValueFactory();
666
74
667
74
  QualType sizeTy = svalBuilder.getContext().getSizeType();
668
74
  const llvm::APSInt &maxValInt = BVF.getMaxValue(sizeTy);
669
74
  NonLoc maxVal = svalBuilder.makeIntVal(maxValInt);
670
74
671
74
  SVal maxMinusRight;
672
74
  if (right.getAs<nonloc::ConcreteInt>()) {
673
62
    maxMinusRight = svalBuilder.evalBinOpNN(state, BO_Sub, maxVal, right,
674
62
                                                 sizeTy);
675
62
  } else {
676
12
    // Try switching the operands. (The order of these two assignments is
677
12
    // important!)
678
12
    maxMinusRight = svalBuilder.evalBinOpNN(state, BO_Sub, maxVal, left,
679
12
                                            sizeTy);
680
12
    left = right;
681
12
  }
682
74
683
74
  if (Optional<NonLoc> maxMinusRightNL = maxMinusRight.getAs<NonLoc>()) {
684
74
    QualType cmpTy = svalBuilder.getConditionType();
685
74
    // If left > max - right, we have an overflow.
686
74
    SVal willOverflow = svalBuilder.evalBinOpNN(state, BO_GT, left,
687
74
                                                *maxMinusRightNL, cmpTy);
688
74
689
74
    ProgramStateRef stateOverflow, stateOkay;
690
74
    std::tie(stateOverflow, stateOkay) =
691
74
      state->assume(willOverflow.castAs<DefinedOrUnknownSVal>());
692
74
693
74
    if (stateOverflow && 
!stateOkay0
) {
694
0
      // We have an overflow. Emit a bug report.
695
0
      emitAdditionOverflowBug(C, stateOverflow);
696
0
      return nullptr;
697
0
    }
698
74
699
74
    // From now on, assume an overflow didn't occur.
700
74
    assert(stateOkay);
701
74
    state = stateOkay;
702
74
  }
703
74
704
74
  return state;
705
74
}
706
707
ProgramStateRef CStringChecker::setCStringLength(ProgramStateRef state,
708
                                                const MemRegion *MR,
709
361
                                                SVal strLength) {
710
361
  assert(!strLength.isUndef() && "Attempt to set an undefined string length");
711
361
712
361
  MR = MR->StripCasts();
713
361
714
361
  switch (MR->getKind()) {
715
361
  case MemRegion::StringRegionKind:
716
0
    // FIXME: This can happen if we strcpy() into a string region. This is
717
0
    // undefined [C99 6.4.5p6], but we should still warn about it.
718
0
    return state;
719
361
720
361
  case MemRegion::SymbolicRegionKind:
721
353
  case MemRegion::AllocaRegionKind:
722
353
  case MemRegion::VarRegionKind:
723
353
  case MemRegion::FieldRegionKind:
724
353
  case MemRegion::ObjCIvarRegionKind:
725
353
    // These are the types we can currently track string lengths for.
726
353
    break;
727
353
728
353
  case MemRegion::ElementRegionKind:
729
8
    // FIXME: Handle element regions by upper-bounding the parent region's
730
8
    // string length.
731
8
    return state;
732
353
733
353
  default:
734
0
    // Other regions (mostly non-data) can't have a reliable C string length.
735
0
    // For now, just ignore the change.
736
0
    // FIXME: These are rare but not impossible. We should output some kind of
737
0
    // warning for things like strcpy((char[]){'a', 0}, "b");
738
0
    return state;
739
353
  }
740
353
741
353
  if (strLength.isUnknown())
742
44
    return state->remove<CStringLength>(MR);
743
309
744
309
  return state->set<CStringLength>(MR, strLength);
745
309
}
746
747
SVal CStringChecker::getCStringLengthForRegion(CheckerContext &C,
748
                                               ProgramStateRef &state,
749
                                               const Expr *Ex,
750
                                               const MemRegion *MR,
751
1.17k
                                               bool hypothetical) {
752
1.17k
  if (!hypothetical) {
753
1.08k
    // If there's a recorded length, go ahead and return it.
754
1.08k
    const SVal *Recorded = state->get<CStringLength>(MR);
755
1.08k
    if (Recorded)
756
726
      return *Recorded;
757
451
  }
758
451
759
451
  // Otherwise, get a new symbol and update the state.
760
451
  SValBuilder &svalBuilder = C.getSValBuilder();
761
451
  QualType sizeTy = svalBuilder.getContext().getSizeType();
762
451
  SVal strLength = svalBuilder.getMetadataSymbolVal(CStringChecker::getTag(),
763
451
                                                    MR, Ex, sizeTy,
764
451
                                                    C.getLocationContext(),
765
451
                                                    C.blockCount());
766
451
767
451
  if (!hypothetical) {
768
358
    if (Optional<NonLoc> strLn = strLength.getAs<NonLoc>()) {
769
358
      // In case of unbounded calls strlen etc bound the range to SIZE_MAX/4
770
358
      BasicValueFactory &BVF = svalBuilder.getBasicValueFactory();
771
358
      const llvm::APSInt &maxValInt = BVF.getMaxValue(sizeTy);
772
358
      llvm::APSInt fourInt = APSIntType(maxValInt).getValue(4);
773
358
      const llvm::APSInt *maxLengthInt = BVF.evalAPSInt(BO_Div, maxValInt,
774
358
                                                        fourInt);
775
358
      NonLoc maxLength = svalBuilder.makeIntVal(*maxLengthInt);
776
358
      SVal evalLength = svalBuilder.evalBinOpNN(state, BO_LE, *strLn,
777
358
                                                maxLength, sizeTy);
778
358
      state = state->assume(evalLength.castAs<DefinedOrUnknownSVal>(), true);
779
358
    }
780
358
    state = state->set<CStringLength>(MR, strLength);
781
358
  }
782
451
783
451
  return strLength;
784
451
}
785
786
SVal CStringChecker::getCStringLength(CheckerContext &C, ProgramStateRef &state,
787
                                      const Expr *Ex, SVal Buf,
788
2.33k
                                      bool hypothetical) const {
789
2.33k
  const MemRegion *MR = Buf.getAsRegion();
790
2.33k
  if (!MR) {
791
15
    // If we can't get a region, see if it's something we /know/ isn't a
792
15
    // C string. In the context of locations, the only time we can issue such
793
15
    // a warning is for labels.
794
15
    if (Optional<loc::GotoLabel> Label = Buf.getAs<loc::GotoLabel>()) {
795
10
      if (Filter.CheckCStringNotNullTerm) {
796
10
        SmallString<120> buf;
797
10
        llvm::raw_svector_ostream os(buf);
798
10
        assert(CurrentFunctionDescription);
799
10
        os << "Argument to " << CurrentFunctionDescription
800
10
           << " is the address of the label '" << Label->getLabel()->getName()
801
10
           << "', which is not a null-terminated string";
802
10
803
10
        emitNotCStringBug(C, state, Ex, os.str());
804
10
      }
805
10
      return UndefinedVal();
806
10
    }
807
5
808
5
    // If it's not a region and not a label, give up.
809
5
    return UnknownVal();
810
5
  }
811
2.32k
812
2.32k
  // If we have a region, strip casts from it and see if we can figure out
813
2.32k
  // its length. For anything we can't figure out, just return UnknownVal.
814
2.32k
  MR = MR->StripCasts();
815
2.32k
816
2.32k
  switch (MR->getKind()) {
817
2.32k
  case MemRegion::StringRegionKind: {
818
1.07k
    // Modifying the contents of string regions is undefined [C99 6.4.5p6],
819
1.07k
    // so we can assume that the byte length is the correct C string length.
820
1.07k
    SValBuilder &svalBuilder = C.getSValBuilder();
821
1.07k
    QualType sizeTy = svalBuilder.getContext().getSizeType();
822
1.07k
    const StringLiteral *strLit = cast<StringRegion>(MR)->getStringLiteral();
823
1.07k
    return svalBuilder.makeIntVal(strLit->getByteLength(), sizeTy);
824
2.32k
  }
825
2.32k
  case MemRegion::SymbolicRegionKind:
826
1.17k
  case MemRegion::AllocaRegionKind:
827
1.17k
  case MemRegion::VarRegionKind:
828
1.17k
  case MemRegion::FieldRegionKind:
829
1.17k
  case MemRegion::ObjCIvarRegionKind:
830
1.17k
    return getCStringLengthForRegion(C, state, Ex, MR, hypothetical);
831
1.17k
  case MemRegion::CompoundLiteralRegionKind:
832
5
    // FIXME: Can we track this? Is it necessary?
833
5
    return UnknownVal();
834
1.17k
  case MemRegion::ElementRegionKind:
835
28
    // FIXME: How can we handle this? It's not good enough to subtract the
836
28
    // offset from the base string length; consider "123\x00567" and &a[5].
837
28
    return UnknownVal();
838
1.17k
  default:
839
36
    // Other regions (mostly non-data) can't have a reliable C string length.
840
36
    // In this case, an error is emitted and UndefinedVal is returned.
841
36
    // The caller should always be prepared to handle this case.
842
36
    if (Filter.CheckCStringNotNullTerm) {
843
36
      SmallString<120> buf;
844
36
      llvm::raw_svector_ostream os(buf);
845
36
846
36
      assert(CurrentFunctionDescription);
847
36
      os << "Argument to " << CurrentFunctionDescription << " is ";
848
36
849
36
      if (SummarizeRegion(os, C.getASTContext(), MR))
850
36
        os << ", which is not a null-terminated string";
851
0
      else
852
0
        os << "not a null-terminated string";
853
36
854
36
      emitNotCStringBug(C, state, Ex, os.str());
855
36
    }
856
36
    return UndefinedVal();
857
2.32k
  }
858
2.32k
}
859
860
const StringLiteral *CStringChecker::getCStringLiteral(CheckerContext &C,
861
752
  ProgramStateRef &state, const Expr *expr, SVal val) const {
862
752
863
752
  // Get the memory region pointed to by the val.
864
752
  const MemRegion *bufRegion = val.getAsRegion();
865
752
  if (!bufRegion)
866
5
    return nullptr;
867
747
868
747
  // Strip casts off the memory region.
869
747
  bufRegion = bufRegion->StripCasts();
870
747
871
747
  // Cast the memory region to a string region.
872
747
  const StringRegion *strRegion= dyn_cast<StringRegion>(bufRegion);
873
747
  if (!strRegion)
874
2
    return nullptr;
875
745
876
745
  // Return the actual string in the string region.
877
745
  return strRegion->getStringLiteral();
878
745
}
879
880
bool CStringChecker::IsFirstBufInBound(CheckerContext &C,
881
                                       ProgramStateRef state,
882
                                       const Expr *FirstBuf,
883
42
                                       const Expr *Size) {
884
42
  // If we do not know that the buffer is long enough we return 'true'.
885
42
  // Otherwise the parent region of this field region would also get
886
42
  // invalidated, which would lead to warnings based on an unknown state.
887
42
888
42
  // Originally copied from CheckBufferAccess and CheckLocation.
889
42
  SValBuilder &svalBuilder = C.getSValBuilder();
890
42
  ASTContext &Ctx = svalBuilder.getContext();
891
42
  const LocationContext *LCtx = C.getLocationContext();
892
42
893
42
  QualType sizeTy = Size->getType();
894
42
  QualType PtrTy = Ctx.getPointerType(Ctx.CharTy);
895
42
  SVal BufVal = state->getSVal(FirstBuf, LCtx);
896
42
897
42
  SVal LengthVal = state->getSVal(Size, LCtx);
898
42
  Optional<NonLoc> Length = LengthVal.getAs<NonLoc>();
899
42
  if (!Length)
900
1
    return true; // cf top comment.
901
41
902
41
  // Compute the offset of the last element to be accessed: size-1.
903
41
  NonLoc One = svalBuilder.makeIntVal(1, sizeTy).castAs<NonLoc>();
904
41
  SVal Offset = svalBuilder.evalBinOpNN(state, BO_Sub, *Length, One, sizeTy);
905
41
  if (Offset.isUnknown())
906
0
    return true; // cf top comment
907
41
  NonLoc LastOffset = Offset.castAs<NonLoc>();
908
41
909
41
  // Check that the first buffer is sufficiently long.
910
41
  SVal BufStart = svalBuilder.evalCast(BufVal, PtrTy, FirstBuf->getType());
911
41
  Optional<Loc> BufLoc = BufStart.getAs<Loc>();
912
41
  if (!BufLoc)
913
1
    return true; // cf top comment.
914
40
915
40
  SVal BufEnd =
916
40
      svalBuilder.evalBinOpLN(state, BO_Add, *BufLoc, LastOffset, PtrTy);
917
40
918
40
  // Check for out of bound array element access.
919
40
  const MemRegion *R = BufEnd.getAsRegion();
920
40
  if (!R)
921
0
    return true; // cf top comment.
922
40
923
40
  const ElementRegion *ER = dyn_cast<ElementRegion>(R);
924
40
  if (!ER)
925
0
    return true; // cf top comment.
926
40
927
40
  // FIXME: Does this crash when a non-standard definition
928
40
  // of a library function is encountered?
929
40
  assert(ER->getValueType() == C.getASTContext().CharTy &&
930
40
         "IsFirstBufInBound should only be called with char* ElementRegions");
931
40
932
40
  // Get the size of the array.
933
40
  const SubRegion *superReg = cast<SubRegion>(ER->getSuperRegion());
934
40
  SVal Extent =
935
40
      svalBuilder.convertToArrayIndex(superReg->getExtent(svalBuilder));
936
40
  DefinedOrUnknownSVal ExtentSize = Extent.castAs<DefinedOrUnknownSVal>();
937
40
938
40
  // Get the index of the accessed element.
939
40
  DefinedOrUnknownSVal Idx = ER->getIndex().castAs<DefinedOrUnknownSVal>();
940
40
941
40
  ProgramStateRef StInBound = state->assumeInBound(Idx, ExtentSize, true);
942
40
943
40
  return static_cast<bool>(StInBound);
944
40
}
945
946
ProgramStateRef CStringChecker::InvalidateBuffer(CheckerContext &C,
947
                                                 ProgramStateRef state,
948
                                                 const Expr *E, SVal V,
949
                                                 bool IsSourceBuffer,
950
811
                                                 const Expr *Size) {
951
811
  Optional<Loc> L = V.getAs<Loc>();
952
811
  if (!L)
953
0
    return state;
954
811
955
811
  // FIXME: This is a simplified version of what's in CFRefCount.cpp -- it makes
956
811
  // some assumptions about the value that CFRefCount can't. Even so, it should
957
811
  // probably be refactored.
958
811
  if (Optional<loc::MemRegionVal> MR = L->getAs<loc::MemRegionVal>()) {
959
805
    const MemRegion *R = MR->getRegion()->StripCasts();
960
805
961
805
    // Are we dealing with an ElementRegion?  If so, we should be invalidating
962
805
    // the super-region.
963
805
    if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
964
101
      R = ER->getSuperRegion();
965
101
      // FIXME: What about layers of ElementRegions?
966
101
    }
967
805
968
805
    // Invalidate this region.
969
805
    const LocationContext *LCtx = C.getPredecessor()->getLocationContext();
970
805
971
805
    bool CausesPointerEscape = false;
972
805
    RegionAndSymbolInvalidationTraits ITraits;
973
805
    // Invalidate and escape only indirect regions accessible through the source
974
805
    // buffer.
975
805
    if (IsSourceBuffer) {
976
350
      ITraits.setTrait(R->getBaseRegion(),
977
350
                       RegionAndSymbolInvalidationTraits::TK_PreserveContents);
978
350
      ITraits.setTrait(R, RegionAndSymbolInvalidationTraits::TK_SuppressEscape);
979
350
      CausesPointerEscape = true;
980
455
    } else {
981
455
      const MemRegion::Kind& K = R->getKind();
982
455
      if (K == MemRegion::FieldRegionKind)
983
42
        if (Size && IsFirstBufInBound(C, state, E, Size)) {
984
35
          // If destination buffer is a field region and access is in bound,
985
35
          // do not invalidate its super region.
986
35
          ITraits.setTrait(
987
35
              R,
988
35
              RegionAndSymbolInvalidationTraits::TK_DoNotInvalidateSuperRegion);
989
35
        }
990
455
    }
991
805
992
805
    return state->invalidateRegions(R, E, C.blockCount(), LCtx,
993
805
                                    CausesPointerEscape, nullptr, nullptr,
994
805
                                    &ITraits);
995
805
  }
996
6
997
6
  // If we have a non-region value by chance, just remove the binding.
998
6
  // FIXME: is this necessary or correct? This handles the non-Region
999
6
  //  cases.  Is it ever valid to store to these?
1000
6
  return state->killBinding(*L);
1001
6
}
1002
1003
bool CStringChecker::SummarizeRegion(raw_ostream &os, ASTContext &Ctx,
1004
36
                                     const MemRegion *MR) {
1005
36
  const TypedValueRegion *TVR = dyn_cast<TypedValueRegion>(MR);
1006
36
1007
36
  switch (MR->getKind()) {
1008
36
  case MemRegion::FunctionCodeRegionKind: {
1009
36
    const NamedDecl *FD = cast<FunctionCodeRegion>(MR)->getDecl();
1010
36
    if (FD)
1011
36
      os << "the address of the function '" << *FD << '\'';
1012
0
    else
1013
0
      os << "the address of a function";
1014
36
    return true;
1015
36
  }
1016
36
  case MemRegion::BlockCodeRegionKind:
1017
0
    os << "block text";
1018
0
    return true;
1019
36
  case MemRegion::BlockDataRegionKind:
1020
0
    os << "a block";
1021
0
    return true;
1022
36
  case MemRegion::CXXThisRegionKind:
1023
0
  case MemRegion::CXXTempObjectRegionKind:
1024
0
    os << "a C++ temp object of type " << TVR->getValueType().getAsString();
1025
0
    return true;
1026
0
  case MemRegion::VarRegionKind:
1027
0
    os << "a variable of type" << TVR->getValueType().getAsString();
1028
0
    return true;
1029
0
  case MemRegion::FieldRegionKind:
1030
0
    os << "a field of type " << TVR->getValueType().getAsString();
1031
0
    return true;
1032
0
  case MemRegion::ObjCIvarRegionKind:
1033
0
    os << "an instance variable of type " << TVR->getValueType().getAsString();
1034
0
    return true;
1035
0
  default:
1036
0
    return false;
1037
36
  }
1038
36
}
1039
1040
bool CStringChecker::memsetAux(const Expr *DstBuffer, SVal CharVal,
1041
                               const Expr *Size, CheckerContext &C,
1042
172
                               ProgramStateRef &State) {
1043
172
  SVal MemVal = C.getSVal(DstBuffer);
1044
172
  SVal SizeVal = C.getSVal(Size);
1045
172
  const MemRegion *MR = MemVal.getAsRegion();
1046
172
  if (!MR)
1047
0
    return false;
1048
172
1049
172
  // We're about to model memset by producing a "default binding" in the Store.
1050
172
  // Our current implementation - RegionStore - doesn't support default bindings
1051
172
  // that don't cover the whole base region. So we should first get the offset
1052
172
  // and the base region to figure out whether the offset of buffer is 0.
1053
172
  RegionOffset Offset = MR->getAsOffset();
1054
172
  const MemRegion *BR = Offset.getRegion();
1055
172
1056
172
  Optional<NonLoc> SizeNL = SizeVal.getAs<NonLoc>();
1057
172
  if (!SizeNL)
1058
0
    return false;
1059
172
1060
172
  SValBuilder &svalBuilder = C.getSValBuilder();
1061
172
  ASTContext &Ctx = C.getASTContext();
1062
172
1063
172
  // void *memset(void *dest, int ch, size_t count);
1064
172
  // For now we can only handle the case of offset is 0 and concrete char value.
1065
172
  if (Offset.isValid() && !Offset.hasSymbolicOffset() &&
1066
172
      
Offset.getOffset() == 0171
) {
1067
145
    // Get the base region's extent.
1068
145
    auto *SubReg = cast<SubRegion>(BR);
1069
145
    DefinedOrUnknownSVal Extent = SubReg->getExtent(svalBuilder);
1070
145
1071
145
    ProgramStateRef StateWholeReg, StateNotWholeReg;
1072
145
    std::tie(StateWholeReg, StateNotWholeReg) =
1073
145
        State->assume(svalBuilder.evalEQ(State, Extent, *SizeNL));
1074
145
1075
145
    // With the semantic of 'memset()', we should convert the CharVal to
1076
145
    // unsigned char.
1077
145
    CharVal = svalBuilder.evalCast(CharVal, Ctx.UnsignedCharTy, Ctx.IntTy);
1078
145
1079
145
    ProgramStateRef StateNullChar, StateNonNullChar;
1080
145
    std::tie(StateNullChar, StateNonNullChar) =
1081
145
        assumeZero(C, State, CharVal, Ctx.UnsignedCharTy);
1082
145
1083
145
    if (StateWholeReg && 
!StateNotWholeReg113
&&
StateNullChar113
&&
1084
145
        
!StateNonNullChar91
) {
1085
91
      // If the 'memset()' acts on the whole region of destination buffer and
1086
91
      // the value of the second argument of 'memset()' is zero, bind the second
1087
91
      // argument's value to the destination buffer with 'default binding'.
1088
91
      // FIXME: Since there is no perfect way to bind the non-zero character, we
1089
91
      // can only deal with zero value here. In the future, we need to deal with
1090
91
      // the binding of non-zero value in the case of whole region.
1091
91
      State = State->bindDefaultZero(svalBuilder.makeLoc(BR),
1092
91
                                     C.getLocationContext());
1093
91
    } else {
1094
54
      // If the destination buffer's extent is not equal to the value of
1095
54
      // third argument, just invalidate buffer.
1096
54
      State = InvalidateBuffer(C, State, DstBuffer, MemVal,
1097
54
                               /*IsSourceBuffer*/ false, Size);
1098
54
    }
1099
145
1100
145
    if (StateNullChar && 
!StateNonNullChar116
) {
1101
116
      // If the value of the second argument of 'memset()' is zero, set the
1102
116
      // string length of destination buffer to 0 directly.
1103
116
      State = setCStringLength(State, MR,
1104
116
                               svalBuilder.makeZeroVal(Ctx.getSizeType()));
1105
116
    } else 
if (29
!StateNullChar29
&&
StateNonNullChar29
) {
1106
29
      SVal NewStrLen = svalBuilder.getMetadataSymbolVal(
1107
29
          CStringChecker::getTag(), MR, DstBuffer, Ctx.getSizeType(),
1108
29
          C.getLocationContext(), C.blockCount());
1109
29
1110
29
      // If the value of second argument is not zero, then the string length
1111
29
      // is at least the size argument.
1112
29
      SVal NewStrLenGESize = svalBuilder.evalBinOp(
1113
29
          State, BO_GE, NewStrLen, SizeVal, svalBuilder.getConditionType());
1114
29
1115
29
      State = setCStringLength(
1116
29
          State->assume(NewStrLenGESize.castAs<DefinedOrUnknownSVal>(), true),
1117
29
          MR, NewStrLen);
1118
29
    }
1119
145
  } else {
1120
27
    // If the offset is not zero and char value is not concrete, we can do
1121
27
    // nothing but invalidate the buffer.
1122
27
    State = InvalidateBuffer(C, State, DstBuffer, MemVal,
1123
27
                             /*IsSourceBuffer*/ false, Size);
1124
27
  }
1125
172
  return true;
1126
172
}
1127
1128
//===----------------------------------------------------------------------===//
1129
// evaluation of individual function calls.
1130
//===----------------------------------------------------------------------===//
1131
1132
void CStringChecker::evalCopyCommon(CheckerContext &C,
1133
                                    const CallExpr *CE,
1134
                                    ProgramStateRef state,
1135
                                    const Expr *Size, const Expr *Dest,
1136
                                    const Expr *Source, bool Restricted,
1137
256
                                    bool IsMempcpy) const {
1138
256
  CurrentFunctionDescription = "memory copy function";
1139
256
1140
256
  // See if the size argument is zero.
1141
256
  const LocationContext *LCtx = C.getLocationContext();
1142
256
  SVal sizeVal = state->getSVal(Size, LCtx);
1143
256
  QualType sizeTy = Size->getType();
1144
256
1145
256
  ProgramStateRef stateZeroSize, stateNonZeroSize;
1146
256
  std::tie(stateZeroSize, stateNonZeroSize) =
1147
256
    assumeZero(C, state, sizeVal, sizeTy);
1148
256
1149
256
  // Get the value of the Dest.
1150
256
  SVal destVal = state->getSVal(Dest, LCtx);
1151
256
1152
256
  // If the size is zero, there won't be any actual memory access, so
1153
256
  // just bind the return value to the destination buffer and return.
1154
256
  if (stateZeroSize && 
!stateNonZeroSize48
) {
1155
16
    stateZeroSize = stateZeroSize->BindExpr(CE, LCtx, destVal);
1156
16
    C.addTransition(stateZeroSize);
1157
16
    return;
1158
16
  }
1159
240
1160
240
  // If the size can be nonzero, we have to check the other arguments.
1161
240
  if (stateNonZeroSize) {
1162
240
    state = stateNonZeroSize;
1163
240
1164
240
    // Ensure the destination is not null. If it is NULL there will be a
1165
240
    // NULL pointer dereference.
1166
240
    state = checkNonNull(C, state, Dest, destVal);
1167
240
    if (!state)
1168
14
      return;
1169
226
1170
226
    // Get the value of the Src.
1171
226
    SVal srcVal = state->getSVal(Source, LCtx);
1172
226
1173
226
    // Ensure the source is not null. If it is NULL there will be a
1174
226
    // NULL pointer dereference.
1175
226
    state = checkNonNull(C, state, Source, srcVal);
1176
226
    if (!state)
1177
16
      return;
1178
210
1179
210
    // Ensure the accesses are valid and that the buffers do not overlap.
1180
210
    const char * const writeWarning =
1181
210
      "Memory copy function overflows destination buffer";
1182
210
    state = CheckBufferAccess(C, state, Size, Dest, Source,
1183
210
                              writeWarning, /* sourceWarning = */ nullptr);
1184
210
    if (Restricted)
1185
182
      state = CheckOverlap(C, state, Size, Dest, Source);
1186
210
1187
210
    if (!state)
1188
76
      return;
1189
134
1190
134
    // If this is mempcpy, get the byte after the last byte copied and
1191
134
    // bind the expr.
1192
134
    if (IsMempcpy) {
1193
41
      // Get the byte after the last byte copied.
1194
41
      SValBuilder &SvalBuilder = C.getSValBuilder();
1195
41
      ASTContext &Ctx = SvalBuilder.getContext();
1196
41
      QualType CharPtrTy = Ctx.getPointerType(Ctx.CharTy);
1197
41
      SVal DestRegCharVal =
1198
41
          SvalBuilder.evalCast(destVal, CharPtrTy, Dest->getType());
1199
41
      SVal lastElement = C.getSValBuilder().evalBinOp(
1200
41
          state, BO_Add, DestRegCharVal, sizeVal, Dest->getType());
1201
41
      // If we don't know how much we copied, we can at least
1202
41
      // conjure a return value for later.
1203
41
      if (lastElement.isUnknown())
1204
9
        lastElement = C.getSValBuilder().conjureSymbolVal(nullptr, CE, LCtx,
1205
9
                                                          C.blockCount());
1206
41
1207
41
      // The byte after the last byte copied is the return value.
1208
41
      state = state->BindExpr(CE, LCtx, lastElement);
1209
93
    } else {
1210
93
      // All other copies return the destination buffer.
1211
93
      // (Well, bcopy() has a void return type, but this won't hurt.)
1212
93
      state = state->BindExpr(CE, LCtx, destVal);
1213
93
    }
1214
134
1215
134
    // Invalidate the destination (regular invalidation without pointer-escaping
1216
134
    // the address of the top-level region).
1217
134
    // FIXME: Even if we can't perfectly model the copy, we should see if we
1218
134
    // can use LazyCompoundVals to copy the source values into the destination.
1219
134
    // This would probably remove any existing bindings past the end of the
1220
134
    // copied region, but that's still an improvement over blank invalidation.
1221
134
    state = InvalidateBuffer(C, state, Dest, C.getSVal(Dest),
1222
134
                             /*IsSourceBuffer*/false, Size);
1223
134
1224
134
    // Invalidate the source (const-invalidation without const-pointer-escaping
1225
134
    // the address of the top-level region).
1226
134
    state = InvalidateBuffer(C, state, Source, C.getSVal(Source),
1227
134
                             /*IsSourceBuffer*/true, nullptr);
1228
134
1229
134
    C.addTransition(state);
1230
134
  }
1231
240
}
1232
1233
1234
139
void CStringChecker::evalMemcpy(CheckerContext &C, const CallExpr *CE) const {
1235
139
  // void *memcpy(void *restrict dst, const void *restrict src, size_t n);
1236
139
  // The return value is the address of the destination buffer.
1237
139
  const Expr *Dest = CE->getArg(0);
1238
139
  ProgramStateRef state = C.getState();
1239
139
1240
139
  evalCopyCommon(C, CE, state, CE->getArg(2), Dest, CE->getArg(1), true);
1241
139
}
1242
1243
89
void CStringChecker::evalMempcpy(CheckerContext &C, const CallExpr *CE) const {
1244
89
  // void *mempcpy(void *restrict dst, const void *restrict src, size_t n);
1245
89
  // The return value is a pointer to the byte following the last written byte.
1246
89
  const Expr *Dest = CE->getArg(0);
1247
89
  ProgramStateRef state = C.getState();
1248
89
1249
89
  evalCopyCommon(C, CE, state, CE->getArg(2), Dest, CE->getArg(1), true, true);
1250
89
}
1251
1252
16
void CStringChecker::evalMemmove(CheckerContext &C, const CallExpr *CE) const {
1253
16
  // void *memmove(void *dst, const void *src, size_t n);
1254
16
  // The return value is the address of the destination buffer.
1255
16
  const Expr *Dest = CE->getArg(0);
1256
16
  ProgramStateRef state = C.getState();
1257
16
1258
16
  evalCopyCommon(C, CE, state, CE->getArg(2), Dest, CE->getArg(1));
1259
16
}
1260
1261
12
void CStringChecker::evalBcopy(CheckerContext &C, const CallExpr *CE) const {
1262
12
  // void bcopy(const void *src, void *dst, size_t n);
1263
12
  evalCopyCommon(C, CE, C.getState(),
1264
12
                 CE->getArg(2), CE->getArg(1), CE->getArg(0));
1265
12
}
1266
1267
54
void CStringChecker::evalMemcmp(CheckerContext &C, const CallExpr *CE) const {
1268
54
  // int memcmp(const void *s1, const void *s2, size_t n);
1269
54
  CurrentFunctionDescription = "memory comparison function";
1270
54
1271
54
  const Expr *Left = CE->getArg(0);
1272
54
  const Expr *Right = CE->getArg(1);
1273
54
  const Expr *Size = CE->getArg(2);
1274
54
1275
54
  ProgramStateRef state = C.getState();
1276
54
  SValBuilder &svalBuilder = C.getSValBuilder();
1277
54
1278
54
  // See if the size argument is zero.
1279
54
  const LocationContext *LCtx = C.getLocationContext();
1280
54
  SVal sizeVal = state->getSVal(Size, LCtx);
1281
54
  QualType sizeTy = Size->getType();
1282
54
1283
54
  ProgramStateRef stateZeroSize, stateNonZeroSize;
1284
54
  std::tie(stateZeroSize, stateNonZeroSize) =
1285
54
    assumeZero(C, state, sizeVal, sizeTy);
1286
54
1287
54
  // If the size can be zero, the result will be 0 in that case, and we don't
1288
54
  // have to check either of the buffers.
1289
54
  if (stateZeroSize) {
1290
24
    state = stateZeroSize;
1291
24
    state = state->BindExpr(CE, LCtx,
1292
24
                            svalBuilder.makeZeroVal(CE->getType()));
1293
24
    C.addTransition(state);
1294
24
  }
1295
54
1296
54
  // If the size can be nonzero, we have to check the other arguments.
1297
54
  if (stateNonZeroSize) {
1298
38
    state = stateNonZeroSize;
1299
38
    // If we know the two buffers are the same, we know the result is 0.
1300
38
    // First, get the two buffers' addresses. Another checker will have already
1301
38
    // made sure they're not undefined.
1302
38
    DefinedOrUnknownSVal LV =
1303
38
        state->getSVal(Left, LCtx).castAs<DefinedOrUnknownSVal>();
1304
38
    DefinedOrUnknownSVal RV =
1305
38
        state->getSVal(Right, LCtx).castAs<DefinedOrUnknownSVal>();
1306
38
1307
38
    // See if they are the same.
1308
38
    DefinedOrUnknownSVal SameBuf = svalBuilder.evalEQ(state, LV, RV);
1309
38
    ProgramStateRef StSameBuf, StNotSameBuf;
1310
38
    std::tie(StSameBuf, StNotSameBuf) = state->assume(SameBuf);
1311
38
1312
38
    // If the two arguments might be the same buffer, we know the result is 0,
1313
38
    // and we only need to check one size.
1314
38
    if (StSameBuf) {
1315
22
      state = StSameBuf;
1316
22
      state = CheckBufferAccess(C, state, Size, Left);
1317
22
      if (state) {
1318
22
        state = StSameBuf->BindExpr(CE, LCtx,
1319
22
                                    svalBuilder.makeZeroVal(CE->getType()));
1320
22
        C.addTransition(state);
1321
22
      }
1322
22
    }
1323
38
1324
38
    // If the two arguments might be different buffers, we have to check the
1325
38
    // size of both of them.
1326
38
    if (StNotSameBuf) {
1327
32
      state = StNotSameBuf;
1328
32
      state = CheckBufferAccess(C, state, Size, Left, Right);
1329
32
      if (state) {
1330
24
        // The return value is the comparison result, which we don't know.
1331
24
        SVal CmpV = svalBuilder.conjureSymbolVal(nullptr, CE, LCtx,
1332
24
                                                 C.blockCount());
1333
24
        state = state->BindExpr(CE, LCtx, CmpV);
1334
24
        C.addTransition(state);
1335
24
      }
1336
32
    }
1337
38
  }
1338
54
}
1339
1340
void CStringChecker::evalstrLength(CheckerContext &C,
1341
569
                                   const CallExpr *CE) const {
1342
569
  // size_t strlen(const char *s);
1343
569
  evalstrLengthCommon(C, CE, /* IsStrnlen = */ false);
1344
569
}
1345
1346
void CStringChecker::evalstrnLength(CheckerContext &C,
1347
108
                                    const CallExpr *CE) const {
1348
108
  // size_t strnlen(const char *s, size_t maxlen);
1349
108
  evalstrLengthCommon(C, CE, /* IsStrnlen = */ true);
1350
108
}
1351
1352
void CStringChecker::evalstrLengthCommon(CheckerContext &C, const CallExpr *CE,
1353
677
                                         bool IsStrnlen) const {
1354
677
  CurrentFunctionDescription = "string length function";
1355
677
  ProgramStateRef state = C.getState();
1356
677
  const LocationContext *LCtx = C.getLocationContext();
1357
677
1358
677
  if (IsStrnlen) {
1359
108
    const Expr *maxlenExpr = CE->getArg(1);
1360
108
    SVal maxlenVal = state->getSVal(maxlenExpr, LCtx);
1361
108
1362
108
    ProgramStateRef stateZeroSize, stateNonZeroSize;
1363
108
    std::tie(stateZeroSize, stateNonZeroSize) =
1364
108
      assumeZero(C, state, maxlenVal, maxlenExpr->getType());
1365
108
1366
108
    // If the size can be zero, the result will be 0 in that case, and we don't
1367
108
    // have to check the string itself.
1368
108
    if (stateZeroSize) {
1369
20
      SVal zero = C.getSValBuilder().makeZeroVal(CE->getType());
1370
20
      stateZeroSize = stateZeroSize->BindExpr(CE, LCtx, zero);
1371
20
      C.addTransition(stateZeroSize);
1372
20
    }
1373
108
1374
108
    // If the size is GUARANTEED to be zero, we're done!
1375
108
    if (!stateNonZeroSize)
1376
10
      return;
1377
98
1378
98
    // Otherwise, record the assumption that the size is nonzero.
1379
98
    state = stateNonZeroSize;
1380
98
  }
1381
677
1382
677
  // Check that the string argument is non-null.
1383
677
  const Expr *Arg = CE->getArg(0);
1384
667
  SVal ArgVal = state->getSVal(Arg, LCtx);
1385
667
1386
667
  state = checkNonNull(C, state, Arg, ArgVal);
1387
667
1388
667
  if (!state)
1389
10
    return;
1390
657
1391
657
  SVal strLength = getCStringLength(C, state, Arg, ArgVal);
1392
657
1393
657
  // If the argument isn't a valid C string, there's no valid state to
1394
657
  // transition to.
1395
657
  if (strLength.isUndef())
1396
21
    return;
1397
636
1398
636
  DefinedOrUnknownSVal result = UnknownVal();
1399
636
1400
636
  // If the check is for strnlen() then bind the return value to no more than
1401
636
  // the maxlen value.
1402
636
  if (IsStrnlen) {
1403
83
    QualType cmpTy = C.getSValBuilder().getConditionType();
1404
83
1405
83
    // It's a little unfortunate to be getting this again,
1406
83
    // but it's not that expensive...
1407
83
    const Expr *maxlenExpr = CE->getArg(1);
1408
83
    SVal maxlenVal = state->getSVal(maxlenExpr, LCtx);
1409
83
1410
83
    Optional<NonLoc> strLengthNL = strLength.getAs<NonLoc>();
1411
83
    Optional<NonLoc> maxlenValNL = maxlenVal.getAs<NonLoc>();
1412
83
1413
83
    if (strLengthNL && 
maxlenValNL78
) {
1414
73
      ProgramStateRef stateStringTooLong, stateStringNotTooLong;
1415
73
1416
73
      // Check if the strLength is greater than the maxlen.
1417
73
      std::tie(stateStringTooLong, stateStringNotTooLong) = state->assume(
1418
73
          C.getSValBuilder()
1419
73
              .evalBinOpNN(state, BO_GT, *strLengthNL, *maxlenValNL, cmpTy)
1420
73
              .castAs<DefinedOrUnknownSVal>());
1421
73
1422
73
      if (stateStringTooLong && 
!stateStringNotTooLong58
) {
1423
15
        // If the string is longer than maxlen, return maxlen.
1424
15
        result = *maxlenValNL;
1425
58
      } else if (stateStringNotTooLong && !stateStringTooLong) {
1426
15
        // If the string is shorter than maxlen, return its length.
1427
15
        result = *strLengthNL;
1428
15
      }
1429
73
    }
1430
83
1431
83
    if (result.isUnknown()) {
1432
53
      // If we don't have enough information for a comparison, there's
1433
53
      // no guarantee the full string length will actually be returned.
1434
53
      // All we know is the return value is the min of the string length
1435
53
      // and the limit. This is better than nothing.
1436
53
      result = C.getSValBuilder().conjureSymbolVal(nullptr, CE, LCtx,
1437
53
                                                   C.blockCount());
1438
53
      NonLoc resultNL = result.castAs<NonLoc>();
1439
53
1440
53
      if (strLengthNL) {
1441
48
        state = state->assume(C.getSValBuilder().evalBinOpNN(
1442
48
                                  state, BO_LE, resultNL, *strLengthNL, cmpTy)
1443
48
                                  .castAs<DefinedOrUnknownSVal>(), true);
1444
48
      }
1445
53
1446
53
      if (maxlenValNL) {
1447
48
        state = state->assume(C.getSValBuilder().evalBinOpNN(
1448
48
                                  state, BO_LE, resultNL, *maxlenValNL, cmpTy)
1449
48
                                  .castAs<DefinedOrUnknownSVal>(), true);
1450
48
      }
1451
53
    }
1452
83
1453
553
  } else {
1454
553
    // This is a plain strlen(), not strnlen().
1455
553
    result = strLength.castAs<DefinedOrUnknownSVal>();
1456
553
1457
553
    // If we don't know the length of the string, conjure a return
1458
553
    // value, so it can be used in constraints, at least.
1459
553
    if (result.isUnknown()) {
1460
2
      result = C.getSValBuilder().conjureSymbolVal(nullptr, CE, LCtx,
1461
2
                                                   C.blockCount());
1462
2
    }
1463
553
  }
1464
636
1465
636
  // Bind the return value.
1466
636
  assert(!result.isUnknown() && "Should have conjured a value by now");
1467
636
  state = state->BindExpr(CE, LCtx, result);
1468
636
  C.addTransition(state);
1469
636
}
1470
1471
48
void CStringChecker::evalStrcpy(CheckerContext &C, const CallExpr *CE) const {
1472
48
  // char *strcpy(char *restrict dst, const char *restrict src);
1473
48
  evalStrcpyCommon(C, CE,
1474
48
                   /* returnEnd = */ false,
1475
48
                   /* isBounded = */ false,
1476
48
                   /* isAppending = */ false);
1477
48
}
1478
1479
67
void CStringChecker::evalStrncpy(CheckerContext &C, const CallExpr *CE) const {
1480
67
  // char *strncpy(char *restrict dst, const char *restrict src, size_t n);
1481
67
  evalStrcpyCommon(C, CE,
1482
67
                   /* returnEnd = */ false,
1483
67
                   /* isBounded = */ true,
1484
67
                   /* isAppending = */ false);
1485
67
}
1486
1487
14
void CStringChecker::evalStpcpy(CheckerContext &C, const CallExpr *CE) const {
1488
14
  // char *stpcpy(char *restrict dst, const char *restrict src);
1489
14
  evalStrcpyCommon(C, CE,
1490
14
                   /* returnEnd = */ true,
1491
14
                   /* isBounded = */ false,
1492
14
                   /* isAppending = */ false);
1493
14
}
1494
1495
62
void CStringChecker::evalStrlcpy(CheckerContext &C, const CallExpr *CE) const {
1496
62
  // char *strlcpy(char *dst, const char *src, size_t n);
1497
62
  evalStrcpyCommon(C, CE,
1498
62
                   /* returnEnd = */ true,
1499
62
                   /* isBounded = */ true,
1500
62
                   /* isAppending = */ false,
1501
62
                   /* returnPtr = */ false);
1502
62
}
1503
1504
57
void CStringChecker::evalStrcat(CheckerContext &C, const CallExpr *CE) const {
1505
57
  //char *strcat(char *restrict s1, const char *restrict s2);
1506
57
  evalStrcpyCommon(C, CE,
1507
57
                   /* returnEnd = */ false,
1508
57
                   /* isBounded = */ false,
1509
57
                   /* isAppending = */ true);
1510
57
}
1511
1512
107
void CStringChecker::evalStrncat(CheckerContext &C, const CallExpr *CE) const {
1513
107
  //char *strncat(char *restrict s1, const char *restrict s2, size_t n);
1514
107
  evalStrcpyCommon(C, CE,
1515
107
                   /* returnEnd = */ false,
1516
107
                   /* isBounded = */ true,
1517
107
                   /* isAppending = */ true);
1518
107
}
1519
1520
35
void CStringChecker::evalStrlcat(CheckerContext &C, const CallExpr *CE) const {
1521
35
  // FIXME: strlcat() uses a different rule for bound checking, i.e. 'n' means
1522
35
  // a different thing as compared to strncat(). This currently causes
1523
35
  // false positives in the alpha string bound checker.
1524
35
1525
35
  //char *strlcat(char *s1, const char *s2, size_t n);
1526
35
  evalStrcpyCommon(C, CE,
1527
35
                   /* returnEnd = */ false,
1528
35
                   /* isBounded = */ true,
1529
35
                   /* isAppending = */ true,
1530
35
                   /* returnPtr = */ false);
1531
35
}
1532
1533
void CStringChecker::evalStrcpyCommon(CheckerContext &C, const CallExpr *CE,
1534
                                      bool returnEnd, bool isBounded,
1535
390
                                      bool isAppending, bool returnPtr) const {
1536
390
  CurrentFunctionDescription = "string copy function";
1537
390
  ProgramStateRef state = C.getState();
1538
390
  const LocationContext *LCtx = C.getLocationContext();
1539
390
1540
390
  // Check that the destination is non-null.
1541
390
  const Expr *Dst = CE->getArg(0);
1542
390
  SVal DstVal = state->getSVal(Dst, LCtx);
1543
390
1544
390
  state = checkNonNull(C, state, Dst, DstVal);
1545
390
  if (!state)
1546
23
    return;
1547
367
1548
367
  // Check that the source is non-null.
1549
367
  const Expr *srcExpr = CE->getArg(1);
1550
367
  SVal srcVal = state->getSVal(srcExpr, LCtx);
1551
367
  state = checkNonNull(C, state, srcExpr, srcVal);
1552
367
  if (!state)
1553
20
    return;
1554
347
1555
347
  // Get the string length of the source.
1556
347
  SVal strLength = getCStringLength(C, state, srcExpr, srcVal);
1557
347
1558
347
  // If the source isn't a valid C string, give up.
1559
347
  if (strLength.isUndef())
1560
25
    return;
1561
322
1562
322
  SValBuilder &svalBuilder = C.getSValBuilder();
1563
322
  QualType cmpTy = svalBuilder.getConditionType();
1564
322
  QualType sizeTy = svalBuilder.getContext().getSizeType();
1565
322
1566
322
  // These two values allow checking two kinds of errors:
1567
322
  // - actual overflows caused by a source that doesn't fit in the destination
1568
322
  // - potential overflows caused by a bound that could exceed the destination
1569
322
  SVal amountCopied = UnknownVal();
1570
322
  SVal maxLastElementIndex = UnknownVal();
1571
322
  const char *boundWarning = nullptr;
1572
322
1573
322
  state = CheckOverlap(C, state, isBounded ? 
CE->getArg(2)239
:
CE->getArg(1)83
, Dst, srcExpr);
1574
322
1575
322
  if (!state)
1576
1
    return;
1577
321
1578
321
  // If the function is strncpy, strncat, etc... it is bounded.
1579
321
  if (isBounded) {
1580
238
    // Get the max number of characters to copy.
1581
238
    const Expr *lenExpr = CE->getArg(2);
1582
238
    SVal lenVal = state->getSVal(lenExpr, LCtx);
1583
238
1584
238
    // Protect against misdeclared strncpy().
1585
238
    lenVal = svalBuilder.evalCast(lenVal, sizeTy, lenExpr->getType());
1586
238
1587
238
    Optional<NonLoc> strLengthNL = strLength.getAs<NonLoc>();
1588
238
    Optional<NonLoc> lenValNL = lenVal.getAs<NonLoc>();
1589
238
1590
238
    // If we know both values, we might be able to figure out how much
1591
238
    // we're copying.
1592
238
    if (strLengthNL && 
lenValNL230
) {
1593
217
      ProgramStateRef stateSourceTooLong, stateSourceNotTooLong;
1594
217
1595
217
      // Check if the max number to copy is less than the length of the src.
1596
217
      // If the bound is equal to the source length, strncpy won't null-
1597
217
      // terminate the result!
1598
217
      std::tie(stateSourceTooLong, stateSourceNotTooLong) = state->assume(
1599
217
          svalBuilder.evalBinOpNN(state, BO_GE, *strLengthNL, *lenValNL, cmpTy)
1600
217
              .castAs<DefinedOrUnknownSVal>());
1601
217
1602
217
      if (stateSourceTooLong && 
!stateSourceNotTooLong162
) {
1603
91
        // Max number to copy is less than the length of the src, so the actual
1604
91
        // strLength copied is the max number arg.
1605
91
        state = stateSourceTooLong;
1606
91
        amountCopied = lenVal;
1607
91
1608
126
      } else if (!stateSourceTooLong && 
stateSourceNotTooLong55
) {
1609
55
        // The source buffer entirely fits in the bound.
1610
55
        state = stateSourceNotTooLong;
1611
55
        amountCopied = strLength;
1612
55
      }
1613
217
    }
1614
238
1615
238
    // We still want to know if the bound is known to be too large.
1616
238
    if (lenValNL) {
1617
225
      if (isAppending) {
1618
117
        // For strncat, the check is strlen(dst) + lenVal < sizeof(dst)
1619
117
1620
117
        // Get the string length of the destination. If the destination is
1621
117
        // memory that can't have a string length, we shouldn't be copying
1622
117
        // into it anyway.
1623
117
        SVal dstStrLength = getCStringLength(C, state, Dst, DstVal);
1624
117
        if (dstStrLength.isUndef())
1625
0
          return;
1626
117
1627
117
        if (Optional<NonLoc> dstStrLengthNL = dstStrLength.getAs<NonLoc>()) {
1628
113
          maxLastElementIndex = svalBuilder.evalBinOpNN(state, BO_Add,
1629
113
                                                        *lenValNL,
1630
113
                                                        *dstStrLengthNL,
1631
113
                                                        sizeTy);
1632
113
          boundWarning = "Size argument is greater than the free space in the "
1633
113
                         "destination buffer";
1634
113
        }
1635
117
1636
117
      } else {
1637
108
        // For strncpy, this is just checking that lenVal <= sizeof(dst)
1638
108
        // (Yes, strncpy and strncat differ in how they treat termination.
1639
108
        // strncat ALWAYS terminates, but strncpy doesn't.)
1640
108
1641
108
        // We need a special case for when the copy size is zero, in which
1642
108
        // case strncpy will do no work at all. Our bounds check uses n-1
1643
108
        // as the last element accessed, so n == 0 is problematic.
1644
108
        ProgramStateRef StateZeroSize, StateNonZeroSize;
1645
108
        std::tie(StateZeroSize, StateNonZeroSize) =
1646
108
          assumeZero(C, state, *lenValNL, sizeTy);
1647
108
1648
108
        // If the size is known to be zero, we're done.
1649
108
        if (StateZeroSize && 
!StateNonZeroSize6
) {
1650
6
          if (returnPtr) {
1651
5
            StateZeroSize = StateZeroSize->BindExpr(CE, LCtx, DstVal);
1652
5
          } else {
1653
1
            StateZeroSize = StateZeroSize->BindExpr(CE, LCtx, *lenValNL);
1654
1
          }
1655
6
          C.addTransition(StateZeroSize);
1656
6
          return;
1657
6
        }
1658
102
1659
102
        // Otherwise, go ahead and figure out the last element we'll touch.
1660
102
        // We don't record the non-zero assumption here because we can't
1661
102
        // be sure. We won't warn on a possible zero.
1662
102
        NonLoc one = svalBuilder.makeIntVal(1, sizeTy).castAs<NonLoc>();
1663
102
        maxLastElementIndex = svalBuilder.evalBinOpNN(state, BO_Sub, *lenValNL,
1664
102
                                                      one, sizeTy);
1665
102
        boundWarning = "Size argument is greater than the length of the "
1666
102
                       "destination buffer";
1667
102
      }
1668
225
    }
1669
238
1670
238
    // If we couldn't pin down the copy length, at least bound it.
1671
238
    // FIXME: We should actually run this code path for append as well, but
1672
238
    // right now it creates problems with constraints (since we can end up
1673
238
    // trying to pass constraints from symbol to symbol).
1674
238
    
if (232
amountCopied.isUnknown()232
&&
!isAppending92
) {
1675
46
      // Try to get a "hypothetical" string length symbol, which we can later
1676
46
      // set as a real value if that turns out to be the case.
1677
46
      amountCopied = getCStringLength(C, state, lenExpr, srcVal, true);
1678
46
      assert(!amountCopied.isUndef());
1679
46
1680
46
      if (Optional<NonLoc> amountCopiedNL = amountCopied.getAs<NonLoc>()) {
1681
46
        if (lenValNL) {
1682
42
          // amountCopied <= lenVal
1683
42
          SVal copiedLessThanBound = svalBuilder.evalBinOpNN(state, BO_LE,
1684
42
                                                             *amountCopiedNL,
1685
42
                                                             *lenValNL,
1686
42
                                                             cmpTy);
1687
42
          state = state->assume(
1688
42
              copiedLessThanBound.castAs<DefinedOrUnknownSVal>(), true);
1689
42
          if (!state)
1690
0
            return;
1691
46
        }
1692
46
1693
46
        if (strLengthNL) {
1694
46
          // amountCopied <= strlen(source)
1695
46
          SVal copiedLessThanSrc = svalBuilder.evalBinOpNN(state, BO_LE,
1696
46
                                                           *amountCopiedNL,
1697
46
                                                           *strLengthNL,
1698
46
                                                           cmpTy);
1699
46
          state = state->assume(
1700
46
              copiedLessThanSrc.castAs<DefinedOrUnknownSVal>(), true);
1701
46
          if (!state)
1702
0
            return;
1703
83
        }
1704
46
      }
1705
46
    }
1706
83
1707
83
  } else {
1708
83
    // The function isn't bounded. The amount copied should match the length
1709
83
    // of the source buffer.
1710
83
    amountCopied = strLength;
1711
83
  }
1712
321
1713
321
  assert(state);
1714
315
1715
315
  // This represents the number of characters copied into the destination
1716
315
  // buffer. (It may not actually be the strlen if the destination buffer
1717
315
  // is not terminated.)
1718
315
  SVal finalStrLength = UnknownVal();
1719
315
1720
315
  // If this is an appending function (strcat, strncat...) then set the
1721
315
  // string length to strlen(src) + strlen(dst) since the buffer will
1722
315
  // ultimately contain both.
1723
315
  if (isAppending) {
1724
168
    // Get the string length of the destination. If the destination is memory
1725
168
    // that can't have a string length, we shouldn't be copying into it anyway.
1726
168
    SVal dstStrLength = getCStringLength(C, state, Dst, DstVal);
1727
168
    if (dstStrLength.isUndef())
1728
0
      return;
1729
168
1730
168
    Optional<NonLoc> srcStrLengthNL = amountCopied.getAs<NonLoc>();
1731
168
    Optional<NonLoc> dstStrLengthNL = dstStrLength.getAs<NonLoc>();
1732
168
1733
168
    // If we know both string lengths, we might know the final string length.
1734
168
    if (srcStrLengthNL && 
dstStrLengthNL117
) {
1735
117
      // Make sure the two lengths together don't overflow a size_t.
1736
117
      state = checkAdditionOverflow(C, state, *srcStrLengthNL, *dstStrLengthNL);
1737
117
      if (!state)
1738
0
        return;
1739
117
1740
117
      finalStrLength = svalBuilder.evalBinOpNN(state, BO_Add, *srcStrLengthNL,
1741
117
                                               *dstStrLengthNL, sizeTy);
1742
117
    }
1743
168
1744
168
    // If we couldn't get a single value for the final string length,
1745
168
    // we can at least bound it by the individual lengths.
1746
168
    if (finalStrLength.isUnknown()) {
1747
51
      // Try to get a "hypothetical" string length symbol, which we can later
1748
51
      // set as a real value if that turns out to be the case.
1749
51
      finalStrLength = getCStringLength(C, state, CE, DstVal, true);
1750
51
      assert(!finalStrLength.isUndef());
1751
51
1752
51
      if (Optional<NonLoc> finalStrLengthNL = finalStrLength.getAs<NonLoc>()) {
1753
47
        if (srcStrLengthNL) {
1754
0
          // finalStrLength >= srcStrLength
1755
0
          SVal sourceInResult = svalBuilder.evalBinOpNN(state, BO_GE,
1756
0
                                                        *finalStrLengthNL,
1757
0
                                                        *srcStrLengthNL,
1758
0
                                                        cmpTy);
1759
0
          state = state->assume(sourceInResult.castAs<DefinedOrUnknownSVal>(),
1760
0
                                true);
1761
0
          if (!state)
1762
0
            return;
1763
47
        }
1764
47
1765
47
        if (dstStrLengthNL) {
1766
47
          // finalStrLength >= dstStrLength
1767
47
          SVal destInResult = svalBuilder.evalBinOpNN(state, BO_GE,
1768
47
                                                      *finalStrLengthNL,
1769
47
                                                      *dstStrLengthNL,
1770
47
                                                      cmpTy);
1771
47
          state =
1772
47
              state->assume(destInResult.castAs<DefinedOrUnknownSVal>(), true);
1773
47
          if (!state)
1774
0
            return;
1775
147
        }
1776
47
      }
1777
51
    }
1778
147
1779
147
  } else {
1780
147
    // Otherwise, this is a copy-over function (strcpy, strncpy, ...), and
1781
147
    // the final string length will match the input string length.
1782
147
    finalStrLength = amountCopied;
1783
147
  }
1784
315
1785
315
  SVal Result;
1786
315
1787
315
  if (returnPtr) {
1788
222
    // The final result of the function will either be a pointer past the last
1789
222
    // copied element, or a pointer to the start of the destination buffer.
1790
222
    Result = (returnEnd ? 
UnknownVal()14
:
DstVal208
);
1791
222
  } else {
1792
93
    Result = finalStrLength;
1793
93
  }
1794
315
1795
315
  assert(state);
1796
315
1797
315
  // If the destination is a MemRegion, try to check for a buffer overflow and
1798
315
  // record the new string length.
1799
315
  if (Optional<loc::MemRegionVal> dstRegVal =
1800
315
      DstVal.getAs<loc::MemRegionVal>()) {
1801
315
    QualType ptrTy = Dst->getType();
1802
315
1803
315
    // If we have an exact value on a bounded copy, use that to check for
1804
315
    // overflows, rather than our estimate about how much is actually copied.
1805
315
    if (boundWarning) {
1806
215
      if (Optional<NonLoc> maxLastNL = maxLastElementIndex.getAs<NonLoc>()) {
1807
215
        SVal maxLastElement = svalBuilder.evalBinOpLN(state, BO_Add, *dstRegVal,
1808
215
            *maxLastNL, ptrTy);
1809
215
        state = CheckLocation(C, state, CE->getArg(2), maxLastElement,
1810
215
            boundWarning);
1811
215
        if (!state)
1812
79
          return;
1813
236
      }
1814
215
    }
1815
236
1816
236
    // Then, if the final length is known...
1817
236
    if (Optional<NonLoc> knownStrLength = finalStrLength.getAs<NonLoc>()) {
1818
232
      SVal lastElement = svalBuilder.evalBinOpLN(state, BO_Add, *dstRegVal,
1819
232
          *knownStrLength, ptrTy);
1820
232
1821
232
      // ...and we haven't checked the bound, we'll check the actual copy.
1822
232
      if (!boundWarning) {
1823
96
        const char * const warningMsg =
1824
96
          "String copy function overflows destination buffer";
1825
96
        state = CheckLocation(C, state, Dst, lastElement, warningMsg);
1826
96
        if (!state)
1827
20
          return;
1828
212
      }
1829
212
1830
212
      // If this is a stpcpy-style copy, the last element is the return value.
1831
212
      if (returnPtr && 
returnEnd157
)
1832
10
        Result = lastElement;
1833
212
    }
1834
236
1835
236
    // Invalidate the destination (regular invalidation without pointer-escaping
1836
236
    // the address of the top-level region). This must happen before we set the
1837
236
    // C string length because invalidation will clear the length.
1838
236
    // FIXME: Even if we can't perfectly model the copy, we should see if we
1839
236
    // can use LazyCompoundVals to copy the source values into the destination.
1840
236
    // This would probably remove any existing bindings past the end of the
1841
236
    // string, but that's still an improvement over blank invalidation.
1842
236
    state = InvalidateBuffer(C, state, Dst, *dstRegVal,
1843
216
        /*IsSourceBuffer*/false, nullptr);
1844
216
1845
216
    // Invalidate the source (const-invalidation without const-pointer-escaping
1846
216
    // the address of the top-level region).
1847
216
    state = InvalidateBuffer(C, state, srcExpr, srcVal, /*IsSourceBuffer*/true,
1848
216
        nullptr);
1849
216
1850
216
    // Set the C string length of the destination, if we know it.
1851
216
    if (isBounded && 
!isAppending153
) {
1852
76
      // strncpy is annoying in that it doesn't guarantee to null-terminate
1853
76
      // the result string. If the original string didn't fit entirely inside
1854
76
      // the bound (including the null-terminator), we don't know how long the
1855
76
      // result is.
1856
76
      if (amountCopied != strLength)
1857
48
        finalStrLength = UnknownVal();
1858
76
    }
1859
216
    state = setCStringLength(state, dstRegVal->getRegion(), finalStrLength);
1860
216
  }
1861
315
1862
315
  assert(state);
1863
216
1864
216
  if (returnPtr) {
1865
157
    // If this is a stpcpy-style copy, but we were unable to check for a buffer
1866
157
    // overflow, we still need a result. Conjure a return value.
1867
157
    if (returnEnd && 
Result.isUnknown()10
) {
1868
0
      Result = svalBuilder.conjureSymbolVal(nullptr, CE, LCtx, C.blockCount());
1869
0
    }
1870
157
  }
1871
216
  // Set the return value.
1872
216
  state = state->BindExpr(CE, LCtx, Result);
1873
216
  C.addTransition(state);
1874
216
}
1875
1876
106
void CStringChecker::evalStrcmp(CheckerContext &C, const CallExpr *CE) const {
1877
106
  //int strcmp(const char *s1, const char *s2);
1878
106
  evalStrcmpCommon(C, CE, /* isBounded = */ false, /* ignoreCase = */ false);
1879
106
}
1880
1881
110
void CStringChecker::evalStrncmp(CheckerContext &C, const CallExpr *CE) const {
1882
110
  //int strncmp(const char *s1, const char *s2, size_t n);
1883
110
  evalStrcmpCommon(C, CE, /* isBounded = */ true, /* ignoreCase = */ false);
1884
110
}
1885
1886
void CStringChecker::evalStrcasecmp(CheckerContext &C,
1887
95
    const CallExpr *CE) const {
1888
95
  //int strcasecmp(const char *s1, const char *s2);
1889
95
  evalStrcmpCommon(C, CE, /* isBounded = */ false, /* ignoreCase = */ true);
1890
95
}
1891
1892
void CStringChecker::evalStrncasecmp(CheckerContext &C,
1893
110
    const CallExpr *CE) const {
1894
110
  //int strncasecmp(const char *s1, const char *s2, size_t n);
1895
110
  evalStrcmpCommon(C, CE, /* isBounded = */ true, /* ignoreCase = */ true);
1896
110
}
1897
1898
void CStringChecker::evalStrcmpCommon(CheckerContext &C, const CallExpr *CE,
1899
421
    bool isBounded, bool ignoreCase) const {
1900
421
  CurrentFunctionDescription = "string comparison function";
1901
421
  ProgramStateRef state = C.getState();
1902
421
  const LocationContext *LCtx = C.getLocationContext();
1903
421
1904
421
  // Check that the first string is non-null
1905
421
  const Expr *s1 = CE->getArg(0);
1906
421
  SVal s1Val = state->getSVal(s1, LCtx);
1907
421
  state = checkNonNull(C, state, s1, s1Val);
1908
421
  if (!state)
1909
20
    return;
1910
401
1911
401
  // Check that the second string is non-null.
1912
401
  const Expr *s2 = CE->getArg(1);
1913
401
  SVal s2Val = state->getSVal(s2, LCtx);
1914
401
  state = checkNonNull(C, state, s2, s2Val);
1915
401
  if (!state)
1916
20
    return;
1917
381
1918
381
  // Get the string length of the first string or give up.
1919
381
  SVal s1Length = getCStringLength(C, state, s1, s1Val);
1920
381
  if (s1Length.isUndef())
1921
0
    return;
1922
381
1923
381
  // Get the string length of the second string or give up.
1924
381
  SVal s2Length = getCStringLength(C, state, s2, s2Val);
1925
381
  if (s2Length.isUndef())
1926
0
    return;
1927
381
1928
381
  // If we know the two buffers are the same, we know the result is 0.
1929
381
  // First, get the two buffers' addresses. Another checker will have already
1930
381
  // made sure they're not undefined.
1931
381
  DefinedOrUnknownSVal LV = s1Val.castAs<DefinedOrUnknownSVal>();
1932
381
  DefinedOrUnknownSVal RV = s2Val.castAs<DefinedOrUnknownSVal>();
1933
381
1934
381
  // See if they are the same.
1935
381
  SValBuilder &svalBuilder = C.getSValBuilder();
1936
381
  DefinedOrUnknownSVal SameBuf = svalBuilder.evalEQ(state, LV, RV);
1937
381
  ProgramStateRef StSameBuf, StNotSameBuf;
1938
381
  std::tie(StSameBuf, StNotSameBuf) = state->assume(SameBuf);
1939
381
1940
381
  // If the two arguments might be the same buffer, we know the result is 0,
1941
381
  // and we only need to check one size.
1942
381
  if (StSameBuf) {
1943
11
    StSameBuf = StSameBuf->BindExpr(CE, LCtx,
1944
11
        svalBuilder.makeZeroVal(CE->getType()));
1945
11
    C.addTransition(StSameBuf);
1946
11
1947
11
    // If the two arguments are GUARANTEED to be the same, we're done!
1948
11
    if (!StNotSameBuf)
1949
5
      return;
1950
376
  }
1951
376
1952
376
  assert(StNotSameBuf);
1953
376
  state = StNotSameBuf;
1954
376
1955
376
  // At this point we can go about comparing the two buffers.
1956
376
  // For now, we only do this if they're both known string literals.
1957
376
1958
376
  // Attempt to extract string literals from both expressions.
1959
376
  const StringLiteral *s1StrLiteral = getCStringLiteral(C, state, s1, s1Val);
1960
376
  const StringLiteral *s2StrLiteral = getCStringLiteral(C, state, s2, s2Val);
1961
376
  bool canComputeResult = false;
1962
376
  SVal resultVal = svalBuilder.conjureSymbolVal(nullptr, CE, LCtx,
1963
376
      C.blockCount());
1964
376
1965
376
  if (s1StrLiteral && 
s2StrLiteral375
) {
1966
370
    StringRef s1StrRef = s1StrLiteral->getString();
1967
370
    StringRef s2StrRef = s2StrLiteral->getString();
1968
370
1969
370
    if (isBounded) {
1970
200
      // Get the max number of characters to compare.
1971
200
      const Expr *lenExpr = CE->getArg(2);
1972
200
      SVal lenVal = state->getSVal(lenExpr, LCtx);
1973
200
1974
200
      // If the length is known, we can get the right substrings.
1975
200
      if (const llvm::APSInt *len = svalBuilder.getKnownValue(state, lenVal)) {
1976
200
        // Create substrings of each to compare the prefix.
1977
200
        s1StrRef = s1StrRef.substr(0, (size_t)len->getZExtValue());
1978
200
        s2StrRef = s2StrRef.substr(0, (size_t)len->getZExtValue());
1979
200
        canComputeResult = true;
1980
200
      }
1981
200
    } else {
1982
170
      // This is a normal, unbounded strcmp.
1983
170
      canComputeResult = true;
1984
170
    }
1985
370
1986
370
    if (canComputeResult) {
1987
370
      // Real strcmp stops at null characters.
1988
370
      size_t s1Term = s1StrRef.find('\0');
1989
370
      if (s1Term != StringRef::npos)
1990
20
        s1StrRef = s1StrRef.substr(0, s1Term);
1991
370
1992
370
      size_t s2Term = s2StrRef.find('\0');
1993
370
      if (s2Term != StringRef::npos)
1994
20
        s2StrRef = s2StrRef.substr(0, s2Term);
1995
370
1996
370
      // Use StringRef's comparison methods to compute the actual result.
1997
370
      int compareRes = ignoreCase ? 
s1StrRef.compare_lower(s2StrRef)185
1998
370
        : 
s1StrRef.compare(s2StrRef)185
;
1999
370
2000
370
      // The strcmp function returns an integer greater than, equal to, or less
2001
370
      // than zero, [c11, p7.24.4.2].
2002
370
      if (compareRes == 0) {
2003
110
        resultVal = svalBuilder.makeIntVal(compareRes, CE->getType());
2004
110
      }
2005
260
      else {
2006
260
        DefinedSVal zeroVal = svalBuilder.makeIntVal(0, CE->getType());
2007
260
        // Constrain strcmp's result range based on the result of StringRef's
2008
260
        // comparison methods.
2009
260
        BinaryOperatorKind op = (compareRes == 1) ? 
BO_GT110
:
BO_LT150
;
2010
260
        SVal compareWithZero =
2011
260
          svalBuilder.evalBinOp(state, op, resultVal, zeroVal,
2012
260
              svalBuilder.getConditionType());
2013
260
        DefinedSVal compareWithZeroVal = compareWithZero.castAs<DefinedSVal>();
2014
260
        state = state->assume(compareWithZeroVal, true);
2015
260
      }
2016
370
    }
2017
370
  }
2018
376
2019
376
  state = state->BindExpr(CE, LCtx, resultVal);
2020
376
2021
376
  // Record this as a possible path.
2022
376
  C.addTransition(state);
2023
376
}
2024
2025
30
void CStringChecker::evalStrsep(CheckerContext &C, const CallExpr *CE) const {
2026
30
  //char *strsep(char **stringp, const char *delim);
2027
30
  // Sanity: does the search string parameter match the return type?
2028
30
  const Expr *SearchStrPtr = CE->getArg(0);
2029
30
  QualType CharPtrTy = SearchStrPtr->getType()->getPointeeType();
2030
30
  if (CharPtrTy.isNull() ||
2031
30
      CE->getType().getUnqualifiedType() != CharPtrTy.getUnqualifiedType())
2032
0
    return;
2033
30
2034
30
  CurrentFunctionDescription = "strsep()";
2035
30
  ProgramStateRef State = C.getState();
2036
30
  const LocationContext *LCtx = C.getLocationContext();
2037
30
2038
30
  // Check that the search string pointer is non-null (though it may point to
2039
30
  // a null string).
2040
30
  SVal SearchStrVal = State->getSVal(SearchStrPtr, LCtx);
2041
30
  State = checkNonNull(C, State, SearchStrPtr, SearchStrVal);
2042
30
  if (!State)
2043
5
    return;
2044
25
2045
25
  // Check that the delimiter string is non-null.
2046
25
  const Expr *DelimStr = CE->getArg(1);
2047
25
  SVal DelimStrVal = State->getSVal(DelimStr, LCtx);
2048
25
  State = checkNonNull(C, State, DelimStr, DelimStrVal);
2049
25
  if (!State)
2050
5
    return;
2051
20
2052
20
  SValBuilder &SVB = C.getSValBuilder();
2053
20
  SVal Result;
2054
20
  if (Optional<Loc> SearchStrLoc = SearchStrVal.getAs<Loc>()) {
2055
20
    // Get the current value of the search string pointer, as a char*.
2056
20
    Result = State->getSVal(*SearchStrLoc, CharPtrTy);
2057
20
2058
20
    // Invalidate the search string, representing the change of one delimiter
2059
20
    // character to NUL.
2060
20
    State = InvalidateBuffer(C, State, SearchStrPtr, Result,
2061
20
        /*IsSourceBuffer*/false, nullptr);
2062
20
2063
20
    // Overwrite the search string pointer. The new value is either an address
2064
20
    // further along in the same string, or NULL if there are no more tokens.
2065
20
    State = State->bindLoc(*SearchStrLoc,
2066
20
        SVB.conjureSymbolVal(getTag(),
2067
20
          CE,
2068
20
          LCtx,
2069
20
          CharPtrTy,
2070
20
          C.blockCount()),
2071
20
        LCtx);
2072
20
  } else {
2073
0
    assert(SearchStrVal.isUnknown());
2074
0
    // Conjure a symbolic value. It's the best we can do.
2075
0
    Result = SVB.conjureSymbolVal(nullptr, CE, LCtx, C.blockCount());
2076
0
  }
2077
20
2078
20
  // Set the return value, and finish.
2079
20
  State = State->BindExpr(CE, LCtx, Result);
2080
20
  C.addTransition(State);
2081
20
}
2082
2083
// These should probably be moved into a C++ standard library checker.
2084
7
void CStringChecker::evalStdCopy(CheckerContext &C, const CallExpr *CE) const {
2085
7
  evalStdCopyCommon(C, CE);
2086
7
}
2087
2088
void CStringChecker::evalStdCopyBackward(CheckerContext &C,
2089
5
    const CallExpr *CE) const {
2090
5
  evalStdCopyCommon(C, CE);
2091
5
}
2092
2093
void CStringChecker::evalStdCopyCommon(CheckerContext &C,
2094
12
    const CallExpr *CE) const {
2095
12
  if (!CE->getArg(2)->getType()->isPointerType())
2096
2
    return;
2097
10
2098
10
  ProgramStateRef State = C.getState();
2099
10
2100
10
  const LocationContext *LCtx = C.getLocationContext();
2101
10
2102
10
  // template <class _InputIterator, class _OutputIterator>
2103
10
  // _OutputIterator
2104
10
  // copy(_InputIterator __first, _InputIterator __last,
2105
10
  //        _OutputIterator __result)
2106
10
2107
10
  // Invalidate the destination buffer
2108
10
  const Expr *Dst = CE->getArg(2);
2109
10
  SVal DstVal = State->getSVal(Dst, LCtx);
2110
10
  State = InvalidateBuffer(C, State, Dst, DstVal, /*IsSource=*/false,
2111
10
      /*Size=*/nullptr);
2112
10
2113
10
  SValBuilder &SVB = C.getSValBuilder();
2114
10
2115
10
  SVal ResultVal = SVB.conjureSymbolVal(nullptr, CE, LCtx, C.blockCount());
2116
10
  State = State->BindExpr(CE, LCtx, ResultVal);
2117
10
2118
10
  C.addTransition(State);
2119
10
}
2120
2121
159
void CStringChecker::evalMemset(CheckerContext &C, const CallExpr *CE) const {
2122
159
  CurrentFunctionDescription = "memory set function";
2123
159
2124
159
  const Expr *Mem = CE->getArg(0);
2125
159
  const Expr *CharE = CE->getArg(1);
2126
159
  const Expr *Size = CE->getArg(2);
2127
159
  ProgramStateRef State = C.getState();
2128
159
2129
159
  // See if the size argument is zero.
2130
159
  const LocationContext *LCtx = C.getLocationContext();
2131
159
  SVal SizeVal = State->getSVal(Size, LCtx);
2132
159
  QualType SizeTy = Size->getType();
2133
159
2134
159
  ProgramStateRef StateZeroSize, StateNonZeroSize;
2135
159
  std::tie(StateZeroSize, StateNonZeroSize) =
2136
159
    assumeZero(C, State, SizeVal, SizeTy);
2137
159
2138
159
  // Get the value of the memory area.
2139
159
  SVal MemVal = State->getSVal(Mem, LCtx);
2140
159
2141
159
  // If the size is zero, there won't be any actual memory access, so
2142
159
  // just bind the return value to the Mem buffer and return.
2143
159
  if (StateZeroSize && 
!StateNonZeroSize0
) {
2144
0
    StateZeroSize = StateZeroSize->BindExpr(CE, LCtx, MemVal);
2145
0
    C.addTransition(StateZeroSize);
2146
0
    return;
2147
0
  }
2148
159
2149
159
  // Ensure the memory area is not null.
2150
159
  // If it is NULL there will be a NULL pointer dereference.
2151
159
  State = checkNonNull(C, StateNonZeroSize, Mem, MemVal);
2152
159
  if (!State)
2153
1
    return;
2154
158
2155
158
  State = CheckBufferAccess(C, State, Size, Mem);
2156
158
  if (!State)
2157
2
    return;
2158
156
2159
156
  // According to the values of the arguments, bind the value of the second
2160
156
  // argument to the destination buffer and set string length, or just
2161
156
  // invalidate the destination buffer.
2162
156
  if (!memsetAux(Mem, C.getSVal(CharE), Size, C, State))
2163
0
    return;
2164
156
2165
156
  State = State->BindExpr(CE, LCtx, MemVal);
2166
156
  C.addTransition(State);
2167
156
}
2168
2169
30
void CStringChecker::evalBzero(CheckerContext &C, const CallExpr *CE) const {
2170
30
  CurrentFunctionDescription = "memory clearance function";
2171
30
2172
30
  const Expr *Mem = CE->getArg(0);
2173
30
  const Expr *Size = CE->getArg(1);
2174
30
  SVal Zero = C.getSValBuilder().makeZeroVal(C.getASTContext().IntTy);
2175
30
2176
30
  ProgramStateRef State = C.getState();
2177
30
  
2178
30
  // See if the size argument is zero.
2179
30
  SVal SizeVal = C.getSVal(Size);
2180
30
  QualType SizeTy = Size->getType();
2181
30
2182
30
  ProgramStateRef StateZeroSize, StateNonZeroSize;
2183
30
  std::tie(StateZeroSize, StateNonZeroSize) =
2184
30
    assumeZero(C, State, SizeVal, SizeTy);
2185
30
2186
30
  // If the size is zero, there won't be any actual memory access,
2187
30
  // In this case we just return.
2188
30
  if (StateZeroSize && 
!StateNonZeroSize0
) {
2189
0
    C.addTransition(StateZeroSize);
2190
0
    return;
2191
0
  }
2192
30
2193
30
  // Get the value of the memory area.
2194
30
  SVal MemVal = C.getSVal(Mem);
2195
30
2196
30
  // Ensure the memory area is not null.
2197
30
  // If it is NULL there will be a NULL pointer dereference.
2198
30
  State = checkNonNull(C, StateNonZeroSize, Mem, MemVal);
2199
30
  if (!State)
2200
10
    return;
2201
20
2202
20
  State = CheckBufferAccess(C, State, Size, Mem);
2203
20
  if (!State)
2204
4
    return;
2205
16
2206
16
  if (!memsetAux(Mem, Zero, Size, C, State))
2207
0
    return;
2208
16
2209
16
  C.addTransition(State);
2210
16
}
2211
2212
//===----------------------------------------------------------------------===//
2213
// The driver method, and other Checker callbacks.
2214
//===----------------------------------------------------------------------===//
2215
2216
CStringChecker::FnCheck CStringChecker::identifyCall(const CallEvent &Call,
2217
18.2k
                                                     CheckerContext &C) const {
2218
18.2k
  const auto *CE = dyn_cast_or_null<CallExpr>(Call.getOriginExpr());
2219
18.2k
  if (!CE)
2220
0
    return nullptr;
2221
18.2k
2222
18.2k
  const FunctionDecl *FD = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
2223
18.2k
  if (!FD)
2224
16
    return nullptr;
2225
18.2k
2226
18.2k
  if (Call.isCalled(StdCopy)) {
2227
7
    return &CStringChecker::evalStdCopy;
2228
18.2k
  } else if (Call.isCalled(StdCopyBackward)) {
2229
5
    return &CStringChecker::evalStdCopyBackward;
2230
5
  }
2231
18.2k
2232
18.2k
  // Pro-actively check that argument types are safe to do arithmetic upon.
2233
18.2k
  // We do not want to crash if someone accidentally passes a structure
2234
18.2k
  // into, say, a C++ overload of any of these functions. We could not check
2235
18.2k
  // that for std::copy because they may have arguments of other types.
2236
18.2k
  for (auto I : CE->arguments()) {
2237
17.6k
    QualType T = I->getType();
2238
17.6k
    if (!T->isIntegralOrEnumerationType() && 
!T->isPointerType()13.3k
)
2239
5.47k
      return nullptr;
2240
17.6k
  }
2241
18.2k
2242
18.2k
  const FnCheck *Callback = Callbacks.lookup(Call);
2243
12.7k
  if (Callback)
2244
2.01k
    return *Callback;
2245
10.7k
2246
10.7k
  return nullptr;
2247
10.7k
}
2248
2249
18.2k
bool CStringChecker::evalCall(const CallEvent &Call, CheckerContext &C) const {
2250
18.2k
  FnCheck Callback = identifyCall(Call, C);
2251
18.2k
2252
18.2k
  // If the callee isn't a string function, let another checker handle it.
2253
18.2k
  if (!Callback)
2254
16.2k
    return false;
2255
2.02k
2256
2.02k
  // Check and evaluate the call.
2257
2.02k
  const auto *CE = cast<CallExpr>(Call.getOriginExpr());
2258
2.02k
  (this->*Callback)(C, CE);
2259
2.02k
2260
2.02k
  // If the evaluate call resulted in no change, chain to the next eval call
2261
2.02k
  // handler.
2262
2.02k
  // Note, the custom CString evaluation calls assume that basic safety
2263
2.02k
  // properties are held. However, if the user chooses to turn off some of these
2264
2.02k
  // checks, we ignore the issues and leave the call evaluation to a generic
2265
2.02k
  // handler.
2266
2.02k
  return C.isDifferent();
2267
2.02k
}
2268
2269
9.38k
void CStringChecker::checkPreStmt(const DeclStmt *DS, CheckerContext &C) const {
2270
9.38k
  // Record string length for char a[] = "abc";
2271
9.38k
  ProgramStateRef state = C.getState();
2272
9.38k
2273
9.38k
  for (const auto *I : DS->decls()) {
2274
9.38k
    const VarDecl *D = dyn_cast<VarDecl>(I);
2275
9.38k
    if (!D)
2276
0
      continue;
2277
9.38k
2278
9.38k
    // FIXME: Handle array fields of structs.
2279
9.38k
    if (!D->getType()->isArrayType())
2280
8.70k
      continue;
2281
683
2282
683
    const Expr *Init = D->getInit();
2283
683
    if (!Init)
2284
189
      continue;
2285
494
    if (!isa<StringLiteral>(Init))
2286
306
      continue;
2287
188
2288
188
    Loc VarLoc = state->getLValue(D, C.getLocationContext());
2289
188
    const MemRegion *MR = VarLoc.getAsRegion();
2290
188
    if (!MR)
2291
0
      continue;
2292
188
2293
188
    SVal StrVal = C.getSVal(Init);
2294
188
    assert(StrVal.isValid() && "Initializer string is unknown or undefined");
2295
188
    DefinedOrUnknownSVal strLength =
2296
188
      getCStringLength(C, state, Init, StrVal).castAs<DefinedOrUnknownSVal>();
2297
188
2298
188
    state = state->set<CStringLength>(MR, strLength);
2299
188
  }
2300
9.38k
2301
9.38k
  C.addTransition(state);
2302
9.38k
}
2303
2304
ProgramStateRef
2305
CStringChecker::checkRegionChanges(ProgramStateRef state,
2306
    const InvalidatedSymbols *,
2307
    ArrayRef<const MemRegion *> ExplicitRegions,
2308
    ArrayRef<const MemRegion *> Regions,
2309
    const LocationContext *LCtx,
2310
51.4k
    const CallEvent *Call) const {
2311
51.4k
  CStringLengthTy Entries = state->get<CStringLength>();
2312
51.4k
  if (Entries.isEmpty())
2313
50.5k
    return state;
2314
931
2315
931
  llvm::SmallPtrSet<const MemRegion *, 8> Invalidated;
2316
931
  llvm::SmallPtrSet<const MemRegion *, 32> SuperRegions;
2317
931
2318
931
  // First build sets for the changed regions and their super-regions.
2319
931
  for (ArrayRef<const MemRegion *>::iterator
2320
2.08k
      I = Regions.begin(), E = Regions.end(); I != E; 
++I1.15k
) {
2321
1.15k
    const MemRegion *MR = *I;
2322
1.15k
    Invalidated.insert(MR);
2323
1.15k
2324
1.15k
    SuperRegions.insert(MR);
2325
1.99k
    while (const SubRegion *SR = dyn_cast<SubRegion>(MR)) {
2326
838
      MR = SR->getSuperRegion();
2327
838
      SuperRegions.insert(MR);
2328
838
    }
2329
1.15k
  }
2330
931
2331
931
  CStringLengthTy::Factory &F = state->get_context<CStringLength>();
2332
931
2333
931
  // Then loop over the entries in the current state.
2334
931
  for (CStringLengthTy::iterator I = Entries.begin(),
2335
1.96k
      E = Entries.end(); I != E; 
++I1.03k
) {
2336
1.03k
    const MemRegion *MR = I.getKey();
2337
1.03k
2338
1.03k
    // Is this entry for a super-region of a changed region?
2339
1.03k
    if (SuperRegions.count(MR)) {
2340
470
      Entries = F.remove(Entries, MR);
2341
470
      continue;
2342
470
    }
2343
562
2344
562
    // Is this entry for a sub-region of a changed region?
2345
562
    const MemRegion *Super = MR;
2346
1.13k
    while (const SubRegion *SR = dyn_cast<SubRegion>(Super)) {
2347
596
      Super = SR->getSuperRegion();
2348
596
      if (Invalidated.count(Super)) {
2349
24
        Entries = F.remove(Entries, MR);
2350
24
        break;
2351
24
      }
2352
596
    }
2353
562
  }
2354
931
2355
931
  return state->set<CStringLength>(Entries);
2356
931
}
2357
2358
void CStringChecker::checkLiveSymbols(ProgramStateRef state,
2359
107k
    SymbolReaper &SR) const {
2360
107k
  // Mark all symbols in our string length map as valid.
2361
107k
  CStringLengthTy Entries = state->get<CStringLength>();
2362
107k
2363
107k
  for (CStringLengthTy::iterator I = Entries.begin(), E = Entries.end();
2364
109k
      I != E; 
++I2.68k
) {
2365
2.68k
    SVal Len = I.getData();
2366
2.68k
2367
2.68k
    for (SymExpr::symbol_iterator si = Len.symbol_begin(),
2368
4.31k
        se = Len.symbol_end(); si != se; 
++si1.62k
)
2369
1.62k
      SR.markInUse(*si);
2370
2.68k
  }
2371
107k
}
2372
2373
void CStringChecker::checkDeadSymbols(SymbolReaper &SR,
2374
107k
    CheckerContext &C) const {
2375
107k
  ProgramStateRef state = C.getState();
2376
107k
  CStringLengthTy Entries = state->get<CStringLength>();
2377
107k
  if (Entries.isEmpty())
2378
105k
    return;
2379
2.24k
2380
2.24k
  CStringLengthTy::Factory &F = state->get_context<CStringLength>();
2381
2.24k
  for (CStringLengthTy::iterator I = Entries.begin(), E = Entries.end();
2382
4.92k
      I != E; 
++I2.68k
) {
2383
2.68k
    SVal Len = I.getData();
2384
2.68k
    if (SymbolRef Sym = Len.getAsSymbol()) {
2385
1.56k
      if (SR.isDead(Sym))
2386
429
        Entries = F.remove(Entries, I.getKey());
2387
1.56k
    }
2388
2.68k
  }
2389
2.24k
2390
2.24k
  state = state->set<CStringLength>(Entries);
2391
2.24k
  C.addTransition(state);
2392
2.24k
}
2393
2394
198
void ento::registerCStringModeling(CheckerManager &Mgr) {
2395
198
  Mgr.registerChecker<CStringChecker>();
2396
198
}
2397
2398
47
bool ento::shouldRegisterCStringModeling(const LangOptions &LO) {
2399
47
  return true;
2400
47
}
2401
2402
#define REGISTER_CHECKER(name)                                                 \
2403
110
  void ento::register##name(CheckerManager &mgr) {                             \
2404
110
    CStringChecker *checker = mgr.getChecker<CStringChecker>();                \
2405
110
    checker->Filter.Check##name = true;                                        \
2406
110
    checker->Filter.CheckName##name = mgr.getCurrentCheckName();               \
2407
110
  }                                                                            \
clang::ento::registerCStringNullArg(clang::ento::CheckerManager&)
Line
Count
Source
2403
49
  void ento::register##name(CheckerManager &mgr) {                             \
2404
49
    CStringChecker *checker = mgr.getChecker<CStringChecker>();                \
2405
49
    checker->Filter.Check##name = true;                                        \
2406
49
    checker->Filter.CheckName##name = mgr.getCurrentCheckName();               \
2407
49
  }                                                                            \
clang::ento::registerCStringOutOfBounds(clang::ento::CheckerManager&)
Line
Count
Source
2403
19
  void ento::register##name(CheckerManager &mgr) {                             \
2404
19
    CStringChecker *checker = mgr.getChecker<CStringChecker>();                \
2405
19
    checker->Filter.Check##name = true;                                        \
2406
19
    checker->Filter.CheckName##name = mgr.getCurrentCheckName();               \
2407
19
  }                                                                            \
clang::ento::registerCStringBufferOverlap(clang::ento::CheckerManager&)
Line
Count
Source
2403
21
  void ento::register##name(CheckerManager &mgr) {                             \
2404
21
    CStringChecker *checker = mgr.getChecker<CStringChecker>();                \
2405
21
    checker->Filter.Check##name = true;                                        \
2406
21
    checker->Filter.CheckName##name = mgr.getCurrentCheckName();               \
2407
21
  }                                                                            \
clang::ento::registerCStringNotNullTerm(clang::ento::CheckerManager&)
Line
Count
Source
2403
21
  void ento::register##name(CheckerManager &mgr) {                             \
2404
21
    CStringChecker *checker = mgr.getChecker<CStringChecker>();                \
2405
21
    checker->Filter.Check##name = true;                                        \
2406
21
    checker->Filter.CheckName##name = mgr.getCurrentCheckName();               \
2407
21
  }                                                                            \
2408
                                                                               \
2409
110
  bool ento::shouldRegister##name(const LangOptions &LO) {                     \
2410
110
    return true;                                                               \
2411
110
  }
clang::ento::shouldRegisterCStringNullArg(clang::LangOptions const&)
Line
Count
Source
2409
49
  bool ento::shouldRegister##name(const LangOptions &LO) {                     \
2410
49
    return true;                                                               \
2411
49
  }
clang::ento::shouldRegisterCStringOutOfBounds(clang::LangOptions const&)
Line
Count
Source
2409
19
  bool ento::shouldRegister##name(const LangOptions &LO) {                     \
2410
19
    return true;                                                               \
2411
19
  }
clang::ento::shouldRegisterCStringBufferOverlap(clang::LangOptions const&)
Line
Count
Source
2409
21
  bool ento::shouldRegister##name(const LangOptions &LO) {                     \
2410
21
    return true;                                                               \
2411
21
  }
clang::ento::shouldRegisterCStringNotNullTerm(clang::LangOptions const&)
Line
Count
Source
2409
21
  bool ento::shouldRegister##name(const LangOptions &LO) {                     \
2410
21
    return true;                                                               \
2411
21
  }
2412
2413
  REGISTER_CHECKER(CStringNullArg)
2414
  REGISTER_CHECKER(CStringOutOfBounds)
2415
  REGISTER_CHECKER(CStringBufferOverlap)
2416
REGISTER_CHECKER(CStringNotNullTerm)