clang  6.0.0svn
MallocOverflowSecurityChecker.cpp
Go to the documentation of this file.
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 "ClangSACheckers.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 {
137  return false;
138  llvm::APSInt Result;
139  if (E->EvaluateAsInt(Result, Context))
140  return Result == 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  if (denom->EvaluateAsInt(denomVal, Context))
195  denomKnown = true;
196  const Expr *numerator = BOp->getLHS()->IgnoreParenImpCasts();
197  if (numerator->isEvaluatable(Context))
198  numeratorKnown = true;
199  }
200  }
201  if (!assignKnown && !denomKnown)
202  return;
203  auto denomExtVal = denomVal.getExtValue();
204 
205  // Ignore negative denominator.
206  if (denomExtVal < 0)
207  return;
208 
209  const Expr *lhs = AssignEx->getLHS();
210  const Expr *E = lhs->IgnoreParenImpCasts();
211 
212  auto pred = [assignKnown, numeratorKnown,
213  denomExtVal](const MallocOverflowCheck &Check) {
214  return assignKnown ||
215  (numeratorKnown && (denomExtVal >= Check.maxVal.getExtValue()));
216  };
217 
218  if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E))
219  Erase<DeclRefExpr>(DR, pred);
220  else if (const auto *ME = dyn_cast<MemberExpr>(E))
221  Erase<MemberExpr>(ME, pred);
222  }
223 
224  public:
225  void VisitBinaryOperator(BinaryOperator *E) {
226  if (E->isComparisonOp()) {
227  const Expr * lhs = E->getLHS();
228  const Expr * rhs = E->getRHS();
229  // Ignore comparisons against zero, since they generally don't
230  // protect against an overflow.
231  if (!isIntZeroExpr(lhs) && !isIntZeroExpr(rhs)) {
232  CheckExpr(lhs);
233  CheckExpr(rhs);
234  }
235  }
236  if (E->isAssignmentOp())
237  CheckAssignmentExpr(E);
239  }
240 
241  /* We specifically ignore loop conditions, because they're typically
242  not error checks. */
243  void VisitWhileStmt(WhileStmt *S) {
244  return this->Visit(S->getBody());
245  }
246  void VisitForStmt(ForStmt *S) {
247  return this->Visit(S->getBody());
248  }
249  void VisitDoStmt(DoStmt *S) {
250  return this->Visit(S->getBody());
251  }
252 
253  CheckOverflowOps(theVecType &v, ASTContext &ctx)
255  toScanFor(v), Context(ctx)
256  { }
257  };
258 }
259 
260 // OutputPossibleOverflows - We've found a possible overflow earlier,
261 // now check whether Body might contain a comparison which might be
262 // preventing the overflow.
263 // This doesn't do flow analysis, range analysis, or points-to analysis; it's
264 // just a dumb "is there a comparison" scan. The aim here is to
265 // detect the most blatent cases of overflow and educate the
266 // programmer.
267 void MallocOverflowSecurityChecker::OutputPossibleOverflows(
268  SmallVectorImpl<MallocOverflowCheck> &PossibleMallocOverflows,
269  const Decl *D, BugReporter &BR, AnalysisManager &mgr) const {
270  // By far the most common case: nothing to check.
271  if (PossibleMallocOverflows.empty())
272  return;
273 
274  // Delete any possible overflows which have a comparison.
275  CheckOverflowOps c(PossibleMallocOverflows, BR.getContext());
276  c.Visit(mgr.getAnalysisDeclContext(D)->getBody());
277 
278  // Output warnings for all overflows that are left.
279  for (CheckOverflowOps::theVecType::iterator
280  i = PossibleMallocOverflows.begin(),
281  e = PossibleMallocOverflows.end();
282  i != e;
283  ++i) {
284  BR.EmitBasicReport(
285  D, this, "malloc() size overflow", categories::UnixAPI,
286  "the computation of the size of the memory allocation may overflow",
288  BR.getSourceManager()),
289  i->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 (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 prefix.
317  IdentifierInfo *FnInfo = FD->getIdentifier();
318  if (!FnInfo)
319  continue;
320 
321  if (FnInfo->isStr ("malloc") || FnInfo->isStr ("_MALLOC")) {
322  if (TheCall->getNumArgs() == 1)
323  CheckMallocArgument(PossibleMallocOverflows, TheCall->getArg(0),
324  mgr.getASTContext());
325  }
326  }
327  }
328  }
329  }
330 
331  OutputPossibleOverflows(PossibleMallocOverflows, D, BR, mgr);
332 }
333 
334 void
335 ento::registerMallocOverflowSecurityChecker(CheckerManager &mgr) {
336  mgr.registerChecker<MallocOverflowSecurityChecker>();
337 }
FunctionDecl - An instance of this class is created to represent a function declaration or definition...
Definition: Decl.h:1698
EvaluatedExprVisitor - This class visits &#39;Expr *&#39;s.
ValueDecl * getMemberDecl() const
Retrieve the member declaration to which this expression refers.
Definition: Expr.h:2483
Stmt * getBody() const
Get the body of the Declaration.
ElementList::iterator iterator
Definition: CFG.h:568
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:86
StringRef P
iterator begin()
Definition: CFG.h:576
bool EvaluateAsInt(llvm::APSInt &Result, const ASTContext &Ctx, SideEffectsKind AllowSideEffects=SE_NoSideEffects) const
EvaluateAsInt - Return true if this is a constant which we can fold and convert to an integer...
static bool isAssignmentOp(Opcode Opc)
Definition: Expr.h:3108
IdentifierInfo * getIdentifier() const
getIdentifier - Get the identifier that names this declaration, if there is one.
Definition: Decl.h:265
One of these records is kept for each identifier that is lexed.
Stmt * getBody()
Definition: Stmt.h:1175
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:149
Definition: Format.h:1900
iterator end()
Definition: CFG.h:907
bool isIntegralOrEnumerationType() const
Determine whether this type is an integral or enumeration type.
Definition: Type.h:6221
BinaryOperatorKind
ForStmt - This represents a &#39;for (init;cond;inc)&#39; stmt.
Definition: Stmt.h:1203
ASTContext & getContext()
Definition: BugReporter.h:461
Stmt * getBody()
Definition: Stmt.h:1238
A builtin binary operation expression such as "x + y" or "x <= y".
Definition: Expr.h:2985
CFGBlockListTy::iterator iterator
Definition: CFG.h:898
ASTContext & getASTContext() override
AnalysisDeclContext * getAnalysisDeclContext(const Decl *D)
CFGBlock - Represents a single basic block in a source-level CFG.
Definition: CFG.h:422
llvm::APSInt EvaluateKnownConstInt(const ASTContext &Ctx, SmallVectorImpl< PartialDiagnosticAt > *Diag=nullptr) const
EvaluateKnownConstInt - Call EvaluateAsRValue and return the folded integer.
Expr - This represents one expression.
Definition: Expr.h:106
CFG - Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt...
Definition: CFG.h:834
Stmt * getBody()
Definition: Stmt.h:1130
QualType getType() const
Definition: Expr.h:128
CFG * getCFG(Decl const *D)
ValueDecl * getDecl()
Definition: Expr.h:1041
do v
Definition: arm_acle.h:78
DoStmt - This represents a &#39;do/while&#39; stmt.
Definition: Stmt.h:1154
BugReporter is a utility class for generating PathDiagnostics for analysis.
Definition: BugReporter.h:403
CHECKER * registerChecker()
Used to register checkers.
void EmitBasicReport(const Decl *DeclWithIssue, const CheckerBase *Checker, StringRef BugName, StringRef BugCategory, StringRef BugStr, PathDiagnosticLocation Loc, ArrayRef< SourceRange > Ranges=None)
iterator begin()
Definition: CFG.h:906
Expr * getLHS() const
Definition: Expr.h:3029
Dataflow Directional Tag Classes.
Expr * IgnoreParenImpCasts() LLVM_READONLY
IgnoreParenImpCasts - Ignore parentheses and implicit casts.
Definition: Expr.cpp:2550
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.
SourceManager & getSourceManager()
Definition: BugReporter.h:463
MemberExpr - [C99 6.5.2.3] Structure and Union Members.
Definition: Expr.h:2387
WhileStmt - This represents a &#39;while&#39; stmt.
Definition: Stmt.h:1098
CallExpr - Represents a function call (C99 6.5.2.2, C++ [expr.call]).
Definition: Expr.h:2209
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:956
Expr * getRHS() const
Definition: Expr.h:3031
iterator end()
Definition: CFG.h:577
static bool isComparisonOp(Opcode Opc)
Definition: Expr.h:3075