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