//=== 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/DynamicExtent.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 { public: bool evalCall(const CallEvent &Call, CheckerContext &C) const; void handleOverflowBuiltin(const CallEvent &Call, CheckerContext &C, BinaryOperator::Opcode Op, QualType ResultType) const; const NoteTag *createBuiltinNoOverflowNoteTag(CheckerContext &C, bool BothFeasible, SVal Arg1, SVal Arg2, SVal Result) const; const NoteTag *createBuiltinOverflowNoteTag(CheckerContext &C) const; std::pair 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::createBuiltinNoOverflowNoteTag( CheckerContext &C, bool BothFeasible, SVal Arg1, SVal Arg2, SVal Result) const { return C.getNoteTag([Result, Arg1, Arg2, BothFeasible]( PathSensitiveBugReport &BR, llvm::raw_ostream &OS) { if (!BR.isInteresting(Result)) return; // Propagate interestingness to input argumets if result is interesting. BR.markInteresting(Arg1); BR.markInteresting(Arg2); if (BothFeasible) OS << "Assuming no overflow"; }); } const NoteTag * BuiltinFunctionChecker::createBuiltinOverflowNoteTag(CheckerContext &C) const { return C.getNoteTag([](PathSensitiveBugReport &BR, llvm::raw_ostream &OS) { OS << "Assuming overflow"; }, /*isPrunable=*/true); } std::pair 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()); auto [MayNotUnderflow, MayUnderflow] = State->assume(IsGeMin.castAs()); return {MayOverflow || MayUnderflow, MayNotOverflow && MayNotUnderflow}; } 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(); const Expr *CE = Call.getOriginExpr(); auto BoolTy = C.getASTContext().BoolTy; 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) { ProgramStateRef StateNoOverflow = State->BindExpr( CE, C.getLocationContext(), SVB.makeTruthVal(false, BoolTy)); if (auto L = Call.getArgSVal(2).getAs()) { StateNoOverflow = StateNoOverflow->bindLoc(*L, RetVal, C.getLocationContext()); // Propagate taint if any of the argumets were tainted if (isTainted(State, Arg1) || isTainted(State, Arg2)) StateNoOverflow = addTaint(StateNoOverflow, *L); } C.addTransition( StateNoOverflow, createBuiltinNoOverflowNoteTag( C, /*BothFeasible=*/NotOverflow && Overflow, Arg1, Arg2, RetVal)); } if (Overflow) { C.addTransition(State->BindExpr(CE, C.getLocationContext(), SVB.makeTruthVal(true, BoolTy)), createBuiltinOverflowNoteTag(C)); } } bool BuiltinFunctionChecker::isBuiltinLikeFunction( const CallEvent &Call) const { const auto *FD = llvm::dyn_cast_or_null(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(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_assume: case Builtin::BI__assume: { assert (Call.getNumArgs() > 0); SVal Arg = Call.getArgSVal(0); if (Arg.isUndef()) return true; // Return true to model purity. state = state->assume(Arg.castAs(), true); // FIXME: do we want to warn here? Not right now. The most reports might // come from infeasible paths, thus being false positives. if (!state) { C.generateSink(C.getState(), C.getPredecessor()); return true; } C.addTransition(state); 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(); } bool ento::shouldRegisterBuiltinFunctionChecker(const CheckerManager &mgr) { return true; }