BuiltinFunctionChecker.cpp

Go to the documentation of this file.

//=== BuiltinFunctionChecker.cpp --------------------------------*- 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 checker evaluates "standalone" clang builtin functions that are not
// just special-cased variants of well-known non-builtin functions.
// Builtin functions like __builtin_memcpy and __builtin_alloca should be
// evaluated by the same checker that handles their non-builtin variant to
// ensure that the two variants are handled consistently.
//
//===----------------------------------------------------------------------===//
 
#include "clang/Basic/Builtins.h"
#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
#include "clang/StaticAnalyzer/Checkers/Taint.h"
#include "clang/StaticAnalyzer/Core/Checker.h"
#include "clang/StaticAnalyzer/Core/CheckerManager.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
#include <algorithm>
 
using namespace clang;
using namespace ento;
using namespace taint;
 
namespace {
 
/// \return an integer type that is large enough for the binary operation on the
/// operands of \p Arg1Ty and \p Arg2Ty, respectively.
QualType getSufficientTypeForOverflowOp(CheckerContext &C,
                                        BinaryOperator::Opcode Op,
                                        QualType Arg1Ty, QualType Arg2Ty) {
  assert(Arg1Ty->isIntegerType() && Arg2Ty->isIntegerType());
 
  ASTContext &ACtx = C.getASTContext();
  unsigned BitWidth =
      std::max(ACtx.getIntWidth(Arg1Ty), ACtx.getIntWidth(Arg2Ty));
 
  // A signed type with doubled bits may not be large enough to hold the
  // multiplication result when both operands are unsigned. In other
  // words, if either operand is signed, a signed type with twice the bits is
  // sufficient.
  //
  // Additionally, subtraction always needs a signed result. Note that
  // subtracting a negative operand falls into the prior case, so it is still
  // safe with a signed result type. A signed 1-bit integer is not allowed in
  // Clang.
  bool UseSigned = Op == BO_Sub || Arg1Ty->isSignedIntegerType() ||
                   Arg2Ty->isSignedIntegerType();
  return ACtx.getBitIntType(/*Unsigned=*/!UseSigned, BitWidth * 2);
}
 
QualType getOverflowBuiltinResultType(const CallEvent &Call) {
  // Calling a builtin with an incorrect argument count produces compiler error.
  assert(Call.getNumArgs() == 3);
 
  return Call.getArgExpr(2)->getType()->getPointeeType();
}
 
QualType getOverflowBuiltinResultType(const CallEvent &Call, CheckerContext &C,
                                      unsigned BI) {
  // Calling a builtin with an incorrect argument count produces compiler error.
  assert(Call.getNumArgs() == 3);
 
  ASTContext &ACtx = C.getASTContext();
 
  switch (BI) {
  case Builtin::BI__builtin_smul_overflow:
  case Builtin::BI__builtin_ssub_overflow:
  case Builtin::BI__builtin_sadd_overflow:
    return ACtx.IntTy;
  case Builtin::BI__builtin_smull_overflow:
  case Builtin::BI__builtin_ssubl_overflow:
  case Builtin::BI__builtin_saddl_overflow:
    return ACtx.LongTy;
  case Builtin::BI__builtin_smulll_overflow:
  case Builtin::BI__builtin_ssubll_overflow:
  case Builtin::BI__builtin_saddll_overflow:
    return ACtx.LongLongTy;
  case Builtin::BI__builtin_umul_overflow:
  case Builtin::BI__builtin_usub_overflow:
  case Builtin::BI__builtin_uadd_overflow:
    return ACtx.UnsignedIntTy;
  case Builtin::BI__builtin_umull_overflow:
  case Builtin::BI__builtin_usubl_overflow:
  case Builtin::BI__builtin_uaddl_overflow:
    return ACtx.UnsignedLongTy;
  case Builtin::BI__builtin_umulll_overflow:
  case Builtin::BI__builtin_usubll_overflow:
  case Builtin::BI__builtin_uaddll_overflow:
    return ACtx.UnsignedLongLongTy;
  case Builtin::BI__builtin_mul_overflow:
  case Builtin::BI__builtin_sub_overflow:
  case Builtin::BI__builtin_add_overflow:
    return getOverflowBuiltinResultType(Call);
  default:
    assert(false && "Unknown overflow builtin");
    return ACtx.IntTy;
  }
}
 
class BuiltinFunctionChecker : public Checker<eval::Call> {
public:
  bool evalCall(const CallEvent &Call, CheckerContext &C) const;
  void handleOverflowBuiltin(const CallEvent &Call, CheckerContext &C,
                             BinaryOperator::Opcode Op,
                             QualType ResultType) const;
  const NoteTag *createBuiltinOverflowNoteTag(CheckerContext &C,
                                              bool BothFeasible, SVal Arg1,
                                              SVal Arg2, SVal Result) const;
  ProgramStateRef initStateAftetBuiltinOverflow(CheckerContext &C,
                                                ProgramStateRef State,
                                                const CallEvent &Call,
                                                SVal RetCal,
                                                bool IsOverflow) const;
  std::pair<bool, bool> checkOverflow(CheckerContext &C, SVal RetVal,
                                      QualType Res) const;
 
private:
  // From: clang/include/clang/Basic/Builtins.def
  // C++ standard library builtins in namespace 'std'.
  const CallDescriptionSet BuiltinLikeStdFunctions{
      {CDM::SimpleFunc, {"std", "addressof"}},        //
      {CDM::SimpleFunc, {"std", "__addressof"}},      //
      {CDM::SimpleFunc, {"std", "as_const"}},         //
      {CDM::SimpleFunc, {"std", "forward"}},          //
      {CDM::SimpleFunc, {"std", "forward_like"}},     //
      {CDM::SimpleFunc, {"std", "move"}},             //
      {CDM::SimpleFunc, {"std", "move_if_noexcept"}}, //
  };
 
