xref: /freebsd/contrib/llvm-project/clang/lib/StaticAnalyzer/Checkers/MallocOverflowSecurityChecker.cpp (revision 7ef62cebc2f965b0f640263e179276928885e33d)
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 (CheckOverflowOps::theVecType::iterator
284        i = PossibleMallocOverflows.begin(),
285        e = PossibleMallocOverflows.end();
286        i != e;
287        ++i) {
288     BR.EmitBasicReport(
289         D, this, "malloc() size overflow", categories::UnixAPI,
290         "the computation of the size of the memory allocation may overflow",
291         PathDiagnosticLocation::createOperatorLoc(i->mulop,
292                                                   BR.getSourceManager()),
293         i->mulop->getSourceRange());
294   }
295 }
296 
297 void MallocOverflowSecurityChecker::checkASTCodeBody(const Decl *D,
298                                              AnalysisManager &mgr,
299                                              BugReporter &BR) const {
300 
301   CFG *cfg = mgr.getCFG(D);
302   if (!cfg)
303     return;
304 
305   // A list of variables referenced in possibly overflowing malloc operands.
306   SmallVector<MallocOverflowCheck, 2> PossibleMallocOverflows;
307 
308   for (CFG::iterator it = cfg->begin(), ei = cfg->end(); it != ei; ++it) {
309     CFGBlock *block = *it;
310     for (CFGBlock::iterator bi = block->begin(), be = block->end();
311          bi != be; ++bi) {
312         if (std::optional<CFGStmt> CS = bi->getAs<CFGStmt>()) {
313           if (const CallExpr *TheCall = dyn_cast<CallExpr>(CS->getStmt())) {
314             // Get the callee.
315             const FunctionDecl *FD = TheCall->getDirectCallee();
316 
317             if (!FD)
318               continue;
319 
320             // Get the name of the callee. If it's a builtin, strip off the
321             // prefix.
322             IdentifierInfo *FnInfo = FD->getIdentifier();
323             if (!FnInfo)
324               continue;
325 
326             if (FnInfo->isStr("malloc") || FnInfo->isStr("_MALLOC")) {
327               if (TheCall->getNumArgs() == 1)
328                 CheckMallocArgument(PossibleMallocOverflows, TheCall,
329                                     mgr.getASTContext());
330             }
331           }
332         }
333     }
334   }
335 
336   OutputPossibleOverflows(PossibleMallocOverflows, D, BR, mgr);
337 }
338 
339 void ento::registerMallocOverflowSecurityChecker(CheckerManager &mgr) {
340   mgr.registerChecker<MallocOverflowSecurityChecker>();
341 }
342 
343 bool ento::shouldRegisterMallocOverflowSecurityChecker(const CheckerManager &mgr) {
344   return true;
345 }
346