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