contrib/llvm-project/clang/lib/StaticAnalyzer/Checkers/MallocOverflowSecurityChecker.cpp

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