clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp

   1 //=== BuiltinFunctionChecker.cpp --------------------------------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This checker evaluates "standalone" clang builtin functions that are not
  10 // just special-cased variants of well-known non-builtin functions.
  11 // Builtin functions like __builtin_memcpy and __builtin_alloca should be
  12 // evaluated by the same checker that handles their non-builtin variant to
  13 // ensure that the two variants are handled consistently.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #include "clang/Basic/Builtins.h"
  18 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
  19 #include "clang/StaticAnalyzer/Checkers/Taint.h"
  20 #include "clang/StaticAnalyzer/Core/Checker.h"
  21 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
  22 #include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h"
  23 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
  24 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
  25 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h"
  26 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicExtent.h"
  27 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
  28
  29 using namespace clang;
  30 using namespace ento;
  31 using namespace taint;
  32
  33 namespace {
  34
  35 QualType getSufficientTypeForOverflowOp(CheckerContext &C, const QualType &T) {
  36   // Calling a builtin with a non-integer type result produces compiler error.
  37   assert(T->isIntegerType());
  38
  39   ASTContext &ACtx = C.getASTContext();
  40
  41   unsigned BitWidth = ACtx.getIntWidth(T);
  42   return ACtx.getIntTypeForBitwidth(BitWidth * 2, T->isSignedIntegerType());
  43 }
  44
  45 QualType getOverflowBuiltinResultType(const CallEvent &Call) {
  46   // Calling a builtin with an incorrect argument count produces compiler error.
  47   assert(Call.getNumArgs() == 3);
  48
  49   return Call.getArgExpr(2)->getType()->getPointeeType();
  50 }
  51
  52 QualType getOverflowBuiltinResultType(const CallEvent &Call, CheckerContext &C,
  53                                       unsigned BI) {
  54   // Calling a builtin with an incorrect argument count produces compiler error.
  55   assert(Call.getNumArgs() == 3);
  56
  57   ASTContext &ACtx = C.getASTContext();
  58
  59   switch (BI) {
  60   case Builtin::BI__builtin_smul_overflow:
  61   case Builtin::BI__builtin_ssub_overflow:
  62   case Builtin::BI__builtin_sadd_overflow:
  63     return ACtx.IntTy;
  64   case Builtin::BI__builtin_smull_overflow:
  65   case Builtin::BI__builtin_ssubl_overflow:
  66   case Builtin::BI__builtin_saddl_overflow:
  67     return ACtx.LongTy;
  68   case Builtin::BI__builtin_smulll_overflow:
  69   case Builtin::BI__builtin_ssubll_overflow:
  70   case Builtin::BI__builtin_saddll_overflow:
  71     return ACtx.LongLongTy;
  72   case Builtin::BI__builtin_umul_overflow:
  73   case Builtin::BI__builtin_usub_overflow:
  74   case Builtin::BI__builtin_uadd_overflow:
  75     return ACtx.UnsignedIntTy;
  76   case Builtin::BI__builtin_umull_overflow:
  77   case Builtin::BI__builtin_usubl_overflow:
  78   case Builtin::BI__builtin_uaddl_overflow:
  79     return ACtx.UnsignedLongTy;
  80   case Builtin::BI__builtin_umulll_overflow:
  81   case Builtin::BI__builtin_usubll_overflow:
  82   case Builtin::BI__builtin_uaddll_overflow:
  83     return ACtx.UnsignedLongLongTy;
  84   case Builtin::BI__builtin_mul_overflow:
  85   case Builtin::BI__builtin_sub_overflow:
  86   case Builtin::BI__builtin_add_overflow:
  87     return getOverflowBuiltinResultType(Call);
  88   default:
  89     assert(false && "Unknown overflow builtin");
  90     return ACtx.IntTy;
  91   }
  92 }
  93
  94 class BuiltinFunctionChecker : public Checker<eval::Call> {
  95 public:
  96   bool evalCall(const CallEvent &Call, CheckerContext &C) const;
  97   void handleOverflowBuiltin(const CallEvent &Call, CheckerContext &C,
  98                              BinaryOperator::Opcode Op,
  99                              QualType ResultType) const;
 100   const NoteTag *createBuiltinNoOverflowNoteTag(CheckerContext &C,
 101                                                 bool BothFeasible, SVal Arg1,
 102                                                 SVal Arg2, SVal Result) const;
 103   const NoteTag *createBuiltinOverflowNoteTag(CheckerContext &C) const;
 104   std::pair<bool, bool> checkOverflow(CheckerContext &C, SVal RetVal,
 105                                       QualType Res) const;
 106
 107 private:
 108   // From: clang/include/clang/Basic/Builtins.def
 109   // C++ standard library builtins in namespace 'std'.
 110   const CallDescriptionSet BuiltinLikeStdFunctions{
 111       {CDM::SimpleFunc, {"std", "addressof"}},        //
 112       {CDM::SimpleFunc, {"std", "__addressof"}},      //
 113       {CDM::SimpleFunc, {"std", "as_const"}},         //
 114       {CDM::SimpleFunc, {"std", "forward"}},          //
 115       {CDM::SimpleFunc, {"std", "forward_like"}},     //
 116       {CDM::SimpleFunc, {"std", "move"}},             //
 117       {CDM::SimpleFunc, {"std", "move_if_noexcept"}}, //
 118   };
 119
 120   bool isBuiltinLikeFunction(const CallEvent &Call) const;
 121 };
 122
 123 } // namespace
 124
 125 const NoteTag *BuiltinFunctionChecker::createBuiltinNoOverflowNoteTag(
 126     CheckerContext &C, bool BothFeasible, SVal Arg1, SVal Arg2,
 127     SVal Result) const {
 128   return C.getNoteTag([Result, Arg1, Arg2, BothFeasible](
 129                           PathSensitiveBugReport &BR, llvm::raw_ostream &OS) {
 130     if (!BR.isInteresting(Result))
 131       return;
 132
 133     // Propagate interestingness to input argumets if result is interesting.
 134     BR.markInteresting(Arg1);
 135     BR.markInteresting(Arg2);
 136
 137     if (BothFeasible)
 138       OS << "Assuming no overflow";
 139   });
 140 }
 141
 142 const NoteTag *
 143 BuiltinFunctionChecker::createBuiltinOverflowNoteTag(CheckerContext &C) const {
 144   return C.getNoteTag([](PathSensitiveBugReport &BR,
 145                          llvm::raw_ostream &OS) { OS << "Assuming overflow"; },
 146                       /*isPrunable=*/true);
 147 }
 148
 149 std::pair<bool, bool>
 150 BuiltinFunctionChecker::checkOverflow(CheckerContext &C, SVal RetVal,
 151                                       QualType Res) const {
 152   // Calling a builtin with a non-integer type result produces compiler error.
 153   assert(Res->isIntegerType());
 154
 155   unsigned BitWidth = C.getASTContext().getIntWidth(Res);
 156   bool IsUnsigned = Res->isUnsignedIntegerType();
 157
 158   auto MinValType = llvm::APSInt::getMinValue(BitWidth, IsUnsigned);
 159   auto MaxValType = llvm::APSInt::getMaxValue(BitWidth, IsUnsigned);
 160   nonloc::ConcreteInt MinVal{MinValType};
 161   nonloc::ConcreteInt MaxVal{MaxValType};
 162
 163   SValBuilder &SVB = C.getSValBuilder();
 164   ProgramStateRef State = C.getState();
 165   SVal IsLeMax = SVB.evalBinOp(State, BO_LE, RetVal, MaxVal, Res);
 166   SVal IsGeMin = SVB.evalBinOp(State, BO_GE, RetVal, MinVal, Res);
 167
 168   auto [MayNotOverflow, MayOverflow] =
 169       State->assume(IsLeMax.castAs<DefinedOrUnknownSVal>());
 170   auto [MayNotUnderflow, MayUnderflow] =
 171       State->assume(IsGeMin.castAs<DefinedOrUnknownSVal>());
 172
 173   return {MayOverflow || MayUnderflow, MayNotOverflow && MayNotUnderflow};
 174 }
 175
 176 void BuiltinFunctionChecker::handleOverflowBuiltin(const CallEvent &Call,
 177                                                    CheckerContext &C,
 178                                                    BinaryOperator::Opcode Op,
 179                                                    QualType ResultType) const {
 180   // Calling a builtin with an incorrect argument count produces compiler error.
 181   assert(Call.getNumArgs() == 3);
 182
 183   ProgramStateRef State = C.getState();
 184   SValBuilder &SVB = C.getSValBuilder();
 185   const Expr *CE = Call.getOriginExpr();
 186   auto BoolTy = C.getASTContext().BoolTy;
 187
 188   SVal Arg1 = Call.getArgSVal(0);
 189   SVal Arg2 = Call.getArgSVal(1);
 190
 191   SVal RetValMax = SVB.evalBinOp(State, Op, Arg1, Arg2,
 192                                  getSufficientTypeForOverflowOp(C, ResultType));
 193   SVal RetVal = SVB.evalBinOp(State, Op, Arg1, Arg2, ResultType);
 194
 195   auto [Overflow, NotOverflow] = checkOverflow(C, RetValMax, ResultType);
 196   if (NotOverflow) {
 197     ProgramStateRef StateNoOverflow = State->BindExpr(
 198         CE, C.getLocationContext(), SVB.makeTruthVal(false, BoolTy));
 199
 200     if (auto L = Call.getArgSVal(2).getAs<Loc>()) {
 201       StateNoOverflow =
 202           StateNoOverflow->bindLoc(*L, RetVal, C.getLocationContext());
 203
 204       // Propagate taint if any of the argumets were tainted
 205       if (isTainted(State, Arg1) || isTainted(State, Arg2))
 206         StateNoOverflow = addTaint(StateNoOverflow, *L);
 207     }
 208
 209     C.addTransition(
 210         StateNoOverflow,
 211         createBuiltinNoOverflowNoteTag(
 212             C, /*BothFeasible=*/NotOverflow && Overflow, Arg1, Arg2, RetVal));
 213   }
 214
 215   if (Overflow) {
 216     C.addTransition(State->BindExpr(CE, C.getLocationContext(),
 217                                     SVB.makeTruthVal(true, BoolTy)),
 218                     createBuiltinOverflowNoteTag(C));
 219   }
 220 }
 221
 222 bool BuiltinFunctionChecker::isBuiltinLikeFunction(
 223     const CallEvent &Call) const {
 224   const auto *FD = llvm::dyn_cast_or_null<FunctionDecl>(Call.getDecl());
 225   if (!FD || FD->getNumParams() != 1)
 226     return false;
 227
 228   if (QualType RetTy = FD->getReturnType();
 229       !RetTy->isPointerType() && !RetTy->isReferenceType())
 230     return false;
 231
 232   if (QualType ParmTy = FD->getParamDecl(0)->getType();
 233       !ParmTy->isPointerType() && !ParmTy->isReferenceType())
 234     return false;
 235
 236   return BuiltinLikeStdFunctions.contains(Call);
 237 }
 238
 239 bool BuiltinFunctionChecker::evalCall(const CallEvent &Call,
 240                                       CheckerContext &C) const {
 241   ProgramStateRef state = C.getState();
 242   const auto *FD = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
 243   if (!FD)
 244     return false;
 245
 246   const LocationContext *LCtx = C.getLocationContext();
 247   const Expr *CE = Call.getOriginExpr();
 248
 249   if (isBuiltinLikeFunction(Call)) {
 250     C.addTransition(state->BindExpr(CE, LCtx, Call.getArgSVal(0)));
 251     return true;
 252   }
 253
 254   unsigned BI = FD->getBuiltinID();
 255
 256   switch (BI) {
 257   default:
 258     return false;
 259   case Builtin::BI__builtin_mul_overflow:
 260   case Builtin::BI__builtin_smul_overflow:
 261   case Builtin::BI__builtin_smull_overflow:
 262   case Builtin::BI__builtin_smulll_overflow:
 263   case Builtin::BI__builtin_umul_overflow:
 264   case Builtin::BI__builtin_umull_overflow:
 265   case Builtin::BI__builtin_umulll_overflow:
 266     handleOverflowBuiltin(Call, C, BO_Mul,
 267                           getOverflowBuiltinResultType(Call, C, BI));
 268     return true;
 269   case Builtin::BI__builtin_sub_overflow:
 270   case Builtin::BI__builtin_ssub_overflow:
 271   case Builtin::BI__builtin_ssubl_overflow:
 272   case Builtin::BI__builtin_ssubll_overflow:
 273   case Builtin::BI__builtin_usub_overflow:
 274   case Builtin::BI__builtin_usubl_overflow:
 275   case Builtin::BI__builtin_usubll_overflow:
 276     handleOverflowBuiltin(Call, C, BO_Sub,
 277                           getOverflowBuiltinResultType(Call, C, BI));
 278     return true;
 279   case Builtin::BI__builtin_add_overflow:
 280   case Builtin::BI__builtin_sadd_overflow:
 281   case Builtin::BI__builtin_saddl_overflow:
 282   case Builtin::BI__builtin_saddll_overflow:
 283   case Builtin::BI__builtin_uadd_overflow:
 284   case Builtin::BI__builtin_uaddl_overflow:
 285   case Builtin::BI__builtin_uaddll_overflow:
 286     handleOverflowBuiltin(Call, C, BO_Add,
 287                           getOverflowBuiltinResultType(Call, C, BI));
 288     return true;
 289   case Builtin::BI__builtin_assume:
 290   case Builtin::BI__assume: {
 291     assert (Call.getNumArgs() > 0);
 292     SVal Arg = Call.getArgSVal(0);
 293     if (Arg.isUndef())
 294       return true; // Return true to model purity.
 295
 296     state = state->assume(Arg.castAs<DefinedOrUnknownSVal>(), true);
 297     // FIXME: do we want to warn here? Not right now. The most reports might
 298     // come from infeasible paths, thus being false positives.
 299     if (!state) {
 300       C.generateSink(C.getState(), C.getPredecessor());
 301       return true;
 302     }
 303
 304     C.addTransition(state);
 305     return true;
 306   }
 307
 308   case Builtin::BI__builtin_unpredictable:
 309   case Builtin::BI__builtin_expect:
 310   case Builtin::BI__builtin_expect_with_probability:
 311   case Builtin::BI__builtin_assume_aligned:
 312   case Builtin::BI__builtin_addressof:
 313   case Builtin::BI__builtin_function_start: {
 314     // For __builtin_unpredictable, __builtin_expect,
 315     // __builtin_expect_with_probability and __builtin_assume_aligned,
 316     // just return the value of the subexpression.
 317     // __builtin_addressof is going from a reference to a pointer, but those
 318     // are represented the same way in the analyzer.
 319     assert (Call.getNumArgs() > 0);
 320     SVal Arg = Call.getArgSVal(0);
 321     C.addTransition(state->BindExpr(CE, LCtx, Arg));
 322     return true;
 323   }
 324
 325   case Builtin::BI__builtin_dynamic_object_size:
 326   case Builtin::BI__builtin_object_size:
 327   case Builtin::BI__builtin_constant_p: {
 328     // This must be resolvable at compile time, so we defer to the constant
 329     // evaluator for a value.
 330     SValBuilder &SVB = C.getSValBuilder();
 331     SVal V = UnknownVal();
 332     Expr::EvalResult EVResult;
 333     if (CE->EvaluateAsInt(EVResult, C.getASTContext(), Expr::SE_NoSideEffects)) {
 334       // Make sure the result has the correct type.
 335       llvm::APSInt Result = EVResult.Val.getInt();
 336       BasicValueFactory &BVF = SVB.getBasicValueFactory();
 337       BVF.getAPSIntType(CE->getType()).apply(Result);
 338       V = SVB.makeIntVal(Result);
 339     }
 340
 341     if (FD->getBuiltinID() == Builtin::BI__builtin_constant_p) {
 342       // If we didn't manage to figure out if the value is constant or not,
 343       // it is safe to assume that it's not constant and unsafe to assume
 344       // that it's constant.
 345       if (V.isUnknown())
 346         V = SVB.makeIntVal(0, CE->getType());
 347     }
 348
 349     C.addTransition(state->BindExpr(CE, LCtx, V));
 350     return true;
 351   }
 352   }
 353 }
 354
 355 void ento::registerBuiltinFunctionChecker(CheckerManager &mgr) {
 356   mgr.registerChecker<BuiltinFunctionChecker>();
 357 }
 358
 359 bool ento::shouldRegisterBuiltinFunctionChecker(const CheckerManager &mgr) {
 360   return true;
 361 }