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