  bool isBuiltinLikeFunction(const CallEvent &Call) const;
};
 
} // namespace
 
const NoteTag *BuiltinFunctionChecker::createBuiltinOverflowNoteTag(
    CheckerContext &C, bool overflow, SVal Arg1, SVal Arg2, SVal Result) const {
  return C.getNoteTag([Result, Arg1, Arg2, overflow](PathSensitiveBugReport &BR,
                                                     llvm::raw_ostream &OS) {
    if (!BR.isInteresting(Result))
      return;
 
    // Propagate interestingness to input arguments if result is interesting.
    BR.markInteresting(Arg1);
    BR.markInteresting(Arg2);
 
    if (overflow)
      OS << "Assuming overflow";
    else
      OS << "Assuming no overflow";
  });
}
 
std::pair<bool, bool>
BuiltinFunctionChecker::checkOverflow(CheckerContext &C, SVal RetVal,
                                      QualType Res) const {
  // Calling a builtin with a non-integer type result produces compiler error.
  assert(Res->isIntegerType());
 
  unsigned BitWidth = C.getASTContext().getIntWidth(Res);
  bool IsUnsigned = Res->isUnsignedIntegerType();
 
  SValBuilder &SVB = C.getSValBuilder();
  BasicValueFactory &VF = SVB.getBasicValueFactory();
 
  auto MinValType = llvm::APSInt::getMinValue(BitWidth, IsUnsigned);
  auto MaxValType = llvm::APSInt::getMaxValue(BitWidth, IsUnsigned);
  nonloc::ConcreteInt MinVal{VF.getValue(MinValType)};
  nonloc::ConcreteInt MaxVal{VF.getValue(MaxValType)};
 
  ProgramStateRef State = C.getState();
  SVal IsLeMax = SVB.evalBinOp(State, BO_LE, RetVal, MaxVal, Res);
  SVal IsGeMin = SVB.evalBinOp(State, BO_GE, RetVal, MinVal, Res);
 
  auto [MayNotOverflow, MayOverflow] =
      State->assume(IsLeMax.castAs<DefinedOrUnknownSVal>());
  auto [MayNotUnderflow, MayUnderflow] =
      State->assume(IsGeMin.castAs<DefinedOrUnknownSVal>());
 
  return {MayOverflow || MayUnderflow, MayNotOverflow && MayNotUnderflow};
}
 
