Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/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 BinaryOperator *mulop;
36
  const Expr *variable;
37
  APSInt maxVal;
38
39
  MallocOverflowCheck(const BinaryOperator *m, const Expr *v, APSInt val)
40
19
      : 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
25
static inline bool EvaluatesToZero(APSInt &Val, BinaryOperatorKind op) {
61
25
  return (op == BO_Mul) && 
(Val == 0)24
;
62
25
}
63
64
void MallocOverflowSecurityChecker::CheckMallocArgument(
65
  SmallVectorImpl<MallocOverflowCheck> &PossibleMallocOverflows,
66
  const Expr *TheArgument,
67
22
  ASTContext &Context) const {
68
22
69
22
  /* Look for a linear combination with a single variable, and at least
70
22
   one multiplication.
71
22
   Reject anything that applies to the variable: an explicit cast,
72
22
   conditional expression, an operation that could reduce the range
73
22
   of the result, or anything too complicated :-).  */
74
22
  const Expr *e = TheArgument;
75
22
  const BinaryOperator * mulop = nullptr;
76
22
  APSInt maxVal;
77
22
78
45
  for (;;) {
79
45
    maxVal = 0;
80
45
    e = e->IgnoreParenImpCasts();
81
45
    if (const BinaryOperator *binop = dyn_cast<BinaryOperator>(e)) {
82
25
      BinaryOperatorKind opc = binop->getOpcode();
83
25
      // TODO: ignore multiplications by 1, reject if multiplied by 0.
84
25
      if (mulop == nullptr && 
opc == BO_Mul22
)
85
22
        mulop = binop;
86
25
      if (opc != BO_Mul && 
opc != BO_Add1
&&
opc != BO_Sub0
&&
opc != BO_Shl0
)
87
0
        return;
88
25
89
25
      const Expr *lhs = binop->getLHS();
90
25
      const Expr *rhs = binop->getRHS();
91
25
      if (rhs->isEvaluatable(Context)) {
92
18
        e = lhs;
93
18
        maxVal = rhs->EvaluateKnownConstInt(Context);
94
18
        if (EvaluatesToZero(maxVal, opc))
95
2
          return;
96
7
      } else if ((opc == BO_Add || opc == BO_Mul) &&
97
7
                 lhs->isEvaluatable(Context)) {
98
7
        maxVal = lhs->EvaluateKnownConstInt(Context);
99
7
        if (EvaluatesToZero(maxVal, opc))
100
0
          return;
101
7
        e = rhs;
102
7
      } else
103
0
        return;
104
20
    }
105
20
    else if (isa<DeclRefExpr>(e) || 
isa<MemberExpr>(e)8
)
106
19
      break;
107
1
    else
108
1
      return;
109
45
  }
110
22
111
22
  
if (19
mulop == nullptr19
)
112
0
    return;
113
19
114
19
  //  We've found the right structure of malloc argument, now save
115
19
  // the data so when the body of the function is completely available
116
19
  // we can check for comparisons.
117
19
118
19
  // TODO: Could push this into the innermost scope where 'e' is
119
19
  // defined, rather than the whole function.
120
19
  PossibleMallocOverflows.push_back(MallocOverflowCheck(mulop, e, maxVal));
121
19
}
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
10
    bool isIntZeroExpr(const Expr *E) const {
135
10
      if (!E->getType()->isIntegralOrEnumerationType())
136
0
        return false;
137
10
      Expr::EvalResult Result;
138
10
      if (E->EvaluateAsInt(Result, Context))
139
5
        return Result.Val.getInt() == 0;
140
5
      return false;
141
5
    }
142
143
10
    static const Decl *getDecl(const DeclRefExpr *DR) { return DR->getDecl(); }
144
10
    static const Decl *getDecl(const MemberExpr *ME) {
145
10
      return ME->getMemberDecl();
146
10
    }
147
148
    template <typename T1>
149
    void Erase(const T1 *DR,
150
10
               llvm::function_ref<bool(const MallocOverflowCheck &)> Pred) {
151
14
      auto P = [DR, Pred](const MallocOverflowCheck &Check) {
152
14
        if (const auto *CheckDR = dyn_cast<T1>(Check.variable))
153
10
          return getDecl(CheckDR) == getDecl(DR) && Pred(Check);
154
4
        return false;
155
4
      };
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
151
7
      auto P = [DR, Pred](const MallocOverflowCheck &Check) {
152
7
        if (const auto *CheckDR = dyn_cast<T1>(Check.variable))
153
5
          return getDecl(CheckDR) == getDecl(DR) && Pred(Check);
154
2
        return false;
155
2
      };
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
151
7
      auto P = [DR, Pred](const MallocOverflowCheck &Check) {
152
7
        if (const auto *CheckDR = dyn_cast<T1>(Check.variable))
153
5
          return getDecl(CheckDR) == getDecl(DR) && Pred(Check);
154
2
        return false;
155
2
      };
156
10
      toScanFor.erase(std::remove_if(toScanFor.begin(), toScanFor.end(), P),
157
10
                      toScanFor.end());
158
10
    }
