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