IteratorRangeChecker.cpp revision 360784 
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
23using namespace clang;
24using namespace ento;
25using namespace iterator;
26
27namespace {
28
29class IteratorRangeChecker
30  : public Checker<check::PreCall> {
31
32  std::unique_ptr<BugType> OutOfRangeBugType;
33
34  void verifyDereference(CheckerContext &C, const SVal &Val) const;
35  void verifyIncrement(CheckerContext &C, const SVal &Iter) const;
36  void verifyDecrement(CheckerContext &C, const SVal &Iter) const;
37  void verifyRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op,
38                              const SVal &LHS, const SVal &RHS) const;
39  void reportBug(const StringRef &Message, const SVal &Val,
40                 CheckerContext &C, ExplodedNode *ErrNode) const;
41public:
42  IteratorRangeChecker();
43
44  void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
45
46};
47
48bool isPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos);
49bool isAheadOfRange(ProgramStateRef State, const IteratorPosition &Pos);
50bool isBehindPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos);
51bool isZero(ProgramStateRef State, const NonLoc &Val);
52
53} //namespace
54
55IteratorRangeChecker::IteratorRangeChecker() {
56  OutOfRangeBugType.reset(
57      new BugType(this, "Iterator out of range", "Misuse of STL APIs"));
58}
59
60void IteratorRangeChecker::checkPreCall(const CallEvent &Call,
61                                        CheckerContext &C) const {
62  // Check for out of range access
63  const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
64  if (!Func)
65    return;
66
67  if (Func->isOverloadedOperator()) {
68    if (isIncrementOperator(Func->getOverloadedOperator())) {
69      // Check for out-of-range incrementions
70      if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
71        verifyIncrement(C, InstCall->getCXXThisVal());
72      } else {
73        if (Call.getNumArgs() >= 1) {
74          verifyIncrement(C, Call.getArgSVal(0));
75        }
76      }
77    } else if (isDecrementOperator(Func->getOverloadedOperator())) {
78      // Check for out-of-range decrementions
79      if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
80        verifyDecrement(C, InstCall->getCXXThisVal());
81      } else {
82        if (Call.getNumArgs() >= 1) {
83          verifyDecrement(C, Call.getArgSVal(0));
84        }
85      }
86    } else if (isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) {
87      if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
88        // Check for out-of-range incrementions and decrementions
89        if (Call.getNumArgs() >= 1 &&
90            Call.getArgExpr(0)->getType()->isIntegralOrEnumerationType()) {
91          verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(),
92                                 InstCall->getCXXThisVal(),
93                                 Call.getArgSVal(0));
94        }
95      } else {
96        if (Call.getNumArgs() >= 2 &&
97            Call.getArgExpr(1)->getType()->isIntegralOrEnumerationType()) {
98          verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(),
99                                 Call.getArgSVal(0), Call.getArgSVal(1));
100        }
101      }
102    } else if (isDereferenceOperator(Func->getOverloadedOperator())) {
103      // Check for dereference of out-of-range iterators
104      if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
105        verifyDereference(C, InstCall->getCXXThisVal());
106      } else {
107        verifyDereference(C, Call.getArgSVal(0));
108      }
109    }
110  }
111}
112
113void IteratorRangeChecker::verifyDereference(CheckerContext &C,
114                                             const SVal &Val) const {
115  auto State = C.getState();
116  const auto *Pos = getIteratorPosition(State, Val);
117  if (Pos && isPastTheEnd(State, *Pos)) {
118    auto *N = C.generateErrorNode(State);
119    if (!N)
120      return;
121    reportBug("Past-the-end iterator dereferenced.", Val, C, N);
122    return;
123  }
124}
125
126void IteratorRangeChecker::verifyIncrement(CheckerContext &C,
127                                          const SVal &Iter) const {
128  auto &BVF = C.getSValBuilder().getBasicValueFactory();
129  verifyRandomIncrOrDecr(C, OO_Plus, Iter,
130                     nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
131}
132
133void IteratorRangeChecker::verifyDecrement(CheckerContext &C,
134                                          const SVal &Iter) const {
135  auto &BVF = C.getSValBuilder().getBasicValueFactory();
136  verifyRandomIncrOrDecr(C, OO_Minus, Iter,
137                     nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
138}
139
140void IteratorRangeChecker::verifyRandomIncrOrDecr(CheckerContext &C,
141                                                 OverloadedOperatorKind Op,
142                                                 const SVal &LHS,
143                                                 const SVal &RHS) const {
144  auto State = C.getState();
145
146  auto Value = RHS;
147  if (auto ValAsLoc = RHS.getAs<Loc>()) {
148    Value = State->getRawSVal(*ValAsLoc);
149  }
150
151  if (Value.isUnknown())
152    return;
153
154  // Incremention or decremention by 0 is never a bug.
155  if (isZero(State, Value.castAs<NonLoc>()))
156    return;
157
158  // The result may be the past-end iterator of the container, but any other
159  // out of range position is undefined behaviour
160  auto StateAfter = advancePosition(State, LHS, Op, Value);
161  if (!StateAfter)
162    return;
163
164  const auto *PosAfter = getIteratorPosition(StateAfter, LHS);
165  assert(PosAfter &&
166         "Iterator should have position after successful advancement");
167  if (isAheadOfRange(State, *PosAfter)) {
168    auto *N = C.generateErrorNode(State);
169    if (!N)
170      return;
171    reportBug("Iterator decremented ahead of its valid range.", LHS,
172                        C, N);
173  }
174  if (isBehindPastTheEnd(State, *PosAfter)) {
175    auto *N = C.generateErrorNode(State);
176    if (!N)
177      return;
178    reportBug("Iterator incremented behind the past-the-end "
179                        "iterator.", LHS, C, N);
180  }
181}
182
183void IteratorRangeChecker::reportBug(const StringRef &Message,
184                                    const SVal &Val, CheckerContext &C,
185                                    ExplodedNode *ErrNode) const {
186  auto R = std::make_unique<PathSensitiveBugReport>(*OutOfRangeBugType, Message,
187                                                    ErrNode);
188  R->markInteresting(Val);
189  C.emitReport(std::move(R));
190}
191
192namespace {
193
194bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
195bool isGreater(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
196bool isEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
197
198bool isZero(ProgramStateRef State, const NonLoc &Val) {
199  auto &BVF = State->getBasicVals();
200  return compare(State, Val,
201                 nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(0))),
202                 BO_EQ);
203}
204
205bool isPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos) {
206  const auto *Cont = Pos.getContainer();
207  const auto *CData = getContainerData(State, Cont);
208  if (!CData)
209    return false;
210
211  const auto End = CData->getEnd();
212  if (End) {
213    if (isEqual(State, Pos.getOffset(), End)) {
214      return true;
215    }
216  }
217
218  return false;
219}
220
221bool isAheadOfRange(ProgramStateRef State, const IteratorPosition &Pos) {
222  const auto *Cont = Pos.getContainer();
223  const auto *CData = getContainerData(State, Cont);
224  if (!CData)
225    return false;
226
227  const auto Beg = CData->getBegin();
228  if (Beg) {
229    if (isLess(State, Pos.getOffset(), Beg)) {
230      return true;
231    }
232  }
233
234  return false;
235}
236
237bool isBehindPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos) {
238  const auto *Cont = Pos.getContainer();
239  const auto *CData = getContainerData(State, Cont);
240  if (!CData)
241    return false;
242
243  const auto End = CData->getEnd();
244  if (End) {
245    if (isGreater(State, Pos.getOffset(), End)) {
246      return true;
247    }
248  }
249
250  return false;
251}
252
253bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
254  return compare(State, Sym1, Sym2, BO_LT);
255}
256
257bool isGreater(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
258  return compare(State, Sym1, Sym2, BO_GT);
259}
260
261bool isEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
262  return compare(State, Sym1, Sym2, BO_EQ);
263}
264
265} // namespace
266
267void ento::registerIteratorRangeChecker(CheckerManager &mgr) {
268  mgr.registerChecker<IteratorRangeChecker>();
269}
270
271bool ento::shouldRegisterIteratorRangeChecker(const LangOptions &LO) {
272  return true;
273}
274