//= CStringChecker.cpp - Checks calls to C string functions --------*- C++ -*-//

//

// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

// See https://llvm.org/LICENSE.txt for license information.

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

//

//===----------------------------------------------------------------------===//

//

// This defines CStringChecker, which is an assortment of checks on calls

// to functions in <string.h>.

//

//===----------------------------------------------------------------------===//

#include "InterCheckerAPI.h"

#include "clang/Basic/CharInfo.h"

#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"

#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"

#include "clang/StaticAnalyzer/Core/Checker.h"

#include "clang/StaticAnalyzer/Core/CheckerManager.h"

#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"

#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"

#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicSize.h"

#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"

#include "llvm/ADT/STLExtras.h"

#include "llvm/ADT/SmallString.h"

#include "llvm/ADT/StringExtras.h"

#include "llvm/Support/raw_ostream.h"

using namespace clang;

using namespace ento;

namespace {

struct AnyArgExpr {

  // FIXME: Remove constructor in C++17 to turn it into an aggregate.

  AnyArgExpr(const Expr *Expression, unsigned ArgumentIndex)

      : Expression{Expression}, ArgumentIndex{ArgumentIndex} {}

  const Expr *Expression;

  unsigned ArgumentIndex;

};

struct SourceArgExpr : AnyArgExpr {

  using AnyArgExpr::AnyArgExpr; // FIXME: Remove using in C++17.

};

struct DestinationArgExpr : AnyArgExpr {

  using AnyArgExpr::AnyArgExpr; // FIXME: Same.

};

struct SizeArgExpr : AnyArgExpr {

  using AnyArgExpr::AnyArgExpr; // FIXME: Same.

};

using ErrorMessage = SmallString<128>;

enum class AccessKind { write, read };

static ErrorMessage createOutOfBoundErrorMsg(StringRef FunctionDescription,

                                             AccessKind Access) {

  ErrorMessage Message;

  llvm::raw_svector_ostream Os(Message);

  // Function classification like: Memory copy function

  Os << toUppercase(FunctionDescription.front())

     << &FunctionDescription.data()[1];

  if (Access == AccessKind::write) {

    Os << " overflows the destination buffer";

  } else { // read access

    Os << " accesses out-of-bound array element";

  }

  return Message;

}

enum class ConcatFnKind { none = 0, strcat = 1, strlcat = 2 };

class CStringChecker : public Checker< eval::Call,

                                         check::PreStmt<DeclStmt>,

                                         check::LiveSymbols,

                                         check::DeadSymbols,

                                         check::RegionChanges