ProgramStateRef BuiltinFunctionChecker::initStateAftetBuiltinOverflow(
    CheckerContext &C, ProgramStateRef State, const CallEvent &Call,
    SVal RetVal, bool IsOverflow) const {
  SValBuilder &SVB = C.getSValBuilder();
  SVal Arg1 = Call.getArgSVal(0);
  SVal Arg2 = Call.getArgSVal(1);
  auto BoolTy = C.getASTContext().BoolTy;
 
  ProgramStateRef NewState =
      State->BindExpr(Call.getOriginExpr(), C.getStackFrame(),
                      SVB.makeTruthVal(IsOverflow, BoolTy));
 
  if (auto L = Call.getArgSVal(2).getAs<Loc>()) {
    NewState = NewState->bindLoc(*L, RetVal, C.getStackFrame());
 
    // Propagate taint if any of the arguments were tainted
    if (isTainted(State, Arg1) || isTainted(State, Arg2))
      NewState = addTaint(NewState, *L);
  }
 
  return NewState;
}
 
void BuiltinFunctionChecker::handleOverflowBuiltin(const CallEvent &Call,
                                                   CheckerContext &C,
                                                   BinaryOperator::Opcode Op,
                                                   QualType ResultType) const {
  // Calling a builtin with an incorrect argument count produces compiler error.
  assert(Call.getNumArgs() == 3);
 
  ProgramStateRef State = C.getState();
  SValBuilder &SVB = C.getSValBuilder();
 
  SVal Arg1 = Call.getArgSVal(0);
  SVal Arg2 = Call.getArgSVal(1);
  QualType Arg1Ty = Call.getArgExpr(0)->getType();
  QualType Arg2Ty = Call.getArgExpr(1)->getType();
 
  QualType SufficientlyWideTy =
      getSufficientTypeForOverflowOp(C, Op, Arg1Ty, Arg2Ty);
  assert(!SufficientlyWideTy.isNull());
 
  SVal RetValMax = SVB.evalBinOp(State, Op, Arg1, Arg2, SufficientlyWideTy);
  SVal RetVal = SVB.evalBinOp(State, Op, Arg1, Arg2, ResultType);
 
  auto [Overflow, NotOverflow] = checkOverflow(C, RetValMax, ResultType);
 
  if (NotOverflow) {
    auto NewState =
        initStateAftetBuiltinOverflow(C, State, Call, RetVal, false);
 
    C.addTransition(NewState, createBuiltinOverflowNoteTag(
                                  C, /*overflow=*/false, Arg1, Arg2, RetVal));
  }
 
  if (Overflow) {
    auto NewState = initStateAftetBuiltinOverflow(C, State, Call, RetVal, true);
 
    C.addTransition(NewState, createBuiltinOverflowNoteTag(C, /*overflow=*/true,
                                                           Arg1, Arg2, RetVal));
  }
}
 
bool BuiltinFunctionChecker::isBuiltinLikeFunction(
    const CallEvent &Call) const {
  const auto *FD = llvm::dyn_cast_or_null<FunctionDecl>(Call.getDecl());
  if (!FD || FD->getNumParams() != 1)
    return false;
 
  if (QualType RetTy = FD->getReturnType();
      !RetTy->isPointerType() && !RetTy->isReferenceType())
    return false;
 
  if (QualType ParmTy = FD->getParamDecl(0)->getType();
      !ParmTy->isPointerType() && !ParmTy->isReferenceType())
    return false;
 
  return BuiltinLikeStdFunctions.contains(Call);
}
 
