MallocOverflowSecurityChecker.cpp revision 55fc873017f10f6f566b182b70f6fc22aefa3464 
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/SmallVector.h"
27
28using namespace clang;
29using namespace ento;
30
31namespace {
32struct MallocOverflowCheck {
33  const BinaryOperator *mulop;
34  const Expr *variable;
35
36  MallocOverflowCheck (const BinaryOperator *m, const Expr *v)
37    : mulop(m), variable (v)
38  {}
39};
40
41class MallocOverflowSecurityChecker : public Checker<check::ASTCodeBody> {
42public:
43  void checkASTCodeBody(const Decl *D, AnalysisManager &mgr,
44                        BugReporter &BR) const;
45
46  void CheckMallocArgument(
47    llvm::SmallVectorImpl<MallocOverflowCheck> &PossibleMallocOverflows,
48    const Expr *TheArgument, ASTContext &Context) const;
49
50  void OutputPossibleOverflows(
51    llvm::SmallVectorImpl<MallocOverflowCheck> &PossibleMallocOverflows,
52    const Decl *D, BugReporter &BR, AnalysisManager &mgr) const;
53
54};
55} // end anonymous namespace
56
57void MallocOverflowSecurityChecker::CheckMallocArgument(
58  llvm::SmallVectorImpl<MallocOverflowCheck> &PossibleMallocOverflows,
59  const Expr *TheArgument,
60  ASTContext &Context) const {
61
62  /* Look for a linear combination with a single variable, and at least
63   one multiplication.
64   Reject anything that applies to the variable: an explicit cast,
65   conditional expression, an operation that could reduce the range
66   of the result, or anything too complicated :-).  */
67  const Expr * e = TheArgument;
68  const BinaryOperator * mulop = NULL;
69
70  for (;;) {
71    e = e->IgnoreParenImpCasts();
72    if (isa<BinaryOperator>(e)) {
73      const BinaryOperator * binop = dyn_cast<BinaryOperator>(e);
74      BinaryOperatorKind opc = binop->getOpcode();
75      // TODO: ignore multiplications by 1, reject if multiplied by 0.
76      if (mulop == NULL && opc == BO_Mul)
77        mulop = binop;
78      if (opc != BO_Mul && opc != BO_Add && opc != BO_Sub && opc != BO_Shl)
79        return;
80
81      const Expr *lhs = binop->getLHS();
82      const Expr *rhs = binop->getRHS();
83      if (rhs->isEvaluatable(Context))
84        e = lhs;
85      else if ((opc == BO_Add || opc == BO_Mul)
86               && lhs->isEvaluatable(Context))
87        e = rhs;
88      else
89        return;
90    }
91    else if (isa<DeclRefExpr>(e) || isa<MemberExpr>(e))
92      break;
93    else
94      return;
95  }
96
97  if (mulop == NULL)
98    return;
99
100  //  We've found the right structure of malloc argument, now save
101  // the data so when the body of the function is completely available
102  // we can check for comparisons.
103
104  // TODO: Could push this into the innermost scope where 'e' is
105  // defined, rather than the whole function.
106  PossibleMallocOverflows.push_back(MallocOverflowCheck(mulop, e));
107}
108
109namespace {
110// A worker class for OutputPossibleOverflows.
111class CheckOverflowOps :
112  public EvaluatedExprVisitor<CheckOverflowOps> {
113public:
114  typedef llvm::SmallVectorImpl<MallocOverflowCheck> theVecType;
115
116private:
117    theVecType &toScanFor;
118    ASTContext &Context;
119
120    bool isIntZeroExpr(const Expr *E) const {
121      if (!E->getType()->isIntegralOrEnumerationType())
122        return false;
123      llvm::APSInt Result;
124      if (E->EvaluateAsInt(Result, Context))
125        return Result == 0;
126      return false;
127    }
128
129    void CheckExpr(const Expr *E_p) {
130      const Expr *E = E_p->IgnoreParenImpCasts();
131
132      theVecType::iterator i = toScanFor.end();
133      theVecType::iterator e = toScanFor.begin();
134
135      if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E)) {
136        const Decl * EdreD = DR->getDecl();
137        while (i != e) {
138          --i;
139          if (const DeclRefExpr *DR_i = dyn_cast<DeclRefExpr>(i->variable)) {
140            if (DR_i->getDecl() == EdreD)
141              i = toScanFor.erase(i);
142          }
143        }
144      }
145      else if (isa<MemberExpr>(E)) {
146        // No points-to analysis, just look at the member
147        const Decl * EmeMD = dyn_cast<MemberExpr>(E)->getMemberDecl();
148        while (i != e) {
149          --i;
150          if (isa<MemberExpr>(i->variable)) {
151            if (dyn_cast<MemberExpr>(i->variable)->getMemberDecl() == EmeMD)
152              i = toScanFor.erase (i);
153          }
154        }
155      }
156    }
157
158  public:
159    void VisitBinaryOperator(BinaryOperator *E) {
160      if (E->isComparisonOp()) {
161        const Expr * lhs = E->getLHS();
162        const Expr * rhs = E->getRHS();
163        // Ignore comparisons against zero, since they generally don't
164        // protect against an overflow.
165        if (!isIntZeroExpr(lhs) && ! isIntZeroExpr(rhs)) {
166          CheckExpr(lhs);
167          CheckExpr(rhs);
168        }
169      }
170      EvaluatedExprVisitor<CheckOverflowOps>::VisitBinaryOperator(E);
171    }
172
173    /* We specifically ignore loop conditions, because they're typically
174     not error checks.  */
175    void VisitWhileStmt(WhileStmt *S) {
176      return this->Visit(S->getBody());
177    }
178    void VisitForStmt(ForStmt *S) {
179      return this->Visit(S->getBody());
180    }
181    void VisitDoStmt(DoStmt *S) {
182      return this->Visit(S->getBody());
183    }
184
185    CheckOverflowOps(theVecType &v, ASTContext &ctx)
186    : EvaluatedExprVisitor<CheckOverflowOps>(ctx),
187      toScanFor(v), Context(ctx)
188    { }
189  };
190}
191
192// OutputPossibleOverflows - We've found a possible overflow earlier,
193// now check whether Body might contain a comparison which might be
194// preventing the overflow.
195// This doesn't do flow analysis, range analysis, or points-to analysis; it's
196// just a dumb "is there a comparison" scan.  The aim here is to
197// detect the most blatent cases of overflow and educate the
198// programmer.
199void MallocOverflowSecurityChecker::OutputPossibleOverflows(
200  llvm::SmallVectorImpl<MallocOverflowCheck> &PossibleMallocOverflows,
201  const Decl *D, BugReporter &BR, AnalysisManager &mgr) const {
202  // By far the most common case: nothing to check.
203  if (PossibleMallocOverflows.empty())
204    return;
205
206  // Delete any possible overflows which have a comparison.
207  CheckOverflowOps c(PossibleMallocOverflows, BR.getContext());
208  c.Visit(mgr.getAnalysisDeclContext(D)->getBody());
209
210  // Output warnings for all overflows that are left.
211  for (CheckOverflowOps::theVecType::iterator
212       i = PossibleMallocOverflows.begin(),
213       e = PossibleMallocOverflows.end();
214       i != e;
215       ++i) {
216    SourceRange R = i->mulop->getSourceRange();
217    BR.EmitBasicReport(D, "malloc() size overflow", categories::UnixAPI,
218      "the computation of the size of the memory allocation may overflow",
219      PathDiagnosticLocation::createOperatorLoc(i->mulop,
220                                                BR.getSourceManager()), &R, 1);
221  }
222}
223
224void MallocOverflowSecurityChecker::checkASTCodeBody(const Decl *D,
225                                             AnalysisManager &mgr,
226                                             BugReporter &BR) const {
227
228  CFG *cfg = mgr.getCFG(D);
229  if (!cfg)
230    return;
231
232  // A list of variables referenced in possibly overflowing malloc operands.
233  llvm::SmallVector<MallocOverflowCheck, 2> PossibleMallocOverflows;
234
235  for (CFG::iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) {
236    CFGBlock *block = *it;
237    for (CFGBlock::iterator bi = block->begin(), be = block->end();
238         bi != be; ++bi) {
239      if (const CFGStmt *CS = bi->getAs<CFGStmt>()) {
240        if (const CallExpr *TheCall = dyn_cast<CallExpr>(CS->getStmt())) {
241          // Get the callee.
242          const FunctionDecl *FD = TheCall->getDirectCallee();
243
244          if (!FD)
245            return;
246
247          // Get the name of the callee. If it's a builtin, strip off the prefix.
248          IdentifierInfo *FnInfo = FD->getIdentifier();
249          if (!FnInfo)
250            return;
251
252          if (FnInfo->isStr ("malloc") || FnInfo->isStr ("_MALLOC")) {
253            if (TheCall->getNumArgs() == 1)
254              CheckMallocArgument(PossibleMallocOverflows, TheCall->getArg(0),
255                                  mgr.getASTContext());
256          }
257        }
258      }
259    }
260  }
261
262  OutputPossibleOverflows(PossibleMallocOverflows, D, BR, mgr);
263}
264
265void ento::registerMallocOverflowSecurityChecker(CheckerManager &mgr) {
266  mgr.registerChecker<MallocOverflowSecurityChecker>();
267}
268