                                         > {

  mutable std::unique_ptr<BugType> BT_Null, BT_Bounds, BT_Overlap,

      BT_NotCString, BT_AdditionOverflow;

  mutable const char *CurrentFunctionDescription;

public:

  /// The filter is used to filter out the diagnostics which are not enabled by

  /// the user.

  struct CStringChecksFilter {

    DefaultBool CheckCStringNullArg;

    DefaultBool CheckCStringOutOfBounds;

    DefaultBool CheckCStringBufferOverlap;

    DefaultBool CheckCStringNotNullTerm;

    CheckerNameRef CheckNameCStringNullArg;

    CheckerNameRef CheckNameCStringOutOfBounds;

    CheckerNameRef CheckNameCStringBufferOverlap;

    CheckerNameRef CheckNameCStringNotNullTerm;

  };

  CStringChecksFilter Filter;

  static void *getTag() { static int tag; return &tag; }

  bool evalCall(const CallEvent &Call, CheckerContext &C) const;

  void checkPreStmt(const DeclStmt *DS, CheckerContext &C) const;

  void checkLiveSymbols(ProgramStateRef state, SymbolReaper &SR) const;

  void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;

  ProgramStateRef

    checkRegionChanges(ProgramStateRef state,

                       const InvalidatedSymbols *,

                       ArrayRef<const MemRegion *> ExplicitRegions,

                       ArrayRef<const MemRegion *> Regions,

                       const LocationContext *LCtx,

                       const CallEvent *Call) const;

  typedef void (CStringChecker::*FnCheck)(CheckerContext &,

                                          const CallExpr *) const;

  CallDescriptionMap<FnCheck> Callbacks = {

      {{CDF_MaybeBuiltin, "memcpy", 3}, &CStringChecker::evalMemcpy},

      {{CDF_MaybeBuiltin, "mempcpy", 3}, &CStringChecker::evalMempcpy},

      {{CDF_MaybeBuiltin, "memcmp", 3}, &CStringChecker::evalMemcmp},

      {{CDF_MaybeBuiltin, "memmove", 3}, &CStringChecker::evalMemmove},

      {{CDF_MaybeBuiltin, "memset", 3}, &CStringChecker::evalMemset},

      {{CDF_MaybeBuiltin, "explicit_memset", 3}, &CStringChecker::evalMemset},

      {{CDF_MaybeBuiltin, "strcpy", 2}, &CStringChecker::evalStrcpy},

      {{CDF_MaybeBuiltin, "strncpy", 3}, &CStringChecker::evalStrncpy},

      {{CDF_MaybeBuiltin, "stpcpy", 2}, &CStringChecker::evalStpcpy},

      {{CDF_MaybeBuiltin, "strlcpy", 3}, &CStringChecker::evalStrlcpy},

      {{CDF_MaybeBuiltin, "strcat", 2}, &CStringChecker::evalStrcat},

      {{CDF_MaybeBuiltin, "strncat", 3}, &CStringChecker::evalStrncat},

      {{CDF_MaybeBuiltin, "strlcat", 3}, &CStringChecker::evalStrlcat},

      {{CDF_MaybeBuiltin, "strlen", 1}, &CStringChecker::evalstrLength},

      {{CDF_MaybeBuiltin, "strnlen", 2}, &CStringChecker::evalstrnLength},

      {{CDF_MaybeBuiltin, "strcmp", 2}, &CStringChecker::evalStrcmp},

      {{CDF_MaybeBuiltin, "strncmp", 3}, &CStringChecker::evalStrncmp},

      {{CDF_MaybeBuiltin, "strcasecmp", 2}, &CStringChecker::evalStrcasecmp},

      {{CDF_MaybeBuiltin, "strncasecmp", 3}, &CStringChecker::evalStrncasecmp},

      {{CDF_MaybeBuiltin, "strsep", 2}, &CStringChecker::evalStrsep},

      {{CDF_MaybeBuiltin, "bcopy", 3}, &CStringChecker::evalBcopy},

      {{CDF_MaybeBuiltin, "bcmp", 3}, &CStringChecker::evalMemcmp},

      {{CDF_MaybeBuiltin, "bzero", 2}, &CStringChecker::evalBzero},

      {{CDF_MaybeBuiltin, "explicit_bzero", 2}, &CStringChecker::evalBzero},

  };

  // These require a bit of special handling.

  CallDescription StdCopy{{"std", "copy"}, 3},

      StdCopyBackward{{"std", "copy_backward"}, 3};

  FnCheck identifyCall(const CallEvent &Call, CheckerContext &C) const;

  void evalMemcpy(CheckerContext &C, const CallExpr *CE) const;

  void evalMempcpy(CheckerContext &C, const CallExpr *CE) const;

  void evalMemmove(CheckerContext &C, const CallExpr *CE) const;

  void evalBcopy(CheckerContext &C, const CallExpr *CE) const;

  void evalCopyCommon(CheckerContext &C, const CallExpr *CE,

                      ProgramStateRef state, SizeArgExpr Size,

                      DestinationArgExpr Dest, SourceArgExpr Source,

                      bool Restricted, bool IsMempcpy) const;

  void evalMemcmp(CheckerContext &C, const CallExpr *CE) const;

  void evalstrLength(CheckerContext &C, const CallExpr *CE) const;

  void evalstrnLength(CheckerContext &C, const CallExpr *CE) const;

  void evalstrLengthCommon(CheckerContext &C,

                           const CallExpr *CE,

                           bool IsStrnlen = false) const;

  void evalStrcpy(CheckerContext &C, const CallExpr *CE) const;

  void evalStrncpy(CheckerContext &C, const CallExpr *CE) const;

  void evalStpcpy(CheckerContext &C, const CallExpr *CE) const;

  void evalStrlcpy(CheckerContext &C, const CallExpr *CE) const;

  void evalStrcpyCommon(CheckerContext &C, const CallExpr *CE, bool ReturnEnd,

                        bool IsBounded, ConcatFnKind appendK,

                        bool returnPtr = true) const;

  void evalStrcat(CheckerContext &C, const CallExpr *CE) const;

  void evalStrncat(CheckerContext &C, const CallExpr *CE) const;

  void evalStrlcat(CheckerContext &C, const CallExpr *CE) const;

  void evalStrcmp(CheckerContext &C, const CallExpr *CE) const;

  void evalStrncmp(CheckerContext &C, const CallExpr *CE) const;

  void evalStrcasecmp(CheckerContext &C, const CallExpr *CE) const;

  void evalStrncasecmp(CheckerContext &C, const CallExpr *CE) const;

  void evalStrcmpCommon(CheckerContext &C,

                        const CallExpr *CE,

                        bool IsBounded = false,

                        bool IgnoreCase = false) const;

  void evalStrsep(CheckerContext &C, const CallExpr *CE) const;

  void evalStdCopy(CheckerContext &C, const CallExpr *CE) const;

  void evalStdCopyBackward(CheckerContext &C, const CallExpr *CE) const;

  void evalStdCopyCommon(CheckerContext &C, const CallExpr *CE) const;

  void evalMemset(CheckerContext &C, const CallExpr *CE) const;

  void evalBzero(CheckerContext &C, const CallExpr *CE) const;

  // Utility methods

  std::pair<ProgramStateRef , ProgramStateRef >

  static assumeZero(CheckerContext &C,

                    ProgramStateRef state, SVal V, QualType Ty);

  static ProgramStateRef setCStringLength(ProgramStateRef state,

                                              const MemRegion *MR,

                                              SVal strLength);

  static SVal getCStringLengthForRegion(CheckerContext &C,

                                        ProgramStateRef &state,

                                        const Expr *Ex,

                                        const MemRegion *MR,

                                        bool hypothetical);

  SVal getCStringLength(CheckerContext &C,

                        ProgramStateRef &state,

                        const Expr *Ex,

                        SVal Buf,

                        bool hypothetical = false) const;

  const StringLiteral *getCStringLiteral(CheckerContext &C,

                                         ProgramStateRef &state,

                                         const Expr *expr,

                                         SVal val) const;

  static ProgramStateRef InvalidateBuffer(CheckerContext &C,

                                          ProgramStateRef state,

                                          const Expr *Ex, SVal V,

                                          bool IsSourceBuffer,

                                          const Expr *Size);

  static bool SummarizeRegion(raw_ostream &os, ASTContext &Ctx,

                              const MemRegion *MR);

  static bool memsetAux(const Expr *DstBuffer, SVal CharE,

                        const Expr *Size, CheckerContext &C,

                        ProgramStateRef &State);

  // Re-usable checks

  ProgramStateRef checkNonNull(CheckerContext &C, ProgramStateRef State,

                               AnyArgExpr Arg, SVal l) const;

  ProgramStateRef CheckLocation(CheckerContext &C, ProgramStateRef state,

                                AnyArgExpr Buffer, SVal Element,

                                AccessKind Access) const;

  ProgramStateRef CheckBufferAccess(CheckerContext &C, ProgramStateRef State,

                                    AnyArgExpr Buffer, SizeArgExpr Size,

                                    AccessKind Access) const;

  ProgramStateRef CheckOverlap(CheckerContext &C, ProgramStateRef state,

                               SizeArgExpr Size, AnyArgExpr First,

                               AnyArgExpr Second) const;

  void emitOverlapBug(CheckerContext &C,

                      ProgramStateRef state,

                      const Stmt *First,

                      const Stmt *Second) const;

  void emitNullArgBug(CheckerContext &C, ProgramStateRef State, const Stmt *S,

                      StringRef WarningMsg) const;

  void emitOutOfBoundsBug(CheckerContext &C, ProgramStateRef State,

                          const Stmt *S, StringRef WarningMsg) const;

  void emitNotCStringBug(CheckerContext &C, ProgramStateRef State,

                         const Stmt *S, StringRef WarningMsg) const;

  void emitAdditionOverflowBug(CheckerContext &C, ProgramStateRef State) const;

  ProgramStateRef checkAdditionOverflow(CheckerContext &C,

                                            ProgramStateRef state,

                                            NonLoc left,

                                            NonLoc right) const;

  // Return true if the destination buffer of the copy function may be in bound.

  // Expects SVal of Size to be positive and unsigned.

  // Expects SVal of FirstBuf to be a FieldRegion.

  static bool IsFirstBufInBound(CheckerContext &C,

                                ProgramStateRef state,

                                const Expr *FirstBuf,

                                const Expr *Size);

};

} //end anonymous namespace

