Home | History | Annotate | Download | only in Checkers 
      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 
     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     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 
     57 void 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 
    109 namespace {
    110 // A worker class for OutputPossibleOverflows.
    111 class CheckOverflowOps :
    112   public EvaluatedExprVisitor<CheckOverflowOps> {
    113 public:
    114   typedef llvm::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   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.getAnalysisContext(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("MallocOverflowSecurityChecker",
    218       "the computation of the size of the memory allocation may overflow",
    219       PathDiagnosticLocation::createOperatorLoc(i->mulop,
    220                                                 BR.getSourceManager()),
    221       &R, 1);
    222   }
    223 }
    224 
    225 void MallocOverflowSecurityChecker::checkASTCodeBody(const Decl *D,
    226                                              AnalysisManager &mgr,
    227                                              BugReporter &BR) const {
    228 
    229   CFG *cfg = mgr.getCFG(D);
    230   if (!cfg)
    231     return;
    232 
    233   // A list of variables referenced in possibly overflowing malloc operands.
    234   llvm::SmallVector<MallocOverflowCheck, 2> PossibleMallocOverflows;
    235 
    236   for (CFG::iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) {
    237     CFGBlock *block = *it;
    238     for (CFGBlock::iterator bi = block->begin(), be = block->end();
    239          bi != be; ++bi) {
    240       if (const CFGStmt *CS = bi->getAs<CFGStmt>()) {
    241         if (const CallExpr *TheCall = dyn_cast<CallExpr>(CS->getStmt())) {
    242           // Get the callee.
    243           const FunctionDecl *FD = TheCall->getDirectCallee();
    244 
    245           if (!FD)
    246             return;
    247 
    248           // Get the name of the callee. If it's a builtin, strip off the prefix.
    249           IdentifierInfo *FnInfo = FD->getIdentifier();
    250           if (!FnInfo)
    251             return;
    252 
    253           if (FnInfo->isStr ("malloc") || FnInfo->isStr ("_MALLOC")) {
    254             if (TheCall->getNumArgs() == 1)
    255               CheckMallocArgument(PossibleMallocOverflows, TheCall->getArg(0),
    256                                   mgr.getASTContext());
    257           }
    258         }
    259       }
    260     }
    261   }
    262 
    263   OutputPossibleOverflows(PossibleMallocOverflows, D, BR, mgr);
    264 }
    265 
    266 void ento::registerMallocOverflowSecurityChecker(CheckerManager &mgr) {
    267   mgr.registerChecker<MallocOverflowSecurityChecker>();
    268 }
    269