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