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 187 SVal Arg1 = Call.getArgSVal(0); 188 SVal Arg2 = Call.getArgSVal(1); 189 190 SVal RetValMax = SVB.evalBinOp(State, Op, Arg1, Arg2, 191 getSufficientTypeForOverflowOp(C, ResultType)); 192 SVal RetVal = SVB.evalBinOp(State, Op, Arg1, Arg2, ResultType); 193 194 auto [Overflow, NotOverflow] = checkOverflow(C, RetValMax, ResultType); 195 if (NotOverflow) { 196 ProgramStateRef StateNoOverflow = 197 State->BindExpr(CE, C.getLocationContext(), SVB.makeTruthVal(false)); 198 199 if (auto L = Call.getArgSVal(2).getAs<Loc>()) { 200 StateNoOverflow = 201 StateNoOverflow->bindLoc(*L, RetVal, C.getLocationContext()); 202 203 // Propagate taint if any of the argumets were tainted 204 if (isTainted(State, Arg1) || isTainted(State, Arg2)) 205 StateNoOverflow = addTaint(StateNoOverflow, *L); 206 } 207 208 C.addTransition( 209 StateNoOverflow, 210 createBuiltinNoOverflowNoteTag( 211 C, /*BothFeasible=*/NotOverflow && Overflow, Arg1, Arg2, RetVal)); 212 } 213 214 if (Overflow) { 215 C.addTransition( 216 State->BindExpr(CE, C.getLocationContext(), SVB.makeTruthVal(true)), 217 createBuiltinOverflowNoteTag(C)); 218 } 219 } 220 221 bool BuiltinFunctionChecker::isBuiltinLikeFunction( 222 const CallEvent &Call) const { 223 const auto *FD = llvm::dyn_cast_or_null<FunctionDecl>(Call.getDecl()); 224 if (!FD || FD->getNumParams() != 1) 225 return false; 226 227 if (QualType RetTy = FD->getReturnType(); 228 !RetTy->isPointerType() && !RetTy->isReferenceType()) 229 return false; 230 231 if (QualType ParmTy = FD->getParamDecl(0)->getType(); 232 !ParmTy->isPointerType() && !ParmTy->isReferenceType()) 233 return false; 234 235 return BuiltinLikeStdFunctions.contains(Call); 236 } 237 238 bool BuiltinFunctionChecker::evalCall(const CallEvent &Call, 239 CheckerContext &C) const { 240 ProgramStateRef state = C.getState(); 241 const auto *FD = dyn_cast_or_null<FunctionDecl>(Call.getDecl()); 242 if (!FD) 243 return false; 244 245 const LocationContext *LCtx = C.getLocationContext(); 246 const Expr *CE = Call.getOriginExpr(); 247 248 if (isBuiltinLikeFunction(Call)) { 249 C.addTransition(state->BindExpr(CE, LCtx, Call.getArgSVal(0))); 250 return true; 251 } 252 253 unsigned BI = FD->getBuiltinID(); 254 255 switch (BI) { 256 default: 257 return false; 258 case Builtin::BI__builtin_mul_overflow: 259 case Builtin::BI__builtin_smul_overflow: 260 case Builtin::BI__builtin_smull_overflow: 261 case Builtin::BI__builtin_smulll_overflow: 262 case Builtin::BI__builtin_umul_overflow: 263 case Builtin::BI__builtin_umull_overflow: 264 case Builtin::BI__builtin_umulll_overflow: 265 handleOverflowBuiltin(Call, C, BO_Mul, 266 getOverflowBuiltinResultType(Call, C, BI)); 267 return true; 268 case Builtin::BI__builtin_sub_overflow: 269 case Builtin::BI__builtin_ssub_overflow: 270 case Builtin::BI__builtin_ssubl_overflow: 271 case Builtin::BI__builtin_ssubll_overflow: 272 case Builtin::BI__builtin_usub_overflow: 273 case Builtin::BI__builtin_usubl_overflow: 274 case Builtin::BI__builtin_usubll_overflow: 275 handleOverflowBuiltin(Call, C, BO_Sub, 276 getOverflowBuiltinResultType(Call, C, BI)); 277 return true; 278 case Builtin::BI__builtin_add_overflow: 279 case Builtin::BI__builtin_sadd_overflow: 280 case Builtin::BI__builtin_saddl_overflow: 281 case Builtin::BI__builtin_saddll_overflow: 282 case Builtin::BI__builtin_uadd_overflow: 283 case Builtin::BI__builtin_uaddl_overflow: 284 case Builtin::BI__builtin_uaddll_overflow: 285 handleOverflowBuiltin(Call, C, BO_Add, 286 getOverflowBuiltinResultType(Call, C, BI)); 287 return true; 288 case Builtin::BI__builtin_assume: 289 case Builtin::BI__assume: { 290 assert (Call.getNumArgs() > 0); 291 SVal Arg = Call.getArgSVal(0); 292 if (Arg.isUndef()) 293 return true; // Return true to model purity. 294 295 state = state->assume(Arg.castAs<DefinedOrUnknownSVal>(), true); 296 // FIXME: do we want to warn here? Not right now. The most reports might 297 // come from infeasible paths, thus being false positives. 298 if (!state) { 299 C.generateSink(C.getState(), C.getPredecessor()); 300 return true; 301 } 302 303 C.addTransition(state); 304 return true; 305 } 306 307 case Builtin::BI__builtin_unpredictable: 308 case Builtin::BI__builtin_expect: 309 case Builtin::BI__builtin_expect_with_probability: 310 case Builtin::BI__builtin_assume_aligned: 311 case Builtin::BI__builtin_addressof: 312 case Builtin::BI__builtin_function_start: { 313 // For __builtin_unpredictable, __builtin_expect, 314 // __builtin_expect_with_probability and __builtin_assume_aligned, 315 // just return the value of the subexpression. 316 // __builtin_addressof is going from a reference to a pointer, but those 317 // are represented the same way in the analyzer. 318 assert (Call.getNumArgs() > 0); 319 SVal Arg = Call.getArgSVal(0); 320 C.addTransition(state->BindExpr(CE, LCtx, Arg)); 321 return true; 322 } 323 324 case Builtin::BI__builtin_dynamic_object_size: 325 case Builtin::BI__builtin_object_size: 326 case Builtin::BI__builtin_constant_p: { 327 // This must be resolvable at compile time, so we defer to the constant 328 // evaluator for a value. 329 SValBuilder &SVB = C.getSValBuilder(); 330 SVal V = UnknownVal(); 331 Expr::EvalResult EVResult; 332 if (CE->EvaluateAsInt(EVResult, C.getASTContext(), Expr::SE_NoSideEffects)) { 333 // Make sure the result has the correct type. 334 llvm::APSInt Result = EVResult.Val.getInt(); 335 BasicValueFactory &BVF = SVB.getBasicValueFactory(); 336 BVF.getAPSIntType(CE->getType()).apply(Result); 337 V = SVB.makeIntVal(Result); 338 } 339 340 if (FD->getBuiltinID() == Builtin::BI__builtin_constant_p) { 341 // If we didn't manage to figure out if the value is constant or not, 342 // it is safe to assume that it's not constant and unsafe to assume 343 // that it's constant. 344 if (V.isUnknown()) 345 V = SVB.makeIntVal(0, CE->getType()); 346 } 347 348 C.addTransition(state->BindExpr(CE, LCtx, V)); 349 return true; 350 } 351 } 352 } 353 354 void ento::registerBuiltinFunctionChecker(CheckerManager &mgr) { 355 mgr.registerChecker<BuiltinFunctionChecker>(); 356 } 357 358 bool ento::shouldRegisterBuiltinFunctionChecker(const CheckerManager &mgr) { 359 return true; 360 } 361