clang 19.0.0git
MallocOverflowSecurityChecker.cpp
Go to the documentation of this file.
1// MallocOverflowSecurityChecker.cpp - Check for malloc overflows -*- 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 detects a common memory allocation security flaw.
10// Suppose 'unsigned int n' comes from an untrusted source. If the
11// code looks like 'malloc (n * 4)', and an attacker can make 'n' be
12// say MAX_UINT/4+2, then instead of allocating the correct 'n' 4-byte
13// elements, this will actually allocate only two because of overflow.
14// Then when the rest of the program attempts to store values past the
15// second element, these values will actually overwrite other items in
16// the heap, probably allowing the attacker to execute arbitrary code.
17//
18//===----------------------------------------------------------------------===//
19
25#include "llvm/ADT/APSInt.h"
26#include "llvm/ADT/SmallVector.h"
27#include <optional>
28#include <utility>
29
30using namespace clang;
31using namespace ento;
32using llvm::APSInt;
33
34namespace {
35struct MallocOverflowCheck {
36 const CallExpr *call;
37 const BinaryOperator *mulop;
38 const Expr *variable;
39 APSInt maxVal;
40
41 MallocOverflowCheck(const CallExpr *call, const BinaryOperator *m,
42 const Expr *v, APSInt val)
43 : call(call), mulop(m), variable(v), maxVal(std::move(val)) {}
44};
45
46class MallocOverflowSecurityChecker : public Checker<check::ASTCodeBody> {
47public:
48 void checkASTCodeBody(const Decl *D, AnalysisManager &mgr,
49 BugReporter &BR) const;
50
51 void CheckMallocArgument(
52 SmallVectorImpl<MallocOverflowCheck> &PossibleMallocOverflows,
53 const CallExpr *TheCall, ASTContext &Context) const;
54
55 void OutputPossibleOverflows(
56 SmallVectorImpl<MallocOverflowCheck> &PossibleMallocOverflows,
57 const Decl *D, BugReporter &BR, AnalysisManager &mgr) const;
58
59};
60} // end anonymous namespace
61
62// Return true for computations which evaluate to zero: e.g., mult by 0.
63static inline bool EvaluatesToZero(APSInt &Val, BinaryOperatorKind op) {
64 return (op == BO_Mul) && (Val == 0);
65}
66
67void MallocOverflowSecurityChecker::CheckMallocArgument(
68 SmallVectorImpl<MallocOverflowCheck> &PossibleMallocOverflows,
69 const CallExpr *TheCall, ASTContext &Context) const {
70
71 /* Look for a linear combination with a single variable, and at least
72 one multiplication.
73 Reject anything that applies to the variable: an explicit cast,
74 conditional expression, an operation that could reduce the range
75 of the result, or anything too complicated :-). */
76 const Expr *e = TheCall->getArg(0);
77 const BinaryOperator * mulop = nullptr;
78 APSInt maxVal;
79
80 for (;;) {
81 maxVal = 0;
82 e = e->IgnoreParenImpCasts();
83 if (const BinaryOperator *binop = dyn_cast<BinaryOperator>(e)) {
84 BinaryOperatorKind opc = binop->getOpcode();
85 // TODO: ignore multiplications by 1, reject if multiplied by 0.
86 if (mulop == nullptr && opc == BO_Mul)
87 mulop = binop;
88 if (opc != BO_Mul && opc != BO_Add && opc != BO_Sub && opc != BO_Shl)
89 return;
90
91 const Expr *lhs = binop->getLHS();
92 const Expr *rhs = binop->getRHS();
93 if (rhs->isEvaluatable(Context)) {
94 e = lhs;
95 maxVal = rhs->EvaluateKnownConstInt(Context);
96 if (EvaluatesToZero(maxVal, opc))
97 return;
98 } else if ((opc == BO_Add || opc == BO_Mul) &&
99 lhs->isEvaluatable(Context)) {
100 maxVal = lhs->EvaluateKnownConstInt(Context);
101 if (EvaluatesToZero(maxVal, opc))
102 return;
103 e = rhs;
104 } else
105 return;
106 } else if (isa<DeclRefExpr, MemberExpr>(e))
107 break;
108 else
109 return;
110 }
111
112 if (mulop == nullptr)
113 return;
114
115 // We've found the right structure of malloc argument, now save
116 // the data so when the body of the function is completely available
117 // we can check for comparisons.
118
119 PossibleMallocOverflows.push_back(
120 MallocOverflowCheck(TheCall, mulop, e, maxVal));
121}
122
123namespace {
124// A worker class for OutputPossibleOverflows.
125class CheckOverflowOps :
126 public EvaluatedExprVisitor<CheckOverflowOps> {
127public:
128 typedef SmallVectorImpl<MallocOverflowCheck> theVecType;
129
130private:
131 theVecType &toScanFor;
133
134 bool isIntZeroExpr(const Expr *E) const {
136 return false;
138 if (E->EvaluateAsInt(Result, Context))
139 return Result.Val.getInt() == 0;
140 return false;
141 }
142
143 static const Decl *getDecl(const DeclRefExpr *DR) { return DR->getDecl(); }
144 static const Decl *getDecl(const MemberExpr *ME) {
145 return ME->getMemberDecl();
146 }
147
148 template <typename T1>
149 void Erase(const T1 *DR,
150 llvm::function_ref<bool(const MallocOverflowCheck &)> Pred) {
151 auto P = [DR, Pred](const MallocOverflowCheck &Check) {
152 if (const auto *CheckDR = dyn_cast<T1>(Check.variable))
153 return getDecl(CheckDR) == getDecl(DR) && Pred(Check);
154 return false;
155 };
156 llvm::erase_if(toScanFor, P);
157 }
158
159 void CheckExpr(const Expr *E_p) {
160 const Expr *E = E_p->IgnoreParenImpCasts();
161 const auto PrecedesMalloc = [E, this](const MallocOverflowCheck &c) {
163 E->getExprLoc(), c.call->getExprLoc());
164 };
165 if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E))
166 Erase<DeclRefExpr>(DR, PrecedesMalloc);
167 else if (const auto *ME = dyn_cast<MemberExpr>(E)) {
168 Erase<MemberExpr>(ME, PrecedesMalloc);
169 }
170 }
171
172 // Check if the argument to malloc is assigned a value
173 // which cannot cause an overflow.
174 // e.g., malloc (mul * x) and,
175 // case 1: mul = <constant value>
176 // case 2: mul = a/b, where b > x
177 void CheckAssignmentExpr(BinaryOperator *AssignEx) {
178 bool assignKnown = false;
179 bool numeratorKnown = false, denomKnown = false;
180 APSInt denomVal;
181 denomVal = 0;
182
183 // Erase if the multiplicand was assigned a constant value.
184 const Expr *rhs = AssignEx->getRHS();
185 if (rhs->isEvaluatable(Context))
186 assignKnown = true;
187
188 // Discard the report if the multiplicand was assigned a value,
189 // that can never overflow after multiplication. e.g., the assignment
190 // is a division operator and the denominator is > other multiplicand.
191 const Expr *rhse = rhs->IgnoreParenImpCasts();
192 if (const BinaryOperator *BOp = dyn_cast<BinaryOperator>(rhse)) {
193 if (BOp->getOpcode() == BO_Div) {
194 const Expr *denom = BOp->getRHS()->IgnoreParenImpCasts();
196 if (denom->EvaluateAsInt(Result, Context)) {
197 denomVal = Result.Val.getInt();
198 denomKnown = true;
199 }
200 const Expr *numerator = BOp->getLHS()->IgnoreParenImpCasts();
201 if (numerator->isEvaluatable(Context))
202 numeratorKnown = true;
203 }
204 }
205 if (!assignKnown && !denomKnown)
206 return;
207 auto denomExtVal = denomVal.getExtValue();
208
209 // Ignore negative denominator.
210 if (denomExtVal < 0)
211 return;
212
213 const Expr *lhs = AssignEx->getLHS();
214 const Expr *E = lhs->IgnoreParenImpCasts();
215
216 auto pred = [assignKnown, numeratorKnown,
217 denomExtVal](const MallocOverflowCheck &Check) {
218 return assignKnown ||
219 (numeratorKnown && (denomExtVal >= Check.maxVal.getExtValue()));
220 };
221
222 if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E))
223 Erase<DeclRefExpr>(DR, pred);
224 else if (const auto *ME = dyn_cast<MemberExpr>(E))
225 Erase<MemberExpr>(ME, pred);
226 }
227
228 public:
229 void VisitBinaryOperator(BinaryOperator *E) {
230 if (E->isComparisonOp()) {
231 const Expr * lhs = E->getLHS();
232 const Expr * rhs = E->getRHS();
233 // Ignore comparisons against zero, since they generally don't
234 // protect against an overflow.
235 if (!isIntZeroExpr(lhs) && !isIntZeroExpr(rhs)) {
236 CheckExpr(lhs);
237 CheckExpr(rhs);
238 }
239 }
240 if (E->isAssignmentOp())
241 CheckAssignmentExpr(E);
243 }
244
245 /* We specifically ignore loop conditions, because they're typically
246 not error checks. */
247 void VisitWhileStmt(WhileStmt *S) {
248 return this->Visit(S->getBody());
249 }
250 void VisitForStmt(ForStmt *S) {
251 return this->Visit(S->getBody());
252 }
253 void VisitDoStmt(DoStmt *S) {
254 return this->Visit(S->getBody());
255 }
256
257 CheckOverflowOps(theVecType &v, ASTContext &ctx)
258 : EvaluatedExprVisitor<CheckOverflowOps>(ctx),
259 toScanFor(v), Context(ctx)
260 { }
261 };
262}
263
264// OutputPossibleOverflows - We've found a possible overflow earlier,
265// now check whether Body might contain a comparison which might be
266// preventing the overflow.
267// This doesn't do flow analysis, range analysis, or points-to analysis; it's
268// just a dumb "is there a comparison" scan. The aim here is to
269// detect the most blatent cases of overflow and educate the
270// programmer.
271void MallocOverflowSecurityChecker::OutputPossibleOverflows(
272 SmallVectorImpl<MallocOverflowCheck> &PossibleMallocOverflows,
273 const Decl *D, BugReporter &BR, AnalysisManager &mgr) const {
274 // By far the most common case: nothing to check.
275 if (PossibleMallocOverflows.empty())
276 return;
277
278 // Delete any possible overflows which have a comparison.
279 CheckOverflowOps c(PossibleMallocOverflows, BR.getContext());
280 c.Visit(mgr.getAnalysisDeclContext(D)->getBody());
281
282 // Output warnings for all overflows that are left.
283 for (const MallocOverflowCheck &Check : PossibleMallocOverflows) {
285 D, this, "malloc() size overflow", categories::UnixAPI,
286 "the computation of the size of the memory allocation may overflow",
288 BR.getSourceManager()),
289 Check.mulop->getSourceRange());
290 }
291}
292
293void MallocOverflowSecurityChecker::checkASTCodeBody(const Decl *D,
294 AnalysisManager &mgr,
295 BugReporter &BR) const {
296
297 CFG *cfg = mgr.getCFG(D);
298 if (!cfg)
299 return;
300
301 // A list of variables referenced in possibly overflowing malloc operands.
302 SmallVector<MallocOverflowCheck, 2> PossibleMallocOverflows;
303
304 for (CFG::iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) {
305 CFGBlock *block = *it;
306 for (CFGBlock::iterator bi = block->begin(), be = block->end();
307 bi != be; ++bi) {
308 if (std::optional<CFGStmt> CS = bi->getAs<CFGStmt>()) {
309 if (const CallExpr *TheCall = dyn_cast<CallExpr>(CS->getStmt())) {
310 // Get the callee.
311 const FunctionDecl *FD = TheCall->getDirectCallee();
312
313 if (!FD)
314 continue;
315
316 // Get the name of the callee. If it's a builtin, strip off the
317 // prefix.
318 IdentifierInfo *FnInfo = FD->getIdentifier();
319 if (!FnInfo)
320 continue;
321
322 if (FnInfo->isStr("malloc") || FnInfo->isStr("_MALLOC")) {
323 if (TheCall->getNumArgs() == 1)
324 CheckMallocArgument(PossibleMallocOverflows, TheCall,
325 mgr.getASTContext());
326 }
327 }
328 }
329 }
330 }
331
332 OutputPossibleOverflows(PossibleMallocOverflows, D, BR, mgr);
333}
334
335void ento::registerMallocOverflowSecurityChecker(CheckerManager &mgr) {
336 mgr.registerChecker<MallocOverflowSecurityChecker>();
337}
338
339bool ento::shouldRegisterMallocOverflowSecurityChecker(const CheckerManager &mgr) {
340 return true;
341}
StringRef P
const Decl * D
Expr * E
llvm::APSInt APSInt
Definition: Compiler.cpp:22
static bool EvaluatesToZero(APSInt &Val, BinaryOperatorKind op)
__device__ __2f16 float c
do v
Definition: arm_acle.h:91
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:186
SourceManager & getSourceManager()
Definition: ASTContext.h:717
A builtin binary operation expression such as "x + y" or "x <= y".
Definition: Expr.h:3845
Expr * getLHS() const
Definition: Expr.h:3894
Expr * getRHS() const
Definition: Expr.h:3896
Represents a single basic block in a source-level CFG.
Definition: CFG.h:604
ElementList::iterator iterator
Definition: CFG.h:894
iterator begin()
Definition: CFG.h:904
iterator end()
Definition: CFG.h:905
Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt.
Definition: CFG.h:1214
iterator end()
Definition: CFG.h:1295
iterator begin()
Definition: CFG.h:1294
CallExpr - Represents a function call (C99 6.5.2.2, C++ [expr.call]).
Definition: Expr.h:2825
Expr * getArg(unsigned Arg)
getArg - Return the specified argument.
Definition: Expr.h:3016
FunctionDecl * getDirectCallee()
If the callee is a FunctionDecl, return it. Otherwise return null.
Definition: Expr.h:2995
unsigned getNumArgs() const
getNumArgs - Return the number of actual arguments to this call.
Definition: Expr.h:3003
A reference to a declared variable, function, enum, etc.
Definition: Expr.h:1265
ValueDecl * getDecl()
Definition: Expr.h:1333
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:86
DoStmt - This represents a 'do/while' stmt.
Definition: Stmt.h:2726
Stmt * getBody()
Definition: Stmt.h:2751
EvaluatedExprVisitor - This class visits 'Expr *'s.
This represents one expression.
Definition: Expr.h:110
bool EvaluateAsInt(EvalResult &Result, const ASTContext &Ctx, SideEffectsKind AllowSideEffects=SE_NoSideEffects, bool InConstantContext=false) const
EvaluateAsInt - Return true if this is a constant which we can fold and convert to an integer,...
llvm::APSInt EvaluateKnownConstInt(const ASTContext &Ctx, SmallVectorImpl< PartialDiagnosticAt > *Diag=nullptr) const
EvaluateKnownConstInt - Call EvaluateAsRValue and return the folded integer.
Expr * IgnoreParenImpCasts() LLVM_READONLY
Skip past any parentheses and implicit casts which might surround this expression until reaching a fi...
Definition: Expr.cpp:3070
bool isEvaluatable(const ASTContext &Ctx, SideEffectsKind AllowSideEffects=SE_NoSideEffects) const
isEvaluatable - Call EvaluateAsRValue to see if this expression can be constant folded without side-e...
SourceLocation getExprLoc() const LLVM_READONLY
getExprLoc - Return the preferred location for the arrow when diagnosing a problem with a generic exp...
Definition: Expr.cpp:277
QualType getType() const
Definition: Expr.h:142
ForStmt - This represents a 'for (init;cond;inc)' stmt.
Definition: Stmt.h:2782
Stmt * getBody()
Definition: Stmt.h:2826
Represents a function declaration or definition.
Definition: Decl.h:1971
One of these records is kept for each identifier that is lexed.
bool isStr(const char(&Str)[StrLen]) const
Return true if this is the identifier for the specified string.
MemberExpr - [C99 6.5.2.3] Structure and Union Members.
Definition: Expr.h:3177
ValueDecl * getMemberDecl() const
Retrieve the member declaration to which this expression refers.
Definition: Expr.h:3260
IdentifierInfo * getIdentifier() const
Get the identifier that names this declaration, if there is one.
Definition: Decl.h:270
bool isBeforeInTranslationUnit(SourceLocation LHS, SourceLocation RHS) const
Determines the order of 2 source locations in the translation unit.
RetTy Visit(PTR(Stmt) S, ParamTys... P)
Definition: StmtVisitor.h:44
bool isIntegralOrEnumerationType() const
Determine whether this type is an integral or enumeration type.
Definition: Type.h:8411
WhileStmt - This represents a 'while' stmt.
Definition: Stmt.h:2585
Stmt * getBody()
Definition: Stmt.h:2649
ASTContext & getASTContext() override
AnalysisDeclContext * getAnalysisDeclContext(const Decl *D)
CFG * getCFG(Decl const *D)
BugReporter is a utility class for generating PathDiagnostics for analysis.
Definition: BugReporter.h:585
const SourceManager & getSourceManager()
Definition: BugReporter.h:623
void EmitBasicReport(const Decl *DeclWithIssue, const CheckerBase *Checker, StringRef BugName, StringRef BugCategory, StringRef BugStr, PathDiagnosticLocation Loc, ArrayRef< SourceRange > Ranges=std::nullopt, ArrayRef< FixItHint > Fixits=std::nullopt)
ASTContext & getContext()
Definition: BugReporter.h:621
CHECKER * registerChecker(AT &&... Args)
Used to register checkers.
static PathDiagnosticLocation createOperatorLoc(const BinaryOperator *BO, const SourceManager &SM)
Create the location for the operator of the binary expression.
The JSON file list parser is used to communicate input to InstallAPI.
BinaryOperatorKind
@ Result
The result type of a method or function.
EvalResult is a struct with detailed info about an evaluated expression.
Definition: Expr.h:642