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
20#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
21#include "clang/AST/EvaluatedExprVisitor.h"
22#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
23#include "clang/StaticAnalyzer/Core/Checker.h"
24#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
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;
132    ASTContext &Context;
133
134    bool isIntZeroExpr(const Expr *E) const {
135      if (!E->getType()->isIntegralOrEnumerationType())
136        return false;
137      Expr::EvalResult Result;
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) {
162        return Context.getSourceManager().isBeforeInTranslationUnit(
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();
195          Expr::EvalResult Result;
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);
242      EvaluatedExprVisitor<CheckOverflowOps>::VisitBinaryOperator(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) {
284    BR.EmitBasicReport(
285        D, this, "malloc() size overflow", categories::UnixAPI,
286        "the computation of the size of the memory allocation may overflow",
287        PathDiagnosticLocation::createOperatorLoc(Check.mulop,
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}
342