clang  15.0.0git
MallocOverflowSecurityChecker.cpp
Go to the documentation of this file.
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 
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 CallExpr *call;
36  const BinaryOperator *mulop;
37  const Expr *variable;
38  APSInt maxVal;
39 
40  MallocOverflowCheck(const CallExpr *call, const BinaryOperator *m,
41  const Expr *v, APSInt val)
42  : call(call), mulop(m), variable(v), maxVal(std::move(val)) {}
43 };
44 
45 class MallocOverflowSecurityChecker : public Checker<check::ASTCodeBody> {
46 public:
47  void checkASTCodeBody(const Decl *D, AnalysisManager &mgr,
48  BugReporter &BR) const;
49 
50  void CheckMallocArgument(
51  SmallVectorImpl<MallocOverflowCheck> &PossibleMallocOverflows,
52  const CallExpr *TheCall, ASTContext &Context) const;
53 
54  void OutputPossibleOverflows(
55  SmallVectorImpl<MallocOverflowCheck> &PossibleMallocOverflows,
56  const Decl *D, BugReporter &BR, AnalysisManager &mgr) const;
57 
58 };
59 } // end anonymous namespace
60 
61 // Return true for computations which evaluate to zero: e.g., mult by 0.
62 static inline bool EvaluatesToZero(APSInt &Val, BinaryOperatorKind op) {
63  return (op == BO_Mul) && (Val == 0);
64 }
65 
66 void MallocOverflowSecurityChecker::CheckMallocArgument(
67  SmallVectorImpl<MallocOverflowCheck> &PossibleMallocOverflows,
68  const CallExpr *TheCall, 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 = TheCall->getArg(0);
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  } else if (isa<DeclRefExpr, 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  PossibleMallocOverflows.push_back(
119  MallocOverflowCheck(TheCall, mulop, e, maxVal));
120 }
121 
122 namespace {
123 // A worker class for OutputPossibleOverflows.
124 class CheckOverflowOps :
125  public EvaluatedExprVisitor<CheckOverflowOps> {
126 public:
127  typedef SmallVectorImpl<MallocOverflowCheck> theVecType;
128 
129 private:
130  theVecType &toScanFor;
131  ASTContext &Context;
132 
133  bool isIntZeroExpr(const Expr *E) const {
135  return false;
136  Expr::EvalResult Result;
137  if (E->EvaluateAsInt(Result, Context))
138  return Result.Val.getInt() == 0;
139  return false;
140  }
141 
142  static const Decl *getDecl(const DeclRefExpr *DR) { return DR->getDecl(); }
143  static const Decl *getDecl(const MemberExpr *ME) {
144  return ME->getMemberDecl();
145  }
146 
147  template <typename T1>
148  void Erase(const T1 *DR,
149  llvm::function_ref<bool(const MallocOverflowCheck &)> Pred) {
150  auto P = [DR, Pred](const MallocOverflowCheck &Check) {
151  if (const auto *CheckDR = dyn_cast<T1>(Check.variable))
152  return getDecl(CheckDR) == getDecl(DR) && Pred(Check);
153  return false;
154  };
155  llvm::erase_if(toScanFor, P);
156  }
157 
158  void CheckExpr(const Expr *E_p) {
159  const Expr *E = E_p->IgnoreParenImpCasts();
160  const auto PrecedesMalloc = [E, this](const MallocOverflowCheck &c) {
162  E->getExprLoc(), c.call->getExprLoc());
163  };
164  if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E))
165  Erase<DeclRefExpr>(DR, PrecedesMalloc);
166  else if (const auto *ME = dyn_cast<MemberExpr>(E)) {
167  Erase<MemberExpr>(ME, PrecedesMalloc);
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);
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",
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,
327  mgr.getASTContext());
328  }
329  }
330  }
331  }
332  }
333 
334  OutputPossibleOverflows(PossibleMallocOverflows, D, BR, mgr);
335 }
336 
337 void ento::registerMallocOverflowSecurityChecker(CheckerManager &mgr) {
338  mgr.registerChecker<MallocOverflowSecurityChecker>();
339 }
340 
341 bool ento::shouldRegisterMallocOverflowSecurityChecker(const CheckerManager &mgr) {
342  return true;
343 }
clang::BinaryOperator::isAssignmentOp
static bool isAssignmentOp(Opcode Opc)
Definition: Expr.h:3942
clang::CFGBlock::begin
iterator begin()
Definition: CFG.h:875
clang::WhileStmt
WhileStmt - This represents a 'while' stmt.
Definition: Stmt.h:2373
clang::BinaryOperator::isComparisonOp
static bool isComparisonOp(Opcode Opc)
Definition: Expr.h:3906
clang::CFGBlock::iterator
ElementList::iterator iterator
Definition: CFG.h:865
llvm::SmallVector
Definition: LLVM.h:38
EvaluatedExprVisitor.h
clang::CFG::end
iterator end()
Definition: CFG.h:1304
llvm::Optional
Definition: LLVM.h:40
clang::CFG
Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt.
Definition: CFG.h:1225
clang::ASTContext::getSourceManager
SourceManager & getSourceManager()
Definition: ASTContext.h:716
clang::CFGBlock
Represents a single basic block in a source-level CFG.
Definition: CFG.h:576
APSInt
llvm::APSInt APSInt
Definition: ByteCodeEmitter.cpp:19
clang::IdentifierInfo::isStr
bool isStr(const char(&Str)[StrLen]) const
Return true if this is the identifier for the specified string.
Definition: IdentifierTable.h:176
clang::CallExpr::getDirectCallee
FunctionDecl * getDirectCallee()
If the callee is a FunctionDecl, return it. Otherwise return null.
Definition: Expr.h:2971
BuiltinCheckerRegistration.h
clang::BinaryOperator
A builtin binary operation expression such as "x + y" or "x <= y".
Definition: Expr.h:3807
BugReporter.h
clang::ASTContext
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:208
clang::CallExpr::getArg
Expr * getArg(unsigned Arg)
getArg - Return the specified argument.
Definition: Expr.h:2992
clang::ForStmt
ForStmt - This represents a 'for (init;cond;inc)' stmt.
Definition: Stmt.h:2566
clang::ento::PathDiagnosticLocation::createOperatorLoc
static PathDiagnosticLocation createOperatorLoc(const BinaryOperator *BO, const SourceManager &SM)
Create the location for the operator of the binary expression.
Definition: PathDiagnostic.cpp:604
clang::DeclRefExpr::getDecl
ValueDecl * getDecl()
Definition: Expr.h:1295
clang::Expr::EvalResult
EvalResult is a struct with detailed info about an evaluated expression.
Definition: Expr.h:612
clang::Expr::EvaluateKnownConstInt
llvm::APSInt EvaluateKnownConstInt(const ASTContext &Ctx, SmallVectorImpl< PartialDiagnosticAt > *Diag=nullptr) const
EvaluateKnownConstInt - Call EvaluateAsRValue and return the folded integer.
Definition: ExprConstant.cpp:15216
clang::MemberExpr::getMemberDecl
ValueDecl * getMemberDecl() const
Retrieve the member declaration to which this expression refers.
Definition: Expr.h:3247
clang::SourceManager::isBeforeInTranslationUnit
bool isBeforeInTranslationUnit(SourceLocation LHS, SourceLocation RHS) const
Determines the order of 2 source locations in the translation unit.
Definition: SourceManager.cpp:2014
P
StringRef P
Definition: ASTMatchersInternal.cpp:563
clang::CFGStmt
Definition: CFG.h:132
clang::NamedDecl::getIdentifier
IdentifierInfo * getIdentifier() const
Get the identifier that names this declaration, if there is one.
Definition: Decl.h:268
clang::BinaryOperator::getLHS
Expr * getLHS() const
Definition: Expr.h:3856
clang::CallExpr::getNumArgs
unsigned getNumArgs() const
getNumArgs - Return the number of actual arguments to this call.
Definition: Expr.h:2979
clang::Expr::getExprLoc
SourceLocation getExprLoc() const LLVM_READONLY
getExprLoc - Return the preferred location for the arrow when diagnosing a problem with a generic exp...
Definition: Expr.cpp:247
clang::Decl
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:83
clang::Expr::IgnoreParenImpCasts
Expr * IgnoreParenImpCasts() LLVM_READONLY
Skip past any parentheses and implicit casts which might surround this expression until reaching a fi...
Definition: Expr.cpp:2953
clang::DoStmt
DoStmt - This represents a 'do/while' stmt.
Definition: Stmt.h:2510
clang::BinaryOperatorKind
BinaryOperatorKind
Definition: OperationKinds.h:25
clang::IdentifierInfo
One of these records is kept for each identifier that is lexed.
Definition: IdentifierTable.h:84
clang::Expr::EvaluateAsInt
bool EvaluateAsInt(EvalResult &Result, const ASTContext &Ctx, SideEffectsKind AllowSideEffects=SE_NoSideEffects, bool InConstantContext=false) const
EvaluateAsInt - Return true if this is a constant which we can fold and convert to an integer,...
Definition: ExprConstant.cpp:14993
Checker.h
std
Definition: Format.h:4303
clang
Definition: CalledOnceCheck.h:17
clang::BinaryOperator::getRHS
Expr * getRHS() const
Definition: Expr.h:3858
clang::Expr::getType
QualType getType() const
Definition: Expr.h:141
clang::CFG::begin
iterator begin()
Definition: CFG.h:1303
c
__device__ __2f16 float c
Definition: __clang_hip_libdevice_declares.h:315
clang::MemberExpr
MemberExpr - [C99 6.5.2.3] Structure and Union Members.
Definition: Expr.h:3164
clang::Expr::isEvaluatable
bool isEvaluatable(const ASTContext &Ctx, SideEffectsKind AllowSideEffects=SE_NoSideEffects) const
isEvaluatable - Call EvaluateAsRValue to see if this expression can be constant folded without side-e...
Definition: ExprConstant.cpp:15207
v
do v
Definition: arm_acle.h:76
llvm::SmallVectorImpl
Definition: Randstruct.h:18
clang::EvaluatedExprVisitor
EvaluatedExprVisitor - This class visits 'Expr *'s.
Definition: EvaluatedExprVisitor.h:128
clang::Expr
This represents one expression.
Definition: Expr.h:109
clang::CFGBlock::end
iterator end()
Definition: CFG.h:876
AnalysisManager.h
clang::ento::categories::UnixAPI
const char *const UnixAPI
Definition: CommonBugCategories.cpp:21
clang::DeclRefExpr
A reference to a declared variable, function, enum, etc.
Definition: Expr.h:1223
clang::FunctionDecl
Represents a function declaration or definition.
Definition: Decl.h:1872
clang::CallExpr
CallExpr - Represents a function call (C99 6.5.2.2, C++ [expr.call]).
Definition: Expr.h:2801
clang::Type::isIntegralOrEnumerationType
bool isIntegralOrEnumerationType() const
Determine whether this type is an integral or enumeration type.
Definition: Type.h:7199
EvaluatesToZero
static bool EvaluatesToZero(APSInt &Val, BinaryOperatorKind op)
Definition: MallocOverflowSecurityChecker.cpp:62