REGISTER_MAP_WITH_PROGRAMSTATE(CStringLength, const MemRegion *, SVal)

//===----------------------------------------------------------------------===//

// Individual checks and utility methods.

//===----------------------------------------------------------------------===//

std::pair<ProgramStateRef , ProgramStateRef >

CStringChecker::assumeZero(CheckerContext &C, ProgramStateRef state, SVal V,

                           QualType Ty) {

  Optional<DefinedSVal> val = V.getAs<DefinedSVal>();

  if (!val)

    return std::pair<ProgramStateRef , ProgramStateRef >(state, state);

  SValBuilder &svalBuilder = C.getSValBuilder();

  DefinedOrUnknownSVal zero = svalBuilder.makeZeroVal(Ty);

  return state->assume(svalBuilder.evalEQ(state, *val, zero));

}

ProgramStateRef CStringChecker::checkNonNull(CheckerContext &C,

                                             ProgramStateRef State,

                                             AnyArgExpr Arg, SVal l) const {

  // If a previous check has failed, propagate the failure.

  if (!State)

    return nullptr;

  ProgramStateRef stateNull, stateNonNull;

  std::tie(stateNull, stateNonNull) =

      assumeZero(C, State, l, Arg.Expression->getType());

  if (stateNull && 
!stateNonNull572
) {

    if (Filter.CheckCStringNullArg) {

      SmallString<80> buf;

      llvm::raw_svector_ostream OS(buf);

      assert(CurrentFunctionDescription);

      OS << "Null pointer passed as " << (Arg.ArgumentIndex + 1)

         << llvm::getOrdinalSuffix(Arg.ArgumentIndex + 1) << " argument to "

         << CurrentFunctionDescription;

      emitNullArgBug(C, stateNull, Arg.Expression, OS.str());

    }

    return nullptr;

  }

  // From here on, assume that the value is non-null.

  assert(stateNonNull);

  return stateNonNull;

}

// FIXME: This was originally copied from ArrayBoundChecker.cpp. Refactor?

ProgramStateRef CStringChecker::CheckLocation(CheckerContext &C,

                                              ProgramStateRef state,

                                              AnyArgExpr Buffer, SVal Element,

                                              AccessKind Access) const {

  // If a previous check has failed, propagate the failure.

  if (!state)

    return nullptr;

  // Check for out of bound array element access.

  const MemRegion *R = Element.getAsRegion();

  if (!R)

    return state;

  const auto *ER = dyn_cast<ElementRegion>(R);

  if (!ER)

    return state;

  if (ER->getValueType() != C.getASTContext().CharTy)

    return state;

  // Get the size of the array.

  const auto *superReg = cast<SubRegion>(ER->getSuperRegion());

  DefinedOrUnknownSVal Size =

      getDynamicSize(state, superReg, C.getSValBuilder());

  // Get the index of the accessed element.

  DefinedOrUnknownSVal Idx = ER->getIndex().castAs<DefinedOrUnknownSVal>();

  ProgramStateRef StInBound = state->assumeInBound(Idx, Size, true);

  ProgramStateRef StOutBound = state->assumeInBound(Idx, Size, false);

  if (StOutBound && 
!StInBound268
) {

    // These checks are either enabled by the CString out-of-bounds checker

    // explicitly or implicitly by the Malloc checker.

    // In the latter case we only do modeling but do not emit warning.

    if (!Filter.CheckCStringOutOfBounds)

      return nullptr;

    // Emit a bug report.

    ErrorMessage Message =

        createOutOfBoundErrorMsg(CurrentFunctionDescription, Access);

    emitOutOfBoundsBug(C, StOutBound, Buffer.Expression, Message);

    return nullptr;

  }

  // Array bound check succeeded.  From this point forward the array bound

  // should always succeed.

  return StInBound;

}