bool BuiltinFunctionChecker::evalCall(const CallEvent &Call,
                                      CheckerContext &C) const {
  ProgramStateRef state = C.getState();
  const auto *FD = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
  if (!FD)
    return false;
 
  const StackFrame *SF = C.getStackFrame();
  const Expr *CE = Call.getOriginExpr();
 
  if (isBuiltinLikeFunction(Call)) {
    C.addTransition(state->BindExpr(CE, SF, Call.getArgSVal(0)));
    return true;
  }
 
  unsigned BI = FD->getBuiltinID();
 
  switch (BI) {
  default:
    return false;
  case Builtin::BI__builtin_mul_overflow:
  case Builtin::BI__builtin_smul_overflow:
  case Builtin::BI__builtin_smull_overflow:
  case Builtin::BI__builtin_smulll_overflow:
  case Builtin::BI__builtin_umul_overflow:
  case Builtin::BI__builtin_umull_overflow:
  case Builtin::BI__builtin_umulll_overflow:
    handleOverflowBuiltin(Call, C, BO_Mul,
                          getOverflowBuiltinResultType(Call, C, BI));
    return true;
  case Builtin::BI__builtin_sub_overflow:
  case Builtin::BI__builtin_ssub_overflow:
  case Builtin::BI__builtin_ssubl_overflow:
  case Builtin::BI__builtin_ssubll_overflow:
  case Builtin::BI__builtin_usub_overflow:
  case Builtin::BI__builtin_usubl_overflow:
  case Builtin::BI__builtin_usubll_overflow:
    handleOverflowBuiltin(Call, C, BO_Sub,
                          getOverflowBuiltinResultType(Call, C, BI));
    return true;
  case Builtin::BI__builtin_add_overflow:
  case Builtin::BI__builtin_sadd_overflow:
  case Builtin::BI__builtin_saddl_overflow:
  case Builtin::BI__builtin_saddll_overflow:
  case Builtin::BI__builtin_uadd_overflow:
  case Builtin::BI__builtin_uaddl_overflow:
  case Builtin::BI__builtin_uaddll_overflow:
    handleOverflowBuiltin(Call, C, BO_Add,
                          getOverflowBuiltinResultType(Call, C, BI));
    return true;
  case Builtin::BI__builtin_unpredictable:
  case Builtin::BI__builtin_expect:
  case Builtin::BI__builtin_expect_with_probability:
  case Builtin::BI__builtin_assume_aligned:
  case Builtin::BI__builtin_addressof:
  case Builtin::BI__builtin_function_start: {
    // For __builtin_unpredictable, __builtin_expect,
    // __builtin_expect_with_probability and __builtin_assume_aligned,
    // just return the value of the subexpression.
    // __builtin_addressof is going from a reference to a pointer, but those
    // are represented the same way in the analyzer.
    assert (Call.getNumArgs() > 0);
    SVal Arg = Call.getArgSVal(0);
    C.addTransition(state->BindExpr(CE, SF, Arg));
    return true;
  }
 
  case Builtin::BI__builtin_dynamic_object_size:
  case Builtin::BI__builtin_object_size:
  case Builtin::BI__builtin_constant_p: {
    // This must be resolvable at compile time, so we defer to the constant
    // evaluator for a value.
    SValBuilder &SVB = C.getSValBuilder();
    SVal V = UnknownVal();
    Expr::EvalResult EVResult;
    if (CE->EvaluateAsInt(EVResult, C.getASTContext(), Expr::SE_NoSideEffects)) {
      // Make sure the result has the correct type.
      llvm::APSInt Result = EVResult.Val.getInt();
      BasicValueFactory &BVF = SVB.getBasicValueFactory();
      BVF.getAPSIntType(CE->getType()).apply(Result);
      V = SVB.makeIntVal(Result);
    }
 
    if (FD->getBuiltinID() == Builtin::BI__builtin_constant_p) {
      // If we didn't manage to figure out if the value is constant or not,
      // it is safe to assume that it's not constant and unsafe to assume
      // that it's constant.
      if (V.isUnknown())
        V = SVB.makeIntVal(0, CE->getType());
    }
 
    C.addTransition(state->BindExpr(CE, SF, V));
    return true;
  }
  }
}
 
void ento::registerBuiltinFunctionChecker(CheckerManager &mgr) {
  mgr.registerChecker<BuiltinFunctionChecker>();
}
 
bool ento::shouldRegisterBuiltinFunctionChecker(const CheckerManager &mgr) {
  return true;
}