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