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 CallEvent *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     bugreporter::addTrackNullOrUndefValueVisitor(N, S, report);
 256     C.EmitReport(report);
 257     return NULL;
 258   }
 259
 260   // From here on, assume that the value is non-null.
 261   assert(stateNonNull);
 262   return stateNonNull;
 263 }
 264
 265 // FIXME: This was originally copied from ArrayBoundChecker.cpp. Refactor?
 266 ProgramStateRef CStringChecker::CheckLocation(CheckerContext &C,
 267                                              ProgramStateRef state,
 268                                              const Expr *S, SVal l,
 269                                              const char *warningMsg) const {
 270   // If a previous check has failed, propagate the failure.
 271   if (!state)
 272     return NULL;
 273
 274   // Check for out of bound array element access.
 275   const MemRegion *R = l.getAsRegion();
 276   if (!R)
 277     return state;
 278
 279   const ElementRegion *ER = dyn_cast<ElementRegion>(R);
 280   if (!ER)
 281     return state;
 282
 283   assert(ER->getValueType() == C.getASTContext().CharTy &&
 284     "CheckLocation should only be called with char* ElementRegions");
 285
 286   // Get the size of the array.
 287   const SubRegion *superReg = cast<SubRegion>(ER->getSuperRegion());
 288   SValBuilder &svalBuilder = C.getSValBuilder();
 289   SVal Extent =
 290     svalBuilder.convertToArrayIndex(superReg->getExtent(svalBuilder));
 291   DefinedOrUnknownSVal Size = cast<DefinedOrUnknownSVal>(Extent);
 292
 293   // Get the index of the accessed element.
 294   DefinedOrUnknownSVal Idx = cast<DefinedOrUnknownSVal>(ER->getIndex());
 295
 296   ProgramStateRef StInBound = state->assumeInBound(Idx, Size, true);
 297   ProgramStateRef StOutBound = state->assumeInBound(Idx, Size, false);
 298   if (StOutBound && !StInBound) {
 299     ExplodedNode *N = C.generateSink(StOutBound);
 300     if (!N)
 301       return NULL;
 302
 303     if (!BT_Bounds) {
 304       BT_Bounds.reset(new BuiltinBug("Out-of-bound array access",
 305         "Byte string function accesses out-of-bound array element"));
 306     }
 307     BuiltinBug *BT = static_cast<BuiltinBug*>(BT_Bounds.get());
 308
 309     // Generate a report for this bug.
 310     BugReport *report;
 311     if (warningMsg) {
 312       report = new BugReport(*BT, warningMsg, N);
 313     } else {
 314       assert(CurrentFunctionDescription);
 315       assert(CurrentFunctionDescription[0] != '\0');
 316
 317       SmallString<80> buf;
 318       llvm::raw_svector_ostream os(buf);
 319       os << (char)toupper(CurrentFunctionDescription[0])
 320          << &CurrentFunctionDescription[1]
 321          << " accesses out-of-bound array element";
 322       report = new BugReport(*BT, os.str(), N);
 323     }
 324
 325     // FIXME: It would be nice to eventually make this diagnostic more clear,
 326     // e.g., by referencing the original declaration or by saying *why* this
 327     // reference is outside the range.
 328
 329     report->addRange(S->getSourceRange());
 330     C.EmitReport(report);
 331     return NULL;
 332   }
 333
 334   // Array bound check succeeded.  From this point forward the array bound
 335   // should always succeed.
 336   return StInBound;
 337 }
 338
 339 ProgramStateRef CStringChecker::CheckBufferAccess(CheckerContext &C,
 340                                                  ProgramStateRef state,
 341                                                  const Expr *Size,
 342                                                  const Expr *FirstBuf,
 343                                                  const Expr *SecondBuf,
 344                                                  const char *firstMessage,
 345                                                  const char *secondMessage,
 346                                                  bool WarnAboutSize) const {
 347   // If a previous check has failed, propagate the failure.
 348   if (!state)
 349     return NULL;
 350
 351   SValBuilder &svalBuilder = C.getSValBuilder();
 352   ASTContext &Ctx = svalBuilder.getContext();
 353   const LocationContext *LCtx = C.getLocationContext();
 354
 355   QualType sizeTy = Size->getType();
 356   QualType PtrTy = Ctx.getPointerType(Ctx.CharTy);
 357
 358   // Check that the first buffer is non-null.
 359   SVal BufVal = state->getSVal(FirstBuf, LCtx);
 360   state = checkNonNull(C, state, FirstBuf, BufVal);
 361   if (!state)
 362     return NULL;
 363
 364   // If out-of-bounds checking is turned off, skip the rest.
 365   if (!Filter.CheckCStringOutOfBounds)
 366     return state;
 367
 368   // Get the access length and make sure it is known.
 369   // FIXME: This assumes the caller has already checked that the access length
 370   // is positive. And that it's unsigned.
 371   SVal LengthVal = state->getSVal(Size, LCtx);
 372   NonLoc *Length = dyn_cast<NonLoc>(&LengthVal);
 373   if (!Length)
 374     return state;
 375
 376   // Compute the offset of the last element to be accessed: size-1.
 377   NonLoc One = cast<NonLoc>(svalBuilder.makeIntVal(1, sizeTy));
 378   NonLoc LastOffset = cast<NonLoc>(svalBuilder.evalBinOpNN(state, BO_Sub,
 379                                                     *Length, One, sizeTy));
 380
 381   // Check that the first buffer is sufficiently long.
 382   SVal BufStart = svalBuilder.evalCast(BufVal, PtrTy, FirstBuf->getType());
 383   if (Loc *BufLoc = dyn_cast<Loc>(&BufStart)) {
 384     const Expr *warningExpr = (WarnAboutSize ? Size : FirstBuf);
 385
 386     SVal BufEnd = svalBuilder.evalBinOpLN(state, BO_Add, *BufLoc,
 387                                           LastOffset, PtrTy);
 388     state = CheckLocation(C, state, warningExpr, BufEnd, firstMessage);
 389
 390     // If the buffer isn't large enough, abort.
 391     if (!state)
 392       return NULL;
 393   }
 394
 395   // If there's a second buffer, check it as well.
 396   if (SecondBuf) {
 397     BufVal = state->getSVal(SecondBuf, LCtx);
 398     state = checkNonNull(C, state, SecondBuf, BufVal);
 399     if (!state)
 400       return NULL;
 401
 402     BufStart = svalBuilder.evalCast(BufVal, PtrTy, SecondBuf->getType());
 403     if (Loc *BufLoc = dyn_cast<Loc>(&BufStart)) {
 404       const Expr *warningExpr = (WarnAboutSize ? Size : SecondBuf);
 405
 406       SVal BufEnd = svalBuilder.evalBinOpLN(state, BO_Add, *BufLoc,
 407                                             LastOffset, PtrTy);
 408       state = CheckLocation(C, state, warningExpr, BufEnd, secondMessage);
 409     }
 410   }
 411
 412   // Large enough or not, return this state!
 413   return state;
 414 }
 415
 416 ProgramStateRef CStringChecker::CheckOverlap(CheckerContext &C,
 417                                             ProgramStateRef state,
 418                                             const Expr *Size,
 419                                             const Expr *First,
 420                                             const Expr *Second) const {
 421   if (!Filter.CheckCStringBufferOverlap)
 422     return state;
 423
 424   // Do a simple check for overlap: if the two arguments are from the same
 425   // buffer, see if the end of the first is greater than the start of the second
 426   // or vice versa.
 427
 428   // If a previous check has failed, propagate the failure.
 429   if (!state)
 430     return NULL;
 431
 432   ProgramStateRef stateTrue, stateFalse;
 433
 434   // Get the buffer values and make sure they're known locations.
 435   const LocationContext *LCtx = C.getLocationContext();
 436   SVal firstVal = state->getSVal(First, LCtx);
 437   SVal secondVal = state->getSVal(Second, LCtx);
 438
 439   Loc *firstLoc = dyn_cast<Loc>(&firstVal);
 440   if (!firstLoc)
 441     return state;
 442
 443   Loc *secondLoc = dyn_cast<Loc>(&secondVal);
 444   if (!secondLoc)
 445     return state;
 446
 447   // Are the two values the same?
 448   SValBuilder &svalBuilder = C.getSValBuilder();
 449   llvm::tie(stateTrue, stateFalse) =
 450     state->assume(svalBuilder.evalEQ(state, *firstLoc, *secondLoc));
 451
 452   if (stateTrue && !stateFalse) {
 453     // If the values are known to be equal, that's automatically an overlap.
 454     emitOverlapBug(C, stateTrue, First, Second);
 455     return NULL;
 456   }
 457
 458   // assume the two expressions are not equal.
 459   assert(stateFalse);
 460   state = stateFalse;
 461
 462   // Which value comes first?
 463   QualType cmpTy = svalBuilder.getConditionType();
 464   SVal reverse = svalBuilder.evalBinOpLL(state, BO_GT,
 465                                          *firstLoc, *secondLoc, cmpTy);
 466   DefinedOrUnknownSVal *reverseTest = dyn_cast<DefinedOrUnknownSVal>(&reverse);
 467   if (!reverseTest)
 468     return state;
 469
 470   llvm::tie(stateTrue, stateFalse) = state->assume(*reverseTest);
 471   if (stateTrue) {
 472     if (stateFalse) {
 473       // If we don't know which one comes first, we can't perform this test.
 474       return state;
 475     } else {
 476       // Switch the values so that firstVal is before secondVal.
 477       Loc *tmpLoc = firstLoc;
 478       firstLoc = secondLoc;
 479       secondLoc = tmpLoc;
 480
 481       // Switch the Exprs as well, so that they still correspond.
 482       const Expr *tmpExpr = First;
 483       First = Second;
 484       Second = tmpExpr;
 485     }
 486   }
 487
 488   // Get the length, and make sure it too is known.
 489   SVal LengthVal = state->getSVal(Size, LCtx);
 490   NonLoc *Length = dyn_cast<NonLoc>(&LengthVal);
 491   if (!Length)
 492     return state;
 493
 494   // Convert the first buffer's start address to char*.
 495   // Bail out if the cast fails.
 496   ASTContext &Ctx = svalBuilder.getContext();
 497   QualType CharPtrTy = Ctx.getPointerType(Ctx.CharTy);
 498   SVal FirstStart = svalBuilder.evalCast(*firstLoc, CharPtrTy,
 499                                          First->getType());
 500   Loc *FirstStartLoc = dyn_cast<Loc>(&FirstStart);
 501   if (!FirstStartLoc)
 502     return state;
 503
 504   // Compute the end of the first buffer. Bail out if THAT fails.
 505   SVal FirstEnd = svalBuilder.evalBinOpLN(state, BO_Add,
 506                                  *FirstStartLoc, *Length, CharPtrTy);
 507   Loc *FirstEndLoc = dyn_cast<Loc>(&FirstEnd);
 508   if (!FirstEndLoc)
 509     return state;
 510
 511   // Is the end of the first buffer past the start of the second buffer?
 512   SVal Overlap = svalBuilder.evalBinOpLL(state, BO_GT,
 513                                 *FirstEndLoc, *secondLoc, cmpTy);
 514   DefinedOrUnknownSVal *OverlapTest = dyn_cast<DefinedOrUnknownSVal>(&Overlap);
 515   if (!OverlapTest)
 516     return state;
 517
 518   llvm::tie(stateTrue, stateFalse) = state->assume(*OverlapTest);
 519
 520   if (stateTrue && !stateFalse) {
 521     // Overlap!
 522     emitOverlapBug(C, stateTrue, First, Second);
 523     return NULL;
 524   }
 525
 526   // assume the two expressions don't overlap.
 527   assert(stateFalse);
 528   return stateFalse;
 529 }
 530
 531 void CStringChecker::emitOverlapBug(CheckerContext &C, ProgramStateRef state,
 532                                   const Stmt *First, const Stmt *Second) const {
 533   ExplodedNode *N = C.generateSink(state);
 534   if (!N)
 535     return;
 536
 537   if (!BT_Overlap)
 538     BT_Overlap.reset(new BugType("Unix API", "Improper arguments"));
 539
 540   // Generate a report for this bug.
 541   BugReport *report =
 542     new BugReport(*BT_Overlap,
 543       "Arguments must not be overlapping buffers", N);
 544   report->addRange(First->getSourceRange());
 545   report->addRange(Second->getSourceRange());
 546
 547   C.EmitReport(report);
 548 }
 549
 550 ProgramStateRef CStringChecker::checkAdditionOverflow(CheckerContext &C,
 551                                                      ProgramStateRef state,
 552                                                      NonLoc left,
 553                                                      NonLoc right) const {
 554   // If out-of-bounds checking is turned off, skip the rest.
 555   if (!Filter.CheckCStringOutOfBounds)
 556     return state;
 557
 558   // If a previous check has failed, propagate the failure.
 559   if (!state)
 560     return NULL;
 561
 562   SValBuilder &svalBuilder = C.getSValBuilder();
 563   BasicValueFactory &BVF = svalBuilder.getBasicValueFactory();
 564
 565   QualType sizeTy = svalBuilder.getContext().getSizeType();
 566   const llvm::APSInt &maxValInt = BVF.getMaxValue(sizeTy);
 567   NonLoc maxVal = svalBuilder.makeIntVal(maxValInt);
 568
 569   SVal maxMinusRight;
 570   if (isa<nonloc::ConcreteInt>(right)) {
 571     maxMinusRight = svalBuilder.evalBinOpNN(state, BO_Sub, maxVal, right,
 572                                                  sizeTy);
 573   } else {
 574     // Try switching the operands. (The order of these two assignments is
 575     // important!)
 576     maxMinusRight = svalBuilder.evalBinOpNN(state, BO_Sub, maxVal, left,
 577                                             sizeTy);
 578     left = right;
 579   }
 580
 581   if (NonLoc *maxMinusRightNL = dyn_cast<NonLoc>(&maxMinusRight)) {
 582     QualType cmpTy = svalBuilder.getConditionType();
 583     // If left > max - right, we have an overflow.
 584     SVal willOverflow = svalBuilder.evalBinOpNN(state, BO_GT, left,
 585                                                 *maxMinusRightNL, cmpTy);
 586
 587     ProgramStateRef stateOverflow, stateOkay;
 588     llvm::tie(stateOverflow, stateOkay) =
 589       state->assume(cast<DefinedOrUnknownSVal>(willOverflow));
 590
 591     if (stateOverflow && !stateOkay) {
 592       // We have an overflow. Emit a bug report.
 593       ExplodedNode *N = C.generateSink(stateOverflow);
 594       if (!N)
 595         return NULL;
 596
 597       if (!BT_AdditionOverflow)
 598         BT_AdditionOverflow.reset(new BuiltinBug("API",
 599           "Sum of expressions causes overflow"));
 600
 601       // This isn't a great error message, but this should never occur in real
 602       // code anyway -- you'd have to create a buffer longer than a size_t can
 603       // represent, which is sort of a contradiction.
 604       const char *warning =
 605         "This expression will create a string whose length is too big to "
 606         "be represented as a size_t";
 607
 608       // Generate a report for this bug.
 609       BugReport *report = new BugReport(*BT_AdditionOverflow, warning, N);
 610       C.EmitReport(report);
 611
 612       return NULL;
 613     }
 614
 615     // From now on, assume an overflow didn't occur.
 616     assert(stateOkay);
 617     state = stateOkay;
 618   }
 619
 620   return state;
 621 }
 622
 623 ProgramStateRef CStringChecker::setCStringLength(ProgramStateRef state,
 624                                                 const MemRegion *MR,
 625                                                 SVal strLength) {
 626   assert(!strLength.isUndef() && "Attempt to set an undefined string length");
 627
 628   MR = MR->StripCasts();
 629
 630   switch (MR->getKind()) {
 631   case MemRegion::StringRegionKind:
 632     // FIXME: This can happen if we strcpy() into a string region. This is
 633     // undefined [C99 6.4.5p6], but we should still warn about it.
 634     return state;
 635
 636   case MemRegion::SymbolicRegionKind:
 637   case MemRegion::AllocaRegionKind:
 638   case MemRegion::VarRegionKind:
 639   case MemRegion::FieldRegionKind:
 640   case MemRegion::ObjCIvarRegionKind:
 641     // These are the types we can currently track string lengths for.
 642     break;
 643
 644   case MemRegion::ElementRegionKind:
 645     // FIXME: Handle element regions by upper-bounding the parent region's
 646     // string length.
 647     return state;
 648
 649   default:
 650     // Other regions (mostly non-data) can't have a reliable C string length.
 651     // For now, just ignore the change.
 652     // FIXME: These are rare but not impossible. We should output some kind of
 653     // warning for things like strcpy((char[]){'a', 0}, "b");
 654     return state;
 655   }
 656
 657   if (strLength.isUnknown())
 658     return state->remove<CStringLength>(MR);
 659
 660   return state->set<CStringLength>(MR, strLength);
 661 }
 662
 663 SVal CStringChecker::getCStringLengthForRegion(CheckerContext &C,
 664                                                ProgramStateRef &state,
 665                                                const Expr *Ex,
 666                                                const MemRegion *MR,
 667                                                bool hypothetical) {
 668   if (!hypothetical) {
 669     // If there's a recorded length, go ahead and return it.
 670     const SVal *Recorded = state->get<CStringLength>(MR);
 671     if (Recorded)
 672       return *Recorded;
 673   }
 674
 675   // Otherwise, get a new symbol and update the state.
 676   unsigned Count = C.getCurrentBlockCount();
 677   SValBuilder &svalBuilder = C.getSValBuilder();
 678   QualType sizeTy = svalBuilder.getContext().getSizeType();
 679   SVal strLength = svalBuilder.getMetadataSymbolVal(CStringChecker::getTag(),
 680                                                     MR, Ex, sizeTy, Count);
 681
 682   if (!hypothetical)
 683     state = state->set<CStringLength>(MR, strLength);
 684
 685   return strLength;
 686 }
 687
 688 SVal CStringChecker::getCStringLength(CheckerContext &C, ProgramStateRef &state,
 689                                       const Expr *Ex, SVal Buf,
 690                                       bool hypothetical) const {
 691   const MemRegion *MR = Buf.getAsRegion();
 692   if (!MR) {
 693     // If we can't get a region, see if it's something we /know/ isn't a
 694     // C string. In the context of locations, the only time we can issue such
 695     // a warning is for labels.
 696     if (loc::GotoLabel *Label = dyn_cast<loc::GotoLabel>(&Buf)) {
 697       if (!Filter.CheckCStringNotNullTerm)
 698         return UndefinedVal();
 699
 700       if (ExplodedNode *N = C.addTransition(state)) {
 701         if (!BT_NotCString)
 702           BT_NotCString.reset(new BuiltinBug("Unix API",
 703             "Argument is not a null-terminated string."));
 704
 705         SmallString<120> buf;
 706         llvm::raw_svector_ostream os(buf);
 707         assert(CurrentFunctionDescription);
 708         os << "Argument to " << CurrentFunctionDescription
 709            << " is the address of the label '" << Label->getLabel()->getName()
 710            << "', which is not a null-terminated string";
 711
 712         // Generate a report for this bug.
 713         BugReport *report = new BugReport(*BT_NotCString,
 714                                                           os.str(), N);
 715
 716         report->addRange(Ex->getSourceRange());
 717         C.EmitReport(report);
 718       }
 719       return UndefinedVal();
 720
 721     }
 722
 723     // If it's not a region and not a label, give up.
 724     return UnknownVal();
 725   }
 726
 727   // If we have a region, strip casts from it and see if we can figure out
 728   // its length. For anything we can't figure out, just return UnknownVal.
 729   MR = MR->StripCasts();
 730
 731   switch (MR->getKind()) {
 732   case MemRegion::StringRegionKind: {
 733     // Modifying the contents of string regions is undefined [C99 6.4.5p6],
 734     // so we can assume that the byte length is the correct C string length.
 735     SValBuilder &svalBuilder = C.getSValBuilder();
 736     QualType sizeTy = svalBuilder.getContext().getSizeType();
 737     const StringLiteral *strLit = cast<StringRegion>(MR)->getStringLiteral();
 738     return svalBuilder.makeIntVal(strLit->getByteLength(), sizeTy);
 739   }
 740   case MemRegion::SymbolicRegionKind:
 741   case MemRegion::AllocaRegionKind:
 742   case MemRegion::VarRegionKind:
 743   case MemRegion::FieldRegionKind:
 744   case MemRegion::ObjCIvarRegionKind:
 745     return getCStringLengthForRegion(C, state, Ex, MR, hypothetical);
 746   case MemRegion::CompoundLiteralRegionKind:
 747     // FIXME: Can we track this? Is it necessary?
 748     return UnknownVal();
 749   case MemRegion::ElementRegionKind:
 750     // FIXME: How can we handle this? It's not good enough to subtract the
 751     // offset from the base string length; consider "123\x00567" and &a[5].
 752     return UnknownVal();
 753   default:
 754     // Other regions (mostly non-data) can't have a reliable C string length.
 755     // In this case, an error is emitted and UndefinedVal is returned.
 756     // The caller should always be prepared to handle this case.
 757     if (!Filter.CheckCStringNotNullTerm)
 758       return UndefinedVal();
 759
 760     if (ExplodedNode *N = C.addTransition(state)) {
 761       if (!BT_NotCString)
 762         BT_NotCString.reset(new BuiltinBug("Unix API",
 763           "Argument is not a null-terminated string."));
 764
 765       SmallString<120> buf;
 766       llvm::raw_svector_ostream os(buf);
 767
 768       assert(CurrentFunctionDescription);
 769       os << "Argument to " << CurrentFunctionDescription << " is ";
 770
 771       if (SummarizeRegion(os, C.getASTContext(), MR))
 772         os << ", which is not a null-terminated string";
 773       else
 774         os << "not a null-terminated string";
 775
 776       // Generate a report for this bug.
 777       BugReport *report = new BugReport(*BT_NotCString,
 778                                                         os.str(), N);
 779
 780       report->addRange(Ex->getSourceRange());
 781       C.EmitReport(report);
 782     }
 783
 784     return UndefinedVal();
 785   }
 786 }
 787
 788 const StringLiteral *CStringChecker::getCStringLiteral(CheckerContext &C,
 789   ProgramStateRef &state, const Expr *expr, SVal val) const {
 790
 791   // Get the memory region pointed to by the val.
 792   const MemRegion *bufRegion = val.getAsRegion();
 793   if (!bufRegion)
 794     return NULL;
 795
 796   // Strip casts off the memory region.
 797   bufRegion = bufRegion->StripCasts();
 798
 799   // Cast the memory region to a string region.
 800   const StringRegion *strRegion= dyn_cast<StringRegion>(bufRegion);
 801   if (!strRegion)
 802     return NULL;
 803
 804   // Return the actual string in the string region.
 805   return strRegion->getStringLiteral();
 806 }
 807
 808 ProgramStateRef CStringChecker::InvalidateBuffer(CheckerContext &C,
 809                                                 ProgramStateRef state,
 810                                                 const Expr *E, SVal V) {
 811   Loc *L = dyn_cast<Loc>(&V);
 812   if (!L)
 813     return state;
 814
 815   // FIXME: This is a simplified version of what's in CFRefCount.cpp -- it makes
 816   // some assumptions about the value that CFRefCount can't. Even so, it should
 817   // probably be refactored.
 818   if (loc::MemRegionVal* MR = dyn_cast<loc::MemRegionVal>(L)) {
 819     const MemRegion *R = MR->getRegion()->StripCasts();
 820
 821     // Are we dealing with an ElementRegion?  If so, we should be invalidating
 822     // the super-region.
 823     if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
 824       R = ER->getSuperRegion();
 825       // FIXME: What about layers of ElementRegions?
 826     }
 827
 828     // Invalidate this region.
 829     unsigned Count = C.getCurrentBlockCount();
 830     const LocationContext *LCtx = C.getPredecessor()->getLocationContext();
 831     return state->invalidateRegions(R, E, Count, LCtx);
 832   }
 833
 834   // If we have a non-region value by chance, just remove the binding.
 835   // FIXME: is this necessary or correct? This handles the non-Region
 836   //  cases.  Is it ever valid to store to these?
 837   return state->unbindLoc(*L);
 838 }
 839
 840 bool CStringChecker::SummarizeRegion(raw_ostream &os, ASTContext &Ctx,
 841                                      const MemRegion *MR) {
 842   const TypedValueRegion *TVR = dyn_cast<TypedValueRegion>(MR);
 843
 844   switch (MR->getKind()) {
 845   case MemRegion::FunctionTextRegionKind: {
 846     const FunctionDecl *FD = cast<FunctionTextRegion>(MR)->getDecl();
 847     if (FD)
 848       os << "the address of the function '" << *FD << '\'';
 849     else
 850       os << "the address of a function";
 851     return true;
 852   }
 853   case MemRegion::BlockTextRegionKind:
 854     os << "block text";
 855     return true;
 856   case MemRegion::BlockDataRegionKind:
 857     os << "a block";
 858     return true;
 859   case MemRegion::CXXThisRegionKind:
 860   case MemRegion::CXXTempObjectRegionKind:
 861     os << "a C++ temp object of type " << TVR->getValueType().getAsString();
 862     return true;
 863   case MemRegion::VarRegionKind:
 864     os << "a variable of type" << TVR->getValueType().getAsString();
 865     return true;
 866   case MemRegion::FieldRegionKind:
 867     os << "a field of type " << TVR->getValueType().getAsString();
 868     return true;
 869   case MemRegion::ObjCIvarRegionKind:
 870     os << "an instance variable of type " << TVR->getValueType().getAsString();
 871     return true;
 872   default:
 873     return false;
 874   }
 875 }
 876
 877 //===----------------------------------------------------------------------===//
 878 // evaluation of individual function calls.
 879 //===----------------------------------------------------------------------===//
 880
 881 void CStringChecker::evalCopyCommon(CheckerContext &C,
 882                                     const CallExpr *CE,
 883                                     ProgramStateRef state,
 884                                     const Expr *Size, const Expr *Dest,
 885                                     const Expr *Source, bool Restricted,
 886                                     bool IsMempcpy) const {
 887   CurrentFunctionDescription = "memory copy function";
 888
 889   // See if the size argument is zero.
 890   const LocationContext *LCtx = C.getLocationContext();
 891   SVal sizeVal = state->getSVal(Size, LCtx);
 892   QualType sizeTy = Size->getType();
 893
 894   ProgramStateRef stateZeroSize, stateNonZeroSize;
 895   llvm::tie(stateZeroSize, stateNonZeroSize) =
 896     assumeZero(C, state, sizeVal, sizeTy);
 897
 898   // Get the value of the Dest.
 899   SVal destVal = state->getSVal(Dest, LCtx);
 900
 901   // If the size is zero, there won't be any actual memory access, so
 902   // just bind the return value to the destination buffer and return.
 903   if (stateZeroSize && !stateNonZeroSize) {
 904     stateZeroSize = stateZeroSize->BindExpr(CE, LCtx, destVal);
 905     C.addTransition(stateZeroSize);
 906     return;
 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
1407         // We need a special case for when the copy size is zero, in which
1408         // case strncpy will do no work at all. Our bounds check uses n-1
1409         // as the last element accessed, so n == 0 is problematic.
1410         ProgramStateRef StateZeroSize, StateNonZeroSize;
1411         llvm::tie(StateZeroSize, StateNonZeroSize) =
1412           assumeZero(C, state, *lenValNL, sizeTy);
1413
1414         // If the size is known to be zero, we're done.
1415         if (StateZeroSize && !StateNonZeroSize) {
1416           StateZeroSize = StateZeroSize->BindExpr(CE, LCtx, DstVal);
1417           C.addTransition(StateZeroSize);
1418           return;
1419         }
1420
1421         // Otherwise, go ahead and figure out the last element we'll touch.
1422         // We don't record the non-zero assumption here because we can't
1423         // be sure. We won't warn on a possible zero.
1424         NonLoc one = cast<NonLoc>(svalBuilder.makeIntVal(1, sizeTy));
1425         maxLastElementIndex = svalBuilder.evalBinOpNN(state, BO_Sub, *lenValNL,
1426                                                       one, sizeTy);
1427         boundWarning = "Size argument is greater than the length of the "
1428                        "destination buffer";
1429       }
1430     }
1431
1432     // If we couldn't pin down the copy length, at least bound it.
1433     // FIXME: We should actually run this code path for append as well, but
1434     // right now it creates problems with constraints (since we can end up
1435     // trying to pass constraints from symbol to symbol).
1436     if (amountCopied.isUnknown() && !isAppending) {
1437       // Try to get a "hypothetical" string length symbol, which we can later
1438       // set as a real value if that turns out to be the case.
1439       amountCopied = getCStringLength(C, state, lenExpr, srcVal, true);
1440       assert(!amountCopied.isUndef());
1441
1442       if (NonLoc *amountCopiedNL = dyn_cast<NonLoc>(&amountCopied)) {
1443         if (lenValNL) {
1444           // amountCopied <= lenVal
1445           SVal copiedLessThanBound = svalBuilder.evalBinOpNN(state, BO_LE,
1446                                                              *amountCopiedNL,
1447                                                              *lenValNL,
1448                                                              cmpTy);
1449           state = state->assume(cast<DefinedOrUnknownSVal>(copiedLessThanBound),
1450                                 true);
1451           if (!state)
1452             return;
1453         }
1454
1455         if (strLengthNL) {
1456           // amountCopied <= strlen(source)
1457           SVal copiedLessThanSrc = svalBuilder.evalBinOpNN(state, BO_LE,
1458                                                            *amountCopiedNL,
1459                                                            *strLengthNL,
1460                                                            cmpTy);
1461           state = state->assume(cast<DefinedOrUnknownSVal>(copiedLessThanSrc),
1462                                 true);
1463           if (!state)
1464             return;
1465         }
1466       }
1467     }
1468
1469   } else {
1470     // The function isn't bounded. The amount copied should match the length
1471     // of the source buffer.
1472     amountCopied = strLength;
1473   }
1474
1475   assert(state);
1476
1477   // This represents the number of characters copied into the destination
1478   // buffer. (It may not actually be the strlen if the destination buffer
1479   // is not terminated.)
1480   SVal finalStrLength = UnknownVal();
1481
1482   // If this is an appending function (strcat, strncat...) then set the
1483   // string length to strlen(src) + strlen(dst) since the buffer will
1484   // ultimately contain both.
1485   if (isAppending) {
1486     // Get the string length of the destination. If the destination is memory
1487     // that can't have a string length, we shouldn't be copying into it anyway.
1488     SVal dstStrLength = getCStringLength(C, state, Dst, DstVal);
1489     if (dstStrLength.isUndef())
1490       return;
1491
1492     NonLoc *srcStrLengthNL = dyn_cast<NonLoc>(&amountCopied);
1493     NonLoc *dstStrLengthNL = dyn_cast<NonLoc>(&dstStrLength);
1494
1495     // If we know both string lengths, we might know the final string length.
1496     if (srcStrLengthNL && dstStrLengthNL) {
1497       // Make sure the two lengths together don't overflow a size_t.
1498       state = checkAdditionOverflow(C, state, *srcStrLengthNL, *dstStrLengthNL);
1499       if (!state)
1500         return;
1501
1502       finalStrLength = svalBuilder.evalBinOpNN(state, BO_Add, *srcStrLengthNL,
1503                                                *dstStrLengthNL, sizeTy);
1504     }
1505
1506     // If we couldn't get a single value for the final string length,
1507     // we can at least bound it by the individual lengths.
1508     if (finalStrLength.isUnknown()) {
1509       // Try to get a "hypothetical" string length symbol, which we can later
1510       // set as a real value if that turns out to be the case.
1511       finalStrLength = getCStringLength(C, state, CE, DstVal, true);
1512       assert(!finalStrLength.isUndef());
1513
1514       if (NonLoc *finalStrLengthNL = dyn_cast<NonLoc>(&finalStrLength)) {
1515         if (srcStrLengthNL) {
1516           // finalStrLength >= srcStrLength
1517           SVal sourceInResult = svalBuilder.evalBinOpNN(state, BO_GE,
1518                                                         *finalStrLengthNL,
1519                                                         *srcStrLengthNL,
1520                                                         cmpTy);
1521           state = state->assume(cast<DefinedOrUnknownSVal>(sourceInResult),
1522                                 true);
1523           if (!state)
1524             return;
1525         }
1526
1527         if (dstStrLengthNL) {
1528           // finalStrLength >= dstStrLength
1529           SVal destInResult = svalBuilder.evalBinOpNN(state, BO_GE,
1530                                                       *finalStrLengthNL,
1531                                                       *dstStrLengthNL,
1532                                                       cmpTy);
1533           state = state->assume(cast<DefinedOrUnknownSVal>(destInResult),
1534                                 true);
1535           if (!state)
1536             return;
1537         }
1538       }
1539     }
1540
1541   } else {
1542     // Otherwise, this is a copy-over function (strcpy, strncpy, ...), and
1543     // the final string length will match the input string length.
1544     finalStrLength = amountCopied;
1545   }
1546
1547   // The final result of the function will either be a pointer past the last
1548   // copied element, or a pointer to the start of the destination buffer.
1549   SVal Result = (returnEnd ? UnknownVal() : DstVal);
1550
1551   assert(state);
1552
1553   // If the destination is a MemRegion, try to check for a buffer overflow and
1554   // record the new string length.
1555   if (loc::MemRegionVal *dstRegVal = dyn_cast<loc::MemRegionVal>(&DstVal)) {
1556     QualType ptrTy = Dst->getType();
1557
1558     // If we have an exact value on a bounded copy, use that to check for
1559     // overflows, rather than our estimate about how much is actually copied.
1560     if (boundWarning) {
1561       if (NonLoc *maxLastNL = dyn_cast<NonLoc>(&maxLastElementIndex)) {
1562         SVal maxLastElement = svalBuilder.evalBinOpLN(state, BO_Add, *dstRegVal,
1563                                                       *maxLastNL, ptrTy);
1564         state = CheckLocation(C, state, CE->getArg(2), maxLastElement,
1565                               boundWarning);
1566         if (!state)
1567           return;
1568       }
1569     }
1570
1571     // Then, if the final length is known...
1572     if (NonLoc *knownStrLength = dyn_cast<NonLoc>(&finalStrLength)) {
1573       SVal lastElement = svalBuilder.evalBinOpLN(state, BO_Add, *dstRegVal,
1574                                                  *knownStrLength, ptrTy);
1575
1576       // ...and we haven't checked the bound, we'll check the actual copy.
1577       if (!boundWarning) {
1578         const char * const warningMsg =
1579           "String copy function overflows destination buffer";
1580         state = CheckLocation(C, state, Dst, lastElement, warningMsg);
1581         if (!state)
1582           return;
1583       }
1584
1585       // If this is a stpcpy-style copy, the last element is the return value.
1586       if (returnEnd)
1587         Result = lastElement;
1588     }
1589
1590     // Invalidate the destination. This must happen before we set the C string
1591     // length because invalidation will clear the length.
1592     // FIXME: Even if we can't perfectly model the copy, we should see if we
1593     // can use LazyCompoundVals to copy the source values into the destination.
1594     // This would probably remove any existing bindings past the end of the
1595     // string, but that's still an improvement over blank invalidation.
1596     state = InvalidateBuffer(C, state, Dst, *dstRegVal);
1597
1598     // Set the C string length of the destination, if we know it.
1599     if (isBounded && !isAppending) {
1600       // strncpy is annoying in that it doesn't guarantee to null-terminate
1601       // the result string. If the original string didn't fit entirely inside
1602       // the bound (including the null-terminator), we don't know how long the
1603       // result is.
1604       if (amountCopied != strLength)
1605         finalStrLength = UnknownVal();
1606     }
1607     state = setCStringLength(state, dstRegVal->getRegion(), finalStrLength);
1608   }
1609
1610   assert(state);
1611
1612   // If this is a stpcpy-style copy, but we were unable to check for a buffer
1613   // overflow, we still need a result. Conjure a return value.
1614   if (returnEnd && Result.isUnknown()) {
1615     unsigned Count = C.getCurrentBlockCount();
1616     Result = svalBuilder.getConjuredSymbolVal(NULL, CE, LCtx, Count);
1617   }
1618
1619   // Set the return value.
1620   state = state->BindExpr(CE, LCtx, Result);
1621   C.addTransition(state);
1622 }
1623
1624 void CStringChecker::evalStrcmp(CheckerContext &C, const CallExpr *CE) const {
1625   if (CE->getNumArgs() < 2)
1626     return;
1627
1628   //int strcmp(const char *s1, const char *s2);
1629   evalStrcmpCommon(C, CE, /* isBounded = */ false, /* ignoreCase = */ false);
1630 }
1631
1632 void CStringChecker::evalStrncmp(CheckerContext &C, const CallExpr *CE) const {
1633   if (CE->getNumArgs() < 3)
1634     return;
1635
1636   //int strncmp(const char *s1, const char *s2, size_t n);
1637   evalStrcmpCommon(C, CE, /* isBounded = */ true, /* ignoreCase = */ false);
1638 }
1639
1640 void CStringChecker::evalStrcasecmp(CheckerContext &C,
1641                                     const CallExpr *CE) const {
1642   if (CE->getNumArgs() < 2)
1643     return;
1644
1645   //int strcasecmp(const char *s1, const char *s2);
1646   evalStrcmpCommon(C, CE, /* isBounded = */ false, /* ignoreCase = */ true);
1647 }
1648
1649 void CStringChecker::evalStrncasecmp(CheckerContext &C,
1650                                      const CallExpr *CE) const {
1651   if (CE->getNumArgs() < 3)
1652     return;
1653
1654   //int strncasecmp(const char *s1, const char *s2, size_t n);
1655   evalStrcmpCommon(C, CE, /* isBounded = */ true, /* ignoreCase = */ true);
1656 }
1657
1658 void CStringChecker::evalStrcmpCommon(CheckerContext &C, const CallExpr *CE,
1659                                       bool isBounded, bool ignoreCase) const {
1660   CurrentFunctionDescription = "string comparison function";
1661   ProgramStateRef state = C.getState();
1662   const LocationContext *LCtx = C.getLocationContext();
1663
1664   // Check that the first string is non-null
1665   const Expr *s1 = CE->getArg(0);
1666   SVal s1Val = state->getSVal(s1, LCtx);
1667   state = checkNonNull(C, state, s1, s1Val);
1668   if (!state)
1669     return;
1670
1671   // Check that the second string is non-null.
1672   const Expr *s2 = CE->getArg(1);
1673   SVal s2Val = state->getSVal(s2, LCtx);
1674   state = checkNonNull(C, state, s2, s2Val);
1675   if (!state)
1676     return;
1677
1678   // Get the string length of the first string or give up.
1679   SVal s1Length = getCStringLength(C, state, s1, s1Val);
1680   if (s1Length.isUndef())
1681     return;
1682
1683   // Get the string length of the second string or give up.
1684   SVal s2Length = getCStringLength(C, state, s2, s2Val);
1685   if (s2Length.isUndef())
1686     return;
1687
1688   // If we know the two buffers are the same, we know the result is 0.
1689   // First, get the two buffers' addresses. Another checker will have already
1690   // made sure they're not undefined.
1691   DefinedOrUnknownSVal LV = cast<DefinedOrUnknownSVal>(s1Val);
1692   DefinedOrUnknownSVal RV = cast<DefinedOrUnknownSVal>(s2Val);
1693
1694   // See if they are the same.
1695   SValBuilder &svalBuilder = C.getSValBuilder();
1696   DefinedOrUnknownSVal SameBuf = svalBuilder.evalEQ(state, LV, RV);
1697   ProgramStateRef StSameBuf, StNotSameBuf;
1698   llvm::tie(StSameBuf, StNotSameBuf) = state->assume(SameBuf);
1699
1700   // If the two arguments might be the same buffer, we know the result is 0,
1701   // and we only need to check one size.
1702   if (StSameBuf) {
1703     StSameBuf = StSameBuf->BindExpr(CE, LCtx,
1704                                     svalBuilder.makeZeroVal(CE->getType()));
1705     C.addTransition(StSameBuf);
1706
1707     // If the two arguments are GUARANTEED to be the same, we're done!
1708     if (!StNotSameBuf)
1709       return;
1710   }
1711
1712   assert(StNotSameBuf);
1713   state = StNotSameBuf;
1714
1715   // At this point we can go about comparing the two buffers.
1716   // For now, we only do this if they're both known string literals.
1717
1718   // Attempt to extract string literals from both expressions.
1719   const StringLiteral *s1StrLiteral = getCStringLiteral(C, state, s1, s1Val);
1720   const StringLiteral *s2StrLiteral = getCStringLiteral(C, state, s2, s2Val);
1721   bool canComputeResult = false;
1722
1723   if (s1StrLiteral && s2StrLiteral) {
1724     StringRef s1StrRef = s1StrLiteral->getString();
1725     StringRef s2StrRef = s2StrLiteral->getString();
1726
1727     if (isBounded) {
1728       // Get the max number of characters to compare.
1729       const Expr *lenExpr = CE->getArg(2);
1730       SVal lenVal = state->getSVal(lenExpr, LCtx);
1731
1732       // If the length is known, we can get the right substrings.
1733       if (const llvm::APSInt *len = svalBuilder.getKnownValue(state, lenVal)) {
1734         // Create substrings of each to compare the prefix.
1735         s1StrRef = s1StrRef.substr(0, (size_t)len->getZExtValue());
1736         s2StrRef = s2StrRef.substr(0, (size_t)len->getZExtValue());
1737         canComputeResult = true;
1738       }
1739     } else {
1740       // This is a normal, unbounded strcmp.
1741       canComputeResult = true;
1742     }
1743
1744     if (canComputeResult) {
1745       // Real strcmp stops at null characters.
1746       size_t s1Term = s1StrRef.find('\0');
1747       if (s1Term != StringRef::npos)
1748         s1StrRef = s1StrRef.substr(0, s1Term);
1749
1750       size_t s2Term = s2StrRef.find('\0');
1751       if (s2Term != StringRef::npos)
1752         s2StrRef = s2StrRef.substr(0, s2Term);
1753
1754       // Use StringRef's comparison methods to compute the actual result.
1755       int result;
1756
1757       if (ignoreCase) {
1758         // Compare string 1 to string 2 the same way strcasecmp() does.
1759         result = s1StrRef.compare_lower(s2StrRef);
1760       } else {
1761         // Compare string 1 to string 2 the same way strcmp() does.
1762         result = s1StrRef.compare(s2StrRef);
1763       }
1764
1765       // Build the SVal of the comparison and bind the return value.
1766       SVal resultVal = svalBuilder.makeIntVal(result, CE->getType());
1767       state = state->BindExpr(CE, LCtx, resultVal);
1768     }
1769   }
1770
1771   if (!canComputeResult) {
1772     // Conjure a symbolic value. It's the best we can do.
1773     unsigned Count = C.getCurrentBlockCount();
1774     SVal resultVal = svalBuilder.getConjuredSymbolVal(NULL, CE, LCtx, Count);
1775     state = state->BindExpr(CE, LCtx, resultVal);
1776   }
1777
1778   // Record this as a possible path.
1779   C.addTransition(state);
1780 }
1781
1782 //===----------------------------------------------------------------------===//
1783 // The driver method, and other Checker callbacks.
1784 //===----------------------------------------------------------------------===//
1785
1786 bool CStringChecker::evalCall(const CallExpr *CE, CheckerContext &C) const {
1787   const FunctionDecl *FDecl = C.getCalleeDecl(CE);
1788
1789   if (!FDecl)
1790     return false;
1791
1792   FnCheck evalFunction = 0;
1793   if (C.isCLibraryFunction(FDecl, "memcpy"))
1794     evalFunction =  &CStringChecker::evalMemcpy;
1795   else if (C.isCLibraryFunction(FDecl, "mempcpy"))
1796     evalFunction =  &CStringChecker::evalMempcpy;
1797   else if (C.isCLibraryFunction(FDecl, "memcmp"))
1798     evalFunction =  &CStringChecker::evalMemcmp;
1799   else if (C.isCLibraryFunction(FDecl, "memmove"))
1800     evalFunction =  &CStringChecker::evalMemmove;
1801   else if (C.isCLibraryFunction(FDecl, "strcpy"))
1802     evalFunction =  &CStringChecker::evalStrcpy;
1803   else if (C.isCLibraryFunction(FDecl, "strncpy"))
1804     evalFunction =  &CStringChecker::evalStrncpy;
1805   else if (C.isCLibraryFunction(FDecl, "stpcpy"))
1806     evalFunction =  &CStringChecker::evalStpcpy;
1807   else if (C.isCLibraryFunction(FDecl, "strcat"))
1808     evalFunction =  &CStringChecker::evalStrcat;
1809   else if (C.isCLibraryFunction(FDecl, "strncat"))
1810     evalFunction =  &CStringChecker::evalStrncat;
1811   else if (C.isCLibraryFunction(FDecl, "strlen"))
1812     evalFunction =  &CStringChecker::evalstrLength;
1813   else if (C.isCLibraryFunction(FDecl, "strnlen"))
1814     evalFunction =  &CStringChecker::evalstrnLength;
1815   else if (C.isCLibraryFunction(FDecl, "strcmp"))
1816     evalFunction =  &CStringChecker::evalStrcmp;
1817   else if (C.isCLibraryFunction(FDecl, "strncmp"))
1818     evalFunction =  &CStringChecker::evalStrncmp;
1819   else if (C.isCLibraryFunction(FDecl, "strcasecmp"))
1820     evalFunction =  &CStringChecker::evalStrcasecmp;
1821   else if (C.isCLibraryFunction(FDecl, "strncasecmp"))
1822     evalFunction =  &CStringChecker::evalStrncasecmp;
1823   else if (C.isCLibraryFunction(FDecl, "bcopy"))
1824     evalFunction =  &CStringChecker::evalBcopy;
1825   else if (C.isCLibraryFunction(FDecl, "bcmp"))
1826     evalFunction =  &CStringChecker::evalMemcmp;
1827
1828   // If the callee isn't a string function, let another checker handle it.
1829   if (!evalFunction)
1830     return false;
1831
1832   // Make sure each function sets its own description.
1833   // (But don't bother in a release build.)
1834   assert(!(CurrentFunctionDescription = NULL));
1835
1836   // Check and evaluate the call.
1837   (this->*evalFunction)(C, CE);
1838
1839   // If the evaluate call resulted in no change, chain to the next eval call
1840   // handler.
1841   // Note, the custom CString evaluation calls assume that basic safety
1842   // properties are held. However, if the user chooses to turn off some of these
1843   // checks, we ignore the issues and leave the call evaluation to a generic
1844   // handler.
1845   if (!C.isDifferent())
1846     return false;
1847
1848   return true;
1849 }
1850
1851 void CStringChecker::checkPreStmt(const DeclStmt *DS, CheckerContext &C) const {
1852   // Record string length for char a[] = "abc";
1853   ProgramStateRef state = C.getState();
1854
1855   for (DeclStmt::const_decl_iterator I = DS->decl_begin(), E = DS->decl_end();
1856        I != E; ++I) {
1857     const VarDecl *D = dyn_cast<VarDecl>(*I);
1858     if (!D)
1859       continue;
1860
1861     // FIXME: Handle array fields of structs.
1862     if (!D->getType()->isArrayType())
1863       continue;
1864
1865     const Expr *Init = D->getInit();
1866     if (!Init)
1867       continue;
1868     if (!isa<StringLiteral>(Init))
1869       continue;
1870
1871     Loc VarLoc = state->getLValue(D, C.getLocationContext());
1872     const MemRegion *MR = VarLoc.getAsRegion();
1873     if (!MR)
1874       continue;
1875
1876     SVal StrVal = state->getSVal(Init, C.getLocationContext());
1877     assert(StrVal.isValid() && "Initializer string is unknown or undefined");
1878     DefinedOrUnknownSVal strLength
1879       = cast<DefinedOrUnknownSVal>(getCStringLength(C, state, Init, StrVal));
1880
1881     state = state->set<CStringLength>(MR, strLength);
1882   }
1883
1884   C.addTransition(state);
1885 }
1886
1887 bool CStringChecker::wantsRegionChangeUpdate(ProgramStateRef state) const {
1888   CStringLength::EntryMap Entries = state->get<CStringLength>();
1889   return !Entries.isEmpty();
1890 }
1891
1892 ProgramStateRef
1893 CStringChecker::checkRegionChanges(ProgramStateRef state,
1894                                    const StoreManager::InvalidatedSymbols *,
1895                                    ArrayRef<const MemRegion *> ExplicitRegions,
1896                                    ArrayRef<const MemRegion *> Regions,
1897                                    const CallEvent *Call) const {
1898   CStringLength::EntryMap Entries = state->get<CStringLength>();
1899   if (Entries.isEmpty())
1900     return state;
1901
1902   llvm::SmallPtrSet<const MemRegion *, 8> Invalidated;
1903   llvm::SmallPtrSet<const MemRegion *, 32> SuperRegions;
1904
1905   // First build sets for the changed regions and their super-regions.
1906   for (ArrayRef<const MemRegion *>::iterator
1907        I = Regions.begin(), E = Regions.end(); I != E; ++I) {
1908     const MemRegion *MR = *I;
1909     Invalidated.insert(MR);
1910
1911     SuperRegions.insert(MR);
1912     while (const SubRegion *SR = dyn_cast<SubRegion>(MR)) {
1913       MR = SR->getSuperRegion();
1914       SuperRegions.insert(MR);
1915     }
1916   }
1917
1918   CStringLength::EntryMap::Factory &F = state->get_context<CStringLength>();
1919
1920   // Then loop over the entries in the current state.
1921   for (CStringLength::EntryMap::iterator I = Entries.begin(),
1922        E = Entries.end(); I != E; ++I) {
1923     const MemRegion *MR = I.getKey();
1924
1925     // Is this entry for a super-region of a changed region?
1926     if (SuperRegions.count(MR)) {
1927       Entries = F.remove(Entries, MR);
1928       continue;
1929     }
1930
1931     // Is this entry for a sub-region of a changed region?
1932     const MemRegion *Super = MR;
1933     while (const SubRegion *SR = dyn_cast<SubRegion>(Super)) {
1934       Super = SR->getSuperRegion();
1935       if (Invalidated.count(Super)) {
1936         Entries = F.remove(Entries, MR);
1937         break;
1938       }
1939     }
1940   }
1941
1942   return state->set<CStringLength>(Entries);
1943 }
1944
1945 void CStringChecker::checkLiveSymbols(ProgramStateRef state,
1946                                       SymbolReaper &SR) const {
1947   // Mark all symbols in our string length map as valid.
1948   CStringLength::EntryMap Entries = state->get<CStringLength>();
1949
1950   for (CStringLength::EntryMap::iterator I = Entries.begin(), E = Entries.end();
1951        I != E; ++I) {
1952     SVal Len = I.getData();
1953
1954     for (SymExpr::symbol_iterator si = Len.symbol_begin(),
1955                                   se = Len.symbol_end(); si != se; ++si)
1956       SR.markInUse(*si);
1957   }
1958 }
1959
1960 void CStringChecker::checkDeadSymbols(SymbolReaper &SR,
1961                                       CheckerContext &C) const {
1962   if (!SR.hasDeadSymbols())
1963     return;
1964
1965   ProgramStateRef state = C.getState();
1966   CStringLength::EntryMap Entries = state->get<CStringLength>();
1967   if (Entries.isEmpty())
1968     return;
1969
1970   CStringLength::EntryMap::Factory &F = state->get_context<CStringLength>();
1971   for (CStringLength::EntryMap::iterator I = Entries.begin(), E = Entries.end();
1972        I != E; ++I) {
1973     SVal Len = I.getData();
1974     if (SymbolRef Sym = Len.getAsSymbol()) {
1975       if (SR.isDead(Sym))
1976         Entries = F.remove(Entries, I.getKey());
1977     }
1978   }
1979
1980   state = state->set<CStringLength>(Entries);
1981   C.addTransition(state);
1982 }
1983
1984 #define REGISTER_CHECKER(name) \
1985 void ento::register##name(CheckerManager &mgr) {\
1986   static CStringChecker *TheChecker = 0; \
1987   if (TheChecker == 0) \
1988     TheChecker = mgr.registerChecker<CStringChecker>(); \
1989   TheChecker->Filter.Check##name = true; \
1990 }
1991
1992 REGISTER_CHECKER(CStringNullArg)
1993 REGISTER_CHECKER(CStringOutOfBounds)
1994 REGISTER_CHECKER(CStringBufferOverlap)
1995 REGISTER_CHECKER(CStringNotNullTerm)
1996
1997 void ento::registerCStringCheckerBasic(CheckerManager &Mgr) {
1998   registerCStringNullArg(Mgr);
1999 }