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