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
28using namespace clang;
29using namespace ento;
30using namespace taint;
31
32namespace {
33
34QualType 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(DestWidth: BitWidth * 2, Signed: T->isSignedIntegerType());
42}
43
44QualType 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(Index: 2)->getType()->getPointeeType();
49}
50
51QualType 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
93class BuiltinFunctionChecker : public Checker<eval::Call> {
94public:
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
110private:
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
128const NoteTag *BuiltinFunctionChecker::createBuiltinOverflowNoteTag(
129 CheckerContext &C, bool overflow, SVal Arg1, SVal Arg2, SVal Result) const {
130 return C.getNoteTag(Cb: [Result, Arg1, Arg2, overflow](PathSensitiveBugReport &BR,
131 llvm::raw_ostream &OS) {
132 if (!BR.isInteresting(V: Result))
133 return;
134
135 // Propagate interestingness to input arguments if result is interesting.
136 BR.markInteresting(V: Arg1);
137 BR.markInteresting(V: Arg2);
138
139 if (overflow)
140 OS << "Assuming overflow";
141 else
142 OS << "Assuming no overflow";
143 });
144}
145
146std::pair<bool, bool>
147BuiltinFunctionChecker::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(T: Res);
153 bool IsUnsigned = Res->isUnsignedIntegerType();
154
155 SValBuilder &SVB = C.getSValBuilder();
156 BasicValueFactory &VF = SVB.getBasicValueFactory();
157
158 auto MinValType = llvm::APSInt::getMinValue(numBits: BitWidth, Unsigned: IsUnsigned);
159 auto MaxValType = llvm::APSInt::getMaxValue(numBits: BitWidth, Unsigned: IsUnsigned);
160 nonloc::ConcreteInt MinVal{VF.getValue(X: MinValType)};
161 nonloc::ConcreteInt MaxVal{VF.getValue(X: MaxValType)};
162
163 ProgramStateRef State = C.getState();
164 SVal IsLeMax = SVB.evalBinOp(state: State, op: BO_LE, lhs: RetVal, rhs: MaxVal, type: Res);
165 SVal IsGeMin = SVB.evalBinOp(state: State, op: BO_GE, lhs: RetVal, rhs: MinVal, type: Res);
166
167 auto [MayNotOverflow, MayOverflow] =
168 State->assume(Cond: IsLeMax.castAs<DefinedOrUnknownSVal>());
169 auto [MayNotUnderflow, MayUnderflow] =
170 State->assume(Cond: IsGeMin.castAs<DefinedOrUnknownSVal>());
171
172 return {MayOverflow || MayUnderflow, MayNotOverflow && MayNotUnderflow};
173}
174
175ProgramStateRef 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(Index: 0);
180 SVal Arg2 = Call.getArgSVal(Index: 1);
181 auto BoolTy = C.getASTContext().BoolTy;
182
183 ProgramStateRef NewState =
184 State->BindExpr(S: Call.getOriginExpr(), LCtx: C.getLocationContext(),
185 V: SVB.makeTruthVal(IsOverflow, BoolTy));
186
187 if (auto L = Call.getArgSVal(Index: 2).getAs<Loc>()) {
188 NewState = NewState->bindLoc(location: *L, V: RetVal, LCtx: C.getLocationContext());
189
190 // Propagate taint if any of the arguments were tainted
191 if (isTainted(State, V: Arg1) || isTainted(State, V: Arg2))
192 NewState = addTaint(State: NewState, V: *L);
193 }
194
195 return NewState;
196}
197
198void 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(Index: 0);
209 SVal Arg2 = Call.getArgSVal(Index: 1);
210
211 SVal RetValMax = SVB.evalBinOp(state: State, op: Op, lhs: Arg1, rhs: Arg2,
212 type: getSufficientTypeForOverflowOp(C, T: ResultType));
213 SVal RetVal = SVB.evalBinOp(state: State, op: Op, lhs: Arg1, rhs: Arg2, type: ResultType);
214
215 auto [Overflow, NotOverflow] = checkOverflow(C, RetVal: RetValMax, Res: ResultType);
216
217 if (NotOverflow) {
218 auto NewState =
219 initStateAftetBuiltinOverflow(C, State, Call, RetVal, IsOverflow: false);
220
221 C.addTransition(State: NewState, Tag: createBuiltinOverflowNoteTag(
222 C, /*overflow=*/false, Arg1, Arg2, Result: RetVal));
223 }
224
225 if (Overflow) {
226 auto NewState = initStateAftetBuiltinOverflow(C, State, Call, RetVal, IsOverflow: true);
227
228 C.addTransition(State: NewState, Tag: createBuiltinOverflowNoteTag(C, /*overflow=*/true,
229 Arg1, Arg2, Result: RetVal));
230 }
231}
232
233bool BuiltinFunctionChecker::isBuiltinLikeFunction(
234 const CallEvent &Call) const {
235 const auto *FD = llvm::dyn_cast_or_null<FunctionDecl>(Val: 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(i: 0)->getType();
244 !ParmTy->isPointerType() && !ParmTy->isReferenceType())
245 return false;
246
247 return BuiltinLikeStdFunctions.contains(Call);
248}
249
250bool BuiltinFunctionChecker::evalCall(const CallEvent &Call,
251 CheckerContext &C) const {
252 ProgramStateRef state = C.getState();
253 const auto *FD = dyn_cast_or_null<FunctionDecl>(Val: 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: state->BindExpr(CE, LCtx, Call.getArgSVal(Index: 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, Op: BO_Mul,
278 ResultType: 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, Op: BO_Sub,
288 ResultType: 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, Op: BO_Add,
298 ResultType: 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(Index: 0);
313 C.addTransition(State: 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(Result&: EVResult, Ctx: C.getASTContext(), AllowSideEffects: 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(T: CE->getType()).apply(Value&: Result);
330 V = SVB.makeIntVal(integer: 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(integer: 0, type: CE->getType());
339 }
340
341 C.addTransition(State: state->BindExpr(CE, LCtx, V));
342 return true;
343 }
344 }
345}
346
347void ento::registerBuiltinFunctionChecker(CheckerManager &mgr) {
348 mgr.registerChecker<BuiltinFunctionChecker>();
349}
350
351bool ento::shouldRegisterBuiltinFunctionChecker(const CheckerManager &mgr) {
352 return true;
353}
354

source code of clang/lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp