Coverage Report

Created: 2020-10-24 06:27

/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/lib/StaticAnalyzer/Checkers/IteratorRangeChecker.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-- IteratorRangeChecker.cpp ----------------------------------*- 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
// Defines a checker for dereference of the past-the-end iterator and
10
// out-of-range increments and decrements.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
15
#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
16
#include "clang/StaticAnalyzer/Core/Checker.h"
17
#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
18
#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
19
20
21
#include "Iterator.h"
22
23
using namespace clang;
24
using namespace ento;
25
using namespace iterator;
26
27
namespace {
28
29
class IteratorRangeChecker
30
  : public Checker<check::PreCall, check::PreStmt<UnaryOperator>,
31
                   check::PreStmt<BinaryOperator>,
32
                   check::PreStmt<ArraySubscriptExpr>,
33
                   check::PreStmt<MemberExpr>> {
34
35
  std::unique_ptr<BugType> OutOfRangeBugType;
36
37
  void verifyDereference(CheckerContext &C, SVal Val) const;
38
  void verifyIncrement(CheckerContext &C, SVal Iter) const;
39
  void verifyDecrement(CheckerContext &C, SVal Iter) const;
40
  void verifyRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op,
41
                              SVal LHS, SVal RHS) const;
42
  void verifyAdvance(CheckerContext &C, SVal LHS, SVal RHS) const;
43
  void verifyPrev(CheckerContext &C, SVal LHS, SVal RHS) const;
44
  void verifyNext(CheckerContext &C, SVal LHS, SVal RHS) const;
45
  void reportBug(const StringRef &Message, SVal Val, CheckerContext &C,
46
                 ExplodedNode *ErrNode) const;
47
48
public:
49
  IteratorRangeChecker();
50
51
  void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
52
  void checkPreStmt(const UnaryOperator *UO, CheckerContext &C) const;
53
  void checkPreStmt(const BinaryOperator *BO, CheckerContext &C) const;
54
  void checkPreStmt(const ArraySubscriptExpr *ASE, CheckerContext &C) const;
55
  void checkPreStmt(const MemberExpr *ME, CheckerContext &C) const;
56
57
  using AdvanceFn = void (IteratorRangeChecker::*)(CheckerContext &, SVal,
58
                                                   SVal) const;
59
60
  CallDescriptionMap<AdvanceFn> AdvanceFunctions = {
61
      {{{"std", "advance"}, 2}, &IteratorRangeChecker::verifyAdvance},
62
      {{{"std", "prev"}, 2}, &IteratorRangeChecker::verifyPrev},
63
      {{{"std", "next"}, 2}, &IteratorRangeChecker::verifyNext},
64
  };
65
};
66
67
bool isPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos);
68
bool isAheadOfRange(ProgramStateRef State, const IteratorPosition &Pos);
69
bool isBehindPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos);
70
bool isZero(ProgramStateRef State, const NonLoc &Val);
71
72
} //namespace
73
74
2
IteratorRangeChecker::IteratorRangeChecker() {
75
2
  OutOfRangeBugType.reset(
76
2
      new BugType(this, "Iterator out of range", "Misuse of STL APIs"));
77
2
}
78
79
void IteratorRangeChecker::checkPreCall(const CallEvent &Call,
80
1.74k
                                        CheckerContext &C) const {
81
  // Check for out of range access
82
1.74k
  const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
83
1.74k
  if (!Func)
84
0
    return;
85
86
1.74k
  if (Func->isOverloadedOperator()) {
87
374
    if (isIncrementOperator(Func->getOverloadedOperator())) {
88
      // Check for out-of-range incrementions
89
82
      if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
90
82
        verifyIncrement(C, InstCall->getCXXThisVal());
91
0
      } else {
92
0
        if (Call.getNumArgs() >= 1) {
93
0
          verifyIncrement(C, Call.getArgSVal(0));
94
0
        }
95
0
      }
96
292
    } else if (isDecrementOperator(Func->getOverloadedOperator())) {
97
      // Check for out-of-range decrementions
98
84
      if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
99
84
        verifyDecrement(C, InstCall->getCXXThisVal());
100
0
      } else {
101
0
        if (Call.getNumArgs() >= 1) {
102
0
          verifyDecrement(C, Call.getArgSVal(0));
103
0
        }
104
0
      }
105
208
    } else if (isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) {
106
162
      if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
107
        // Check for out-of-range incrementions and decrementions
108
162
        if (Call.getNumArgs() >= 1 &&
109
162
            Call.getArgExpr(0)->getType()->isIntegralOrEnumerationType()) {
110
162
          verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(),
111
162
                                 InstCall->getCXXThisVal(),
112
162
                                 Call.getArgSVal(0));
113
162
        }
