lib/StaticAnalyzer/Checkers/CStringChecker.cpp

   1 //= CStringChecker.h - 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 "clang/StaticAnalyzer/Core/Checker.h"
  17 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
  18 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
  19 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
  20 #include "clang/StaticAnalyzer/Core/PathSensitive/GRStateTrait.h"
  21 #include "llvm/ADT/StringSwitch.h"
  22
  23 using namespace clang;
  24 using namespace ento;
  25
  26 namespace {
  27 class CStringChecker : public Checker< eval::Call,
  28                                          check::PreStmt<DeclStmt>,
  29                                          check::LiveSymbols,
  30                                          check::DeadSymbols,
  31                                          check::RegionChanges
  32                                          > {
  33   mutable llvm::OwningPtr<BugType> BT_Null, BT_Bounds, BT_BoundsWrite,
  34                                    BT_Overlap, BT_NotCString;
  35 public:
  36   static void *getTag() { static int tag; return &tag; }
  37
  38   bool evalCall(const CallExpr *CE, CheckerContext &C) const;
  39   void checkPreStmt(const DeclStmt *DS, CheckerContext &C) const;
  40   void checkLiveSymbols(const GRState *state, SymbolReaper &SR) const;
  41   void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
  42   bool wantsRegionChangeUpdate(const GRState *state) const;
  43
  44   const GRState *checkRegionChanges(const GRState *state,
  45                                     const StoreManager::InvalidatedSymbols *,
  46                                     const MemRegion * const *Begin,
  47                                     const MemRegion * const *End) const;
  48
  49   typedef void (CStringChecker::*FnCheck)(CheckerContext &,
  50                                           const CallExpr *) const;
  51
  52   void evalMemcpy(CheckerContext &C, const CallExpr *CE) const;
  53   void evalMempcpy(CheckerContext &C, const CallExpr *CE) const;
  54   void evalMemmove(CheckerContext &C, const CallExpr *CE) const;
  55   void evalBcopy(CheckerContext &C, const CallExpr *CE) const;
  56   void evalCopyCommon(CheckerContext &C, const CallExpr *CE,
  57                       const GRState *state,
  58                       const Expr *Size, const Expr *Source, const Expr *Dest,
  59                       bool Restricted = false,
  60                       bool IsMempcpy = false) const;
  61
  62   void evalMemcmp(CheckerContext &C, const CallExpr *CE) const;
  63
  64   void evalstrLength(CheckerContext &C, const CallExpr *CE) const;
  65   void evalstrnLength(CheckerContext &C, const CallExpr *CE) const;
  66   void evalstrLengthCommon(CheckerContext &C, const CallExpr *CE,
  67                            bool IsStrnlen = false) const;
  68
  69   void evalStrcpy(CheckerContext &C, const CallExpr *CE) const;
  70   void evalStrncpy(CheckerContext &C, const CallExpr *CE) const;
  71   void evalStpcpy(CheckerContext &C, const CallExpr *CE) const;
  72   void evalStrcpyCommon(CheckerContext &C, const CallExpr *CE, bool returnEnd,
  73                         bool isBounded, bool isAppending) const;
  74
  75   void evalStrcat(CheckerContext &C, const CallExpr *CE) const;
  76   void evalStrncat(CheckerContext &C, const CallExpr *CE) const;
  77
  78   void evalStrcmp(CheckerContext &C, const CallExpr *CE) const;
  79   void evalStrncmp(CheckerContext &C, const CallExpr *CE) const;
  80   void evalStrcasecmp(CheckerContext &C, const CallExpr *CE) const;
  81   void evalStrncasecmp(CheckerContext &C, const CallExpr *CE) const;
  82   void evalStrcmpCommon(CheckerContext &C, const CallExpr *CE,
  83                         bool isBounded = false, bool ignoreCase = false) const;
  84
  85   // Utility methods
  86   std::pair<const GRState*, const GRState*>
  87   static assumeZero(CheckerContext &C,
  88                     const GRState *state, SVal V, QualType Ty);
  89
  90   static const GRState *setCStringLength(const GRState *state,
  91                                          const MemRegion *MR, SVal strLength);
  92   static SVal getCStringLengthForRegion(CheckerContext &C,
  93                                         const GRState *&state,
  94                                         const Expr *Ex, const MemRegion *MR);
  95   SVal getCStringLength(CheckerContext &C, const GRState *&state,
  96                         const Expr *Ex, SVal Buf) const;
  97
  98   const StringLiteral *getCStringLiteral(CheckerContext &C,
  99                                          const GRState *&state,
 100                                          const Expr *expr,
 101                                          SVal val) const;
 102
 103   static const GRState *InvalidateBuffer(CheckerContext &C,
 104                                          const GRState *state,
 105                                          const Expr *Ex, SVal V);
 106
 107   static bool SummarizeRegion(llvm::raw_ostream& os, ASTContext& Ctx,
 108                               const MemRegion *MR);
 109
 110   // Re-usable checks
 111   const GRState *checkNonNull(CheckerContext &C, const GRState *state,
 112                                const Expr *S, SVal l) const;
 113   const GRState *CheckLocation(CheckerContext &C, const GRState *state,
 114                                const Expr *S, SVal l,
 115                                bool IsDestination = false) const;
 116   const GRState *CheckBufferAccess(CheckerContext &C, const GRState *state,
 117                                    const Expr *Size,
 118                                    const Expr *FirstBuf,
 119                                    const Expr *SecondBuf = NULL,
 120                                    bool FirstIsDestination = false) const;
 121   const GRState *CheckOverlap(CheckerContext &C, const GRState *state,
 122                               const Expr *Size, const Expr *First,
 123                               const Expr *Second) const;
 124   void emitOverlapBug(CheckerContext &C, const GRState *state,
 125                       const Stmt *First, const Stmt *Second) const;
 126 };
 127
 128 class CStringLength {
 129 public:
 130   typedef llvm::ImmutableMap<const MemRegion *, SVal> EntryMap;
 131 };
 132 } //end anonymous namespace
 133
 134 namespace clang {
 135 namespace ento {
 136   template <>
 137   struct GRStateTrait<CStringLength>
 138     : public GRStatePartialTrait<CStringLength::EntryMap> {
 139     static void *GDMIndex() { return CStringChecker::getTag(); }
 140   };
 141 }
 142 }
 143
 144 //===----------------------------------------------------------------------===//
 145 // Individual checks and utility methods.
 146 //===----------------------------------------------------------------------===//
 147
 148 std::pair<const GRState*, const GRState*>
 149 CStringChecker::assumeZero(CheckerContext &C, const GRState *state, SVal V,
 150                            QualType Ty) {
 151   DefinedSVal *val = dyn_cast<DefinedSVal>(&V);
 152   if (!val)
 153     return std::pair<const GRState*, const GRState *>(state, state);
 154
 155   SValBuilder &svalBuilder = C.getSValBuilder();
 156   DefinedOrUnknownSVal zero = svalBuilder.makeZeroVal(Ty);
 157   return state->assume(svalBuilder.evalEQ(state, *val, zero));
 158 }
 159
 160 const GRState *CStringChecker::checkNonNull(CheckerContext &C,
 161                                             const GRState *state,
 162                                             const Expr *S, SVal l) const {
 163   // If a previous check has failed, propagate the failure.
 164   if (!state)
 165     return NULL;
 166
 167   const GRState *stateNull, *stateNonNull;
 168   llvm::tie(stateNull, stateNonNull) = assumeZero(C, state, l, S->getType());
 169
 170   if (stateNull && !stateNonNull) {
 171     ExplodedNode *N = C.generateSink(stateNull);
 172     if (!N)
 173       return NULL;
 174
 175     if (!BT_Null)
 176       BT_Null.reset(new BuiltinBug("API",
 177         "Null pointer argument in call to byte string function"));
 178
 179     // Generate a report for this bug.
 180     BuiltinBug *BT = static_cast<BuiltinBug*>(BT_Null.get());
 181     EnhancedBugReport *report = new EnhancedBugReport(*BT,
 182                                                       BT->getDescription(), N);
 183
 184     report->addRange(S->getSourceRange());
 185     report->addVisitorCreator(bugreporter::registerTrackNullOrUndefValue, S);
 186     C.EmitReport(report);
 187     return NULL;
 188   }
 189
 190   // From here on, assume that the value is non-null.
 191   assert(stateNonNull);
 192   return stateNonNull;
 193 }
 194
 195 // FIXME: This was originally copied from ArrayBoundChecker.cpp. Refactor?
 196 const GRState *CStringChecker::CheckLocation(CheckerContext &C,
 197                                              const GRState *state,
 198                                              const Expr *S, SVal l,
 199                                              bool IsDestination) const {
 200   // If a previous check has failed, propagate the failure.
 201   if (!state)
 202     return NULL;
 203
 204   // Check for out of bound array element access.
 205   const MemRegion *R = l.getAsRegion();
 206   if (!R)
 207     return state;
 208
 209   const ElementRegion *ER = dyn_cast<ElementRegion>(R);
 210   if (!ER)
 211     return state;
 212
 213   assert(ER->getValueType() == C.getASTContext().CharTy &&
 214     "CheckLocation should only be called with char* ElementRegions");
 215
 216   // Get the size of the array.
 217   const SubRegion *superReg = cast<SubRegion>(ER->getSuperRegion());
 218   SValBuilder &svalBuilder = C.getSValBuilder();
 219   SVal Extent = svalBuilder.convertToArrayIndex(superReg->getExtent(svalBuilder));
 220   DefinedOrUnknownSVal Size = cast<DefinedOrUnknownSVal>(Extent);
 221
 222   // Get the index of the accessed element.
 223   DefinedOrUnknownSVal Idx = cast<DefinedOrUnknownSVal>(ER->getIndex());
 224
 225   const GRState *StInBound = state->assumeInBound(Idx, Size, true);
 226   const GRState *StOutBound = state->assumeInBound(Idx, Size, false);
 227   if (StOutBound && !StInBound) {
 228     ExplodedNode *N = C.generateSink(StOutBound);
 229     if (!N)
 230       return NULL;
 231
 232     BuiltinBug *BT;
 233     if (IsDestination) {
 234       if (!BT_BoundsWrite) {
 235         BT_BoundsWrite.reset(new BuiltinBug("Out-of-bound array access",
 236           "Byte string function overflows destination buffer"));
 237       }
 238       BT = static_cast<BuiltinBug*>(BT_BoundsWrite.get());
 239     } else {
 240       if (!BT_Bounds) {
 241         BT_Bounds.reset(new BuiltinBug("Out-of-bound array access",
 242           "Byte string function accesses out-of-bound array element"));
 243       }
 244       BT = static_cast<BuiltinBug*>(BT_Bounds.get());
 245     }
 246
 247     // FIXME: It would be nice to eventually make this diagnostic more clear,
 248     // e.g., by referencing the original declaration or by saying *why* this
 249     // reference is outside the range.
 250
 251     // Generate a report for this bug.
 252     RangedBugReport *report = new RangedBugReport(*BT, BT->getDescription(), N);
 253
 254     report->addRange(S->getSourceRange());
 255     C.EmitReport(report);
 256     return NULL;
 257   }
 258
 259   // Array bound check succeeded.  From this point forward the array bound
 260   // should always succeed.
 261   return StInBound;
 262 }
 263
 264 const GRState *CStringChecker::CheckBufferAccess(CheckerContext &C,
 265                                                  const GRState *state,
 266                                                  const Expr *Size,
 267                                                  const Expr *FirstBuf,
 268                                                  const Expr *SecondBuf,
 269                                                 bool FirstIsDestination) const {
 270   // If a previous check has failed, propagate the failure.
 271   if (!state)
 272     return NULL;
 273
 274   SValBuilder &svalBuilder = C.getSValBuilder();
 275   ASTContext &Ctx = C.getASTContext();
 276
 277   QualType sizeTy = Size->getType();
 278   QualType PtrTy = Ctx.getPointerType(Ctx.CharTy);
 279
 280   // Check that the first buffer is non-null.
 281   SVal BufVal = state->getSVal(FirstBuf);
 282   state = checkNonNull(C, state, FirstBuf, BufVal);
 283   if (!state)
 284     return NULL;
 285
 286   // Get the access length and make sure it is known.
 287   SVal LengthVal = state->getSVal(Size);
 288   NonLoc *Length = dyn_cast<NonLoc>(&LengthVal);
 289   if (!Length)
 290     return state;
 291
 292   // Compute the offset of the last element to be accessed: size-1.
 293   NonLoc One = cast<NonLoc>(svalBuilder.makeIntVal(1, sizeTy));
 294   NonLoc LastOffset = cast<NonLoc>(svalBuilder.evalBinOpNN(state, BO_Sub,
 295                                                     *Length, One, sizeTy));
 296
 297   // Check that the first buffer is sufficiently long.
 298   SVal BufStart = svalBuilder.evalCast(BufVal, PtrTy, FirstBuf->getType());
 299   if (Loc *BufLoc = dyn_cast<Loc>(&BufStart)) {
 300     SVal BufEnd = svalBuilder.evalBinOpLN(state, BO_Add, *BufLoc,
 301                                           LastOffset, PtrTy);
 302     state = CheckLocation(C, state, FirstBuf, BufEnd, FirstIsDestination);
 303
 304     // If the buffer isn't large enough, abort.
 305     if (!state)
 306       return NULL;
 307   }
 308
 309   // If there's a second buffer, check it as well.
 310   if (SecondBuf) {
 311     BufVal = state->getSVal(SecondBuf);
 312     state = checkNonNull(C, state, SecondBuf, BufVal);
 313     if (!state)
 314       return NULL;
 315
 316     BufStart = svalBuilder.evalCast(BufVal, PtrTy, SecondBuf->getType());
 317     if (Loc *BufLoc = dyn_cast<Loc>(&BufStart)) {
 318       SVal BufEnd = svalBuilder.evalBinOpLN(state, BO_Add, *BufLoc,
 319                                             LastOffset, PtrTy);
 320       state = CheckLocation(C, state, SecondBuf, BufEnd);
 321     }
 322   }
 323
 324   // Large enough or not, return this state!
 325   return state;
 326 }
 327
 328 const GRState *CStringChecker::CheckOverlap(CheckerContext &C,
 329                                             const GRState *state,
 330                                             const Expr *Size,
 331                                             const Expr *First,
 332                                             const Expr *Second) const {
 333   // Do a simple check for overlap: if the two arguments are from the same
 334   // buffer, see if the end of the first is greater than the start of the second
 335   // or vice versa.
 336
 337   // If a previous check has failed, propagate the failure.
 338   if (!state)
 339     return NULL;
 340
 341   const GRState *stateTrue, *stateFalse;
 342
 343   // Get the buffer values and make sure they're known locations.
 344   SVal firstVal = state->getSVal(First);
 345   SVal secondVal = state->getSVal(Second);
 346
 347   Loc *firstLoc = dyn_cast<Loc>(&firstVal);
 348   if (!firstLoc)
 349     return state;
 350
 351   Loc *secondLoc = dyn_cast<Loc>(&secondVal);
 352   if (!secondLoc)
 353     return state;
 354
 355   // Are the two values the same?
 356   SValBuilder &svalBuilder = C.getSValBuilder();
 357   llvm::tie(stateTrue, stateFalse) =
 358     state->assume(svalBuilder.evalEQ(state, *firstLoc, *secondLoc));
 359
 360   if (stateTrue && !stateFalse) {
 361     // If the values are known to be equal, that's automatically an overlap.
 362     emitOverlapBug(C, stateTrue, First, Second);
 363     return NULL;
 364   }
 365
 366   // assume the two expressions are not equal.
 367   assert(stateFalse);
 368   state = stateFalse;
 369
 370   // Which value comes first?
 371   ASTContext &Ctx = svalBuilder.getContext();
 372   QualType cmpTy = Ctx.IntTy;
 373   SVal reverse = svalBuilder.evalBinOpLL(state, BO_GT,
 374                                          *firstLoc, *secondLoc, cmpTy);
 375   DefinedOrUnknownSVal *reverseTest = dyn_cast<DefinedOrUnknownSVal>(&reverse);
 376   if (!reverseTest)
 377     return state;
 378
 379   llvm::tie(stateTrue, stateFalse) = state->assume(*reverseTest);
 380   if (stateTrue) {
 381     if (stateFalse) {
 382       // If we don't know which one comes first, we can't perform this test.
 383       return state;
 384     } else {
 385       // Switch the values so that firstVal is before secondVal.
 386       Loc *tmpLoc = firstLoc;
 387       firstLoc = secondLoc;
 388       secondLoc = tmpLoc;
 389
 390       // Switch the Exprs as well, so that they still correspond.
 391       const Expr *tmpExpr = First;
 392       First = Second;
 393       Second = tmpExpr;
 394     }
 395   }
 396
 397   // Get the length, and make sure it too is known.
 398   SVal LengthVal = state->getSVal(Size);
 399   NonLoc *Length = dyn_cast<NonLoc>(&LengthVal);
 400   if (!Length)
 401     return state;
 402
 403   // Convert the first buffer's start address to char*.
 404   // Bail out if the cast fails.
 405   QualType CharPtrTy = Ctx.getPointerType(Ctx.CharTy);
 406   SVal FirstStart = svalBuilder.evalCast(*firstLoc, CharPtrTy, First->getType());
 407   Loc *FirstStartLoc = dyn_cast<Loc>(&FirstStart);
 408   if (!FirstStartLoc)
 409     return state;
 410
 411   // Compute the end of the first buffer. Bail out if THAT fails.
 412   SVal FirstEnd = svalBuilder.evalBinOpLN(state, BO_Add,
 413                                  *FirstStartLoc, *Length, CharPtrTy);
 414   Loc *FirstEndLoc = dyn_cast<Loc>(&FirstEnd);
 415   if (!FirstEndLoc)
 416     return state;
 417
 418   // Is the end of the first buffer past the start of the second buffer?
 419   SVal Overlap = svalBuilder.evalBinOpLL(state, BO_GT,
 420                                 *FirstEndLoc, *secondLoc, cmpTy);
 421   DefinedOrUnknownSVal *OverlapTest = dyn_cast<DefinedOrUnknownSVal>(&Overlap);
 422   if (!OverlapTest)
 423     return state;
 424
 425   llvm::tie(stateTrue, stateFalse) = state->assume(*OverlapTest);
 426
 427   if (stateTrue && !stateFalse) {
 428     // Overlap!
 429     emitOverlapBug(C, stateTrue, First, Second);
 430     return NULL;
 431   }
 432
 433   // assume the two expressions don't overlap.
 434   assert(stateFalse);
 435   return stateFalse;
 436 }
 437
 438 void CStringChecker::emitOverlapBug(CheckerContext &C, const GRState *state,
 439                                   const Stmt *First, const Stmt *Second) const {
 440   ExplodedNode *N = C.generateSink(state);
 441   if (!N)
 442     return;
 443
 444   if (!BT_Overlap)
 445     BT_Overlap.reset(new BugType("Unix API", "Improper arguments"));
 446
 447   // Generate a report for this bug.
 448   RangedBugReport *report =
 449     new RangedBugReport(*BT_Overlap,
 450       "Arguments must not be overlapping buffers", N);
 451   report->addRange(First->getSourceRange());
 452   report->addRange(Second->getSourceRange());
 453
 454   C.EmitReport(report);
 455 }
 456
 457 const GRState *CStringChecker::setCStringLength(const GRState *state,
 458                                                 const MemRegion *MR,
 459                                                 SVal strLength) {
 460   assert(!strLength.isUndef() && "Attempt to set an undefined string length");
 461   if (strLength.isUnknown())
 462     return state;
 463
 464   MR = MR->StripCasts();
 465
 466   switch (MR->getKind()) {
 467   case MemRegion::StringRegionKind:
 468     // FIXME: This can happen if we strcpy() into a string region. This is
 469     // undefined [C99 6.4.5p6], but we should still warn about it.
 470     return state;
 471
 472   case MemRegion::SymbolicRegionKind:
 473   case MemRegion::AllocaRegionKind:
 474   case MemRegion::VarRegionKind:
 475   case MemRegion::FieldRegionKind:
 476   case MemRegion::ObjCIvarRegionKind:
 477     return state->set<CStringLength>(MR, strLength);
 478
 479   case MemRegion::ElementRegionKind:
 480     // FIXME: Handle element regions by upper-bounding the parent region's
 481     // string length.
 482     return state;
 483
 484   default:
 485     // Other regions (mostly non-data) can't have a reliable C string length.
 486     // For now, just ignore the change.
 487     // FIXME: These are rare but not impossible. We should output some kind of
 488     // warning for things like strcpy((char[]){'a', 0}, "b");
 489     return state;
 490   }
 491 }
 492
 493 SVal CStringChecker::getCStringLengthForRegion(CheckerContext &C,
 494                                                const GRState *&state,
 495                                                const Expr *Ex,
 496                                                const MemRegion *MR) {
 497   // If there's a recorded length, go ahead and return it.
 498   const SVal *Recorded = state->get<CStringLength>(MR);
 499   if (Recorded)
 500     return *Recorded;
 501
 502   // Otherwise, get a new symbol and update the state.
 503   unsigned Count = C.getNodeBuilder().getCurrentBlockCount();
 504   SValBuilder &svalBuilder = C.getSValBuilder();
 505   QualType sizeTy = svalBuilder.getContext().getSizeType();
 506   SVal strLength = svalBuilder.getMetadataSymbolVal(CStringChecker::getTag(),
 507                                                     MR, Ex, sizeTy, Count);
 508   state = state->set<CStringLength>(MR, strLength);
 509   return strLength;
 510 }
 511
 512 SVal CStringChecker::getCStringLength(CheckerContext &C, const GRState *&state,
 513                                       const Expr *Ex, SVal Buf) const {
 514   const MemRegion *MR = Buf.getAsRegion();
 515   if (!MR) {
 516     // If we can't get a region, see if it's something we /know/ isn't a
 517     // C string. In the context of locations, the only time we can issue such
 518     // a warning is for labels.
 519     if (loc::GotoLabel *Label = dyn_cast<loc::GotoLabel>(&Buf)) {
 520       if (ExplodedNode *N = C.generateNode(state)) {
 521         if (!BT_NotCString)
 522           BT_NotCString.reset(new BuiltinBug("API",
 523             "Argument is not a null-terminated string."));
 524
 525         llvm::SmallString<120> buf;
 526         llvm::raw_svector_ostream os(buf);
 527         os << "Argument to byte string function is the address of the label '"
 528            << Label->getLabel()->getName()
 529            << "', which is not a null-terminated string";
 530
 531         // Generate a report for this bug.
 532         EnhancedBugReport *report = new EnhancedBugReport(*BT_NotCString,
 533                                                           os.str(), N);
 534
 535         report->addRange(Ex->getSourceRange());
 536         C.EmitReport(report);
 537       }
 538
 539       return UndefinedVal();
 540     }
 541
 542     // If it's not a region and not a label, give up.
 543     return UnknownVal();
 544   }
 545
 546   // If we have a region, strip casts from it and see if we can figure out
 547   // its length. For anything we can't figure out, just return UnknownVal.
 548   MR = MR->StripCasts();
 549
 550   switch (MR->getKind()) {
 551   case MemRegion::StringRegionKind: {
 552     // Modifying the contents of string regions is undefined [C99 6.4.5p6],
 553     // so we can assume that the byte length is the correct C string length.
 554     SValBuilder &svalBuilder = C.getSValBuilder();
 555     QualType sizeTy = svalBuilder.getContext().getSizeType();
 556     const StringLiteral *strLit = cast<StringRegion>(MR)->getStringLiteral();
 557     return svalBuilder.makeIntVal(strLit->getByteLength(), sizeTy);
 558   }
 559   case MemRegion::SymbolicRegionKind:
 560   case MemRegion::AllocaRegionKind:
 561   case MemRegion::VarRegionKind:
 562   case MemRegion::FieldRegionKind:
 563   case MemRegion::ObjCIvarRegionKind:
 564     return getCStringLengthForRegion(C, state, Ex, MR);
 565   case MemRegion::CompoundLiteralRegionKind:
 566     // FIXME: Can we track this? Is it necessary?
 567     return UnknownVal();
 568   case MemRegion::ElementRegionKind:
 569     // FIXME: How can we handle this? It's not good enough to subtract the
 570     // offset from the base string length; consider "123\x00567" and &a[5].
 571     return UnknownVal();
 572   default:
 573     // Other regions (mostly non-data) can't have a reliable C string length.
 574     // In this case, an error is emitted and UndefinedVal is returned.
 575     // The caller should always be prepared to handle this case.
 576     if (ExplodedNode *N = C.generateNode(state)) {
 577       if (!BT_NotCString)
 578         BT_NotCString.reset(new BuiltinBug("API",
 579           "Argument is not a null-terminated string."));
 580
 581       llvm::SmallString<120> buf;
 582       llvm::raw_svector_ostream os(buf);
 583
 584       os << "Argument to byte string function is ";
 585
 586       if (SummarizeRegion(os, C.getASTContext(), MR))
 587         os << ", which is not a null-terminated string";
 588       else
 589         os << "not a null-terminated string";
 590
 591       // Generate a report for this bug.
 592       EnhancedBugReport *report = new EnhancedBugReport(*BT_NotCString,
 593                                                         os.str(), N);
 594
 595       report->addRange(Ex->getSourceRange());
 596       C.EmitReport(report);
 597     }
 598
 599     return UndefinedVal();
 600   }
 601 }
 602
 603 const StringLiteral *CStringChecker::getCStringLiteral(CheckerContext &C,
 604   const GRState *&state, const Expr *expr, SVal val) const {
 605
 606   // Get the memory region pointed to by the val.
 607   const MemRegion *bufRegion = val.getAsRegion();
 608   if (!bufRegion)
 609     return NULL;
 610
 611   // Strip casts off the memory region.
 612   bufRegion = bufRegion->StripCasts();
 613
 614   // Cast the memory region to a string region.
 615   const StringRegion *strRegion= dyn_cast<StringRegion>(bufRegion);
 616   if (!strRegion)
 617     return NULL;
 618
 619   // Return the actual string in the string region.
 620   return strRegion->getStringLiteral();
 621 }
 622
 623 const GRState *CStringChecker::InvalidateBuffer(CheckerContext &C,
 624                                                 const GRState *state,
 625                                                 const Expr *E, SVal V) {
 626   Loc *L = dyn_cast<Loc>(&V);
 627   if (!L)
 628     return state;
 629
 630   // FIXME: This is a simplified version of what's in CFRefCount.cpp -- it makes
 631   // some assumptions about the value that CFRefCount can't. Even so, it should
 632   // probably be refactored.
 633   if (loc::MemRegionVal* MR = dyn_cast<loc::MemRegionVal>(L)) {
 634     const MemRegion *R = MR->getRegion()->StripCasts();
 635
 636     // Are we dealing with an ElementRegion?  If so, we should be invalidating
 637     // the super-region.
 638     if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
 639       R = ER->getSuperRegion();
 640       // FIXME: What about layers of ElementRegions?
 641     }
 642
 643     // Invalidate this region.
 644     unsigned Count = C.getNodeBuilder().getCurrentBlockCount();
 645     return state->invalidateRegion(R, E, Count, NULL);
 646   }
 647
 648   // If we have a non-region value by chance, just remove the binding.
 649   // FIXME: is this necessary or correct? This handles the non-Region
 650   //  cases.  Is it ever valid to store to these?
 651   return state->unbindLoc(*L);
 652 }
 653
 654 bool CStringChecker::SummarizeRegion(llvm::raw_ostream& os, ASTContext& Ctx,
 655                                      const MemRegion *MR) {
 656   const TypedRegion *TR = dyn_cast<TypedRegion>(MR);
 657   if (!TR)
 658     return false;
 659
 660   switch (TR->getKind()) {
 661   case MemRegion::FunctionTextRegionKind: {
 662     const FunctionDecl *FD = cast<FunctionTextRegion>(TR)->getDecl();
 663     if (FD)
 664       os << "the address of the function '" << FD << "'";
 665     else
 666       os << "the address of a function";
 667     return true;
 668   }
 669   case MemRegion::BlockTextRegionKind:
 670     os << "block text";
 671     return true;
 672   case MemRegion::BlockDataRegionKind:
 673     os << "a block";
 674     return true;
 675   case MemRegion::CXXThisRegionKind:
 676   case MemRegion::CXXTempObjectRegionKind:
 677     os << "a C++ temp object of type " << TR->getValueType().getAsString();
 678     return true;
 679   case MemRegion::VarRegionKind:
 680     os << "a variable of type" << TR->getValueType().getAsString();
 681     return true;
 682   case MemRegion::FieldRegionKind:
 683     os << "a field of type " << TR->getValueType().getAsString();
 684     return true;
 685   case MemRegion::ObjCIvarRegionKind:
 686     os << "an instance variable of type " << TR->getValueType().getAsString();
 687     return true;
 688   default:
 689     return false;
 690   }
 691 }
 692
 693 //===----------------------------------------------------------------------===//
 694 // evaluation of individual function calls.
 695 //===----------------------------------------------------------------------===//
 696
 697 void CStringChecker::evalCopyCommon(CheckerContext &C,
 698                                     const CallExpr *CE,
 699                                     const GRState *state,
 700                                     const Expr *Size, const Expr *Dest,
 701                                     const Expr *Source, bool Restricted,
 702                                     bool IsMempcpy) const {
 703   // See if the size argument is zero.
 704   SVal sizeVal = state->getSVal(Size);
 705   QualType sizeTy = Size->getType();
 706
 707   const GRState *stateZeroSize, *stateNonZeroSize;
 708   llvm::tie(stateZeroSize, stateNonZeroSize) = assumeZero(C, state, sizeVal, sizeTy);
 709
 710   // Get the value of the Dest.
 711   SVal destVal = state->getSVal(Dest);
 712
 713   // If the size is zero, there won't be any actual memory access, so
 714   // just bind the return value to the destination buffer and return.
 715   if (stateZeroSize) {
 716     stateZeroSize = stateZeroSize->BindExpr(CE, destVal);
 717     C.addTransition(stateZeroSize);
 718   }
 719
 720   // If the size can be nonzero, we have to check the other arguments.
 721   if (stateNonZeroSize) {
 722     state = stateNonZeroSize;
 723
 724     // Ensure the destination is not null. If it is NULL there will be a
 725     // NULL pointer dereference.
 726     state = checkNonNull(C, state, Dest, destVal);
 727     if (!state)
 728       return;
 729
 730     // Get the value of the Src.
 731     SVal srcVal = state->getSVal(Source);
 732
 733     // Ensure the source is not null. If it is NULL there will be a
 734     // NULL pointer dereference.
 735     state = checkNonNull(C, state, Source, srcVal);
 736     if (!state)
 737       return;
 738
 739     // Ensure the accesses are valid and that the buffers do not overlap.
 740     state = CheckBufferAccess(C, state, Size, Dest, Source,
 741                               /* FirstIsDst = */ true);
 742     if (Restricted)
 743       state = CheckOverlap(C, state, Size, Dest, Source);
 744
 745     if (!state)
 746       return;
 747
 748     // If this is mempcpy, get the byte after the last byte copied and
 749     // bind the expr.
 750     if (IsMempcpy) {
 751       loc::MemRegionVal *destRegVal = dyn_cast<loc::MemRegionVal>(&destVal);
 752       assert(destRegVal && "Destination should be a known MemRegionVal here");
 753
 754       // Get the length to copy.
 755       NonLoc *lenValNonLoc = dyn_cast<NonLoc>(&sizeVal);
 756
 757       if (lenValNonLoc) {
 758         // Get the byte after the last byte copied.
 759         SVal lastElement = C.getSValBuilder().evalBinOpLN(state, BO_Add,
 760                                                           *destRegVal,
 761                                                           *lenValNonLoc,
 762                                                           Dest->getType());
 763
 764         // The byte after the last byte copied is the return value.
 765         state = state->BindExpr(CE, lastElement);
 766       } else {
 767         // If we don't know how much we copied, we can at least
 768         // conjure a return value for later.
 769         unsigned Count = C.getNodeBuilder().getCurrentBlockCount();
 770         SVal result =
 771           C.getSValBuilder().getConjuredSymbolVal(NULL, CE, Count);
 772         state = state->BindExpr(CE, result);
 773       }
 774
 775     } else {
 776       // All other copies return the destination buffer.
 777       // (Well, bcopy() has a void return type, but this won't hurt.)
 778       state = state->BindExpr(CE, destVal);
 779     }
 780
 781     // Invalidate the destination.
 782     // FIXME: Even if we can't perfectly model the copy, we should see if we
 783     // can use LazyCompoundVals to copy the source values into the destination.
 784     // This would probably remove any existing bindings past the end of the
 785     // copied region, but that's still an improvement over blank invalidation.
 786     state = InvalidateBuffer(C, state, Dest, state->getSVal(Dest));
 787     C.addTransition(state);
 788   }
 789 }
 790
 791
 792 void CStringChecker::evalMemcpy(CheckerContext &C, const CallExpr *CE) const {
 793   // void *memcpy(void *restrict dst, const void *restrict src, size_t n);
 794   // The return value is the address of the destination buffer.
 795   const Expr *Dest = CE->getArg(0);
 796   const GRState *state = C.getState();
 797
 798   evalCopyCommon(C, CE, state, CE->getArg(2), Dest, CE->getArg(1), true);
 799 }
 800
 801 void CStringChecker::evalMempcpy(CheckerContext &C, const CallExpr *CE) const {
 802   // void *mempcpy(void *restrict dst, const void *restrict src, size_t n);
 803   // The return value is a pointer to the byte following the last written byte.
 804   const Expr *Dest = CE->getArg(0);
 805   const GRState *state = C.getState();
 806
 807   evalCopyCommon(C, CE, state, CE->getArg(2), Dest, CE->getArg(1), true, true);
 808 }
 809
 810 void CStringChecker::evalMemmove(CheckerContext &C, const CallExpr *CE) const {
 811   // void *memmove(void *dst, const void *src, size_t n);
 812   // The return value is the address of the destination buffer.
 813   const Expr *Dest = CE->getArg(0);
 814   const GRState *state = C.getState();
 815
 816   evalCopyCommon(C, CE, state, CE->getArg(2), Dest, CE->getArg(1));
 817 }
 818
 819 void CStringChecker::evalBcopy(CheckerContext &C, const CallExpr *CE) const {
 820   // void bcopy(const void *src, void *dst, size_t n);
 821   evalCopyCommon(C, CE, C.getState(),
 822                  CE->getArg(2), CE->getArg(1), CE->getArg(0));
 823 }
 824
 825 void CStringChecker::evalMemcmp(CheckerContext &C, const CallExpr *CE) const {
 826   // int memcmp(const void *s1, const void *s2, size_t n);
 827   const Expr *Left = CE->getArg(0);
 828   const Expr *Right = CE->getArg(1);
 829   const Expr *Size = CE->getArg(2);
 830
 831   const GRState *state = C.getState();
 832   SValBuilder &svalBuilder = C.getSValBuilder();
 833
 834   // See if the size argument is zero.
 835   SVal sizeVal = state->getSVal(Size);
 836   QualType sizeTy = Size->getType();
 837
 838   const GRState *stateZeroSize, *stateNonZeroSize;
 839   llvm::tie(stateZeroSize, stateNonZeroSize) =
 840     assumeZero(C, state, sizeVal, sizeTy);
 841
 842   // If the size can be zero, the result will be 0 in that case, and we don't
 843   // have to check either of the buffers.
 844   if (stateZeroSize) {
 845     state = stateZeroSize;
 846     state = state->BindExpr(CE, svalBuilder.makeZeroVal(CE->getType()));
 847     C.addTransition(state);
 848   }
 849
 850   // If the size can be nonzero, we have to check the other arguments.
 851   if (stateNonZeroSize) {
 852     state = stateNonZeroSize;
 853     // If we know the two buffers are the same, we know the result is 0.
 854     // First, get the two buffers' addresses. Another checker will have already
 855     // made sure they're not undefined.
 856     DefinedOrUnknownSVal LV = cast<DefinedOrUnknownSVal>(state->getSVal(Left));
 857     DefinedOrUnknownSVal RV = cast<DefinedOrUnknownSVal>(state->getSVal(Right));
 858
 859     // See if they are the same.
 860     DefinedOrUnknownSVal SameBuf = svalBuilder.evalEQ(state, LV, RV);
 861     const GRState *StSameBuf, *StNotSameBuf;
 862     llvm::tie(StSameBuf, StNotSameBuf) = state->assume(SameBuf);
 863
 864     // If the two arguments might be the same buffer, we know the result is zero,
 865     // and we only need to check one size.
 866     if (StSameBuf) {
 867       state = StSameBuf;
 868       state = CheckBufferAccess(C, state, Size, Left);
 869       if (state) {
 870         state = StSameBuf->BindExpr(CE, svalBuilder.makeZeroVal(CE->getType()));
 871         C.addTransition(state);
 872       }
 873     }
 874
 875     // If the two arguments might be different buffers, we have to check the
 876     // size of both of them.
 877     if (StNotSameBuf) {
 878       state = StNotSameBuf;
 879       state = CheckBufferAccess(C, state, Size, Left, Right);
 880       if (state) {
 881         // The return value is the comparison result, which we don't know.
 882         unsigned Count = C.getNodeBuilder().getCurrentBlockCount();
 883         SVal CmpV = svalBuilder.getConjuredSymbolVal(NULL, CE, Count);
 884         state = state->BindExpr(CE, CmpV);
 885         C.addTransition(state);
 886       }
 887     }
 888   }
 889 }
 890
 891 void CStringChecker::evalstrLength(CheckerContext &C,
 892                                    const CallExpr *CE) const {
 893   // size_t strlen(const char *s);
 894   evalstrLengthCommon(C, CE, /* IsStrnlen = */ false);
 895 }
 896
 897 void CStringChecker::evalstrnLength(CheckerContext &C,
 898                                     const CallExpr *CE) const {
 899   // size_t strnlen(const char *s, size_t maxlen);
 900   evalstrLengthCommon(C, CE, /* IsStrnlen = */ true);
 901 }
 902
 903 void CStringChecker::evalstrLengthCommon(CheckerContext &C, const CallExpr *CE,
 904                                          bool IsStrnlen) const {
 905   const GRState *state = C.getState();
 906   const Expr *Arg = CE->getArg(0);
 907   SVal ArgVal = state->getSVal(Arg);
 908
 909   // Check that the argument is non-null.
 910   state = checkNonNull(C, state, Arg, ArgVal);
 911
 912   if (state) {
 913     SVal strLength = getCStringLength(C, state, Arg, ArgVal);
 914
 915     // If the argument isn't a valid C string, there's no valid state to
 916     // transition to.
 917     if (strLength.isUndef())
 918       return;
 919
 920     // If the check is for strnlen() then bind the return value to no more than
 921     // the maxlen value.
 922     if (IsStrnlen) {
 923       const Expr *maxlenExpr = CE->getArg(1);
 924       SVal maxlenVal = state->getSVal(maxlenExpr);
 925
 926       NonLoc *strLengthNL = dyn_cast<NonLoc>(&strLength);
 927       NonLoc *maxlenValNL = dyn_cast<NonLoc>(&maxlenVal);
 928
 929       QualType cmpTy = C.getSValBuilder().getContext().IntTy;
 930       const GRState *stateTrue, *stateFalse;
 931
 932       // Check if the strLength is greater than or equal to the maxlen
 933       llvm::tie(stateTrue, stateFalse) =
 934         state->assume(cast<DefinedOrUnknownSVal>
 935                       (C.getSValBuilder().evalBinOpNN(state, BO_GE,
 936                                                       *strLengthNL, *maxlenValNL,
 937                                                       cmpTy)));
 938
 939       // If the strLength is greater than or equal to the maxlen, set strLength
 940       // to maxlen
 941       if (stateTrue && !stateFalse) {
 942         strLength = maxlenVal;
 943       }
 944     }
 945
 946     // If getCStringLength couldn't figure out the length, conjure a return
 947     // value, so it can be used in constraints, at least.
 948     if (strLength.isUnknown()) {
 949       unsigned Count = C.getNodeBuilder().getCurrentBlockCount();
 950       strLength = C.getSValBuilder().getConjuredSymbolVal(NULL, CE, Count);
 951     }
 952
 953     // Bind the return value.
 954     state = state->BindExpr(CE, strLength);
 955     C.addTransition(state);
 956   }
 957 }
 958
 959 void CStringChecker::evalStrcpy(CheckerContext &C, const CallExpr *CE) const {
 960   // char *strcpy(char *restrict dst, const char *restrict src);
 961   evalStrcpyCommon(C, CE,
 962                    /* returnEnd = */ false,
 963                    /* isBounded = */ false,
 964                    /* isAppending = */ false);
 965 }
 966
 967 void CStringChecker::evalStrncpy(CheckerContext &C, const CallExpr *CE) const {
 968   // char *strncpy(char *restrict dst, const char *restrict src, size_t n);
 969   evalStrcpyCommon(C, CE,
 970                    /* returnEnd = */ false,
 971                    /* isBounded = */ true,
 972                    /* isAppending = */ false);
 973 }
 974
 975 void CStringChecker::evalStpcpy(CheckerContext &C, const CallExpr *CE) const {
 976   // char *stpcpy(char *restrict dst, const char *restrict src);
 977   evalStrcpyCommon(C, CE,
 978                    /* returnEnd = */ true,
 979                    /* isBounded = */ false,
 980                    /* isAppending = */ false);
 981 }
 982
 983 void CStringChecker::evalStrcat(CheckerContext &C, const CallExpr *CE) const {
 984   //char *strcat(char *restrict s1, const char *restrict s2);
 985   evalStrcpyCommon(C, CE,
 986                    /* returnEnd = */ false,
 987                    /* isBounded = */ false,
 988                    /* isAppending = */ true);
 989 }
 990
 991 void CStringChecker::evalStrncat(CheckerContext &C, const CallExpr *CE) const {
 992   //char *strncat(char *restrict s1, const char *restrict s2, size_t n);
 993   evalStrcpyCommon(C, CE,
 994                    /* returnEnd = */ false,
 995                    /* isBounded = */ true,
 996                    /* isAppending = */ true);
 997 }
 998
 999 void CStringChecker::evalStrcpyCommon(CheckerContext &C, const CallExpr *CE,
1000                                       bool returnEnd, bool isBounded,
1001                                       bool isAppending) const {
1002   const GRState *state = C.getState();
1003
1004   // Check that the destination is non-null.
1005   const Expr *Dst = CE->getArg(0);
1006   SVal DstVal = state->getSVal(Dst);
1007
1008   state = checkNonNull(C, state, Dst, DstVal);
1009   if (!state)
1010     return;
1011
1012   // Check that the source is non-null.
1013   const Expr *srcExpr = CE->getArg(1);
1014   SVal srcVal = state->getSVal(srcExpr);
1015   state = checkNonNull(C, state, srcExpr, srcVal);
1016   if (!state)
1017     return;
1018
1019   // Get the string length of the source.
1020   SVal strLength = getCStringLength(C, state, srcExpr, srcVal);
1021
1022   // If the source isn't a valid C string, give up.
1023   if (strLength.isUndef())
1024     return;
1025
1026   // If the function is strncpy, strncat, etc... it is bounded.
1027   if (isBounded) {
1028     // Get the max number of characters to copy.
1029     const Expr *lenExpr = CE->getArg(2);
1030     SVal lenVal = state->getSVal(lenExpr);
1031
1032     // Cast the length to a NonLoc SVal. If it is not a NonLoc then give up.
1033     NonLoc *strLengthNL = dyn_cast<NonLoc>(&strLength);
1034     if (!strLengthNL)
1035       return;
1036
1037     // Cast the max length to a NonLoc SVal. If it is not a NonLoc then give up.
1038     NonLoc *lenValNL = dyn_cast<NonLoc>(&lenVal);
1039     if (!lenValNL)
1040       return;
1041
1042     QualType cmpTy = C.getSValBuilder().getContext().IntTy;
1043     const GRState *stateTrue, *stateFalse;
1044
1045     // Check if the max number to copy is less than the length of the src.
1046     llvm::tie(stateTrue, stateFalse) =
1047       state->assume(cast<DefinedOrUnknownSVal>
1048                     (C.getSValBuilder().evalBinOpNN(state, BO_GT,
1049                                                     *strLengthNL, *lenValNL,
1050                                                     cmpTy)));
1051
1052     if (stateTrue) {
1053       // Max number to copy is less than the length of the src, so the actual
1054       // strLength copied is the max number arg.
1055       strLength = lenVal;
1056     }
1057   }
1058
1059   // If this is an appending function (strcat, strncat...) then set the
1060   // string length to strlen(src) + strlen(dst) since the buffer will
1061   // ultimately contain both.
1062   if (isAppending) {
1063     // Get the string length of the destination, or give up.
1064     SVal dstStrLength = getCStringLength(C, state, Dst, DstVal);
1065     if (dstStrLength.isUndef())
1066       return;
1067
1068     NonLoc *srcStrLengthNL = dyn_cast<NonLoc>(&strLength);
1069     NonLoc *dstStrLengthNL = dyn_cast<NonLoc>(&dstStrLength);
1070
1071     // If src or dst cast to NonLoc is NULL, give up.
1072     if ((!srcStrLengthNL) || (!dstStrLengthNL))
1073       return;
1074
1075     QualType addTy = C.getSValBuilder().getContext().getSizeType();
1076
1077     strLength = C.getSValBuilder().evalBinOpNN(state, BO_Add,
1078                                                *srcStrLengthNL, *dstStrLengthNL,
1079                                                addTy);
1080   }
1081
1082   SVal Result = (returnEnd ? UnknownVal() : DstVal);
1083
1084   // If the destination is a MemRegion, try to check for a buffer overflow and
1085   // record the new string length.
1086   if (loc::MemRegionVal *dstRegVal = dyn_cast<loc::MemRegionVal>(&DstVal)) {
1087     // If the length is known, we can check for an overflow.
1088     if (NonLoc *knownStrLength = dyn_cast<NonLoc>(&strLength)) {
1089       SVal lastElement =
1090         C.getSValBuilder().evalBinOpLN(state, BO_Add, *dstRegVal,
1091                                        *knownStrLength, Dst->getType());
1092
1093       state = CheckLocation(C, state, Dst, lastElement, /* IsDst = */ true);
1094       if (!state)
1095         return;
1096
1097       // If this is a stpcpy-style copy, the last element is the return value.
1098       if (returnEnd)
1099         Result = lastElement;
1100     }
1101
1102     // Invalidate the destination. This must happen before we set the C string
1103     // length because invalidation will clear the length.
1104     // FIXME: Even if we can't perfectly model the copy, we should see if we
1105     // can use LazyCompoundVals to copy the source values into the destination.
1106     // This would probably remove any existing bindings past the end of the
1107     // string, but that's still an improvement over blank invalidation.
1108     state = InvalidateBuffer(C, state, Dst, *dstRegVal);
1109
1110     // Set the C string length of the destination.
1111     state = setCStringLength(state, dstRegVal->getRegion(), strLength);
1112   }
1113
1114   // If this is a stpcpy-style copy, but we were unable to check for a buffer
1115   // overflow, we still need a result. Conjure a return value.
1116   if (returnEnd && Result.isUnknown()) {
1117     SValBuilder &svalBuilder = C.getSValBuilder();
1118     unsigned Count = C.getNodeBuilder().getCurrentBlockCount();
1119     strLength = svalBuilder.getConjuredSymbolVal(NULL, CE, Count);
1120   }
1121
1122   // Set the return value.
1123   state = state->BindExpr(CE, Result);
1124   C.addTransition(state);
1125 }
1126
1127 void CStringChecker::evalStrcmp(CheckerContext &C, const CallExpr *CE) const {
1128   //int strcmp(const char *restrict s1, const char *restrict s2);
1129   evalStrcmpCommon(C, CE, /* isBounded = */ false, /* ignoreCase = */ false);
1130 }
1131
1132 void CStringChecker::evalStrncmp(CheckerContext &C, const CallExpr *CE) const {
1133   //int strncmp(const char *restrict s1, const char *restrict s2, size_t n);
1134   evalStrcmpCommon(C, CE, /* isBounded = */ true, /* ignoreCase = */ false);
1135 }
1136
1137 void CStringChecker::evalStrcasecmp(CheckerContext &C,
1138                                     const CallExpr *CE) const {
1139   //int strcasecmp(const char *restrict s1, const char *restrict s2);
1140   evalStrcmpCommon(C, CE, /* isBounded = */ false, /* ignoreCase = */ true);
1141 }
1142
1143 void CStringChecker::evalStrncasecmp(CheckerContext &C,
1144                                      const CallExpr *CE) const {
1145   //int strncasecmp(const char *restrict s1, const char *restrict s2, size_t n);
1146   evalStrcmpCommon(C, CE, /* isBounded = */ true, /* ignoreCase = */ true);
1147 }
1148
1149 void CStringChecker::evalStrcmpCommon(CheckerContext &C, const CallExpr *CE,
1150                                       bool isBounded, bool ignoreCase) const {
1151   const GRState *state = C.getState();
1152
1153   // Check that the first string is non-null
1154   const Expr *s1 = CE->getArg(0);
1155   SVal s1Val = state->getSVal(s1);
1156   state = checkNonNull(C, state, s1, s1Val);
1157   if (!state)
1158     return;
1159
1160   // Check that the second string is non-null.
1161   const Expr *s2 = CE->getArg(1);
1162   SVal s2Val = state->getSVal(s2);
1163   state = checkNonNull(C, state, s2, s2Val);
1164   if (!state)
1165     return;
1166
1167   // Get the string length of the first string or give up.
1168   SVal s1Length = getCStringLength(C, state, s1, s1Val);
1169   if (s1Length.isUndef())
1170     return;
1171
1172   // Get the string length of the second string or give up.
1173   SVal s2Length = getCStringLength(C, state, s2, s2Val);
1174   if (s2Length.isUndef())
1175     return;
1176
1177   // Get the string literal of the first string.
1178   const StringLiteral *s1StrLiteral = getCStringLiteral(C, state, s1, s1Val);
1179   if (!s1StrLiteral)
1180     return;
1181   llvm::StringRef s1StrRef = s1StrLiteral->getString();
1182
1183   // Get the string literal of the second string.
1184   const StringLiteral *s2StrLiteral = getCStringLiteral(C, state, s2, s2Val);
1185   if (!s2StrLiteral)
1186     return;
1187   llvm::StringRef s2StrRef = s2StrLiteral->getString();
1188
1189   int result;
1190   if (isBounded) {
1191     // Get the max number of characters to compare.
1192     const Expr *lenExpr = CE->getArg(2);
1193     SVal lenVal = state->getSVal(lenExpr);
1194
1195     // Dynamically cast the length to a ConcreteInt. If it is not a ConcreteInt
1196     // then give up, otherwise get the value and use it as the bounds.
1197     nonloc::ConcreteInt *CI = dyn_cast<nonloc::ConcreteInt>(&lenVal);
1198     if (!CI)
1199       return;
1200     llvm::APSInt lenInt(CI->getValue());
1201
1202     // Create substrings of each to compare the prefix.
1203     s1StrRef = s1StrRef.substr(0, (size_t)lenInt.getLimitedValue());
1204     s2StrRef = s2StrRef.substr(0, (size_t)lenInt.getLimitedValue());
1205   }
1206
1207   if (ignoreCase) {
1208     // Compare string 1 to string 2 the same way strcasecmp() does.
1209     result = s1StrRef.compare_lower(s2StrRef);
1210   } else {
1211     // Compare string 1 to string 2 the same way strcmp() does.
1212     result = s1StrRef.compare(s2StrRef);
1213   }
1214
1215   // Build the SVal of the comparison to bind the return value.
1216   SValBuilder &svalBuilder = C.getSValBuilder();
1217   QualType intTy = svalBuilder.getContext().IntTy;
1218   SVal resultVal = svalBuilder.makeIntVal(result, intTy);
1219
1220   // Bind the return value of the expression.
1221   // Set the return value.
1222   state = state->BindExpr(CE, resultVal);
1223   C.addTransition(state);
1224 }
1225
1226 //===----------------------------------------------------------------------===//
1227 // The driver method, and other Checker callbacks.
1228 //===----------------------------------------------------------------------===//
1229
1230 bool CStringChecker::evalCall(const CallExpr *CE, CheckerContext &C) const {
1231   // Get the callee.  All the functions we care about are C functions
1232   // with simple identifiers.
1233   const GRState *state = C.getState();
1234   const Expr *Callee = CE->getCallee();
1235   const FunctionDecl *FD = state->getSVal(Callee).getAsFunctionDecl();
1236
1237   if (!FD)
1238     return false;
1239
1240   // Get the name of the callee. If it's a builtin, strip off the prefix.
1241   IdentifierInfo *II = FD->getIdentifier();
1242   if (!II)   // if no identifier, not a simple C function
1243     return false;
1244   llvm::StringRef Name = II->getName();
1245   if (Name.startswith("__builtin_"))
1246     Name = Name.substr(10);
1247
1248   FnCheck evalFunction = llvm::StringSwitch<FnCheck>(Name)
1249     .Cases("memcpy", "__memcpy_chk", &CStringChecker::evalMemcpy)
1250     .Cases("mempcpy", "__mempcpy_chk", &CStringChecker::evalMempcpy)
1251     .Cases("memcmp", "bcmp", &CStringChecker::evalMemcmp)
1252     .Cases("memmove", "__memmove_chk", &CStringChecker::evalMemmove)
1253     .Cases("strcpy", "__strcpy_chk", &CStringChecker::evalStrcpy)
1254     //.Cases("strncpy", "__strncpy_chk", &CStringChecker::evalStrncpy)
1255     .Cases("stpcpy", "__stpcpy_chk", &CStringChecker::evalStpcpy)
1256     .Cases("strcat", "__strcat_chk", &CStringChecker::evalStrcat)
1257     .Cases("strncat", "__strncat_chk", &CStringChecker::evalStrncat)
1258     .Case("strlen", &CStringChecker::evalstrLength)
1259     .Case("strnlen", &CStringChecker::evalstrnLength)
1260     .Case("strcmp", &CStringChecker::evalStrcmp)
1261     .Case("strncmp", &CStringChecker::evalStrncmp)
1262     .Case("strcasecmp", &CStringChecker::evalStrcasecmp)
1263     .Case("strncasecmp", &CStringChecker::evalStrncasecmp)
1264     .Case("bcopy", &CStringChecker::evalBcopy)
1265     .Default(NULL);
1266
1267   // If the callee isn't a string function, let another checker handle it.
1268   if (!evalFunction)
1269     return false;
1270
1271   // Check and evaluate the call.
1272   (this->*evalFunction)(C, CE);
1273   return true;
1274 }
1275
1276 void CStringChecker::checkPreStmt(const DeclStmt *DS, CheckerContext &C) const {
1277   // Record string length for char a[] = "abc";
1278   const GRState *state = C.getState();
1279
1280   for (DeclStmt::const_decl_iterator I = DS->decl_begin(), E = DS->decl_end();
1281        I != E; ++I) {
1282     const VarDecl *D = dyn_cast<VarDecl>(*I);
1283     if (!D)
1284       continue;
1285
1286     // FIXME: Handle array fields of structs.
1287     if (!D->getType()->isArrayType())
1288       continue;
1289
1290     const Expr *Init = D->getInit();
1291     if (!Init)
1292       continue;
1293     if (!isa<StringLiteral>(Init))
1294       continue;
1295
1296     Loc VarLoc = state->getLValue(D, C.getPredecessor()->getLocationContext());
1297     const MemRegion *MR = VarLoc.getAsRegion();
1298     if (!MR)
1299       continue;
1300
1301     SVal StrVal = state->getSVal(Init);
1302     assert(StrVal.isValid() && "Initializer string is unknown or undefined");
1303     DefinedOrUnknownSVal strLength
1304       = cast<DefinedOrUnknownSVal>(getCStringLength(C, state, Init, StrVal));
1305
1306     state = state->set<CStringLength>(MR, strLength);
1307   }
1308
1309   C.addTransition(state);
1310 }
1311
1312 bool CStringChecker::wantsRegionChangeUpdate(const GRState *state) const {
1313   CStringLength::EntryMap Entries = state->get<CStringLength>();
1314   return !Entries.isEmpty();
1315 }
1316
1317 const GRState *
1318 CStringChecker::checkRegionChanges(const GRState *state,
1319                                    const StoreManager::InvalidatedSymbols *,
1320                                    const MemRegion * const *Begin,
1321                                    const MemRegion * const *End) const {
1322   CStringLength::EntryMap Entries = state->get<CStringLength>();
1323   if (Entries.isEmpty())
1324     return state;
1325
1326   llvm::SmallPtrSet<const MemRegion *, 8> Invalidated;
1327   llvm::SmallPtrSet<const MemRegion *, 32> SuperRegions;
1328
1329   // First build sets for the changed regions and their super-regions.
1330   for ( ; Begin != End; ++Begin) {
1331     const MemRegion *MR = *Begin;
1332     Invalidated.insert(MR);
1333
1334     SuperRegions.insert(MR);
1335     while (const SubRegion *SR = dyn_cast<SubRegion>(MR)) {
1336       MR = SR->getSuperRegion();
1337       SuperRegions.insert(MR);
1338     }
1339   }
1340
1341   CStringLength::EntryMap::Factory &F = state->get_context<CStringLength>();
1342
1343   // Then loop over the entries in the current state.
1344   for (CStringLength::EntryMap::iterator I = Entries.begin(),
1345        E = Entries.end(); I != E; ++I) {
1346     const MemRegion *MR = I.getKey();
1347
1348     // Is this entry for a super-region of a changed region?
1349     if (SuperRegions.count(MR)) {
1350       Entries = F.remove(Entries, MR);
1351       continue;
1352     }
1353
1354     // Is this entry for a sub-region of a changed region?
1355     const MemRegion *Super = MR;
1356     while (const SubRegion *SR = dyn_cast<SubRegion>(Super)) {
1357       Super = SR->getSuperRegion();
1358       if (Invalidated.count(Super)) {
1359         Entries = F.remove(Entries, MR);
1360         break;
1361       }
1362     }
1363   }
1364
1365   return state->set<CStringLength>(Entries);
1366 }
1367
1368 void CStringChecker::checkLiveSymbols(const GRState *state,
1369                                       SymbolReaper &SR) const {
1370   // Mark all symbols in our string length map as valid.
1371   CStringLength::EntryMap Entries = state->get<CStringLength>();
1372
1373   for (CStringLength::EntryMap::iterator I = Entries.begin(), E = Entries.end();
1374        I != E; ++I) {
1375     SVal Len = I.getData();
1376     if (SymbolRef Sym = Len.getAsSymbol())
1377       SR.markInUse(Sym);
1378   }
1379 }
1380
1381 void CStringChecker::checkDeadSymbols(SymbolReaper &SR,
1382                                       CheckerContext &C) const {
1383   if (!SR.hasDeadSymbols())
1384     return;
1385
1386   const GRState *state = C.getState();
1387   CStringLength::EntryMap Entries = state->get<CStringLength>();
1388   if (Entries.isEmpty())
1389     return;
1390
1391   CStringLength::EntryMap::Factory &F = state->get_context<CStringLength>();
1392   for (CStringLength::EntryMap::iterator I = Entries.begin(), E = Entries.end();
1393        I != E; ++I) {
1394     SVal Len = I.getData();
1395     if (SymbolRef Sym = Len.getAsSymbol()) {
1396       if (SR.isDead(Sym))
1397         Entries = F.remove(Entries, I.getKey());
1398     }
1399   }
1400
1401   state = state->set<CStringLength>(Entries);
1402   C.generateNode(state);
1403 }
1404
1405 void ento::registerCStringChecker(CheckerManager &mgr) {
1406   mgr.registerChecker<CStringChecker>();
1407 }