| //=== 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" |
| |
| using namespace clang; |
| using namespace ento; |
| using namespace taint; |
| |
| namespace { |
| |
| QualType getSufficientTypeForOverflowOp(CheckerContext &C, const QualType &T) { |
| // Calling a builtin with a non-integer type result produces compiler error. |
| assert(T->isIntegerType()); |
| |
| ASTContext &ACtx = C.getASTContext(); |
| |
| unsigned BitWidth = ACtx.getIntWidth(T); |
| return ACtx.getIntTypeForBitwidth(BitWidth * 2, T->isSignedIntegerType()); |
| } |
| |
| 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.getLocationContext(), |
| SVB.makeTruthVal(IsOverflow, BoolTy)); |
| |
| if (auto L = Call.getArgSVal(2).getAs<Loc>()) { |
| NewState = NewState->bindLoc(*L, RetVal, C.getLocationContext()); |
| |
| // 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); |
| |
| SVal RetValMax = SVB.evalBinOp(State, Op, Arg1, Arg2, |
| getSufficientTypeForOverflowOp(C, ResultType)); |
| 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 LocationContext *LCtx = C.getLocationContext(); |
| const Expr *CE = Call.getOriginExpr(); |
| |
| if (isBuiltinLikeFunction(Call)) { |
| C.addTransition(state->BindExpr(CE, LCtx, 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, LCtx, 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, LCtx, V)); |
| return true; |
| } |
| } |
| } |
| |
| void ento::registerBuiltinFunctionChecker(CheckerManager &mgr) { |
| mgr.registerChecker<BuiltinFunctionChecker>(); |
| } |
| |
| bool ento::shouldRegisterBuiltinFunctionChecker(const CheckerManager &mgr) { |
| return true; |
| } |