path: root/lib/Checker/CStringChecker.cpp

//= CStringChecker.h - Checks calls to C string functions ----------*- C++ -*-//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This defines CStringChecker, which is an assortment of checks on calls
// to functions in <string.h>.
//
//===----------------------------------------------------------------------===//

#include "GRExprEngineExperimentalChecks.h"
#include "clang/Checker/BugReporter/BugType.h"
#include "clang/Checker/PathSensitive/CheckerVisitor.h"
#include "llvm/ADT/StringSwitch.h"

using namespace clang;

namespace {
class CStringChecker : public CheckerVisitor<CStringChecker> {
  BugType *BT_Bounds;
  BugType *BT_Overlap;
public:
  CStringChecker()
  : BT_Bounds(0), BT_Overlap(0) {}
  static void *getTag() { static int tag; return &tag; }

  bool EvalCallExpr(CheckerContext &C, const CallExpr *CE);

  typedef const GRState *(CStringChecker::*FnCheck)(CheckerContext &,
                                                    const CallExpr *);

  const GRState *EvalMemcpy(CheckerContext &C, const CallExpr *CE);
  const GRState *EvalMemmove(CheckerContext &C, const CallExpr *CE);
  const GRState *EvalMemcmp(CheckerContext &C, const CallExpr *CE);
  const GRState *EvalBcopy(CheckerContext &C, const CallExpr *CE);

  // Utility methods
  const GRState *CheckNonNull(CheckerContext &C, const GRState *state,
                               const Stmt *S, SVal l);
  const GRState *CheckLocation(CheckerContext &C, const GRState *state,
                               const Stmt *S, SVal l);
  const GRState *CheckBufferAccess(CheckerContext &C, const GRState *state,
                                   const Expr *Size,
                                   const Expr *FirstBuf,
                                   const Expr *SecondBuf = NULL);
  const GRState *CheckOverlap(CheckerContext &C, const GRState *state,
                              const Expr *First, const Expr *Second,
                              const Expr *Size);
  void EmitOverlapBug(CheckerContext &C, const GRState *state,
                      const Stmt *First, const Stmt *Second);
};
} //end anonymous namespace

void clang::RegisterCStringChecker(GRExprEngine &Eng) {
  Eng.registerCheck(new CStringChecker());
}

const GRState *CStringChecker::CheckNonNull(CheckerContext &C,
                                            const GRState *state,
                                            const Stmt *S, SVal l) {
  // FIXME: This method just checks, of course, that the value is non-null.
  // It should maybe be refactored and combined with AttrNonNullChecker.
  if (l.isUnknownOrUndef())
    return state;

  ValueManager &ValMgr = C.getValueManager();
  SValuator &SV = ValMgr.getSValuator();

  Loc Null = ValMgr.makeNull();
  DefinedOrUnknownSVal LocIsNull = SV.EvalEQ(state, cast<Loc>(l), Null);

  const GRState *stateIsNull, *stateIsNonNull;
  llvm::tie(stateIsNull, stateIsNonNull) = state->Assume(LocIsNull);

  if (stateIsNull && !stateIsNonNull) {
    ExplodedNode *N = C.GenerateSink(stateIsNull);
    if (!N)
      return NULL;

    if (!BT_Bounds)
      BT_Bounds = new BuiltinBug("API",
        "Null pointer argument in call to byte string function");

    // Generate a report for this bug.
    BuiltinBug *BT = static_cast<BuiltinBug*>(BT_Bounds);
    EnhancedBugReport *report = new EnhancedBugReport(*BT,
                                                      BT->getDescription(), N);

    report->addRange(S->getSourceRange());
    report->addVisitorCreator(bugreporter::registerTrackNullOrUndefValue, S);
    C.EmitReport(report);
    return NULL;
  }

  // From here on, assume that the value is non-null.
  assert(stateIsNonNull);
  return stateIsNonNull;
}

// FIXME: This was originally copied from ArrayBoundChecker.cpp. Refactor?
const GRState *CStringChecker::CheckLocation(CheckerContext &C,
                                             const GRState *state,
                                             const Stmt *S, SVal l) {
  // Check for out of bound array element access.
  const MemRegion *R = l.getAsRegion();
  if (!R)
    return state;

  const ElementRegion *ER = dyn_cast<ElementRegion>(R);
  if (!ER)
    return state;

  assert(ER->getValueType(C.getASTContext()) == C.getASTContext().CharTy &&
    "CheckLocation should only be called with char* ElementRegions");

  // Get the size of the array.
  const SubRegion *Super = cast<SubRegion>(ER->getSuperRegion());
  ValueManager &ValMgr = C.getValueManager();
  SVal Extent = ValMgr.convertToArrayIndex(Super->getExtent(ValMgr));
  DefinedOrUnknownSVal Size = cast<DefinedOrUnknownSVal>(Extent);

  // Get the index of the accessed element.
  DefinedOrUnknownSVal &Idx = cast<DefinedOrUnknownSVal>(ER->getIndex());

  const GRState *StInBound = state->AssumeInBound(Idx, Size, true);
  const GRState *StOutBound = state->AssumeInBound(Idx, Size, false);
  if (StOutBound && !StInBound) {
    ExplodedNode *N = C.GenerateSink(StOutBound);
    if (!N)
      return NULL;

    if (!BT_Bounds)
      BT_Bounds = new BuiltinBug("Out-of-bound array access",
        "Byte string function accesses out-of-bound array element "
        "(buffer overflow)");

    // 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.

    // Generate a report for this bug.
    BuiltinBug *BT = static_cast<BuiltinBug*>(BT_Bounds);
    RangedBugReport *report = new RangedBugReport(*BT, BT->getDescription(), N);

    report->addRange(S->getSourceRange());
    C.EmitReport(report);
    return NULL;
  }
  
  // Array bound check succeeded.  From this point forward the array bound
  // should always succeed.
  return StInBound;
}

const GRState *CStringChecker::CheckBufferAccess(CheckerContext &C,
                                                 const GRState *state,
                                                 const Expr *Size,
                                                 const Expr *FirstBuf,
                                                 const Expr *SecondBuf) {
  ValueManager &VM = C.getValueManager();
  SValuator &SV = VM.getSValuator();
  ASTContext &Ctx = C.getASTContext();

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

  // Get the access length and make sure it is known.
  SVal LengthVal = state->getSVal(Size);
  NonLoc *Length = dyn_cast<NonLoc>(&LengthVal);
  if (!Length)
    return state;

  // If the length is zero, it doesn't matter what the two buffers are.
  DefinedOrUnknownSVal Zero = VM.makeZeroVal(SizeTy);
  DefinedOrUnknownSVal LengthIsZero = SV.EvalEQ(state, *Length, Zero);

  const GRState *stateZeroLength, *stateNonZeroLength;
  llvm::tie(stateZeroLength, stateNonZeroLength) = state->Assume(LengthIsZero);
  if (stateZeroLength && !stateNonZeroLength)
    return stateZeroLength;

  // FIXME: At this point all we know is it's *possible* for the length to be
  // nonzero; we don't know it for sure. Unfortunately, that means the next few
  // tests are incorrect for the edge cases in which a buffer is null or invalid
  // but the size argument was set to zero in some way that we couldn't track.
  // What we should really do is bifurcate the state here, but that doesn't
  // match the way CheckBufferAccess is being used.

  // From here on, we're going to pretend that even if the length is zero, the
  // buffer access rules still apply. That means the buffer must be non-NULL,
  // and the value at buffer[size-1] must be valid.

  // Check that the first buffer is non-null.
  SVal BufVal =<