ProgramStateRef CStringChecker::CheckBufferAccess(CheckerContext &C,

                                                  ProgramStateRef State,

                                                  AnyArgExpr Buffer,

                                                  SizeArgExpr Size,

                                                  AccessKind Access) const {

  // If a previous check has failed, propagate the failure.

  if (!State)

    return nullptr;

  SValBuilder &svalBuilder = C.getSValBuilder();

  ASTContext &Ctx = svalBuilder.getContext();

  QualType SizeTy = Size.Expression->getType();

  QualType PtrTy = Ctx.getPointerType(Ctx.CharTy);

  // Check that the first buffer is non-null.

  SVal BufVal = C.getSVal(Buffer.Expression);

  State = checkNonNull(C, State, Buffer, BufVal);

  if (!State)

    return nullptr;

  // If out-of-bounds checking is turned off, skip the rest.

  if (!Filter.CheckCStringOutOfBounds)

    return State;

  // Get the access length and make sure it is known.

  // FIXME: This assumes the caller has already checked that the access length

  // is positive. And that it's unsigned.

  SVal LengthVal = C.getSVal(Size.Expression);

  Optional<NonLoc> Length = LengthVal.getAs<NonLoc>();

  if (!Length)

    return State;

  // Compute the offset of the last element to be accessed: size-1.

  NonLoc One = svalBuilder.makeIntVal(1, SizeTy).castAs<NonLoc>();

  SVal Offset = svalBuilder.evalBinOpNN(State, BO_Sub, *Length, One, SizeTy);

  if (Offset.isUnknown())

    return nullptr;

  NonLoc LastOffset = Offset.castAs<NonLoc>();

  // Check that the first buffer is sufficiently long.

  SVal BufStart =

      svalBuilder.evalCast(BufVal, PtrTy, Buffer.Expression->getType());

  if (Optional<Loc> BufLoc = BufStart.getAs<Loc>()) {

    SVal BufEnd =

        svalBuilder.evalBinOpLN(State, BO_Add, *BufLoc, LastOffset, PtrTy);

    State = CheckLocation(C, State, Buffer, BufEnd, Access);

    // If the buffer isn't large enough, abort.

    if (!State)

      return nullptr;

  }

  // Large enough or not, return this state!

  return State;

}

ProgramStateRef CStringChecker::CheckOverlap(CheckerContext &C,

                                             ProgramStateRef state,

                                             SizeArgExpr Size, AnyArgExpr First,

                                             AnyArgExpr Second) const {

  if (!Filter.CheckCStringBufferOverlap)

    return state;

  // Do a simple check for overlap: if the two arguments are from the same

  // buffer, see if the end of the first is greater than the start of the second

  // or vice versa.

  // If a previous check has failed, propagate the failure.

  if (!state)

    return nullptr;

  ProgramStateRef stateTrue, stateFalse;

  // Get the buffer values and make sure they're known locations.

  const LocationContext *LCtx = C.getLocationContext();

  SVal firstVal = state->getSVal(First.Expression, LCtx);

  SVal secondVal = state->getSVal(Second.Expression, LCtx);

  Optional<Loc> firstLoc = firstVal.getAs<Loc>();

  if (!firstLoc)

    return state;

  Optional<Loc> secondLoc = secondVal.getAs<Loc>();

  if (!secondLoc)

    return state;

  // Are the two values the same?

  SValBuilder &svalBuilder = C.getSValBuilder();

  std::tie(stateTrue, stateFalse) =

      state->assume(svalBuilder.evalEQ(state, *firstLoc, *secondLoc));

  if (stateTrue && 
!stateFalse49
) {

    // If the values are known to be equal, that's automatically an overlap.

    emitOverlapBug(C, stateTrue, First.Expression, Second.Expression);

    return nullptr;

  }

  // assume the two expressions are not equal.

  assert(stateFalse);

  state = stateFalse;

  // Which value comes first?

  QualType cmpTy = svalBuilder.getConditionType();

  SVal reverse =

      svalBuilder.evalBinOpLL(state, BO_GT, *firstLoc, *secondLoc, cmpTy);

  Optional<DefinedOrUnknownSVal> reverseTest =

      reverse.getAs<DefinedOrUnknownSVal>();

  if (!reverseTest)

    return state;

  std::tie(stateTrue, stateFalse) = state->assume(*reverseTest);

  if (stateTrue) {

    if (stateFalse) {

      // If we don't know which one comes first, we can't perform this test.

      return state;

    } else {

      // Switch the values so that firstVal is before secondVal.

      std::swap(firstLoc, secondLoc);

      // Switch the Exprs as well, so that they still correspond.

      std::swap(First, Second);

    }

  }

  // Get the length, and make sure it too is known.

  SVal LengthVal = state->getSVal(Size.Expression, LCtx);

  Optional<NonLoc> Length = LengthVal.getAs<NonLoc>();

  if (!Length)

    return state;

  // Convert the first buffer's start address to char*.

  // Bail out if the cast fails.

  ASTContext &Ctx = svalBuilder.getContext();

  QualType CharPtrTy = Ctx.getPointerType(Ctx.CharTy);

  SVal FirstStart =

      svalBuilder.evalCast(*firstLoc, CharPtrTy, First.Expression->getType());

  Optional<Loc> FirstStartLoc = FirstStart.getAs<Loc>();

  if (!FirstStartLoc)

    return state;

  // Compute the end of the first buffer. Bail out if THAT fails.

  SVal FirstEnd = svalBuilder.evalBinOpLN(state, BO_Add, *FirstStartLoc,

                                          *Length, CharPtrTy);

  Optional<Loc> FirstEndLoc = FirstEnd.getAs<Loc>();

  if (!FirstEndLoc)

    return state;

  // Is the end of the first buffer past the start of the second buffer?

  SVal Overlap =

      svalBuilder.evalBinOpLL(state, BO_GT, *FirstEndLoc, *secondLoc, cmpTy);

  Optional<DefinedOrUnknownSVal> OverlapTest =

      Overlap.getAs<DefinedOrUnknownSVal>();

  if (!OverlapTest)

    return state;

  std::tie(stateTrue, stateFalse) = state->assume(*OverlapTest);

  if (stateTrue && 
!stateFalse17
) {

    // Overlap!

    emitOverlapBug(C, stateTrue, First.Expression, Second.Expression);

    return nullptr;

  }

  // assume the two expressions don't overlap.

  assert(stateFalse);

  return stateFalse;

}