MallocOverflowSecurityChecker.cpp:void (anonymous namespace)::CheckOverflowOps::Erase<clang::DeclRefExpr>(clang::DeclRefExpr const*, llvm::function_ref<bool ((anonymous namespace)::MallocOverflowCheck const&)>)
Line
Count
Source
150
5
               llvm::function_ref<bool(const MallocOverflowCheck &)> Pred) {
151
5
      auto P = [DR, Pred](const MallocOverflowCheck &Check) {
152
5
        if (const auto *CheckDR = dyn_cast<T1>(Check.variable))
153
5
          return getDecl(CheckDR) == getDecl(DR) && Pred(Check);
154
5
        return false;
155
5
      };
156
5
      toScanFor.erase(std::remove_if(toScanFor.begin(), toScanFor.end(), P),
157
5
                      toScanFor.end());
158
5
    }
MallocOverflowSecurityChecker.cpp:void (anonymous namespace)::CheckOverflowOps::Erase<clang::MemberExpr>(clang::MemberExpr const*, llvm::function_ref<bool ((anonymous namespace)::MallocOverflowCheck const&)>)
Line
Count
Source
150
5
               llvm::function_ref<bool(const MallocOverflowCheck &)> Pred) {
151
5
      auto P = [DR, Pred](const MallocOverflowCheck &Check) {
152
5
        if (const auto *CheckDR = dyn_cast<T1>(Check.variable))
153
5
          return getDecl(CheckDR) == getDecl(DR) && Pred(Check);
154
5
        return false;
155
5
      };
156
5
      toScanFor.erase(std::remove_if(toScanFor.begin(), toScanFor.end(), P),
157
5
                      toScanFor.end());
158
5
    }
159
160
8
    void CheckExpr(const Expr *E_p) {
161
8
      auto PredTrue = [](const MallocOverflowCheck &) 
{ return true; }4
;
162
8
      const Expr *E = E_p->IgnoreParenImpCasts();
163
8
      if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E))
164
3
        Erase<DeclRefExpr>(DR, PredTrue);
165
5
      else if (const auto *ME = dyn_cast<MemberExpr>(E)) {
166
1
        Erase<MemberExpr>(ME, PredTrue);
167
1
      }
168
8
    }
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
15
    void CheckAssignmentExpr(BinaryOperator *AssignEx) {
176
15
      bool assignKnown = false;
177
15
      bool numeratorKnown = false, denomKnown = false;
178
15
      APSInt denomVal;
179
15
      denomVal = 0;
180
15
181
15
      // Erase if the multiplicand was assigned a constant value.
182
15
      const Expr *rhs = AssignEx->getRHS();
183
15
      if (rhs->isEvaluatable(Context))
184
6
        assignKnown = true;
185
15
186
15
      // Discard the report if the multiplicand was assigned a value,
187
15
      // that can never overflow after multiplication. e.g., the assignment
188
15
      // is a division operator and the denominator is > other multiplicand.
189
15
      const Expr *rhse = rhs->IgnoreParenImpCasts();
190
15
      if (const BinaryOperator *BOp = dyn_cast<BinaryOperator>(rhse)) {
191
4
        if (BOp->getOpcode() == BO_Div) {
192
4
          const Expr *denom = BOp->getRHS()->IgnoreParenImpCasts();
193
4
          Expr::EvalResult Result;
194
4
          if (denom->EvaluateAsInt(Result, Context)) {
195
4
            denomVal = Result.Val.getInt();
196
4
            denomKnown = true;
197
4
          }
198
4
          const Expr *numerator = BOp->getLHS()->IgnoreParenImpCasts();
199
4
          if (numerator->isEvaluatable(Context))
200
2
            numeratorKnown = true;
201
4
        }
202
4
      }
203
15
      if (!assignKnown && 
!denomKnown9
)
204
7
        return;
205
8
      auto denomExtVal = denomVal.getExtValue();
206
8
207
8
      // Ignore negative denominator.
208
8
      if (denomExtVal < 0)
209
0
        return;
210
8
211
8
      const Expr *lhs = AssignEx->getLHS();
212
8
      const Expr *E = lhs->IgnoreParenImpCasts();
213
8
214
8
      auto pred = [assignKnown, numeratorKnown,
215
8
                   denomExtVal](const MallocOverflowCheck &Check) {
216
6
        return assignKnown ||
217
6
               
(2
numeratorKnown2
&&
(denomExtVal >= Check.maxVal.getExtValue())0
);
218
6
      };
219
8
220
8
      if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E))
221
2
        Erase<DeclRefExpr>(DR, pred);
222
6
      else if (const auto *ME = dyn_cast<MemberExpr>(E))
223
4
        Erase<MemberExpr>(ME, pred);
224
8
    }
225
226
  public:
