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