Clang Project

clang_source_code/lib/StaticAnalyzer/Checkers/MallocOverflowSecurityChecker.cpp
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 <utility>
28
29using namespace clang;
30using namespace ento;
31using llvm::APSInt;
32
33namespace {
34struct MallocOverflowCheck {
35  const BinaryOperator *mulop;
36  const Expr *variable;
37  APSInt maxVal;
38
39  MallocOverflowCheck(const BinaryOperator *m, const Expr *v, APSInt val)
40      : mulop(m), variable(v), maxVal(std::move(val)) {}
41};
42
43class MallocOverflowSecurityChecker : public Checker<check::ASTCodeBody> {
44public:
45  void checkASTCodeBody(const Decl *D, AnalysisManager &mgr,
46                        BugReporter &BR) const;
47
48  void CheckMallocArgument(
49    SmallVectorImpl<MallocOverflowCheck> &PossibleMallocOverflows,
50    const Expr *TheArgument, ASTContext &Context) const;
51
52  void OutputPossibleOverflows(
53    SmallVectorImpl<MallocOverflowCheck> &PossibleMallocOverflows,
54    const Decl *D, BugReporter &BR, AnalysisManager &mgr) const;
55
56};
57} // end anonymous namespace
58
59// Return true for computations which evaluate to zero: e.g., mult by 0.
60static inline bool EvaluatesToZero(APSInt &Val, BinaryOperatorKind op) {
61  return (op == BO_Mul) && (Val == 0);
62}
63
64void MallocOverflowSecurityChecker::CheckMallocArgument(
65  SmallVectorImpl<MallocOverflowCheck> &PossibleMallocOverflows,
66  const Expr *TheArgument,
67  ASTContext &Context) const {
68
69  /* Look for a linear combination with a single variable, and at least
70   one multiplication.
71   Reject anything that applies to the variable: an explicit cast,
72   conditional expression, an operation that could reduce the range
73   of the result, or anything too complicated :-).  */
74  const Expr *e = TheArgument;
75  const BinaryOperator * mulop = nullptr;
76  APSInt maxVal;
77
78  for (;;) {
79    maxVal = 0;
80    e = e->IgnoreParenImpCasts();
81    if (const BinaryOperator *binop = dyn_cast<BinaryOperator>(e)) {
82      BinaryOperatorKind opc = binop->getOpcode();
83      // TODO: ignore multiplications by 1, reject if multiplied by 0.
84      if (mulop == nullptr && opc == BO_Mul)
85        mulop = binop;
86      if (opc != BO_Mul && opc != BO_Add && opc != BO_Sub && opc != BO_Shl)
87        return;
88
89      const Expr *lhs = binop->getLHS();
90      const Expr *rhs = binop->getRHS();
91      if (rhs->isEvaluatable(Context)) {
92        e = lhs;
93        maxVal = rhs->EvaluateKnownConstInt(Context);
94        if (EvaluatesToZero(maxVal, opc))
95          return;
96      } else if ((opc == BO_Add || opc == BO_Mul) &&
97                 lhs->isEvaluatable(Context)) {
98        maxVal = lhs->EvaluateKnownConstInt(Context);
99        if (EvaluatesToZero(maxVal, opc))
100          return;
101        e = rhs;
102      } else
103        return;
104    }
105    else if (isa<DeclRefExpr>(e) || isa<MemberExpr>(e))
106      break;
107    else
108      return;
109  }
110
111  if (mulop == nullptr)
112    return;
113
114  //  We've found the right structure of malloc argument, now save
115  // the data so when the body of the function is completely available
116  // we can check for comparisons.
117
118  // TODO: Could push this into the innermost scope where 'e' is
119  // defined, rather than the whole function.
120  PossibleMallocOverflows.push_back(MallocOverflowCheck(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      toScanFor.erase(std::remove_if(toScanFor.begin(), toScanFor.end(), P),
157                      toScanFor.end());
158    }
159
160    void CheckExpr(const Expr *E_p) {
161      auto PredTrue = [](const MallocOverflowCheck &) { return true; };
162      const Expr *E = E_p->IgnoreParenImpCasts();
163      if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E))
164        Erase<DeclRefExpr>(DR, PredTrue);
165      else if (const auto *ME = dyn_cast<MemberExpr>(E)) {
166        Erase<MemberExpr>(ME, PredTrue);
167      }
168    }
169
170    // Check if the argument to malloc is assigned a value
171    // which cannot cause an overflow.
172    // e.g., malloc (mul * x) and,
173    // case 1: mul = <constant value>
174    // case 2: mul = a/b, where b > x
175    void CheckAssignmentExpr(BinaryOperator *AssignEx) {
176      bool assignKnown = false;
177      bool numeratorKnown = false, denomKnown = false;
178      APSInt denomVal;
179      denomVal = 0;
180
181      // Erase if the multiplicand was assigned a constant value.
182      const Expr *rhs = AssignEx->getRHS();
183      if (rhs->isEvaluatable(Context))
184        assignKnown = true;
185
186      // Discard the report if the multiplicand was assigned a value,
187      // that can never overflow after multiplication. e.g., the assignment
188      // is a division operator and the denominator is > other multiplicand.
189      const Expr *rhse = rhs->IgnoreParenImpCasts();
190      if (const BinaryOperator *BOp = dyn_cast<BinaryOperator>(rhse)) {
191        if (BOp->getOpcode() == BO_Div) {
192          const Expr *denom = BOp->getRHS()->IgnoreParenImpCasts();
193          Expr::EvalResult Result;
194          if (denom->EvaluateAsInt(Result, Context)) {
195            denomVal = Result.Val.getInt();
196            denomKnown = true;
197          }
198          const Expr *numerator = BOp->getLHS()->IgnoreParenImpCasts();
199          if (numerator->isEvaluatable(Context))
200            numeratorKnown = true;
201        }
202      }
203      if (!assignKnown && !denomKnown)
204        return;
205      auto denomExtVal = denomVal.getExtValue();
206
207      // Ignore negative denominator.
208      if (denomExtVal < 0)
209        return;
210
211      const Expr *lhs = AssignEx->getLHS();
212      const Expr *E = lhs->IgnoreParenImpCasts();
213
214      auto pred = [assignKnown, numeratorKnown,
215                   denomExtVal](const MallocOverflowCheck &Check) {
216        return assignKnown ||
217               (numeratorKnown && (denomExtVal >= Check.maxVal.getExtValue()));
218      };
219
220      if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E))
221        Erase<DeclRefExpr>(DR, pred);
222      else if (const auto *ME = dyn_cast<MemberExpr>(E))
223        Erase<MemberExpr>(ME, pred);
224    }
225
226  public:
227    void VisitBinaryOperator(BinaryOperator *E) {
228      if (E->isComparisonOp()) {
229        const Expr * lhs = E->getLHS();
230        const Expr * rhs = E->getRHS();
231        // Ignore comparisons against zero, since they generally don't
232        // protect against an overflow.
233        if (!isIntZeroExpr(lhs) && !isIntZeroExpr(rhs)) {
234          CheckExpr(lhs);
235          CheckExpr(rhs);
236        }
237      }
238      if (E->isAssignmentOp())
239        CheckAssignmentExpr(E);
240      EvaluatedExprVisitor<CheckOverflowOps>::VisitBinaryOperator(E);
241    }
242
243    /* We specifically ignore loop conditions, because they're typically
244     not error checks.  */
245    void VisitWhileStmt(WhileStmt *S) {
246      return this->Visit(S->getBody());
247    }
248    void VisitForStmt(ForStmt *S) {
249      return this->Visit(S->getBody());
250    }
251    void VisitDoStmt(DoStmt *S) {
252      return this->Visit(S->getBody());
253    }
254
255    CheckOverflowOps(theVecType &v, ASTContext &ctx)
256    : EvaluatedExprVisitor<CheckOverflowOps>(ctx),
257      toScanFor(v), Context(ctx)
258    { }
259  };
260}
261
262// OutputPossibleOverflows - We've found a possible overflow earlier,
263// now check whether Body might contain a comparison which might be
264// preventing the overflow.
265// This doesn't do flow analysis, range analysis, or points-to analysis; it's
266// just a dumb "is there a comparison" scan.  The aim here is to
267// detect the most blatent cases of overflow and educate the
268// programmer.
269void MallocOverflowSecurityChecker::OutputPossibleOverflows(
270  SmallVectorImpl<MallocOverflowCheck> &PossibleMallocOverflows,
271  const Decl *D, BugReporter &BR, AnalysisManager &mgr) const {
272  // By far the most common case: nothing to check.
273  if (PossibleMallocOverflows.empty())
274    return;
275
276  // Delete any possible overflows which have a comparison.
277  CheckOverflowOps c(PossibleMallocOverflows, BR.getContext());
278  c.Visit(mgr.getAnalysisDeclContext(D)->getBody());
279
280  // Output warnings for all overflows that are left.
281  for (CheckOverflowOps::theVecType::iterator
282       i = PossibleMallocOverflows.begin(),
283       e = PossibleMallocOverflows.end();
284       i != e;
285       ++i) {
286    BR.EmitBasicReport(
287        D, this, "malloc() size overflow", categories::UnixAPI,
288        "the computation of the size of the memory allocation may overflow",
289        PathDiagnosticLocation::createOperatorLoc(i->mulop,
290                                                  BR.getSourceManager()),
291        i->mulop->getSourceRange());
292  }
293}
294
295void MallocOverflowSecurityChecker::checkASTCodeBody(const Decl *D,
296                                             AnalysisManager &mgr,
297                                             BugReporter &BR) const {
298
299  CFG *cfg = mgr.getCFG(D);
300  if (!cfg)
301    return;
302
303  // A list of variables referenced in possibly overflowing malloc operands.
304  SmallVector<MallocOverflowCheck, 2> PossibleMallocOverflows;
305
306  for (CFG::iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) {
307    CFGBlock *block = *it;
308    for (CFGBlock::iterator bi = block->begin(), be = block->end();
309         bi != be; ++bi) {
310      if (Optional<CFGStmt> CS = bi->getAs<CFGStmt>()) {
311        if (const CallExpr *TheCall = dyn_cast<CallExpr>(CS->getStmt())) {
312          // Get the callee.
313          const FunctionDecl *FD = TheCall->getDirectCallee();
314
315          if (!FD)
316            continue;
317
318          // Get the name of the callee. If it's a builtin, strip off the prefix.
319          IdentifierInfo *FnInfo = FD->getIdentifier();
320          if (!FnInfo)
321            continue;
322
323          if (FnInfo->isStr ("malloc") || FnInfo->isStr ("_MALLOC")) {
324            if (TheCall->getNumArgs() == 1)
325              CheckMallocArgument(PossibleMallocOverflows, TheCall->getArg(0),
326                                  mgr.getASTContext());
327          }
328        }
329      }
330    }
331  }
332
333  OutputPossibleOverflows(PossibleMallocOverflows, D, BR, mgr);
334}
335
336void ento::registerMallocOverflowSecurityChecker(CheckerManager &mgr) {
337  mgr.registerChecker<MallocOverflowSecurityChecker>();
338}
339
340bool ento::shouldRegisterMallocOverflowSecurityChecker(const LangOptions &LO) {
341  return true;
342}
343
CodeThinker, Enjoy your reading code