clang  10.0.0svn
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 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 {
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);
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)
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",
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 }
Represents a function declaration or definition.
Definition: Decl.h:1756
EvaluatedExprVisitor - This class visits &#39;Expr *&#39;s.
ValueDecl * getMemberDecl() const
Retrieve the member declaration to which this expression refers.
Definition: Expr.h:2889
ElementList::iterator iterator
Definition: CFG.h:866
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:88
StringRef P
iterator begin()
Definition: CFG.h:876
static bool isAssignmentOp(Opcode Opc)
Definition: Expr.h:3530
IdentifierInfo * getIdentifier() const
Get the identifier that names this declaration, if there is one.
Definition: Decl.h:269
One of these records is kept for each identifier that is lexed.
Stmt * getBody()
Definition: Stmt.h:2353
bool isStr(const char(&Str)[StrLen]) const
Return true if this is the identifier for the specified string.
Holds long-lived AST nodes (such as types and decls) that can be referred to throughout the semantic ...
Definition: ASTContext.h:160
Definition: Format.h:2327
Keeps track of the various options that can be enabled, which controls the dialect of C or C++ that i...
Definition: LangOptions.h:49
iterator end()
Definition: CFG.h:1302
bool isIntegralOrEnumerationType() const
Determine whether this type is an integral or enumeration type.
Definition: Type.h:6753
BinaryOperatorKind
ForStmt - This represents a &#39;for (init;cond;inc)&#39; stmt.
Definition: Stmt.h:2384
APValue Val
Val - This is the value the expression can be folded to.
Definition: Expr.h:582
Stmt * getBody()
Definition: Stmt.h:2418
A builtin binary operation expression such as "x + y" or "x <= y".
Definition: Expr.h:3404
CFGBlockListTy::iterator iterator
Definition: CFG.h:1293
Represents a single basic block in a source-level CFG.
Definition: CFG.h:576
llvm::APSInt EvaluateKnownConstInt(const ASTContext &Ctx, SmallVectorImpl< PartialDiagnosticAt > *Diag=nullptr) const
EvaluateKnownConstInt - Call EvaluateAsRValue and return the folded integer.
This represents one expression.
Definition: Expr.h:108
Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt...
Definition: CFG.h:1225
Stmt * getBody()
Definition: Stmt.h:2261
QualType getType() const
Definition: Expr.h:137
ValueDecl * getDecl()
Definition: Expr.h:1217
do v
Definition: arm_acle.h:64
DoStmt - This represents a &#39;do/while&#39; stmt.
Definition: Stmt.h:2328
llvm::APSInt APSInt
iterator begin()
Definition: CFG.h:1301
Expr * getLHS() const
Definition: Expr.h:3444
Dataflow Directional Tag Classes.
EvalResult is a struct with detailed info about an evaluated expression.
Definition: Expr.h:580
Expr * IgnoreParenImpCasts() LLVM_READONLY
Skip past any parentheses and implicit casts which might surround this expression until reaching a fi...
Definition: Expr.cpp:2960
static bool EvaluatesToZero(APSInt &Val, BinaryOperatorKind op)
static PathDiagnosticLocation createOperatorLoc(const BinaryOperator *BO, const SourceManager &SM)
Create the location for the operator of the binary expression.
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...
MemberExpr - [C99 6.5.2.3] Structure and Union Members.
Definition: Expr.h:2806
WhileStmt - This represents a &#39;while&#39; stmt.
Definition: Stmt.h:2200
CallExpr - Represents a function call (C99 6.5.2.2, C++ [expr.call]).
Definition: Expr.h:2516
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...
A reference to a declared variable, function, enum, etc.
Definition: Expr.h:1141
Expr * getRHS() const
Definition: Expr.h:3446
iterator end()
Definition: CFG.h:877
APSInt & getInt()
Definition: APValue.h:336
static bool isComparisonOp(Opcode Opc)
Definition: Expr.h:3494