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
getSufficientTypeForOverflowOp(CheckerContext & C,const QualType & T)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
getOverflowBuiltinResultType(const CallEvent & Call)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
getOverflowBuiltinResultType(const CallEvent & Call,CheckerContext & C,unsigned BI)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
createBuiltinOverflowNoteTag(CheckerContext & C,bool overflow,SVal Arg1,SVal Arg2,SVal Result) const128 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>
checkOverflow(CheckerContext & C,SVal RetVal,QualType Res) const147 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
initStateAftetBuiltinOverflow(CheckerContext & C,ProgramStateRef State,const CallEvent & Call,SVal RetVal,bool IsOverflow) const175 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
handleOverflowBuiltin(const CallEvent & Call,CheckerContext & C,BinaryOperator::Opcode Op,QualType ResultType) const198 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
isBuiltinLikeFunction(const CallEvent & Call) const233 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
evalCall(const CallEvent & Call,CheckerContext & C) const250 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
registerBuiltinFunctionChecker(CheckerManager & mgr)347 void ento::registerBuiltinFunctionChecker(CheckerManager &mgr) {
348 mgr.registerChecker<BuiltinFunctionChecker>();
349 }
350
shouldRegisterBuiltinFunctionChecker(const CheckerManager & mgr)351 bool ento::shouldRegisterBuiltinFunctionChecker(const CheckerManager &mgr) {
352 return true;
353 }
354