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 <optional>
  28 #include <utility>
  29
  30 using namespace clang;
  31 using namespace ento;
  32 using llvm::APSInt;
  33
  34 namespace {
  35 struct MallocOverflowCheck {
  36   const CallExpr *call;
  37   const BinaryOperator *mulop;
  38   const Expr *variable;
  39   APSInt maxVal;
  40
  41   MallocOverflowCheck(const CallExpr *call, const BinaryOperator *m,
  42                       const Expr *v, APSInt val)
  43       : call(call), mulop(m), variable(v), maxVal(std::move(val)) {}
  44 };
  45
  46 class MallocOverflowSecurityChecker : public Checker<check::ASTCodeBody> {
  47 public:
  48   void checkASTCodeBody(const Decl *D, AnalysisManager &mgr,
  49                         BugReporter &BR) const;
  50
  51   void CheckMallocArgument(
  52       SmallVectorImpl<MallocOverflowCheck> &PossibleMallocOverflows,
  53       const CallExpr *TheCall, ASTContext &Context) const;
  54
  55   void OutputPossibleOverflows(
  56     SmallVectorImpl<MallocOverflowCheck> &PossibleMallocOverflows,
  57     const Decl *D, BugReporter &BR, AnalysisManager &mgr) const;
  58
  59 };
  60 } // end anonymous namespace
  61
  62 // Return true for computations which evaluate to zero: e.g., mult by 0.
  63 static inline bool EvaluatesToZero(APSInt &Val, BinaryOperatorKind op) {
  64   return (op == BO_Mul) && (Val == 0);
  65 }
  66
  67 void MallocOverflowSecurityChecker::CheckMallocArgument(
  68     SmallVectorImpl<MallocOverflowCheck> &PossibleMallocOverflows,
  69     const CallExpr *TheCall, ASTContext &Context) const {
  70
  71   /* Look for a linear combination with a single variable, and at least
  72    one multiplication.
  73    Reject anything that applies to the variable: an explicit cast,
  74    conditional expression, an operation that could reduce the range
  75    of the result, or anything too complicated :-).  */
  76   const Expr *e = TheCall->getArg(0);
  77   const BinaryOperator * mulop = nullptr;
  78   APSInt maxVal;
  79
  80   for (;;) {
  81     maxVal = 0;
  82     e = e->IgnoreParenImpCasts();
  83     if (const BinaryOperator *binop = dyn_cast<BinaryOperator>(e)) {
  84       BinaryOperatorKind opc = binop->getOpcode();
  85       // TODO: ignore multiplications by 1, reject if multiplied by 0.
  86       if (mulop == nullptr && opc == BO_Mul)
  87         mulop = binop;
  88       if (opc != BO_Mul && opc != BO_Add && opc != BO_Sub && opc != BO_Shl)
  89         return;
  90
  91       const Expr *lhs = binop->getLHS();
  92       const Expr *rhs = binop->getRHS();
  93       if (rhs->isEvaluatable(Context)) {
  94         e = lhs;
  95         maxVal = rhs->EvaluateKnownConstInt(Context);
  96         if (EvaluatesToZero(maxVal, opc))
  97           return;
  98       } else if ((opc == BO_Add || opc == BO_Mul) &&
  99                  lhs->isEvaluatable(Context)) {
 100         maxVal = lhs->EvaluateKnownConstInt(Context);
 101         if (EvaluatesToZero(maxVal, opc))
 102           return;
 103         e = rhs;
 104       } else
 105         return;
 106     } else if (isa<DeclRefExpr, 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   PossibleMallocOverflows.push_back(
 120       MallocOverflowCheck(TheCall, 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       llvm::erase_if(toScanFor, P);
 157     }
 158
 159     void CheckExpr(const Expr *E_p) {
 160       const Expr *E = E_p->IgnoreParenImpCasts();
 161       const auto PrecedesMalloc = [E, this](const MallocOverflowCheck &c) {
 162         return Context.getSourceManager().isBeforeInTranslationUnit(
 163             E->getExprLoc(), c.call->getExprLoc());
 164       };
 165       if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E))
 166         Erase<DeclRefExpr>(DR, PrecedesMalloc);
 167       else if (const auto *ME = dyn_cast<MemberExpr>(E)) {
 168         Erase<MemberExpr>(ME, PrecedesMalloc);
 169       }
 170     }
 171
 172     // Check if the argument to malloc is assigned a value
 173     // which cannot cause an overflow.
 174     // e.g., malloc (mul * x) and,
 175     // case 1: mul = <constant value>
 176     // case 2: mul = a/b, where b > x
 177     void CheckAssignmentExpr(BinaryOperator *AssignEx) {
 178       bool assignKnown = false;
 179       bool numeratorKnown = false, denomKnown = false;
 180       APSInt denomVal;
 181       denomVal = 0;
 182
 183       // Erase if the multiplicand was assigned a constant value.
 184       const Expr *rhs = AssignEx->getRHS();
 185       if (rhs->isEvaluatable(Context))
 186         assignKnown = true;
 187
 188       // Discard the report if the multiplicand was assigned a value,
 189       // that can never overflow after multiplication. e.g., the assignment
 190       // is a division operator and the denominator is > other multiplicand.
 191       const Expr *rhse = rhs->IgnoreParenImpCasts();
 192       if (const BinaryOperator *BOp = dyn_cast<BinaryOperator>(rhse)) {
 193         if (BOp->getOpcode() == BO_Div) {
 194           const Expr *denom = BOp->getRHS()->IgnoreParenImpCasts();
 195           Expr::EvalResult Result;
 196           if (denom->EvaluateAsInt(Result, Context)) {
 197             denomVal = Result.Val.getInt();
 198             denomKnown = true;
 199           }
 200           const Expr *numerator = BOp->getLHS()->IgnoreParenImpCasts();
 201           if (numerator->isEvaluatable(Context))
 202             numeratorKnown = true;
 203         }
 204       }
 205       if (!assignKnown && !denomKnown)
 206         return;
 207       auto denomExtVal = denomVal.getExtValue();
 208
 209       // Ignore negative denominator.
 210       if (denomExtVal < 0)
 211         return;
 212
 213       const Expr *lhs = AssignEx->getLHS();
 214       const Expr *E = lhs->IgnoreParenImpCasts();
 215
 216       auto pred = [assignKnown, numeratorKnown,
 217                    denomExtVal](const MallocOverflowCheck &Check) {
 218         return assignKnown ||
 219                (numeratorKnown && (denomExtVal >= Check.maxVal.getExtValue()));
 220       };
 221
 222       if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E))
 223         Erase<DeclRefExpr>(DR, pred);
 224       else if (const auto *ME = dyn_cast<MemberExpr>(E))
 225         Erase<MemberExpr>(ME, pred);
 226     }
 227
 228   public:
 229     void VisitBinaryOperator(BinaryOperator *E) {
 230       if (E->isComparisonOp()) {
 231         const Expr * lhs = E->getLHS();
 232         const Expr * rhs = E->getRHS();
 233         // Ignore comparisons against zero, since they generally don't
 234         // protect against an overflow.
 235         if (!isIntZeroExpr(lhs) && !isIntZeroExpr(rhs)) {
 236           CheckExpr(lhs);
 237           CheckExpr(rhs);
 238         }
 239       }
 240       if (E->isAssignmentOp())
 241         CheckAssignmentExpr(E);
 242       EvaluatedExprVisitor<CheckOverflowOps>::VisitBinaryOperator(E);
 243     }
 244
 245     /* We specifically ignore loop conditions, because they're typically
 246      not error checks.  */
 247     void VisitWhileStmt(WhileStmt *S) {
 248       return this->Visit(S->getBody());
 249     }
 250     void VisitForStmt(ForStmt *S) {
 251       return this->Visit(S->getBody());
 252     }
 253     void VisitDoStmt(DoStmt *S) {
 254       return this->Visit(S->getBody());
 255     }
 256
 257     CheckOverflowOps(theVecType &v, ASTContext &ctx)
 258     : EvaluatedExprVisitor<CheckOverflowOps>(ctx),
 259       toScanFor(v), Context(ctx)
 260     { }
 261   };
 262 }
 263
 264 // OutputPossibleOverflows - We've found a possible overflow earlier,
 265 // now check whether Body might contain a comparison which might be
 266 // preventing the overflow.
 267 // This doesn't do flow analysis, range analysis, or points-to analysis; it's
 268 // just a dumb "is there a comparison" scan.  The aim here is to
 269 // detect the most blatent cases of overflow and educate the
 270 // programmer.
 271 void MallocOverflowSecurityChecker::OutputPossibleOverflows(
 272   SmallVectorImpl<MallocOverflowCheck> &PossibleMallocOverflows,
 273   const Decl *D, BugReporter &BR, AnalysisManager &mgr) const {
 274   // By far the most common case: nothing to check.
 275   if (PossibleMallocOverflows.empty())
 276     return;
 277
 278   // Delete any possible overflows which have a comparison.
 279   CheckOverflowOps c(PossibleMallocOverflows, BR.getContext());
 280   c.Visit(mgr.getAnalysisDeclContext(D)->getBody());
 281
 282   // Output warnings for all overflows that are left.
 283   for (const MallocOverflowCheck &Check : PossibleMallocOverflows) {
 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(Check.mulop,
 288                                                   BR.getSourceManager()),
 289         Check.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 (std::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
 317             // prefix.
 318             IdentifierInfo *FnInfo = FD->getIdentifier();
 319             if (!FnInfo)
 320               continue;
 321
 322             if (FnInfo->isStr("malloc") || FnInfo->isStr("_MALLOC")) {
 323               if (TheCall->getNumArgs() == 1)
 324                 CheckMallocArgument(PossibleMallocOverflows, TheCall,
 325                                     mgr.getASTContext());
 326             }
 327           }
 328         }
 329     }
 330   }
 331
 332   OutputPossibleOverflows(PossibleMallocOverflows, D, BR, mgr);
 333 }
 334
 335 void ento::registerMallocOverflowSecurityChecker(CheckerManager &mgr) {
 336   mgr.registerChecker<MallocOverflowSecurityChecker>();
 337 }
 338
 339 bool ento::shouldRegisterMallocOverflowSecurityChecker(const CheckerManager &mgr) {
 340   return true;
 341 }