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 "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.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 #include <utility>
  29
  30 using namespace clang;
  31 using namespace ento;
  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(std::move(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       Expr::EvalResult Result;
 139       if (E->EvaluateAsInt(Result, Context))
 140         return Result.Val.getInt() == 0;
 141       return false;
 142     }
 143
 144     static const Decl *getDecl(const DeclRefExpr *DR) { return DR->getDecl(); }
 145     static const Decl *getDecl(const MemberExpr *ME) {
 146       return ME->getMemberDecl();
 147     }
 148
 149     template <typename T1>
 150     void Erase(const T1 *DR,
 151                llvm::function_ref<bool(const MallocOverflowCheck &)> Pred) {
 152       auto P = [DR, Pred](const MallocOverflowCheck &Check) {
 153         if (const auto *CheckDR = dyn_cast<T1>(Check.variable))
 154           return getDecl(CheckDR) == getDecl(DR) && Pred(Check);
 155         return false;
 156       };
 157       toScanFor.erase(std::remove_if(toScanFor.begin(), toScanFor.end(), P),
 158                       toScanFor.end());
 159     }
 160
 161     void CheckExpr(const Expr *E_p) {
 162       auto PredTrue = [](const MallocOverflowCheck &) { 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           Expr::EvalResult Result;
 195           if (denom->EvaluateAsInt(Result, Context)) {
 196             denomVal = Result.Val.getInt();
 197             denomKnown = true;
 198           }
 199           const Expr *numerator = BOp->getLHS()->IgnoreParenImpCasts();
 200           if (numerator->isEvaluatable(Context))
 201             numeratorKnown = true;
 202         }
 203       }
 204       if (!assignKnown && !denomKnown)
 205         return;
 206       auto denomExtVal = denomVal.getExtValue();
 207
 208       // Ignore negative denominator.
 209       if (denomExtVal < 0)
 210         return;
 211
 212       const Expr *lhs = AssignEx->getLHS();
 213       const Expr *E = lhs->IgnoreParenImpCasts();
 214
 215       auto pred = [assignKnown, numeratorKnown,
 216                    denomExtVal](const MallocOverflowCheck &Check) {
 217         return assignKnown ||
 218                (numeratorKnown && (denomExtVal >= Check.maxVal.getExtValue()));
 219       };
 220
 221       if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E))
 222         Erase<DeclRefExpr>(DR, pred);
 223       else if (const auto *ME = dyn_cast<MemberExpr>(E))
 224         Erase<MemberExpr>(ME, pred);
 225     }
 226
 227   public:
 228     void VisitBinaryOperator(BinaryOperator *E) {
 229       if (E->isComparisonOp()) {
 230         const Expr * lhs = E->getLHS();
 231         const Expr * rhs = E->getRHS();
 232         // Ignore comparisons against zero, since they generally don't
 233         // protect against an overflow.
 234         if (!isIntZeroExpr(lhs) && !isIntZeroExpr(rhs)) {
 235           CheckExpr(lhs);
 236           CheckExpr(rhs);
 237         }
 238       }
 239       if (E->isAssignmentOp())
 240         CheckAssignmentExpr(E);
 241       EvaluatedExprVisitor<CheckOverflowOps>::VisitBinaryOperator(E);
 242     }
 243
 244     /* We specifically ignore loop conditions, because they're typically
 245      not error checks.  */
 246     void VisitWhileStmt(WhileStmt *S) {
 247       return this->Visit(S->getBody());
 248     }
 249     void VisitForStmt(ForStmt *S) {
 250       return this->Visit(S->getBody());
 251     }
 252     void VisitDoStmt(DoStmt *S) {
 253       return this->Visit(S->getBody());
 254     }
 255
 256     CheckOverflowOps(theVecType &v, ASTContext &ctx)
 257     : EvaluatedExprVisitor<CheckOverflowOps>(ctx),
 258       toScanFor(v), Context(ctx)
 259     { }
 260   };
 261 }
 262
 263 // OutputPossibleOverflows - We've found a possible overflow earlier,
 264 // now check whether Body might contain a comparison which might be
 265 // preventing the overflow.
 266 // This doesn't do flow analysis, range analysis, or points-to analysis; it's
 267 // just a dumb "is there a comparison" scan.  The aim here is to
 268 // detect the most blatent cases of overflow and educate the
 269 // programmer.
 270 void MallocOverflowSecurityChecker::OutputPossibleOverflows(
 271   SmallVectorImpl<MallocOverflowCheck> &PossibleMallocOverflows,
 272   const Decl *D, BugReporter &BR, AnalysisManager &mgr) const {
 273   // By far the most common case: nothing to check.
 274   if (PossibleMallocOverflows.empty())
 275     return;
 276
 277   // Delete any possible overflows which have a comparison.
 278   CheckOverflowOps c(PossibleMallocOverflows, BR.getContext());
 279   c.Visit(mgr.getAnalysisDeclContext(D)->getBody());
 280
 281   // Output warnings for all overflows that are left.
 282   for (CheckOverflowOps::theVecType::iterator
 283        i = PossibleMallocOverflows.begin(),
 284        e = PossibleMallocOverflows.end();
 285        i != e;
 286        ++i) {
 287     BR.EmitBasicReport(
 288         D, this, "malloc() size overflow", categories::UnixAPI,
 289         "the computation of the size of the memory allocation may overflow",
 290         PathDiagnosticLocation::createOperatorLoc(i->mulop,
 291                                                   BR.getSourceManager()),
 292         i->mulop->getSourceRange());
 293   }
 294 }
 295
 296 void MallocOverflowSecurityChecker::checkASTCodeBody(const Decl *D,
 297                                              AnalysisManager &mgr,
 298                                              BugReporter &BR) const {
 299
 300   CFG *cfg = mgr.getCFG(D);
 301   if (!cfg)
 302     return;
 303
 304   // A list of variables referenced in possibly overflowing malloc operands.
 305   SmallVector<MallocOverflowCheck, 2> PossibleMallocOverflows;
 306
 307   for (CFG::iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) {
 308     CFGBlock *block = *it;
 309     for (CFGBlock::iterator bi = block->begin(), be = block->end();
 310          bi != be; ++bi) {
 311       if (Optional<CFGStmt> CS = bi->getAs<CFGStmt>()) {
 312         if (const CallExpr *TheCall = dyn_cast<CallExpr>(CS->getStmt())) {
 313           // Get the callee.
 314           const FunctionDecl *FD = TheCall->getDirectCallee();
 315
 316           if (!FD)
 317             continue;
 318
 319           // Get the name of the callee. If it's a builtin, strip off the prefix.
 320           IdentifierInfo *FnInfo = FD->getIdentifier();
 321           if (!FnInfo)
 322             continue;
 323
 324           if (FnInfo->isStr ("malloc") || FnInfo->isStr ("_MALLOC")) {
 325             if (TheCall->getNumArgs() == 1)
 326               CheckMallocArgument(PossibleMallocOverflows, TheCall->getArg(0),
 327                                   mgr.getASTContext());
 328           }
 329         }
 330       }
 331     }
 332   }
 333
 334   OutputPossibleOverflows(PossibleMallocOverflows, D, BR, mgr);
 335 }
 336
 337 void
 338 ento::registerMallocOverflowSecurityChecker(CheckerManager &mgr) {
 339   mgr.registerChecker<MallocOverflowSecurityChecker>();
 340 }