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

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