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