227
52
    void VisitBinaryOperator(BinaryOperator *E) {
228
52
      if (E->isComparisonOp()) {
229
5
        const Expr * lhs = E->getLHS();
230
5
        const Expr * rhs = E->getRHS();
231
5
        // Ignore comparisons against zero, since they generally don't
232
5
        // protect against an overflow.
233
5
        if (!isIntZeroExpr(lhs) && !isIntZeroExpr(rhs)) {
234
4
          CheckExpr(lhs);
235
4
          CheckExpr(rhs);
236
4
        }
237
5
      }
238
52
      if (E->isAssignmentOp())
239
15
        CheckAssignmentExpr(E);
240
52
      EvaluatedExprVisitor<CheckOverflowOps>::VisitBinaryOperator(E);
241
52
    }
242
243
    /* We specifically ignore loop conditions, because they're typically
244
     not error checks.  */
245
1
    void VisitWhileStmt(WhileStmt *S) {
246
1
      return this->Visit(S->getBody());
247
1
    }
248
2
    void VisitForStmt(ForStmt *S) {
249
2
      return this->Visit(S->getBody());
250
2
    }
251
1
    void VisitDoStmt(DoStmt *S) {
252
1
      return this->Visit(S->getBody());
253
1
    }
254
255
    CheckOverflowOps(theVecType &v, ASTContext &ctx)
256
    : EvaluatedExprVisitor<CheckOverflowOps>(ctx),
257
      toScanFor(v), Context(ctx)
258
17
    { }
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
25
  const Decl *D, BugReporter &BR, AnalysisManager &mgr) const {
272
25
  // By far the most common case: nothing to check.
273
25
  if (PossibleMallocOverflows.empty())
274
8
    return;
275
17
276
17
  // Delete any possible overflows which have a comparison.
277
17
  CheckOverflowOps c(PossibleMallocOverflows, BR.getContext());
278
17
  c.Visit(mgr.getAnalysisDeclContext(D)->getBody());
279
17
280
17
  // Output warnings for all overflows that are left.
281
17
  for (CheckOverflowOps::theVecType::iterator
282
17
       i = PossibleMallocOverflows.begin(),
283
17
       e = PossibleMallocOverflows.end();
284
28
       i != e;
285
17
       
++i11
) {
286
11
    BR.EmitBasicReport(
287
11
        D, this, "malloc() size overflow", categories::UnixAPI,
288
11
        "the computation of the size of the memory allocation may overflow",
289
11
        PathDiagnosticLocation::createOperatorLoc(i->mulop,
290
11
                                                  BR.getSourceManager()),
291
11
        i->mulop->getSourceRange());
292
11
  }
293
17
}
294
295
void MallocOverflowSecurityChecker::checkASTCodeBody(const Decl *D,
296
                                             AnalysisManager &mgr,
297
25
                                             BugReporter &BR) const {
298
25
299
25
  CFG *cfg = mgr.getCFG(D);
300
25
  if (!cfg)
301
0
    return;
302
25
303
25
  // A list of variables referenced in possibly overflowing malloc operands.
304
25
  SmallVector<MallocOverflowCheck, 2> PossibleMallocOverflows;
305
25
306
153
  for (CFG::iterator it = cfg->begin(), ei = cfg->end(); it != ei; 
++it128
) {
307
128
    CFGBlock *block = *it;
308
128
    for (CFGBlock::iterator bi = block->begin(), be = block->end();
309
726
         bi != be; 
++bi598
) {
310
598
      if (Optional<CFGStmt> CS = bi->getAs<CFGStmt>()) {
311
597
        if (const CallExpr *TheCall = dyn_cast<CallExpr>(CS->getStmt())) {
312
26
          // Get the callee.
313
26
          const FunctionDecl *FD = TheCall->getDirectCallee();
314
26
315
26
          if (!FD)
316
0
            continue;
317
26
318
26
          // Get the name of the callee. If it's a builtin, strip off the prefix.
319
26
          IdentifierInfo *FnInfo = FD->getIdentifier();
320
26
          if (!FnInfo)
321
1
            continue;
322
25
323
25
          if (FnInfo->isStr ("malloc") || 
FnInfo->isStr ("_MALLOC")3
) {
324
22
            if (TheCall->getNumArgs() == 1)
325
22
              CheckMallocArgument(PossibleMallocOverflows, TheCall->getArg(0),
326
22
                                  mgr.getASTContext());
327
22
          }
328
25
        }
329
597
      }
330
598
    }
331
128
  }
332
25
333
25
  OutputPossibleOverflows(PossibleMallocOverflows, D, BR, mgr);
334
25
}
335
336
5
void ento::registerMallocOverflowSecurityChecker(CheckerManager &mgr) {
337
5
  mgr.registerChecker<MallocOverflowSecurityChecker>();
338
5
}
339
340
5
bool ento::shouldRegisterMallocOverflowSecurityChecker(const LangOptions &LO) {
341
5
  return true;
342
5
}