Coverage Report

Created: 2022-01-25 06:29

/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/StaticAnalyzer/Checkers/MallocOverflowSecurityChecker.cpp
Line
Count
Source (jump to first uncovered line)
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 <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
22
      : 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
28
static inline bool EvaluatesToZero(APSInt &Val, BinaryOperatorKind op) {
63
28
  return (op == BO_Mul) && 
(Val == 0)27
;
64
28
}
65
66
void MallocOverflowSecurityChecker::CheckMallocArgument(
67
    SmallVectorImpl<MallocOverflowCheck> &PossibleMallocOverflows,
68
25
    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
25
  const Expr *e = TheCall->getArg(0);
76
25
  const BinaryOperator * mulop = nullptr;
77
25
  APSInt maxVal;
78
79
51
  for (;;) {
80
51
    maxVal = 0;
81
51
    e = e->IgnoreParenImpCasts();
82
51
    if (const BinaryOperator *binop = dyn_cast<BinaryOperator>(e)) {
83
28
      BinaryOperatorKind opc = binop->getOpcode();
84
      // TODO: ignore multiplications by 1, reject if multiplied by 0.
85
28
      if (mulop == nullptr && 
opc == BO_Mul25
)
86
25
        mulop = binop;
87
28
      if (opc != BO_Mul && 
opc != BO_Add1
&&
opc != BO_Sub0
&&
opc != BO_Shl0
)
88
0
        return;
89
90
28
      const Expr *lhs = binop->getLHS();
91
28
      const Expr *rhs = binop->getRHS();
92
28
      if (rhs->isEvaluatable(Context)) {
93
21
        e = lhs;
94
21
        maxVal = rhs->EvaluateKnownConstInt(Context);
95
21
        if (EvaluatesToZero(maxVal, opc))
96
2
          return;
97
21
      } else 
if (7
(7
opc == BO_Add7
||
opc == BO_Mul7
) &&
98
7
                 lhs->isEvaluatable(Context)) {
99
7
        maxVal = lhs->EvaluateKnownConstInt(Context);
100
7
        if (EvaluatesToZero(maxVal, opc))
101
0
          return;
102
7
        e = rhs;
103
7
      } else
104
0
        return;
105
28
    } else 
if (23
isa<DeclRefExpr, MemberExpr>(e)23
)
106
22
      break;
107
1
    else
108
1
      return;
109
51
  }
110
111
22
  if (mulop == nullptr)
112
0
    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
22
  PossibleMallocOverflows.push_back(
119
22
      MallocOverflowCheck(TheCall, mulop, e, maxVal));
120
22
}
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
22
    bool isIntZeroExpr(const Expr *E) const {
134
22
      if (!E->getType()->isIntegralOrEnumerationType())
135
0
        return false;
136
22
      Expr::EvalResult Result;
137
22
      if (E->EvaluateAsInt(Result, Context))
138
11
        return Result.Val.getInt() == 0;
139
11
      return false;
140
22
    }
141
142
20
    static const Decl *getDecl(const DeclRefExpr *DR) { return DR->getDecl(); }
143
10
    static const Decl *getDecl(const MemberExpr *ME) {
144
10
      return ME->getMemberDecl();
145
10
    }
146
147
    template <typename T1>
148
    void Erase(const T1 *DR,
149
16
               llvm::function_ref<bool(const MallocOverflowCheck &)> Pred) {
150
19
      auto P = [DR, Pred](const MallocOverflowCheck &Check) {
151
19
        if (const auto *CheckDR = dyn_cast<T1>(Check.variable))
152
15
          return getDecl(CheckDR) == getDecl(DR) && 
Pred(Check)13
;
153
4
        return false;
154
19
      };
MallocOverflowSecurityChecker.cpp:void (anonymous namespace)::CheckOverflowOps::Erase<clang::DeclRefExpr>(clang::DeclRefExpr const*, llvm::function_ref<bool ((anonymous namespace)::MallocOverflowCheck const&)>)::'lambda'((anonymous namespace)::MallocOverflowCheck const&)::operator()((anonymous namespace)::MallocOverflowCheck const&) const
Line
Count
Source
150
12
      auto P = [DR, Pred](const MallocOverflowCheck &Check) {
151
12
        if (const auto *CheckDR = dyn_cast<T1>(Check.variable))
152
10
          return getDecl(CheckDR) == getDecl(DR) && 
Pred(Check)8
;
153
2
        return false;
154
12
      };
MallocOverflowSecurityChecker.cpp:void (anonymous namespace)::CheckOverflowOps::Erase<clang::MemberExpr>(clang::MemberExpr const*, llvm::function_ref<bool ((anonymous namespace)::MallocOverflowCheck const&)>)::'lambda'((anonymous namespace)::MallocOverflowCheck const&)::operator()((anonymous namespace)::MallocOverflowCheck const&) const
Line
Count
Source
150
7
      auto P = [DR, Pred](const MallocOverflowCheck &Check) {
151
7
        if (const auto *CheckDR = dyn_cast<T1>(Check.variable))
152
5
          return getDecl(CheckDR) == getDecl(DR) && Pred(Check);
153
2
        return false;
154
7
      };
155
16
      llvm::erase_if(toScanFor, P);
156
16
    }