void CStringChecker::emitOverlapBug(CheckerContext &C, ProgramStateRef state,

                                  const Stmt *First, const Stmt *Second) const {

  ExplodedNode *N = C.generateErrorNode(state);

  if (!N)

    return;

  if (!BT_Overlap)

    BT_Overlap.reset(new BugType(Filter.CheckNameCStringBufferOverlap,

                                 categories::UnixAPI, "Improper arguments"));

  // Generate a report for this bug.

  auto report = std::make_unique<PathSensitiveBugReport>(

      *BT_Overlap, "Arguments must not be overlapping buffers", N);

  report->addRange(First->getSourceRange());

  report->addRange(Second->getSourceRange());

  C.emitReport(std::move(report));

}

void CStringChecker::emitNullArgBug(CheckerContext &C, ProgramStateRef State,

                                    const Stmt *S, StringRef WarningMsg) const {

  if (ExplodedNode *N = C.generateErrorNode(State)) {

    if (!BT_Null)

      BT_Null.reset(new BuiltinBug(

          Filter.CheckNameCStringNullArg, categories::UnixAPI,

          "Null pointer argument in call to byte string function"));

    BuiltinBug *BT = static_cast<BuiltinBug *>(BT_Null.get());

    auto Report = std::make_unique<PathSensitiveBugReport>(*BT, WarningMsg, N);

    Report->addRange(S->getSourceRange());

    if (const auto *Ex = dyn_cast<Expr>(S))

      bugreporter::trackExpressionValue(N, Ex, *Report);

    C.emitReport(std::move(Report));

  }

}

void CStringChecker::emitOutOfBoundsBug(CheckerContext &C,

                                        ProgramStateRef State, const Stmt *S,

                                        StringRef WarningMsg) const {

  if (ExplodedNode *N = C.generateErrorNode(State)) {

    if (!BT_Bounds)

      BT_Bounds.reset(new BuiltinBug(

          Filter.CheckCStringOutOfBounds ? Filter.CheckNameCStringOutOfBounds

                                         : Filter.CheckNameCStringNullArg,

          "Out-of-bound array access",

          "Byte string function accesses out-of-bound array element"));

    BuiltinBug *BT = static_cast<BuiltinBug *>(BT_Bounds.get());

    // FIXME: It would be nice to eventually make this diagnostic more clear,

    // e.g., by referencing the original declaration or by saying *why* this

    // reference is outside the range.

    auto Report = std::make_unique<PathSensitiveBugReport>(*BT, WarningMsg, N);

    Report->addRange(S->getSourceRange());

    C.emitReport(std::move(Report));

  }

}

void CStringChecker::emitNotCStringBug(CheckerContext &C, ProgramStateRef State,

                                       const Stmt *S,

                                       StringRef WarningMsg) const {

  if (ExplodedNode *N = C.generateNonFatalErrorNode(State)) {

    if (!BT_NotCString)

      BT_NotCString.reset(new BuiltinBug(

          Filter.CheckNameCStringNotNullTerm, categories::UnixAPI,

          "Argument is not a null-terminated string."));

    auto Report =

        std::make_unique<PathSensitiveBugReport>(*BT_NotCString, WarningMsg, N);

    Report->addRange(S->getSourceRange());

    C.emitReport(std::move(Report));

  }

}

void CStringChecker::emitAdditionOverflowBug(CheckerContext &C,

                                             ProgramStateRef State) const {

  if (ExplodedNode *N = C.generateErrorNode(State)) {

    if (!BT_NotCString)

      BT_NotCString.reset(

          new BuiltinBug(Filter.CheckNameCStringOutOfBounds, "API",

                         "Sum of expressions causes overflow."));

    // This isn't a great error message, but this should never occur in real

    // code anyway -- you'd have to create a buffer longer than a size_t can

    // represent, which is sort of a contradiction.

    const char *WarningMsg =

        "This expression will create a string whose length is too big to "

        "be represented as a size_t";

    auto Report =

        std::make_unique<PathSensitiveBugReport>(*BT_NotCString, WarningMsg, N);

    C.emitReport(std::move(Report));

  }

}

