1e5dd7070Spatrick // MallocOverflowSecurityChecker.cpp - Check for malloc overflows -*- C++ -*-=//
2e5dd7070Spatrick //
3e5dd7070Spatrick // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4e5dd7070Spatrick // See https://llvm.org/LICENSE.txt for license information.
5e5dd7070Spatrick // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6e5dd7070Spatrick //
7e5dd7070Spatrick //===----------------------------------------------------------------------===//
8e5dd7070Spatrick //
9e5dd7070Spatrick // This checker detects a common memory allocation security flaw.
10e5dd7070Spatrick // Suppose 'unsigned int n' comes from an untrusted source. If the
11e5dd7070Spatrick // code looks like 'malloc (n * 4)', and an attacker can make 'n' be
12e5dd7070Spatrick // say MAX_UINT/4+2, then instead of allocating the correct 'n' 4-byte
13e5dd7070Spatrick // elements, this will actually allocate only two because of overflow.
14e5dd7070Spatrick // Then when the rest of the program attempts to store values past the
15e5dd7070Spatrick // second element, these values will actually overwrite other items in
16e5dd7070Spatrick // the heap, probably allowing the attacker to execute arbitrary code.
17e5dd7070Spatrick //
18e5dd7070Spatrick //===----------------------------------------------------------------------===//
19e5dd7070Spatrick
20e5dd7070Spatrick #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
21e5dd7070Spatrick #include "clang/AST/EvaluatedExprVisitor.h"
22e5dd7070Spatrick #include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
23e5dd7070Spatrick #include "clang/StaticAnalyzer/Core/Checker.h"
24e5dd7070Spatrick #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
25e5dd7070Spatrick #include "llvm/ADT/APSInt.h"
26e5dd7070Spatrick #include "llvm/ADT/SmallVector.h"
27*12c85518Srobert #include <optional>
28e5dd7070Spatrick #include <utility>
29e5dd7070Spatrick
30e5dd7070Spatrick using namespace clang;
31e5dd7070Spatrick using namespace ento;
32e5dd7070Spatrick using llvm::APSInt;
33e5dd7070Spatrick
34e5dd7070Spatrick namespace {
35e5dd7070Spatrick struct MallocOverflowCheck {
36*12c85518Srobert const CallExpr *call;
37e5dd7070Spatrick const BinaryOperator *mulop;
38e5dd7070Spatrick const Expr *variable;
39e5dd7070Spatrick APSInt maxVal;
40e5dd7070Spatrick
MallocOverflowCheck__anon55ae42fe0111::MallocOverflowCheck41*12c85518Srobert MallocOverflowCheck(const CallExpr *call, const BinaryOperator *m,
42*12c85518Srobert const Expr *v, APSInt val)
43*12c85518Srobert : call(call), mulop(m), variable(v), maxVal(std::move(val)) {}
44e5dd7070Spatrick };
45e5dd7070Spatrick
46e5dd7070Spatrick class MallocOverflowSecurityChecker : public Checker<check::ASTCodeBody> {
47e5dd7070Spatrick public:
48e5dd7070Spatrick void checkASTCodeBody(const Decl *D, AnalysisManager &mgr,
49e5dd7070Spatrick BugReporter &BR) const;
50e5dd7070Spatrick
51e5dd7070Spatrick void CheckMallocArgument(
52e5dd7070Spatrick SmallVectorImpl<MallocOverflowCheck> &PossibleMallocOverflows,
53*12c85518Srobert const CallExpr *TheCall, ASTContext &Context) const;
54e5dd7070Spatrick
55e5dd7070Spatrick void OutputPossibleOverflows(
56e5dd7070Spatrick SmallVectorImpl<MallocOverflowCheck> &PossibleMallocOverflows,
57e5dd7070Spatrick const Decl *D, BugReporter &BR, AnalysisManager &mgr) const;
58e5dd7070Spatrick
59e5dd7070Spatrick };
60e5dd7070Spatrick } // end anonymous namespace
61e5dd7070Spatrick
62e5dd7070Spatrick // Return true for computations which evaluate to zero: e.g., mult by 0.
EvaluatesToZero(APSInt & Val,BinaryOperatorKind op)63e5dd7070Spatrick static inline bool EvaluatesToZero(APSInt &Val, BinaryOperatorKind op) {
64e5dd7070Spatrick return (op == BO_Mul) && (Val == 0);
65e5dd7070Spatrick }
66e5dd7070Spatrick
CheckMallocArgument(SmallVectorImpl<MallocOverflowCheck> & PossibleMallocOverflows,const CallExpr * TheCall,ASTContext & Context) const67e5dd7070Spatrick void MallocOverflowSecurityChecker::CheckMallocArgument(
68e5dd7070Spatrick SmallVectorImpl<MallocOverflowCheck> &PossibleMallocOverflows,
69*12c85518Srobert const CallExpr *TheCall, ASTContext &Context) const {
70e5dd7070Spatrick
71e5dd7070Spatrick /* Look for a linear combination with a single variable, and at least
72e5dd7070Spatrick one multiplication.
73e5dd7070Spatrick Reject anything that applies to the variable: an explicit cast,
74e5dd7070Spatrick conditional expression, an operation that could reduce the range
75e5dd7070Spatrick of the result, or anything too complicated :-). */
76*12c85518Srobert const Expr *e = TheCall->getArg(0);
77e5dd7070Spatrick const BinaryOperator * mulop = nullptr;
78e5dd7070Spatrick APSInt maxVal;
79e5dd7070Spatrick
80e5dd7070Spatrick for (;;) {
81e5dd7070Spatrick maxVal = 0;
82e5dd7070Spatrick e = e->IgnoreParenImpCasts();
83e5dd7070Spatrick if (const BinaryOperator *binop = dyn_cast<BinaryOperator>(e)) {
84e5dd7070Spatrick BinaryOperatorKind opc = binop->getOpcode();
85e5dd7070Spatrick // TODO: ignore multiplications by 1, reject if multiplied by 0.
86e5dd7070Spatrick if (mulop == nullptr && opc == BO_Mul)
87e5dd7070Spatrick mulop = binop;
88e5dd7070Spatrick if (opc != BO_Mul && opc != BO_Add && opc != BO_Sub && opc != BO_Shl)
89e5dd7070Spatrick return;
90e5dd7070Spatrick
91e5dd7070Spatrick const Expr *lhs = binop->getLHS();
92e5dd7070Spatrick const Expr *rhs = binop->getRHS();
93e5dd7070Spatrick if (rhs->isEvaluatable(Context)) {
94e5dd7070Spatrick e = lhs;
95e5dd7070Spatrick maxVal = rhs->EvaluateKnownConstInt(Context);
96e5dd7070Spatrick if (EvaluatesToZero(maxVal, opc))
97e5dd7070Spatrick return;
98e5dd7070Spatrick } else if ((opc == BO_Add || opc == BO_Mul) &&
99e5dd7070Spatrick lhs->isEvaluatable(Context)) {
100e5dd7070Spatrick maxVal = lhs->EvaluateKnownConstInt(Context);
101e5dd7070Spatrick if (EvaluatesToZero(maxVal, opc))
102e5dd7070Spatrick return;
103e5dd7070Spatrick e = rhs;
104e5dd7070Spatrick } else
105e5dd7070Spatrick return;
106*12c85518Srobert } else if (isa<DeclRefExpr, MemberExpr>(e))
107e5dd7070Spatrick break;
108e5dd7070Spatrick else
109e5dd7070Spatrick return;
110e5dd7070Spatrick }
111e5dd7070Spatrick
112e5dd7070Spatrick if (mulop == nullptr)
113e5dd7070Spatrick return;
114e5dd7070Spatrick
115e5dd7070Spatrick // We've found the right structure of malloc argument, now save
116e5dd7070Spatrick // the data so when the body of the function is completely available
117e5dd7070Spatrick // we can check for comparisons.
118e5dd7070Spatrick
119*12c85518Srobert PossibleMallocOverflows.push_back(
120*12c85518Srobert MallocOverflowCheck(TheCall, mulop, e, maxVal));
121e5dd7070Spatrick }
122e5dd7070Spatrick
123e5dd7070Spatrick namespace {
124e5dd7070Spatrick // A worker class for OutputPossibleOverflows.
125e5dd7070Spatrick class CheckOverflowOps :
126e5dd7070Spatrick public EvaluatedExprVisitor<CheckOverflowOps> {
127e5dd7070Spatrick public:
128e5dd7070Spatrick typedef SmallVectorImpl<MallocOverflowCheck> theVecType;
129e5dd7070Spatrick
130e5dd7070Spatrick private:
131e5dd7070Spatrick theVecType &toScanFor;
132e5dd7070Spatrick ASTContext &Context;
133e5dd7070Spatrick
isIntZeroExpr(const Expr * E) const134e5dd7070Spatrick bool isIntZeroExpr(const Expr *E) const {
135e5dd7070Spatrick if (!E->getType()->isIntegralOrEnumerationType())
136e5dd7070Spatrick return false;
137e5dd7070Spatrick Expr::EvalResult Result;
138e5dd7070Spatrick if (E->EvaluateAsInt(Result, Context))
139e5dd7070Spatrick return Result.Val.getInt() == 0;
140e5dd7070Spatrick return false;
141e5dd7070Spatrick }
142e5dd7070Spatrick
getDecl(const DeclRefExpr * DR)143e5dd7070Spatrick static const Decl *getDecl(const DeclRefExpr *DR) { return DR->getDecl(); }
getDecl(const MemberExpr * ME)144e5dd7070Spatrick static const Decl *getDecl(const MemberExpr *ME) {
145e5dd7070Spatrick return ME->getMemberDecl();
146e5dd7070Spatrick }
147e5dd7070Spatrick
148e5dd7070Spatrick template <typename T1>
Erase(const T1 * DR,llvm::function_ref<bool (const MallocOverflowCheck &)> Pred)149e5dd7070Spatrick void Erase(const T1 *DR,
150e5dd7070Spatrick llvm::function_ref<bool(const MallocOverflowCheck &)> Pred) {
151e5dd7070Spatrick auto P = [DR, Pred](const MallocOverflowCheck &Check) {
152e5dd7070Spatrick if (const auto *CheckDR = dyn_cast<T1>(Check.variable))
153e5dd7070Spatrick return getDecl(CheckDR) == getDecl(DR) && Pred(Check);
154e5dd7070Spatrick return false;
155e5dd7070Spatrick };
156*12c85518Srobert llvm::erase_if(toScanFor, P);
157e5dd7070Spatrick }
158e5dd7070Spatrick
CheckExpr(const Expr * E_p)159e5dd7070Spatrick void CheckExpr(const Expr *E_p) {
160e5dd7070Spatrick const Expr *E = E_p->IgnoreParenImpCasts();
161*12c85518Srobert const auto PrecedesMalloc = [E, this](const MallocOverflowCheck &c) {
162*12c85518Srobert return Context.getSourceManager().isBeforeInTranslationUnit(
163*12c85518Srobert E->getExprLoc(), c.call->getExprLoc());
164*12c85518Srobert };
165e5dd7070Spatrick if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E))
166*12c85518Srobert Erase<DeclRefExpr>(DR, PrecedesMalloc);
167e5dd7070Spatrick else if (const auto *ME = dyn_cast<MemberExpr>(E)) {
168*12c85518Srobert Erase<MemberExpr>(ME, PrecedesMalloc);
169e5dd7070Spatrick }
170e5dd7070Spatrick }
171e5dd7070Spatrick
172e5dd7070Spatrick // Check if the argument to malloc is assigned a value
173e5dd7070Spatrick // which cannot cause an overflow.
174e5dd7070Spatrick // e.g., malloc (mul * x) and,
175e5dd7070Spatrick // case 1: mul = <constant value>
176e5dd7070Spatrick // case 2: mul = a/b, where b > x
CheckAssignmentExpr(BinaryOperator * AssignEx)177e5dd7070Spatrick void CheckAssignmentExpr(BinaryOperator *AssignEx) {
178e5dd7070Spatrick bool assignKnown = false;
179e5dd7070Spatrick bool numeratorKnown = false, denomKnown = false;
180e5dd7070Spatrick APSInt denomVal;
181e5dd7070Spatrick denomVal = 0;
182e5dd7070Spatrick
183e5dd7070Spatrick // Erase if the multiplicand was assigned a constant value.
184e5dd7070Spatrick const Expr *rhs = AssignEx->getRHS();
185e5dd7070Spatrick if (rhs->isEvaluatable(Context))
186e5dd7070Spatrick assignKnown = true;
187e5dd7070Spatrick
188e5dd7070Spatrick // Discard the report if the multiplicand was assigned a value,
189e5dd7070Spatrick // that can never overflow after multiplication. e.g., the assignment
190e5dd7070Spatrick // is a division operator and the denominator is > other multiplicand.
191e5dd7070Spatrick const Expr *rhse = rhs->IgnoreParenImpCasts();
192e5dd7070Spatrick if (const BinaryOperator *BOp = dyn_cast<BinaryOperator>(rhse)) {
193e5dd7070Spatrick if (BOp->getOpcode() == BO_Div) {
194e5dd7070Spatrick const Expr *denom = BOp->getRHS()->IgnoreParenImpCasts();
195e5dd7070Spatrick Expr::EvalResult Result;
196e5dd7070Spatrick if (denom->EvaluateAsInt(Result, Context)) {
197e5dd7070Spatrick denomVal = Result.Val.getInt();
198e5dd7070Spatrick denomKnown = true;
199e5dd7070Spatrick }
200e5dd7070Spatrick const Expr *numerator = BOp->getLHS()->IgnoreParenImpCasts();
201e5dd7070Spatrick if (numerator->isEvaluatable(Context))
202e5dd7070Spatrick numeratorKnown = true;
203e5dd7070Spatrick }
204e5dd7070Spatrick }
205e5dd7070Spatrick if (!assignKnown && !denomKnown)
206e5dd7070Spatrick return;
207e5dd7070Spatrick auto denomExtVal = denomVal.getExtValue();
208e5dd7070Spatrick
209e5dd7070Spatrick // Ignore negative denominator.
210e5dd7070Spatrick if (denomExtVal < 0)
211e5dd7070Spatrick return;
212e5dd7070Spatrick
213e5dd7070Spatrick const Expr *lhs = AssignEx->getLHS();
214e5dd7070Spatrick const Expr *E = lhs->IgnoreParenImpCasts();
215e5dd7070Spatrick
216e5dd7070Spatrick auto pred = [assignKnown, numeratorKnown,
217e5dd7070Spatrick denomExtVal](const MallocOverflowCheck &Check) {
218e5dd7070Spatrick return assignKnown ||
219e5dd7070Spatrick (numeratorKnown && (denomExtVal >= Check.maxVal.getExtValue()));
220e5dd7070Spatrick };
221e5dd7070Spatrick
222e5dd7070Spatrick if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E))
223e5dd7070Spatrick Erase<DeclRefExpr>(DR, pred);
224e5dd7070Spatrick else if (const auto *ME = dyn_cast<MemberExpr>(E))
225e5dd7070Spatrick Erase<MemberExpr>(ME, pred);
226e5dd7070Spatrick }
227e5dd7070Spatrick
228e5dd7070Spatrick public:
VisitBinaryOperator(BinaryOperator * E)229e5dd7070Spatrick void VisitBinaryOperator(BinaryOperator *E) {
230e5dd7070Spatrick if (E->isComparisonOp()) {
231e5dd7070Spatrick const Expr * lhs = E->getLHS();
232e5dd7070Spatrick const Expr * rhs = E->getRHS();
233e5dd7070Spatrick // Ignore comparisons against zero, since they generally don't
234e5dd7070Spatrick // protect against an overflow.
235e5dd7070Spatrick if (!isIntZeroExpr(lhs) && !isIntZeroExpr(rhs)) {
236e5dd7070Spatrick CheckExpr(lhs);
237e5dd7070Spatrick CheckExpr(rhs);
238e5dd7070Spatrick }
239e5dd7070Spatrick }
240e5dd7070Spatrick if (E->isAssignmentOp())
241e5dd7070Spatrick CheckAssignmentExpr(E);
242e5dd7070Spatrick EvaluatedExprVisitor<CheckOverflowOps>::VisitBinaryOperator(E);
243e5dd7070Spatrick }
244e5dd7070Spatrick
245e5dd7070Spatrick /* We specifically ignore loop conditions, because they're typically
246e5dd7070Spatrick not error checks. */
VisitWhileStmt(WhileStmt * S)247e5dd7070Spatrick void VisitWhileStmt(WhileStmt *S) {
248e5dd7070Spatrick return this->Visit(S->getBody());
249e5dd7070Spatrick }
VisitForStmt(ForStmt * S)250e5dd7070Spatrick void VisitForStmt(ForStmt *S) {
251e5dd7070Spatrick return this->Visit(S->getBody());
252e5dd7070Spatrick }
VisitDoStmt(DoStmt * S)253e5dd7070Spatrick void VisitDoStmt(DoStmt *S) {
254e5dd7070Spatrick return this->Visit(S->getBody());
255e5dd7070Spatrick }
256e5dd7070Spatrick
CheckOverflowOps(theVecType & v,ASTContext & ctx)257e5dd7070Spatrick CheckOverflowOps(theVecType &v, ASTContext &ctx)
258e5dd7070Spatrick : EvaluatedExprVisitor<CheckOverflowOps>(ctx),
259e5dd7070Spatrick toScanFor(v), Context(ctx)
260e5dd7070Spatrick { }
261e5dd7070Spatrick };
262e5dd7070Spatrick }
263e5dd7070Spatrick
264e5dd7070Spatrick // OutputPossibleOverflows - We've found a possible overflow earlier,
265e5dd7070Spatrick // now check whether Body might contain a comparison which might be
266e5dd7070Spatrick // preventing the overflow.
267e5dd7070Spatrick // This doesn't do flow analysis, range analysis, or points-to analysis; it's
268e5dd7070Spatrick // just a dumb "is there a comparison" scan. The aim here is to
269e5dd7070Spatrick // detect the most blatent cases of overflow and educate the
270e5dd7070Spatrick // programmer.
OutputPossibleOverflows(SmallVectorImpl<MallocOverflowCheck> & PossibleMallocOverflows,const Decl * D,BugReporter & BR,AnalysisManager & mgr) const271e5dd7070Spatrick void MallocOverflowSecurityChecker::OutputPossibleOverflows(
272e5dd7070Spatrick SmallVectorImpl<MallocOverflowCheck> &PossibleMallocOverflows,
273e5dd7070Spatrick const Decl *D, BugReporter &BR, AnalysisManager &mgr) const {
274e5dd7070Spatrick // By far the most common case: nothing to check.
275e5dd7070Spatrick if (PossibleMallocOverflows.empty())
276e5dd7070Spatrick return;
277e5dd7070Spatrick
278e5dd7070Spatrick // Delete any possible overflows which have a comparison.
279e5dd7070Spatrick CheckOverflowOps c(PossibleMallocOverflows, BR.getContext());
280e5dd7070Spatrick c.Visit(mgr.getAnalysisDeclContext(D)->getBody());
281e5dd7070Spatrick
282e5dd7070Spatrick // Output warnings for all overflows that are left.
283e5dd7070Spatrick for (CheckOverflowOps::theVecType::iterator
284e5dd7070Spatrick i = PossibleMallocOverflows.begin(),
285e5dd7070Spatrick e = PossibleMallocOverflows.end();
286e5dd7070Spatrick i != e;
287e5dd7070Spatrick ++i) {
288e5dd7070Spatrick BR.EmitBasicReport(
289e5dd7070Spatrick D, this, "malloc() size overflow", categories::UnixAPI,
290e5dd7070Spatrick "the computation of the size of the memory allocation may overflow",
291e5dd7070Spatrick PathDiagnosticLocation::createOperatorLoc(i->mulop,
292e5dd7070Spatrick BR.getSourceManager()),
293e5dd7070Spatrick i->mulop->getSourceRange());
294e5dd7070Spatrick }
295e5dd7070Spatrick }
296e5dd7070Spatrick
checkASTCodeBody(const Decl * D,AnalysisManager & mgr,BugReporter & BR) const297e5dd7070Spatrick void MallocOverflowSecurityChecker::checkASTCodeBody(const Decl *D,
298e5dd7070Spatrick AnalysisManager &mgr,
299e5dd7070Spatrick BugReporter &BR) const {
300e5dd7070Spatrick
301e5dd7070Spatrick CFG *cfg = mgr.getCFG(D);
302e5dd7070Spatrick if (!cfg)
303e5dd7070Spatrick return;
304e5dd7070Spatrick
305e5dd7070Spatrick // A list of variables referenced in possibly overflowing malloc operands.
306e5dd7070Spatrick SmallVector<MallocOverflowCheck, 2> PossibleMallocOverflows;
307e5dd7070Spatrick
308e5dd7070Spatrick for (CFG::iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) {
309e5dd7070Spatrick CFGBlock *block = *it;
310e5dd7070Spatrick for (CFGBlock::iterator bi = block->begin(), be = block->end();
311e5dd7070Spatrick bi != be; ++bi) {
312*12c85518Srobert if (std::optional<CFGStmt> CS = bi->getAs<CFGStmt>()) {
313e5dd7070Spatrick if (const CallExpr *TheCall = dyn_cast<CallExpr>(CS->getStmt())) {
314e5dd7070Spatrick // Get the callee.
315e5dd7070Spatrick const FunctionDecl *FD = TheCall->getDirectCallee();
316e5dd7070Spatrick
317e5dd7070Spatrick if (!FD)
318e5dd7070Spatrick continue;
319e5dd7070Spatrick
320*12c85518Srobert // Get the name of the callee. If it's a builtin, strip off the
321*12c85518Srobert // prefix.
322e5dd7070Spatrick IdentifierInfo *FnInfo = FD->getIdentifier();
323e5dd7070Spatrick if (!FnInfo)
324e5dd7070Spatrick continue;
325e5dd7070Spatrick
326e5dd7070Spatrick if (FnInfo->isStr("malloc") || FnInfo->isStr("_MALLOC")) {
327e5dd7070Spatrick if (TheCall->getNumArgs() == 1)
328*12c85518Srobert CheckMallocArgument(PossibleMallocOverflows, TheCall,
329e5dd7070Spatrick mgr.getASTContext());
330e5dd7070Spatrick }
331e5dd7070Spatrick }
332e5dd7070Spatrick }
333e5dd7070Spatrick }
334e5dd7070Spatrick }
335e5dd7070Spatrick
336e5dd7070Spatrick OutputPossibleOverflows(PossibleMallocOverflows, D, BR, mgr);
337e5dd7070Spatrick }
338e5dd7070Spatrick
registerMallocOverflowSecurityChecker(CheckerManager & mgr)339e5dd7070Spatrick void ento::registerMallocOverflowSecurityChecker(CheckerManager &mgr) {
340e5dd7070Spatrick mgr.registerChecker<MallocOverflowSecurityChecker>();
341e5dd7070Spatrick }
342e5dd7070Spatrick
shouldRegisterMallocOverflowSecurityChecker(const CheckerManager & mgr)343ec727ea7Spatrick bool ento::shouldRegisterMallocOverflowSecurityChecker(const CheckerManager &mgr) {
344e5dd7070Spatrick return true;
345e5dd7070Spatrick }
346