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