contrib/llvm/tools/clang/lib/StaticAnalyzer/Checkers/CStringChecker.cpp

   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
  28 using namespace clang;
  29 using namespace ento;
  30
  31 namespace {
  32 class 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
  46 public:
  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
 197 REGISTER_MAP_WITH_PROGRAMSTATE(CStringLength, const MemRegion *, SVal)
 198
 199 //===----------------------------------------------------------------------===//
 200 // Individual checks and utility methods.
 201 //===----------------------------------------------------------------------===//
 202
 203 std::pair<ProgramStateRef , ProgramStateRef >
 204 CStringChecker::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
 215 ProgramStateRef 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?
 258 ProgramStateRef 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
 331 ProgramStateRef 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
 408 ProgramStateRef 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
 521 void 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
 540 ProgramStateRef 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
 613 ProgramStateRef 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
 653 SVal 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
 678 SVal 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
 778 const 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
 798 ProgramStateRef 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
 830 bool 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
 871 void 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
 970 void 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
 982 void 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
 994 void 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
1006 void 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
1015 void 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
1090 void 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
1099 void 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
1108 void 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
1225 void 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
1236 void 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
1247 void 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
1258 void 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
1269 void 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
1280 void 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
1600 void 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
1608 void 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
1616 void 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
1625 void 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
1634 void 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
1757 void 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
1818 bool 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
1886 void 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
1922 bool CStringChecker::wantsRegionChangeUpdate(ProgramStateRef state) const {
1923   CStringLengthTy Entries = state->get<CStringLength>();
1924   return !Entries.isEmpty();
1925 }
1926
1927 ProgramStateRef
1928 CStringChecker::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
1980 void 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
1995 void 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) \
2020 void ento::register##name(CheckerManager &mgr) {\
2021   static CStringChecker *TheChecker = 0; \
2022   if (TheChecker == 0) \
2023     TheChecker = mgr.registerChecker<CStringChecker>(); \
2024   TheChecker->Filter.Check##name = true; \
2025 }
2026
2027 REGISTER_CHECKER(CStringNullArg)
2028 REGISTER_CHECKER(CStringOutOfBounds)
2029 REGISTER_CHECKER(CStringBufferOverlap)
2030 REGISTER_CHECKER(CStringNotNullTerm)
2031
2032 void ento::registerCStringCheckerBasic(CheckerManager &Mgr) {
2033   registerCStringNullArg(Mgr);
2034 }