ProgramStateRef CStringChecker::checkAdditionOverflow(CheckerContext &C,

                                                     ProgramStateRef state,

                                                     NonLoc left,

                                                     NonLoc right) const {

  // If out-of-bounds checking is turned off, skip the rest.

  if (!Filter.CheckCStringOutOfBounds)

    return state;

  // If a previous check has failed, propagate the failure.

  if (!state)

    return nullptr;

  SValBuilder &svalBuilder = C.getSValBuilder();

  BasicValueFactory &BVF = svalBuilder.getBasicValueFactory();

  QualType sizeTy = svalBuilder.getContext().getSizeType();

  const llvm::APSInt &maxValInt = BVF.getMaxValue(sizeTy);

  NonLoc maxVal = svalBuilder.makeIntVal(maxValInt);

  SVal maxMinusRight;

  if (right.getAs<nonloc::ConcreteInt>()) {

    maxMinusRight = svalBuilder.evalBinOpNN(state, BO_Sub, maxVal, right,

                                                 sizeTy);

  } else {

    // Try switching the operands. (The order of these two assignments is

    // important!)

    maxMinusRight = svalBuilder.evalBinOpNN(state, BO_Sub, maxVal, left,

                                            sizeTy);

    left = right;

  }

  if (Optional<NonLoc> maxMinusRightNL = maxMinusRight.getAs<NonLoc>()) {

    QualType cmpTy = svalBuilder.getConditionType();

    // If left > max - right, we have an overflow.

    SVal willOverflow = svalBuilder.evalBinOpNN(state, BO_GT, left,

                                                *maxMinusRightNL, cmpTy);

    ProgramStateRef stateOverflow, stateOkay;

    std::tie(stateOverflow, stateOkay) =

      state->assume(willOverflow.castAs<DefinedOrUnknownSVal>());

    if (stateOverflow && 
!stateOkay0
) {

      // We have an overflow. Emit a bug report.

      emitAdditionOverflowBug(C, stateOverflow);

      return nullptr;

    }

    // From now on, assume an overflow didn't occur.

    assert(stateOkay);

    state = stateOkay;

  }

  return state;

}

ProgramStateRef CStringChecker::setCStringLength(ProgramStateRef state,

                                                const MemRegion *MR,

                                                SVal strLength) {

  assert(!strLength.isUndef() && "Attempt to set an undefined string length");

  MR = MR->StripCasts();

  switch (MR->getKind()) {

  case MemRegion::StringRegionKind:

    // FIXME: This can happen if we strcpy() into a string region. This is

    // undefined [C99 6.4.5p6], but we should still warn about it.

    return state;

  case MemRegion::SymbolicRegionKind:

  case MemRegion::AllocaRegionKind:

  case MemRegion::NonParamVarRegionKind:

  case MemRegion::ParamVarRegionKind:

  case MemRegion::FieldRegionKind:

  case MemRegion::ObjCIvarRegionKind:

    // These are the types we can currently track string lengths for.

    break;

  case MemRegion::ElementRegionKind:

    // FIXME: Handle element regions by upper-bounding the parent region's

    // string length.

    return state;

  default:

    // Other regions (mostly non-data) can't have a reliable C string length.

    // For now, just ignore the change.

    // FIXME: These are rare but not impossible. We should output some kind of

    // warning for things like strcpy((char[]){'a', 0}, "b");

    return state;

  }

  if (strLength.isUnknown())

    return state->remove<CStringLength>(MR);

  return state->set<CStringLength>(MR, strLength);

}

SVal CStringChecker::getCStringLengthForRegion(CheckerContext &C,

                                               ProgramStateRef &state,

                                               const Expr *Ex,

                                               const MemRegion *MR,

                                               bool hypothetical) {

  if (!hypothetical) {

    // If there's a recorded length, go ahead and return it.

    const SVal *Recorded = state->get<CStringLength>(MR);

    if (Recorded)

      return *Recorded;

  }

  // Otherwise, get a new symbol and update the state.

  SValBuilder &svalBuilder = C.getSValBuilder();

  QualType sizeTy = svalBuilder.getContext().getSizeType();

  SVal strLength = svalBuilder.getMetadataSymbolVal(CStringChecker::getTag(),

                                                    MR, Ex, sizeTy,

                                                    C.getLocationContext(),

                                                    C.blockCount());

  if (!hypothetical) {

    if (Optional<NonLoc> strLn = strLength.getAs<NonLoc>()) {

      // In case of unbounded calls strlen etc bound the range to SIZE_MAX/4

      BasicValueFactory &BVF = svalBuilder.getBasicValueFactory();

      const llvm::APSInt &maxValInt = BVF.getMaxValue(sizeTy);

      llvm::APSInt fourInt = APSIntType(maxValInt).getValue(4);

      const llvm::APSInt *maxLengthInt = BVF.evalAPSInt(BO_Div, maxValInt,

                                                        fourInt);

      NonLoc maxLength = svalBuilder.makeIntVal(*maxLengthInt);

      SVal evalLength = svalBuilder.evalBinOpNN(state, BO_LE, *strLn,

                                                maxLength, sizeTy);

      state = state->assume(evalLength.castAs<DefinedOrUnknownSVal>(), true);

    }

    state = state->set<CStringLength>(MR, strLength);

  }

  return strLength;

}

