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/SVals.h" 27 28 using namespace clang; 29 using namespace ento; 30 using namespace taint; 31 32 namespace { 33 34 QualType 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 44 QualType 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 51 QualType 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 93 class BuiltinFunctionChecker : public Checker<eval::Call> { 94 public: 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 110 private: 111 // From: clang/include/clang/Basic/Builtins.def 112 // 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 } // namespace 127 128 const 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 else 142 OS << "Assuming no overflow"; 143 }); 144 } 145 146 std::pair<bool, bool> 147 BuiltinFunctionChecker::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 175 ProgramStateRef 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 tainted 191 if (isTainted(State, Arg1) || isTainted(State, Arg2)) 192 NewState = addTaint(NewState, *L); 193 } 194 195 return NewState; 196 } 197 198 void 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 233 bool 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 250 bool 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 those 310 // 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 constant 321 // 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 assume 336 // 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 347 void ento::registerBuiltinFunctionChecker(CheckerManager &mgr) { 348 mgr.registerChecker<BuiltinFunctionChecker>(); 349 } 350 351 bool ento::shouldRegisterBuiltinFunctionChecker(const CheckerManager &mgr) { 352 return true; 353 } 354