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#include <algorithm>
28
29using namespace clang;
30using namespace ento;
31using namespace taint;
32
33namespace {
34
35/// \return an integer type that is large enough for the binary operation on the
36/// operands of \p Arg1Ty and \p Arg2Ty, respectively.
37QualType getSufficientTypeForOverflowOp(CheckerContext &C,
38 BinaryOperator::Opcode Op,
39 QualType Arg1Ty, QualType Arg2Ty) {
40 assert(Arg1Ty->isIntegerType() && Arg2Ty->isIntegerType());
41
42 ASTContext &ACtx = C.getASTContext();
43 unsigned BitWidth =
44 std::max(a: ACtx.getIntWidth(T: Arg1Ty), b: ACtx.getIntWidth(T: Arg2Ty));
45
46 // A signed type with doubled bits may not be large enough to hold the
47 // multiplication result when both operands are unsigned. In other
48 // words, if either operand is signed, a signed type with twice the bits is
49 // sufficient.
50 //
51 // Additionally, subtraction always needs a signed result. Note that
52 // subtracting a negative operand falls into the prior case, so it is still
53 // safe with a signed result type. A signed 1-bit integer is not allowed in
54 // Clang.
55 bool UseSigned = Op == BO_Sub || Arg1Ty->isSignedIntegerType() ||
56 Arg2Ty->isSignedIntegerType();
57 return ACtx.getBitIntType(/*Unsigned=*/!UseSigned, NumBits: BitWidth * 2);
58}
59
60QualType getOverflowBuiltinResultType(const CallEvent &Call) {
61 // Calling a builtin with an incorrect argument count produces compiler error.
62 assert(Call.getNumArgs() == 3);
63
64 return Call.getArgExpr(Index: 2)->getType()->getPointeeType();
65}
66
67QualType getOverflowBuiltinResultType(const CallEvent &Call, CheckerContext &C,
68 unsigned BI) {
69 // Calling a builtin with an incorrect argument count produces compiler error.
70 assert(Call.getNumArgs() == 3);
71
72 ASTContext &ACtx = C.getASTContext();
73
74 switch (BI) {
75 case Builtin::BI__builtin_smul_overflow:
76 case Builtin::BI__builtin_ssub_overflow:
77 case Builtin::BI__builtin_sadd_overflow:
78 return ACtx.IntTy;
79 case Builtin::BI__builtin_smull_overflow:
80 case Builtin::BI__builtin_ssubl_overflow:
81 case Builtin::BI__builtin_saddl_overflow:
82 return ACtx.LongTy;
83 case Builtin::BI__builtin_smulll_overflow:
84 case Builtin::BI__builtin_ssubll_overflow:
85 case Builtin::BI__builtin_saddll_overflow:
86 return ACtx.LongLongTy;
87 case Builtin::BI__builtin_umul_overflow:
88 case Builtin::BI__builtin_usub_overflow:
89 case Builtin::BI__builtin_uadd_overflow:
90 return ACtx.UnsignedIntTy;
91 case Builtin::BI__builtin_umull_overflow:
92 case Builtin::BI__builtin_usubl_overflow:
93 case Builtin::BI__builtin_uaddl_overflow:
94 return ACtx.UnsignedLongTy;
95 case Builtin::BI__builtin_umulll_overflow:
96 case Builtin::BI__builtin_usubll_overflow:
97 case Builtin::BI__builtin_uaddll_overflow:
98 return ACtx.UnsignedLongLongTy;
99 case Builtin::BI__builtin_mul_overflow:
100 case Builtin::BI__builtin_sub_overflow:
101 case Builtin::BI__builtin_add_overflow:
102 return getOverflowBuiltinResultType(Call);
103 default:
104 assert(false && "Unknown overflow builtin");
105 return ACtx.IntTy;
106 }
107}
108
109class BuiltinFunctionChecker : public Checker<eval::Call> {
110public:
111 bool evalCall(const CallEvent &Call, CheckerContext &C) const;
112 void handleOverflowBuiltin(const CallEvent &Call, CheckerContext &C,
113 BinaryOperator::Opcode Op,
114 QualType ResultType) const;
115 const NoteTag *createBuiltinOverflowNoteTag(CheckerContext &C,
116 bool BothFeasible, SVal Arg1,
117 SVal Arg2, SVal Result) const;
118 ProgramStateRef initStateAftetBuiltinOverflow(CheckerContext &C,
119 ProgramStateRef State,
120 const CallEvent &Call,
121 SVal RetCal,
122 bool IsOverflow) const;
123 std::pair<bool, bool> checkOverflow(CheckerContext &C, SVal RetVal,
124 QualType Res) const;
125
126private:
127 // From: clang/include/clang/Basic/Builtins.def
128 // C++ standard library builtins in namespace 'std'.
129 const CallDescriptionSet BuiltinLikeStdFunctions{
130 {CDM::SimpleFunc, {"std", "addressof"}}, //
131 {CDM::SimpleFunc, {"std", "__addressof"}}, //
132 {CDM::SimpleFunc, {"std", "as_const"}}, //
133 {CDM::SimpleFunc, {"std", "forward"}}, //
134 {CDM::SimpleFunc, {"std", "forward_like"}}, //
135 {CDM::SimpleFunc, {"std", "move"}}, //
136 {CDM::SimpleFunc, {"std", "move_if_noexcept"}}, //
137 };
138
139 bool isBuiltinLikeFunction(const CallEvent &Call) const;
140};
141
142} // namespace
143
144const NoteTag *BuiltinFunctionChecker::createBuiltinOverflowNoteTag(
145 CheckerContext &C, bool overflow, SVal Arg1, SVal Arg2, SVal Result) const {
146 return C.getNoteTag(Cb: [Result, Arg1, Arg2, overflow](PathSensitiveBugReport &BR,
147 llvm::raw_ostream &OS) {
148 if (!BR.isInteresting(V: Result))
149 return;
150
151 // Propagate interestingness to input arguments if result is interesting.
152 BR.markInteresting(V: Arg1);
153 BR.markInteresting(V: Arg2);
154
155 if (overflow)
156 OS << "Assuming overflow";
157 else
158 OS << "Assuming no overflow";
159 });
160}
161
162std::pair<bool, bool>
163BuiltinFunctionChecker::checkOverflow(CheckerContext &C, SVal RetVal,
164 QualType Res) const {
165 // Calling a builtin with a non-integer type result produces compiler error.
166 assert(Res->isIntegerType());
167
168 unsigned BitWidth = C.getASTContext().getIntWidth(T: Res);
169 bool IsUnsigned = Res->isUnsignedIntegerType();
170
171 SValBuilder &SVB = C.getSValBuilder();
172 BasicValueFactory &VF = SVB.getBasicValueFactory();
173
174 auto MinValType = llvm::APSInt::getMinValue(numBits: BitWidth, Unsigned: IsUnsigned);
175 auto MaxValType = llvm::APSInt::getMaxValue(numBits: BitWidth, Unsigned: IsUnsigned);
176 nonloc::ConcreteInt MinVal{VF.getValue(X: MinValType)};
177 nonloc::ConcreteInt MaxVal{VF.getValue(X: MaxValType)};
178
179 ProgramStateRef State = C.getState();
180 SVal IsLeMax = SVB.evalBinOp(state: State, op: BO_LE, lhs: RetVal, rhs: MaxVal, type: Res);
181 SVal IsGeMin = SVB.evalBinOp(state: State, op: BO_GE, lhs: RetVal, rhs: MinVal, type: Res);
182
183 auto [MayNotOverflow, MayOverflow] =
184 State->assume(Cond: IsLeMax.castAs<DefinedOrUnknownSVal>());
185 auto [MayNotUnderflow, MayUnderflow] =
186 State->assume(Cond: IsGeMin.castAs<DefinedOrUnknownSVal>());
187
188 return {MayOverflow || MayUnderflow, MayNotOverflow && MayNotUnderflow};
189}
190
191ProgramStateRef BuiltinFunctionChecker::initStateAftetBuiltinOverflow(
192 CheckerContext &C, ProgramStateRef State, const CallEvent &Call,
193 SVal RetVal, bool IsOverflow) const {
194 SValBuilder &SVB = C.getSValBuilder();
195 SVal Arg1 = Call.getArgSVal(Index: 0);
196 SVal Arg2 = Call.getArgSVal(Index: 1);
197 auto BoolTy = C.getASTContext().BoolTy;
198
199 ProgramStateRef NewState =
200 State->BindExpr(E: Call.getOriginExpr(), SF: C.getStackFrame(),
201 V: SVB.makeTruthVal(b: IsOverflow, type: BoolTy));
202
203 if (auto L = Call.getArgSVal(Index: 2).getAs<Loc>()) {
204 NewState = NewState->bindLoc(location: *L, V: RetVal, SF: C.getStackFrame());
205
206 // Propagate taint if any of the arguments were tainted
207 if (isTainted(State, V: Arg1) || isTainted(State, V: Arg2))
208 NewState = addTaint(State: NewState, V: *L);
209 }
210
211 return NewState;
212}
213
214void BuiltinFunctionChecker::handleOverflowBuiltin(const CallEvent &Call,
215 CheckerContext &C,
216 BinaryOperator::Opcode Op,
217 QualType ResultType) const {
218 // Calling a builtin with an incorrect argument count produces compiler error.
219 assert(Call.getNumArgs() == 3);
220
221 ProgramStateRef State = C.getState();
222 SValBuilder &SVB = C.getSValBuilder();
223
224 SVal Arg1 = Call.getArgSVal(Index: 0);
225 SVal Arg2 = Call.getArgSVal(Index: 1);
226 QualType Arg1Ty = Call.getArgExpr(Index: 0)->getType();
227 QualType Arg2Ty = Call.getArgExpr(Index: 1)->getType();
228
229 QualType SufficientlyWideTy =
230 getSufficientTypeForOverflowOp(C, Op, Arg1Ty, Arg2Ty);
231 assert(!SufficientlyWideTy.isNull());
232
233 SVal RetValMax = SVB.evalBinOp(state: State, op: Op, lhs: Arg1, rhs: Arg2, type: SufficientlyWideTy);
234 SVal RetVal = SVB.evalBinOp(state: State, op: Op, lhs: Arg1, rhs: Arg2, type: ResultType);
235
236 auto [Overflow, NotOverflow] = checkOverflow(C, RetVal: RetValMax, Res: ResultType);
237
238 if (NotOverflow) {
239 auto NewState =
240 initStateAftetBuiltinOverflow(C, State, Call, RetVal, IsOverflow: false);
241
242 C.addTransition(State: NewState, Tag: createBuiltinOverflowNoteTag(
243 C, /*overflow=*/false, Arg1, Arg2, Result: RetVal));
244 }
245
246 if (Overflow) {
247 auto NewState = initStateAftetBuiltinOverflow(C, State, Call, RetVal, IsOverflow: true);
248
249 C.addTransition(State: NewState, Tag: createBuiltinOverflowNoteTag(C, /*overflow=*/true,
250 Arg1, Arg2, Result: RetVal));
251 }
252}
253
254bool BuiltinFunctionChecker::isBuiltinLikeFunction(
255 const CallEvent &Call) const {
256 const auto *FD = llvm::dyn_cast_or_null<FunctionDecl>(Val: Call.getDecl());
257 if (!FD || FD->getNumParams() != 1)
258 return false;
259
260 if (QualType RetTy = FD->getReturnType();
261 !RetTy->isPointerType() && !RetTy->isReferenceType())
262 return false;
263
264 if (QualType ParmTy = FD->getParamDecl(i: 0)->getType();
265 !ParmTy->isPointerType() && !ParmTy->isReferenceType())
266 return false;
267
268 return BuiltinLikeStdFunctions.contains(Call);
269}
270
271bool BuiltinFunctionChecker::evalCall(const CallEvent &Call,
272 CheckerContext &C) const {
273 ProgramStateRef state = C.getState();
274 const auto *FD = dyn_cast_or_null<FunctionDecl>(Val: Call.getDecl());
275 if (!FD)
276 return false;
277
278 const StackFrame *SF = C.getStackFrame();
279 const Expr *CE = Call.getOriginExpr();
280
281 if (isBuiltinLikeFunction(Call)) {
282 C.addTransition(State: state->BindExpr(E: CE, SF, V: Call.getArgSVal(Index: 0)));
283 return true;
284 }
285
286 unsigned BI = FD->getBuiltinID();
287
288 switch (BI) {
289 default:
290 return false;
291 case Builtin::BI__builtin_mul_overflow:
292 case Builtin::BI__builtin_smul_overflow:
293 case Builtin::BI__builtin_smull_overflow:
294 case Builtin::BI__builtin_smulll_overflow:
295 case Builtin::BI__builtin_umul_overflow:
296 case Builtin::BI__builtin_umull_overflow:
297 case Builtin::BI__builtin_umulll_overflow:
298 handleOverflowBuiltin(Call, C, Op: BO_Mul,
299 ResultType: getOverflowBuiltinResultType(Call, C, BI));
300 return true;
301 case Builtin::BI__builtin_sub_overflow:
302 case Builtin::BI__builtin_ssub_overflow:
303 case Builtin::BI__builtin_ssubl_overflow:
304 case Builtin::BI__builtin_ssubll_overflow:
305 case Builtin::BI__builtin_usub_overflow:
306 case Builtin::BI__builtin_usubl_overflow:
307 case Builtin::BI__builtin_usubll_overflow:
308 handleOverflowBuiltin(Call, C, Op: BO_Sub,
309 ResultType: getOverflowBuiltinResultType(Call, C, BI));
310 return true;
311 case Builtin::BI__builtin_add_overflow:
312 case Builtin::BI__builtin_sadd_overflow:
313 case Builtin::BI__builtin_saddl_overflow:
314 case Builtin::BI__builtin_saddll_overflow:
315 case Builtin::BI__builtin_uadd_overflow:
316 case Builtin::BI__builtin_uaddl_overflow:
317 case Builtin::BI__builtin_uaddll_overflow:
318 handleOverflowBuiltin(Call, C, Op: BO_Add,
319 ResultType: getOverflowBuiltinResultType(Call, C, BI));
320 return true;
321 case Builtin::BI__builtin_unpredictable:
322 case Builtin::BI__builtin_expect:
323 case Builtin::BI__builtin_expect_with_probability:
324 case Builtin::BI__builtin_assume_aligned:
325 case Builtin::BI__builtin_addressof:
326 case Builtin::BI__builtin_function_start: {
327 // For __builtin_unpredictable, __builtin_expect,
328 // __builtin_expect_with_probability and __builtin_assume_aligned,
329 // just return the value of the subexpression.
330 // __builtin_addressof is going from a reference to a pointer, but those
331 // are represented the same way in the analyzer.
332 assert (Call.getNumArgs() > 0);
333 SVal Arg = Call.getArgSVal(Index: 0);
334 C.addTransition(State: state->BindExpr(E: CE, SF, V: Arg));
335 return true;
336 }
337
338 case Builtin::BI__builtin_dynamic_object_size:
339 case Builtin::BI__builtin_object_size:
340 case Builtin::BI__builtin_constant_p: {
341 // This must be resolvable at compile time, so we defer to the constant
342 // evaluator for a value.
343 SValBuilder &SVB = C.getSValBuilder();
344 SVal V = UnknownVal();
345 Expr::EvalResult EVResult;
346 if (CE->EvaluateAsInt(Result&: EVResult, Ctx: C.getASTContext(), AllowSideEffects: Expr::SE_NoSideEffects)) {
347 // Make sure the result has the correct type.
348 llvm::APSInt Result = EVResult.Val.getInt();
349 BasicValueFactory &BVF = SVB.getBasicValueFactory();
350 BVF.getAPSIntType(T: CE->getType()).apply(Value&: Result);
351 V = SVB.makeIntVal(integer: Result);
352 }
353
354 if (FD->getBuiltinID() == Builtin::BI__builtin_constant_p) {
355 // If we didn't manage to figure out if the value is constant or not,
356 // it is safe to assume that it's not constant and unsafe to assume
357 // that it's constant.
358 if (V.isUnknown())
359 V = SVB.makeIntVal(integer: 0, type: CE->getType());
360 }
361
362 C.addTransition(State: state->BindExpr(E: CE, SF, V));
363 return true;
364 }
365 }
366}
367
368void ento::registerBuiltinFunctionChecker(CheckerManager &mgr) {
369 mgr.registerChecker<BuiltinFunctionChecker>();
370}
371
372bool ento::shouldRegisterBuiltinFunctionChecker(const CheckerManager &mgr) {
373 return true;
374}
375