SVal CStringChecker::getCStringLength(CheckerContext &C, ProgramStateRef &state,

                                      const Expr *Ex, SVal Buf,

                                      bool hypothetical) const {

  const MemRegion *MR = Buf.getAsRegion();

  if (!MR) {

    // If we can't get a region, see if it's something we /know/ isn't a

    // C string. In the context of locations, the only time we can issue such

    // a warning is for labels.

    if (Optional<loc::GotoLabel> Label = Buf.getAs<loc::GotoLabel>()) {

      if (Filter.CheckCStringNotNullTerm) {

        SmallString<120> buf;

        llvm::raw_svector_ostream os(buf);

        assert(CurrentFunctionDescription);

        os << "Argument to " << CurrentFunctionDescription

           << " is the address of the label '" << Label->getLabel()->getName()

           << "', which is not a null-terminated string";

        emitNotCStringBug(C, state, Ex, os.str());

      }

      return UndefinedVal();

    }

    // If it's not a region and not a label, give up.

    return UnknownVal();

  }

  // If we have a region, strip casts from it and see if we can figure out

  // its length. For anything we can't figure out, just return UnknownVal.

  MR = MR->StripCasts();

  switch (MR->getKind()) {

  case MemRegion::StringRegionKind: {

    // Modifying the contents of string regions is undefined [C99 6.4.5p6],

    // so we can assume that the byte length is the correct C string length.

    SValBuilder &svalBuilder = C.getSValBuilder();

    QualType sizeTy = svalBuilder.getContext().getSizeType();

    const StringLiteral *strLit = cast<StringRegion>(MR)->getStringLiteral();

    return svalBuilder.makeIntVal(strLit->getByteLength(), sizeTy);

  }

  case MemRegion::SymbolicRegionKind:

  case MemRegion::AllocaRegionKind:

  case MemRegion::NonParamVarRegionKind:

  case MemRegion::ParamVarRegionKind:

  case MemRegion::FieldRegionKind:

  case MemRegion::ObjCIvarRegionKind:

    return getCStringLengthForRegion(C, state, Ex, MR, hypothetical);

  case MemRegion::CompoundLiteralRegionKind:

    // FIXME: Can we track this? Is it necessary?

    return UnknownVal();

  case MemRegion::ElementRegionKind:

    // FIXME: How can we handle this? It's not good enough to subtract the

    // offset from the base string length; consider "123\x00567" and &a[5].

    return UnknownVal();

  default:

    // Other regions (mostly non-data) can't have a reliable C string length.

    // In this case, an error is emitted and UndefinedVal is returned.

    // The caller should always be prepared to handle this case.

    if (Filter.CheckCStringNotNullTerm) {

      SmallString<120> buf;

      llvm::raw_svector_ostream os(buf);

      assert(CurrentFunctionDescription);

      os << "Argument to " << CurrentFunctionDescription << " is ";

      if (SummarizeRegion(os, C.getASTContext(), MR))

        os << ", which is not a null-terminated string";

      else

        os << "not a null-terminated string";

      emitNotCStringBug(C, state, Ex, os.str());

    }

    return UndefinedVal();

  }

}

const StringLiteral *CStringChecker::getCStringLiteral(CheckerContext &C,

  ProgramStateRef &state, const Expr *expr, SVal val) const {

  // Get the memory region pointed to by the val.

  const MemRegion *bufRegion = val.getAsRegion();

  if (!bufRegion)

    return nullptr;

  // Strip casts off the memory region.

  bufRegion = bufRegion->StripCasts();

  // Cast the memory region to a string region.

  const StringRegion *strRegion= dyn_cast<StringRegion>(bufRegion);

  if (!strRegion)

    return nullptr;

  // Return the actual string in the string region.

  return strRegion->getStringLiteral();

}

bool CStringChecker::IsFirstBufInBound(CheckerContext &C,

                                       ProgramStateRef state,

                                       const Expr *FirstBuf,

                                       const Expr *Size) {

  // If we do not know that the buffer is long enough we return 'true'.

  // Otherwise the parent region of this field region would also get

  // invalidated, which would lead to warnings based on an unknown state.

  // Originally copied from CheckBufferAccess and CheckLocation.

  SValBuilder &svalBuilder = C.getSValBuilder();

  ASTContext &Ctx = svalBuilder.getContext();

  const LocationContext *LCtx = C.getLocationContext();

  QualType sizeTy = Size->getType();

  QualType PtrTy = Ctx.getPointerType(Ctx.CharTy);

  SVal BufVal = state->getSVal(FirstBuf, LCtx);

  SVal LengthVal = state->getSVal(Size, LCtx);

  Optional<NonLoc> Length = LengthVal.getAs<NonLoc>();

  if (!Length)

    return true; // cf top comment.

  // Compute the offset of the last element to be accessed: size-1.

  NonLoc One = svalBuilder.makeIntVal(1, sizeTy).castAs<NonLoc>();

  SVal Offset = svalBuilder.evalBinOpNN(state, BO_Sub, *Length, One, sizeTy);

  if (Offset.isUnknown())

    return true; // cf top comment

  NonLoc LastOffset = Offset.castAs<NonLoc>();

  // Check that the first buffer is sufficiently long.

  SVal BufStart = svalBuilder.evalCast(BufVal, PtrTy, FirstBuf->getType());

  Optional<Loc> BufLoc = BufStart.getAs<Loc>();

  if (!BufLoc)

    return true; // cf top comment.

  SVal BufEnd =

      svalBuilder.evalBinOpLN(state, BO_Add, *BufLoc, LastOffset, PtrTy);

  // Check for out of bound array element access.

  const MemRegion *R = BufEnd.getAsRegion();

  if (!R)

    return true; // cf top comment.

  const ElementRegion *ER = dyn_cast<ElementRegion>(R);

  if (!ER)

    return true; // cf top comment.

  // FIXME: Does this crash when a non-standard definition

  // of a library function is encountered?

  assert(ER->getValueType() == C.getASTContext().CharTy &&

         "IsFirstBufInBound should only be called with char* ElementRegions");

  // Get the size of the array.

  const SubRegion *superReg = cast<SubRegion>(ER->getSuperRegion());

  DefinedOrUnknownSVal SizeDV = getDynamicSize(state, superReg, svalBuilder);

  // Get the index of the accessed element.

  DefinedOrUnknownSVal Idx = ER->getIndex().castAs<DefinedOrUnknownSVal>();

  ProgramStateRef StInBound = state->assumeInBound(Idx, SizeDV, true);

  return static_cast<bool>(StInBound);

}

ProgramStateRef CStringChecker::InvalidateBuffer(CheckerContext &C,

                                                 ProgramStateRef state,

                                                 const Expr *E, SVal V,

                                                 bool IsSourceBuffer,

                                                 const Expr *Size) {

  Optional<Loc> L = V.getAs<Loc>();

  if (!L)

    return state;

  // FIXME: This is a simplified version of what's in CFRefCount.cpp -- it makes

  // some assumptions about the value that CFRefCount can't. Even so, it should

  // probably be refactored.

  if (Optional<loc::MemRegionVal> MR = L->getAs<loc::MemRegionVal>()) {

    const MemRegion *R = MR->getRegion()->StripCasts();

    // Are we dealing with an ElementRegion?  If so, we should be invalidating

    // the super-region.

    if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {

      R = ER->getSuperRegion();

      // FIXME: What about layers of ElementRegions?

    }

    // Invalidate this region.

    const LocationContext *LCtx = C.getPredecessor()->getLocationContext();

    bool CausesPointerEscape = false;

    RegionAndSymbolInvalidationTraits ITraits;

    // Invalidate and escape only indirect regions accessible through the source

    // buffer.

    if (IsSourceBuffer) {

      ITraits.setTrait(R->getBaseRegion(),

                       RegionAndSymbolInvalidationTraits::TK_PreserveContents);

      ITraits.setTrait(R, RegionAndSymbolInvalidationTraits::TK_SuppressEscape);

      CausesPointerEscape = true;

    } else {

      const MemRegion::Kind& K = R->getKind();

      if (K == MemRegion::FieldRegionKind)

        if (Size && IsFirstBufInBound(C, state, E, Size)) {

          // If destination buffer is a field region and access is in bound,

          // do not invalidate its super region.

          ITraits.setTrait(

              R,

              RegionAndSymbolInvalidationTraits::TK_DoNotInvalidateSuperRegion);

        }

    }

    return state->invalidateRegions(R, E, C.blockCount(), LCtx,

                                    CausesPointerEscape, nullptr, nullptr,

                                    &ITraits);

  }

  // If we have a non-region value by chance, just remove the binding.

  // FIXME: is this necessary or correct? This handles the non-Region

  //  cases.  Is it ever valid to store to these?

  return state->killBinding(*L);

}

bool CStringChecker::SummarizeRegion(raw_ostream &os, ASTContext &Ctx,

                                     const MemRegion *MR) {

  switch (MR->getKind()) {

  case MemRegion::FunctionCodeRegionKind: {

    if (const auto *FD = cast<FunctionCodeRegion>(MR)->getDecl())

      os << "the address of the function '" << *FD << '\'';

    else

      os << "the address of a function";

    return true;

  }

  case MemRegion::BlockCodeRegionKind:

    os << "block text";

    return true;

  case MemRegion::BlockDataRegionKind:

    os << "a block";

    return true;

  case MemRegion::CXXThisRegionKind:

  case MemRegion::CXXTempObjectRegionKind:

    os << "a C++ temp object of type "

       << cast<TypedValueRegion>(MR)->getValueType().getAsString();

    return true;

  case MemRegion::NonParamVarRegionKind:

    os << "a variable of type"

       << cast<TypedValueRegion>(MR)->getValueType().getAsString();

    return true;

  case MemRegion::ParamVarRegionKind:

    os << "a parameter of type"

       << cast<TypedValueRegion>(MR)->getValueType().getAsString();

    return true;

  case MemRegion::FieldRegionKind:

    os << "a field of type "

       << cast<TypedValueRegion>(MR)->getValueType().getAsString();

    return true;

  case MemRegion::ObjCIvarRegionKind:

    os << "an instance variable of type "

       << cast<TypedValueRegion>(MR)->getValueType().getAsString();

    return true;

  default:

    return false;

  }

}

bool CStringChecker::memsetAux(const Expr *DstBuffer, SVal CharVal,

                               const Expr *Size, CheckerContext &C,