1 // MallocOverflowSecurityChecker.cpp - Check for malloc overflows -*- C++ -*-=//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
19 //===----------------------------------------------------------------------===//
21 #include "ClangSACheckers.h"
22 #include "clang/AST/EvaluatedExprVisitor.h"
23 #include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
24 #include "clang/StaticAnalyzer/Core/Checker.h"
25 #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
26 #include "llvm/ADT/APSInt.h"
27 #include "llvm/ADT/SmallVector.h"
30 using namespace clang;
35 struct MallocOverflowCheck {
36 const BinaryOperator *mulop;
40 MallocOverflowCheck(const BinaryOperator *m, const Expr *v, APSInt val)
41 : mulop(m), variable(v), maxVal(std::move(val)) {}
44 class MallocOverflowSecurityChecker : public Checker<check::ASTCodeBody> {
46 void checkASTCodeBody(const Decl *D, AnalysisManager &mgr,
47 BugReporter &BR) const;
49 void CheckMallocArgument(
50 SmallVectorImpl<MallocOverflowCheck> &PossibleMallocOverflows,
51 const Expr *TheArgument, ASTContext &Context) const;
53 void OutputPossibleOverflows(
54 SmallVectorImpl<MallocOverflowCheck> &PossibleMallocOverflows,
55 const Decl *D, BugReporter &BR, AnalysisManager &mgr) const;
58 } // end anonymous namespace
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);
65 void MallocOverflowSecurityChecker::CheckMallocArgument(
66 SmallVectorImpl<MallocOverflowCheck> &PossibleMallocOverflows,
67 const Expr *TheArgument,
68 ASTContext &Context) const {
70 /* Look for a linear combination with a single variable, and at least
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;
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)
87 if (opc != BO_Mul && opc != BO_Add && opc != BO_Sub && opc != BO_Shl)
90 const Expr *lhs = binop->getLHS();
91 const Expr *rhs = binop->getRHS();
92 if (rhs->isEvaluatable(Context)) {
94 maxVal = rhs->EvaluateKnownConstInt(Context);
95 if (EvaluatesToZero(maxVal, opc))
97 } else if ((opc == BO_Add || opc == BO_Mul) &&
98 lhs->isEvaluatable(Context)) {
99 maxVal = lhs->EvaluateKnownConstInt(Context);
100 if (EvaluatesToZero(maxVal, opc))
106 else if (isa<DeclRefExpr>(e) || isa<MemberExpr>(e))
112 if (mulop == nullptr)
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.
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));
125 // A worker class for OutputPossibleOverflows.
126 class CheckOverflowOps :
127 public EvaluatedExprVisitor<CheckOverflowOps> {
129 typedef SmallVectorImpl<MallocOverflowCheck> theVecType;
132 theVecType &toScanFor;
135 bool isIntZeroExpr(const Expr *E) const {
136 if (!E->getType()->isIntegralOrEnumerationType())
139 if (E->EvaluateAsInt(Result, Context))
144 static const Decl *getDecl(const DeclRefExpr *DR) { return DR->getDecl(); }
145 static const Decl *getDecl(const MemberExpr *ME) {
146 return ME->getMemberDecl();
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);
157 toScanFor.erase(std::remove_if(toScanFor.begin(), toScanFor.end(), P),
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);
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;
182 // Erase if the multiplicand was assigned a constant value.
183 const Expr *rhs = AssignEx->getRHS();
184 if (rhs->isEvaluatable(Context))
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))
196 const Expr *numerator = BOp->getLHS()->IgnoreParenImpCasts();
197 if (numerator->isEvaluatable(Context))
198 numeratorKnown = true;
201 if (!assignKnown && !denomKnown)
203 auto denomExtVal = denomVal.getExtValue();
205 // Ignore negative denominator.
209 const Expr *lhs = AssignEx->getLHS();
210 const Expr *E = lhs->IgnoreParenImpCasts();
212 auto pred = [assignKnown, numeratorKnown,
213 denomExtVal](const MallocOverflowCheck &Check) {
214 return assignKnown ||
215 (numeratorKnown && (denomExtVal >= Check.maxVal.getExtValue()));
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);
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)) {
236 if (E->isAssignmentOp())
237 CheckAssignmentExpr(E);
238 EvaluatedExprVisitor<CheckOverflowOps>::VisitBinaryOperator(E);
241 /* We specifically ignore loop conditions, because they're typically
243 void VisitWhileStmt(WhileStmt *S) {
244 return this->Visit(S->getBody());
246 void VisitForStmt(ForStmt *S) {
247 return this->Visit(S->getBody());
249 void VisitDoStmt(DoStmt *S) {
250 return this->Visit(S->getBody());
253 CheckOverflowOps(theVecType &v, ASTContext &ctx)
254 : EvaluatedExprVisitor<CheckOverflowOps>(ctx),
255 toScanFor(v), Context(ctx)
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
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())
274 // Delete any possible overflows which have a comparison.
275 CheckOverflowOps c(PossibleMallocOverflows, BR.getContext());
276 c.Visit(mgr.getAnalysisDeclContext(D)->getBody());
278 // Output warnings for all overflows that are left.
279 for (CheckOverflowOps::theVecType::iterator
280 i = PossibleMallocOverflows.begin(),
281 e = PossibleMallocOverflows.end();
285 D, this, "malloc() size overflow", categories::UnixAPI,
286 "the computation of the size of the memory allocation may overflow",
287 PathDiagnosticLocation::createOperatorLoc(i->mulop,
288 BR.getSourceManager()),
289 i->mulop->getSourceRange());
293 void MallocOverflowSecurityChecker::checkASTCodeBody(const Decl *D,
294 AnalysisManager &mgr,
295 BugReporter &BR) const {
297 CFG *cfg = mgr.getCFG(D);
301 // A list of variables referenced in possibly overflowing malloc operands.
302 SmallVector<MallocOverflowCheck, 2> PossibleMallocOverflows;
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();
308 if (Optional<CFGStmt> CS = bi->getAs<CFGStmt>()) {
309 if (const CallExpr *TheCall = dyn_cast<CallExpr>(CS->getStmt())) {
311 const FunctionDecl *FD = TheCall->getDirectCallee();
316 // Get the name of the callee. If it's a builtin, strip off the prefix.
317 IdentifierInfo *FnInfo = FD->getIdentifier();
321 if (FnInfo->isStr ("malloc") || FnInfo->isStr ("_MALLOC")) {
322 if (TheCall->getNumArgs() == 1)
323 CheckMallocArgument(PossibleMallocOverflows, TheCall->getArg(0),
324 mgr.getASTContext());
331 OutputPossibleOverflows(PossibleMallocOverflows, D, BR, mgr);
335 ento::registerMallocOverflowSecurityChecker(CheckerManager &mgr) {
336 mgr.registerChecker<MallocOverflowSecurityChecker>();