114
0
      } else {
115
0
        if (Call.getNumArgs() >= 2 &&
116
0
            Call.getArgExpr(1)->getType()->isIntegralOrEnumerationType()) {
117
0
          verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(),
118
0
                                 Call.getArgSVal(0), Call.getArgSVal(1));
119
0
        }
120
0
      }
121
46
    } else if (isDereferenceOperator(Func->getOverloadedOperator())) {
122
      // Check for dereference of out-of-range iterators
123
46
      if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
124
46
        verifyDereference(C, InstCall->getCXXThisVal());
125
0
      } else {
126
0
        verifyDereference(C, Call.getArgSVal(0));
127
0
      }
128
46
    }
129
1.37k
  } else {
130
1.37k
    const AdvanceFn *Verifier = AdvanceFunctions.lookup(Call);
131
1.37k
    if (Verifier) {
132
228
      if (Call.getNumArgs() > 1) {
133
228
        (this->**Verifier)(C, Call.getArgSVal(0), Call.getArgSVal(1));
134
0
      } else {
135
0
        auto &BVF = C.getSValBuilder().getBasicValueFactory();
136
0
        (this->**Verifier)(
137
0
            C, Call.getArgSVal(0),
138
0
            nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
139
0
      }
140
228
    }
141
1.37k
  }
142
1.74k
}
143
144
void IteratorRangeChecker::checkPreStmt(const UnaryOperator *UO,
145
294
                                        CheckerContext &C) const {
146
294
  if (isa<CXXThisExpr>(UO->getSubExpr()))
147
79
    return;
148
149
215
  ProgramStateRef State = C.getState();
150
215
  UnaryOperatorKind OK = UO->getOpcode();
151
215
  SVal SubVal = State->getSVal(UO->getSubExpr(), C.getLocationContext());
152
153
215
  if (isDereferenceOperator(OK)) {
154
18
    verifyDereference(C, SubVal);
155
197
  } else if (isIncrementOperator(OK)) {
156
43
    verifyIncrement(C, SubVal);
157
154
  } else if (isDecrementOperator(OK)) {
158
44
    verifyDecrement(C, SubVal);
159
44
  }
160
215
}
161
162
void IteratorRangeChecker::checkPreStmt(const BinaryOperator *BO,
163
97
                                        CheckerContext &C) const {
164
97
  ProgramStateRef State = C.getState();
165
97
  BinaryOperatorKind OK = BO->getOpcode();
166
97
  SVal LVal = State->getSVal(BO->getLHS(), C.getLocationContext());
167
168
97
  if (isDereferenceOperator(OK)) {
169
2
    verifyDereference(C, LVal);
170
95
  } else if (isRandomIncrOrDecrOperator(OK)) {
171
95
    SVal RVal = State->getSVal(BO->getRHS(), C.getLocationContext());
172
95
    if (!BO->getRHS()->getType()->isIntegralOrEnumerationType())
173
2
      return;
174
93
    verifyRandomIncrOrDecr(C, BinaryOperator::getOverloadedOperator(OK), LVal,
175
93
                           RVal);
176
93
  }
177
97
}
178
179
void IteratorRangeChecker::checkPreStmt(const ArraySubscriptExpr *ASE,
180
2
                                        CheckerContext &C) const {
181
2
  ProgramStateRef State = C.getState();
182
2
  SVal LVal = State->getSVal(ASE->getLHS(), C.getLocationContext());
183
2
  verifyDereference(C, LVal);
184
2
}
185
186
void IteratorRangeChecker::checkPreStmt(const MemberExpr *ME,
187
634
                                        CheckerContext &C) const {
188
634
  if (!ME->isArrow() || 
ME->isImplicitAccess()317
)
189
630
    return;
190
191
4
  ProgramStateRef State = C.getState();
192
4
  SVal BaseVal = State->getSVal(ME->getBase(), C.getLocationContext());
193
4
  verifyDereference(C, BaseVal);
194
4
}
195
196
void IteratorRangeChecker::verifyDereference(CheckerContext &C,
197
72
                                             SVal Val) const {
198
72
  auto State = C.getState();
199
72
  const auto *Pos = getIteratorPosition(State, Val);
200
72
  if (Pos && 
isPastTheEnd(State, *Pos)54
) {
201
20
    auto *N = C.generateErrorNode(State);
202
20
    if (!N)
203
0
      return;
204
20
    reportBug("Past-the-end iterator dereferenced.", Val, C, N);
205
20
    return;
206
20
  }
207
72
}
208
209
125
void IteratorRangeChecker::verifyIncrement(CheckerContext &C, SVal Iter) const {
210
125
  auto &BVF = C.getSValBuilder().getBasicValueFactory();
211
125
  verifyRandomIncrOrDecr(C, OO_Plus, Iter,
212
125
                     nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
213
125
}
214
215
128
void IteratorRangeChecker::verifyDecrement(CheckerContext &C, SVal Iter) const {
216
128
  auto &BVF = C.getSValBuilder().getBasicValueFactory();
217
128
  verifyRandomIncrOrDecr(C, OO_Minus, Iter,
218
128
                     nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
219
128
}
220
221
void IteratorRangeChecker::verifyRandomIncrOrDecr(CheckerContext &C,
222
                                                  OverloadedOperatorKind Op,
223
736
                                                  SVal LHS, SVal RHS) const {
224
736
  auto State = C.getState();
225
226
736
  auto Value = RHS;
227
736
  if (auto ValAsLoc = RHS.getAs<Loc>()) {
228
2
    Value = State->getRawSVal(*ValAsLoc);
229
2
  }
230
231
736
  if (Value.isUnknown())
232
0
    return;
233
234
  // Incremention or decremention by 0 is never a bug.
235
736
  if (isZero(State, Value.castAs<NonLoc>()))
236
99
    return;
237
238
  // The result may be the past-end iterator of the container, but any other
239
  // out of range position is undefined behaviour
240
637
  auto StateAfter = advancePosition(State, LHS, Op, Value);
241
637
  if (!StateAfter)
242
147
    return;
243
244
490
  const auto *PosAfter = getIteratorPosition(StateAfter, LHS);
245
490
  assert(PosAfter &&
246
490
         "Iterator should have position after successful advancement");
247
490
  if (isAheadOfRange(State, *PosAfter)) {
248
38
    auto *N = C.generateErrorNode(State);
249
38
    if (!N)
250
0
      return;
251
38
    reportBug("Iterator decremented ahead of its valid range.", LHS,
252
38
                        C, N);
253
38
  }
254
490
  if (isBehindPastTheEnd(State, *PosAfter)) {
255
38
    auto *N = C.generateErrorNode(State);
256
38
    if (!N)
257
0
      return;
258
38
    reportBug("Iterator incremented behind the past-the-end "
259
38
                        "iterator.", LHS, C, N);
260
38
  }
261
490
}
262
263
void IteratorRangeChecker::verifyAdvance(CheckerContext &C, SVal LHS,
264
126
                                         SVal RHS) const {
265
126
  verifyRandomIncrOrDecr(C, OO_PlusEqual, LHS, RHS);
266
126
}
267
268
void IteratorRangeChecker::verifyPrev(CheckerContext &C, SVal LHS,
269
52
                                      SVal RHS) const {
270
52
  verifyRandomIncrOrDecr(C, OO_Minus, LHS, RHS);
271
52
}
272
273
void IteratorRangeChecker::verifyNext(CheckerContext &C, SVal LHS,
274
50
                                      SVal RHS) const {
275
50
  verifyRandomIncrOrDecr(C, OO_Plus, LHS, RHS);
276
50
}
277
278
void IteratorRangeChecker::reportBug(const StringRef &Message, SVal Val,
279
                                     CheckerContext &C,
280
96
                                     ExplodedNode *ErrNode) const {
281
96
  auto R = std::make_unique<PathSensitiveBugReport>(*OutOfRangeBugType, Message,
282
96
                                                    ErrNode);
283
284
96
  const auto *Pos = getIteratorPosition(C.getState(), Val);
285
96
  assert(Pos && "Iterator without known position cannot be out-of-range.");
286
287
96
  R->markInteresting(Val);
288
96
  R->markInteresting(Pos->getContainer());
289
96
  C.emitReport(std::move(R));
290
96
}
291
292
namespace {
293
294
bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
295
bool isGreater(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
296
bool isEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
297
298
736
bool isZero(ProgramStateRef State, const NonLoc &Val) {
299
736
  auto &BVF = State->getBasicVals();
300
736
  return compare(State, Val,
301
736
                 nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(0))),
302
736
                 BO_EQ);
303
736
}
304
305
54
bool isPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos) {
306
54
  const auto *Cont = Pos.getContainer();
307
54
  const auto *CData = getContainerData(State, Cont);
308
54
  if (!CData)
309
0
    return false;
310
311
54
  const auto End = CData->getEnd();
312
54
  if (End) {
313
28
    if (isEqual(State, Pos.getOffset(), End)) {
314
20
      return true;
315
20
    }
316
34
  }
317
318
34
  return false;
319
34
}
320
321
490
bool isAheadOfRange(ProgramStateRef State, const IteratorPosition &Pos) {
322
490
  const auto *Cont = Pos.getContainer();
323
490
  const auto *CData = getContainerData(State, Cont);
324
490
  if (!CData)
325
0
    return false;
326
327
490
  const auto Beg = CData->getBegin();
328
490
  if (Beg) {
329
284
    if (isLess(State, Pos.getOffset(), Beg)) {
330
38
      return true;
331
38
    }
332
452
  }
333
334
452
  return false;
335
452
}
336
337
490
bool isBehindPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos) {
338
490
  const auto *Cont = Pos.getContainer();
339
490
  const auto *CData = getContainerData(State, Cont);
340
490
  if (!CData)
341
0
    return false;
342
343
490
  const auto End = CData->getEnd();
344
490
  if (End) {
345
206
    if (isGreater(State, Pos.getOffset(), End)) {
346
38
      return true;
347
38
    }
348
452
  }
349
350
452
  return false;
351
452
}
352
353
284
bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
354
284
  return compare(State, Sym1, Sym2, BO_LT);
355
284
}
356
357
206
bool isGreater(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
358
206
  return compare(State, Sym1, Sym2, BO_GT);
359
206
}
360
361
28
bool isEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
362
28
  return compare(State, Sym1, Sym2, BO_EQ);
363
28
}
364
365
} // namespace
366
367
2
void ento::registerIteratorRangeChecker(CheckerManager &mgr) {
368
2
  mgr.registerChecker<IteratorRangeChecker>();
369
2
}
370
371
6
bool ento::shouldRegisterIteratorRangeChecker(const CheckerManager &mgr) {
372
6
  return true;
373
6
}