MallocOverflowSecurityChecker.cpp:void (anonymous namespace)::CheckOverflowOps::Erase<clang::DeclRefExpr>(clang::DeclRefExpr const*, llvm::function_ref<bool ((anonymous namespace)::MallocOverflowCheck const&)>)
Line
Count
Source
149
11
               llvm::function_ref<bool(const MallocOverflowCheck &)> Pred) {
150
11
      auto P = [DR, Pred](const MallocOverflowCheck &Check) {
151
11
        if (const auto *CheckDR = dyn_cast<T1>(Check.variable))
152
11
          return getDecl(CheckDR) == getDecl(DR) && Pred(Check);
153
11
        return false;
154
11
      };
155
11
      llvm::erase_if(toScanFor, P);
156
11
    }
MallocOverflowSecurityChecker.cpp:void (anonymous namespace)::CheckOverflowOps::Erase<clang::MemberExpr>(clang::MemberExpr const*, llvm::function_ref<bool ((anonymous namespace)::MallocOverflowCheck const&)>)
Line
Count
Source
149
5
               llvm::function_ref<bool(const MallocOverflowCheck &)> Pred) {
150
5
      auto P = [DR, Pred](const MallocOverflowCheck &Check) {
151
5
        if (const auto *CheckDR = dyn_cast<T1>(Check.variable))
152
5
          return getDecl(CheckDR) == getDecl(DR) && Pred(Check);
153
5
        return false;
154
5
      };
155
5
      llvm::erase_if(toScanFor, P);
156
5
    }
157
158
20
    void CheckExpr(const Expr *E_p) {
159
20
      const Expr *E = E_p->IgnoreParenImpCasts();
160
20
      const auto PrecedesMalloc = [E, this](const MallocOverflowCheck &c) {
161
7
        return Context.getSourceManager().isBeforeInTranslationUnit(
162
7
            E->getExprLoc(), c.call->getExprLoc());
163
7
      };
164
20
      if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E))
165
9
        Erase<DeclRefExpr>(DR, PrecedesMalloc);
166
11
      else if (const auto *ME = dyn_cast<MemberExpr>(E)) {
167
1
        Erase<MemberExpr>(ME, PrecedesMalloc);
168
1
      }
169
20
    }
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
18
    void CheckAssignmentExpr(BinaryOperator *AssignEx) {
177
18
      bool assignKnown = false;
178
18
      bool numeratorKnown = false, denomKnown = false;
179
18
      APSInt denomVal;
180
18
      denomVal = 0;
181
182
      // Erase if the multiplicand was assigned a constant value.
183
18
      const Expr *rhs = AssignEx->getRHS();
184
18
      if (rhs->isEvaluatable(Context))
185
6
        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
18
      const Expr *rhse = rhs->IgnoreParenImpCasts();
191
18
      if (const BinaryOperator *BOp = dyn_cast<BinaryOperator>(rhse)) {
192
4
        if (BOp->getOpcode() == BO_Div) {
193
4
          const Expr *denom = BOp->getRHS()->IgnoreParenImpCasts();
194
4
          Expr::EvalResult Result;
195
4
          if (denom->EvaluateAsInt(Result, Context)) {
196
4
            denomVal = Result.Val.getInt();
197
4
            denomKnown = true;
198
4
          }
199
4
          const Expr *numerator = BOp->getLHS()->IgnoreParenImpCasts();
200
4
          if (numerator->isEvaluatable(Context))
201
2
            numeratorKnown = true;
202
4
        }
203
4
      }
204
18
      if (!assignKnown && 
!denomKnown12
)
205
10
        return;
206
8
      auto denomExtVal = denomVal.getExtValue();
207
208
      // Ignore negative denominator.
209
8
      if (denomExtVal < 0)
210
0
        return;
211
212
8
      const Expr *lhs = AssignEx->getLHS();
213
8
      const Expr *E = lhs->IgnoreParenImpCasts();
214
215
8
      auto pred = [assignKnown, numeratorKnown,
216
8
                   denomExtVal](const MallocOverflowCheck &Check) {
217
6
        return assignKnown ||
218
6
               
(2
numeratorKnown2
&&
(denomExtVal >= Check.maxVal.getExtValue())0
);
219
6
      };
220
221
8
      if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E))
222
2
        Erase<DeclRefExpr>(DR, pred);
223
6
      else if (const auto *ME = dyn_cast<MemberExpr>(E))
224
4
        Erase<MemberExpr>(ME, pred);
225
8
    }
226
227
  public:
