contrib/llvm/tools/clang/lib/StaticAnalyzer/Checkers/MallocOverflowSecurityChecker.cpp

   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
  28 using namespace clang;
  29 using namespace ento;
  30
  31 namespace {
  32 struct 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
  41 class MallocOverflowSecurityChecker : public Checker<check::ASTCodeBody> {
  42 public:
  43   void checkASTCodeBody(const Decl *D, AnalysisManager &mgr,
  44                         BugReporter &BR) const;
  45
  46   void CheckMallocArgument(
  47     SmallVectorImpl<MallocOverflowCheck> &PossibleMallocOverflows,
  48     const Expr *TheArgument, ASTContext &Context) const;
  49
  50   void OutputPossibleOverflows(
  51     SmallVectorImpl<MallocOverflowCheck> &PossibleMallocOverflows,
  52     const Decl *D, BugReporter &BR, AnalysisManager &mgr) const;
  53
  54 };
  55 } // end anonymous namespace
  56
  57 void MallocOverflowSecurityChecker::CheckMallocArgument(
  58   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
 109 namespace {
 110 // A worker class for OutputPossibleOverflows.
 111 class CheckOverflowOps :
 112   public EvaluatedExprVisitor<CheckOverflowOps> {
 113 public:
 114   typedef SmallVectorImpl<MallocOverflowCheck> theVecType;
 115
 116 private:
 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.
 199 void MallocOverflowSecurityChecker::OutputPossibleOverflows(
 200   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
 224 void 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   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 (Optional<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
 265 void ento::registerMallocOverflowSecurityChecker(CheckerManager &mgr) {
 266   mgr.registerChecker<MallocOverflowSecurityChecker>();
 267 }