MallocOverflowSecurityChecker.cpp revision 17f7bdddd11a2dc5b4be248f756e14b1ebfe207b 
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/PathSensitive/AnalysisManager.h"
24#include "clang/StaticAnalyzer/Core/Checker.h"
25#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.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      return (E->getType()->isIntegralOrEnumerationType()
122              && E->isEvaluatable(Context)
123              && E->EvaluateAsInt(Context) == 0);
124    }
125
126    void CheckExpr(const Expr *E_p) {
127      const Expr *E = E_p->IgnoreParenImpCasts();
128
129      theVecType::iterator i = toScanFor.end();
130      theVecType::iterator e = toScanFor.begin();
131
132      if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E)) {
133        const Decl * EdreD = DR->getDecl();
134        while (i != e) {
135          --i;
136          if (const DeclRefExpr *DR_i = dyn_cast<DeclRefExpr>(i->variable)) {
137            if (DR_i->getDecl() == EdreD)
138              i = toScanFor.erase(i);
139          }
140        }
141      }
142      else if (isa<MemberExpr>(E)) {
143        // No points-to analysis, just look at the member
144        const Decl * EmeMD = dyn_cast<MemberExpr>(E)->getMemberDecl();
145        while (i != e) {
146          --i;
147          if (isa<MemberExpr>(i->variable)) {
148            if (dyn_cast<MemberExpr>(i->variable)->getMemberDecl() == EmeMD)
149              i = toScanFor.erase (i);
150          }
151        }
152      }
153    }
154
155  public:
156    void VisitBinaryOperator(BinaryOperator *E) {
157      if (E->isComparisonOp()) {
158        const Expr * lhs = E->getLHS();
159        const Expr * rhs = E->getRHS();
160        // Ignore comparisons against zero, since they generally don't
161        // protect against an overflow.
162        if (!isIntZeroExpr(lhs) && ! isIntZeroExpr(rhs)) {
163          CheckExpr(lhs);
164          CheckExpr(rhs);
165        }
166      }
167      EvaluatedExprVisitor<CheckOverflowOps>::VisitBinaryOperator(E);
168    }
169
170    /* We specifically ignore loop conditions, because they're typically
171     not error checks.  */
172    void VisitWhileStmt(WhileStmt *S) {
173      return this->Visit(S->getBody());
174    }
175    void VisitForStmt(ForStmt *S) {
176      return this->Visit(S->getBody());
177    }
178    void VisitDoStmt(DoStmt *S) {
179      return this->Visit(S->getBody());
180    }
181
182    CheckOverflowOps(theVecType &v, ASTContext &ctx)
183    : EvaluatedExprVisitor<CheckOverflowOps>(ctx),
184      toScanFor(v), Context(ctx)
185    { }
186  };
187}
188
189// OutputPossibleOverflows - We've found a possible overflow earlier,
190// now check whether Body might contain a comparison which might be
191// preventing the overflow.
192// This doesn't do flow analysis, range analysis, or points-to analysis; it's
193// just a dumb "is there a comparison" scan.  The aim here is to
194// detect the most blatent cases of overflow and educate the
195// programmer.
196void MallocOverflowSecurityChecker::OutputPossibleOverflows(
197  llvm::SmallVectorImpl<MallocOverflowCheck> &PossibleMallocOverflows,
198  const Decl *D, BugReporter &BR, AnalysisManager &mgr) const {
199  // By far the most common case: nothing to check.
200  if (PossibleMallocOverflows.empty())
201    return;
202
203  // Delete any possible overflows which have a comparison.
204  CheckOverflowOps c(PossibleMallocOverflows, BR.getContext());
205  c.Visit(mgr.getAnalysisContext(D)->getBody());
206
207  // Output warnings for all overflows that are left.
208  for (CheckOverflowOps::theVecType::iterator
209       i = PossibleMallocOverflows.begin(),
210       e = PossibleMallocOverflows.end();
211       i != e;
212       ++i) {
213    SourceRange R = i->mulop->getSourceRange();
214    BR.EmitBasicReport("MallocOverflowSecurityChecker",
215        "the computation of the size of the memory allocation may overflow",
216        i->mulop->getOperatorLoc(), &R, 1);
217  }
218}
219
220void MallocOverflowSecurityChecker::checkASTCodeBody(const Decl *D,
221                                             AnalysisManager &mgr,
222                                             BugReporter &BR) const {
223
224  CFG *cfg = mgr.getCFG(D);
225  if (!cfg)
226    return;
227
228  // A list of variables referenced in possibly overflowing malloc operands.
229  llvm::SmallVector<MallocOverflowCheck, 2> PossibleMallocOverflows;
230
231  for (CFG::iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) {
232    CFGBlock *block = *it;
233    for (CFGBlock::iterator bi = block->begin(), be = block->end();
234         bi != be; ++bi) {
235      if (const CFGStmt *CS = bi->getAs<CFGStmt>()) {
236        if (const CallExpr *TheCall = dyn_cast<CallExpr>(CS->getStmt())) {
237          // Get the callee.
238          const FunctionDecl *FD = TheCall->getDirectCallee();
239
240          if (!FD)
241            return;
242
243          // Get the name of the callee. If it's a builtin, strip off the prefix.
244          IdentifierInfo *FnInfo = FD->getIdentifier();
245
246          if (FnInfo->isStr ("malloc") || FnInfo->isStr ("_MALLOC")) {
247            if (TheCall->getNumArgs() == 1)
248              CheckMallocArgument(PossibleMallocOverflows, TheCall->getArg(0),
249                                  mgr.getASTContext());
250          }
251        }
252      }
253    }
254  }
255
256  OutputPossibleOverflows(PossibleMallocOverflows, D, BR, mgr);
257}
258
259void ento::registerMallocOverflowSecurityChecker(CheckerManager &mgr) {
260  mgr.registerChecker<MallocOverflowSecurityChecker>();
261}
262
263