228
64
    void VisitBinaryOperator(BinaryOperator *E) {
229
64
      if (E->isComparisonOp()) {
230
11
        const Expr * lhs = E->getLHS();
231
11
        const Expr * rhs = E->getRHS();
232
        // Ignore comparisons against zero, since they generally don't
233
        // protect against an overflow.
234
11
        if (!isIntZeroExpr(lhs) && !isIntZeroExpr(rhs)) {
235
10
          CheckExpr(lhs);
236
10
          CheckExpr(rhs);
237
10
        }
238
11
      }
239
64
      if (E->isAssignmentOp())
240
18
        CheckAssignmentExpr(E);
241
64
      EvaluatedExprVisitor<CheckOverflowOps>::VisitBinaryOperator(E);
242
64
    }
243
244
    /* We specifically ignore loop conditions, because they're typically
245
     not error checks.  */
246
1
    void VisitWhileStmt(WhileStmt *S) {
247
1
      return this->Visit(S->getBody());
248
1
    }
249
2
    void VisitForStmt(ForStmt *S) {
250
2
      return this->Visit(S->getBody());
251
2
    }
252
1
    void VisitDoStmt(DoStmt *S) {
253
1
      return this->Visit(S->getBody());
254
1
    }
255
256
    CheckOverflowOps(theVecType &v, ASTContext &ctx)
257
    : EvaluatedExprVisitor<CheckOverflowOps>(ctx),
258
      toScanFor(v), Context(ctx)
259
20
    { }
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
24
  const Decl *D, BugReporter &BR, AnalysisManager &mgr) const {
273
  // By far the most common case: nothing to check.
274
24
  if (PossibleMallocOverflows.empty())
275
4
    return;
276
277
  // Delete any possible overflows which have a comparison.
278
20
  CheckOverflowOps c(PossibleMallocOverflows, BR.getContext());
279
20
  c.Visit(mgr.getAnalysisDeclContext(D)->getBody());
280
281
  // Output warnings for all overflows that are left.
282
20
  for (CheckOverflowOps::theVecType::iterator
283
20
       i = PossibleMallocOverflows.begin(),
284
20
       e = PossibleMallocOverflows.end();
285
33
       i != e;
286
20
       
++i13
) {
287
13
    BR.EmitBasicReport(
288
13
        D, this, "malloc() size overflow", categories::UnixAPI,
289
13
        "the computation of the size of the memory allocation may overflow",
290
13
        PathDiagnosticLocation::createOperatorLoc(i->mulop,
291
13
                                                  BR.getSourceManager()),
292
13
        i->mulop->getSourceRange());
293
13
  }
294
20
}
295
296
void MallocOverflowSecurityChecker::checkASTCodeBody(const Decl *D,
297
                                             AnalysisManager &mgr,
298
24
                                             BugReporter &BR) const {
299
300
24
  CFG *cfg = mgr.getCFG(D);
301
24
  if (!cfg)
302
0
    return;
303
304
  // A list of variables referenced in possibly overflowing malloc operands.
305
24
  SmallVector<MallocOverflowCheck, 2> PossibleMallocOverflows;
306
307
135
  for (CFG::iterator it = cfg->begin(), ei = cfg->end(); it != ei; 
++it111
) {
308
111
    CFGBlock *block = *it;
309
111
    for (CFGBlock::iterator bi = block->begin(), be = block->end();
310
677
         bi != be; 
++bi566
) {
311
566
      if (Optional<CFGStmt> CS = bi->getAs<CFGStmt>()) {
312
566
        if (const CallExpr *TheCall = dyn_cast<CallExpr>(CS->getStmt())) {
313
          // Get the callee.
314
28
          const FunctionDecl *FD = TheCall->getDirectCallee();
315
316
28
          if (!FD)
317
0
            continue;
318
319
          // Get the name of the callee. If it's a builtin, strip off the prefix.
320
28
          IdentifierInfo *FnInfo = FD->getIdentifier();
321
28
          if (!FnInfo)
322
1
            continue;
323
324
27
          if (FnInfo->isStr ("malloc") || 
FnInfo->isStr ("_MALLOC")2
) {
325
25
            if (TheCall->getNumArgs() == 1)
326
25
              CheckMallocArgument(PossibleMallocOverflows, TheCall,
327
25
                                  mgr.getASTContext());
328
25
          }
329
27
        }
330
566
      }
331
566
    }
332
111
  }
333
334
24
  OutputPossibleOverflows(PossibleMallocOverflows, D, BR, mgr);
335
24
}
336
337
4
void ento::registerMallocOverflowSecurityChecker(CheckerManager &mgr) {
338
4
  mgr.registerChecker<MallocOverflowSecurityChecker>();
339
4
}
340
341
8
bool ento::shouldRegisterMallocOverflowSecurityChecker(const CheckerManager &mgr) {
342
8
  return true;
343
8
}