clang 18.0.0git
IteratorRangeChecker.cpp
Go to the documentation of this file.
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
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 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
48public:
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
67bool isPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos);
68bool isAheadOfRange(ProgramStateRef State, const IteratorPosition &Pos);
69bool isBehindPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos);
70bool isZero(ProgramStateRef State, const NonLoc &Val);
71
72} //namespace
73
74IteratorRangeChecker::IteratorRangeChecker() {
75 OutOfRangeBugType.reset(
76 new BugType(this, "Iterator out of range", "Misuse of STL APIs"));
77}
78
79void IteratorRangeChecker::checkPreCall(const CallEvent &Call,
80 CheckerContext &C) const {
81 // Check for out of range access
82 const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
83 if (!Func)
84 return;
85
86 if (Func->isOverloadedOperator()) {
87 if (isIncrementOperator(Func->getOverloadedOperator())) {
88 // Check for out-of-range incrementions
89 if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
90 verifyIncrement(C, InstCall->getCXXThisVal());
91 } else {
92 if (Call.getNumArgs() >= 1) {
93 verifyIncrement(C, Call.getArgSVal(0));
94 }
95 }
96 } else if (isDecrementOperator(Func->getOverloadedOperator())) {
97 // Check for out-of-range decrementions
98 if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
99 verifyDecrement(C, InstCall->getCXXThisVal());
100 } else {
101 if (Call.getNumArgs() >= 1) {
102 verifyDecrement(C, Call.getArgSVal(0));
103 }
104 }
105 } else if (isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) {
106 if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
107 // Check for out-of-range incrementions and decrementions
108 if (Call.getNumArgs() >= 1 &&
109 Call.getArgExpr(0)->getType()->isIntegralOrEnumerationType()) {
110 verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(),
111 InstCall->getCXXThisVal(),
112 Call.getArgSVal(0));
113 }
114 } else {
115 if (Call.getNumArgs() >= 2 &&
116 Call.getArgExpr(1)->getType()->isIntegralOrEnumerationType()) {
117 verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(),
118 Call.getArgSVal(0), Call.getArgSVal(1));
119 }
120 }
121 } else if (isDereferenceOperator(Func->getOverloadedOperator())) {
122 // Check for dereference of out-of-range iterators
123 if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
124 verifyDereference(C, InstCall->getCXXThisVal());
125 } else {
126 verifyDereference(C, Call.getArgSVal(0));
127 }
128 }
129 } else {
130 const AdvanceFn *Verifier = AdvanceFunctions.lookup(Call);
131 if (Verifier) {
132 if (Call.getNumArgs() > 1) {
133 (this->**Verifier)(C, Call.getArgSVal(0), Call.getArgSVal(1));
134 } else {
135 auto &BVF = C.getSValBuilder().getBasicValueFactory();
136 (this->**Verifier)(
137 C, Call.getArgSVal(0),
138 nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
139 }
140 }
141 }
142}
143
144void IteratorRangeChecker::checkPreStmt(const UnaryOperator *UO,
145 CheckerContext &C) const {
146 if (isa<CXXThisExpr>(UO->getSubExpr()))
147 return;
148
149 ProgramStateRef State = C.getState();
150 UnaryOperatorKind OK = UO->getOpcode();
151 SVal SubVal = State->getSVal(UO->getSubExpr(), C.getLocationContext());
152
153 if (isDereferenceOperator(OK)) {
154 verifyDereference(C, SubVal);
155 } else if (isIncrementOperator(OK)) {
156 verifyIncrement(C, SubVal);
157 } else if (isDecrementOperator(OK)) {
158 verifyDecrement(C, SubVal);
159 }
160}
161
162void IteratorRangeChecker::checkPreStmt(const BinaryOperator *BO,
163 CheckerContext &C) const {
164 ProgramStateRef State = C.getState();
165 BinaryOperatorKind OK = BO->getOpcode();
166 SVal LVal = State->getSVal(BO->getLHS(), C.getLocationContext());
167
168 if (isDereferenceOperator(OK)) {
169 verifyDereference(C, LVal);
170 } else if (isRandomIncrOrDecrOperator(OK)) {
171 SVal RVal = State->getSVal(BO->getRHS(), C.getLocationContext());
173 return;
174 verifyRandomIncrOrDecr(C, BinaryOperator::getOverloadedOperator(OK), LVal,
175 RVal);
176 }
177}
178
179void IteratorRangeChecker::checkPreStmt(const ArraySubscriptExpr *ASE,
180 CheckerContext &C) const {
181 ProgramStateRef State = C.getState();
182 SVal LVal = State->getSVal(ASE->getLHS(), C.getLocationContext());
183 verifyDereference(C, LVal);
184}
185
186void IteratorRangeChecker::checkPreStmt(const MemberExpr *ME,
187 CheckerContext &C) const {
188 if (!ME->isArrow() || ME->isImplicitAccess())
189 return;
190
191 ProgramStateRef State = C.getState();
192 SVal BaseVal = State->getSVal(ME->getBase(), C.getLocationContext());
193 verifyDereference(C, BaseVal);
194}
195
196void IteratorRangeChecker::verifyDereference(CheckerContext &C,
197 SVal Val) const {
198 auto State = C.getState();
199 const auto *Pos = getIteratorPosition(State, Val);
200 if (Pos && isPastTheEnd(State, *Pos)) {
201 auto *N = C.generateErrorNode(State);
202 if (!N)
203 return;
204 reportBug("Past-the-end iterator dereferenced.", Val, C, N);
205 return;
206 }
207}
208
209void IteratorRangeChecker::verifyIncrement(CheckerContext &C, SVal Iter) const {
210 auto &BVF = C.getSValBuilder().getBasicValueFactory();
211 verifyRandomIncrOrDecr(C, OO_Plus, Iter,
212 nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
213}
214
215void IteratorRangeChecker::verifyDecrement(CheckerContext &C, SVal Iter) const {
216 auto &BVF = C.getSValBuilder().getBasicValueFactory();
217 verifyRandomIncrOrDecr(C, OO_Minus, Iter,
218 nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
219}
220
221void IteratorRangeChecker::verifyRandomIncrOrDecr(CheckerContext &C,
223 SVal LHS, SVal RHS) const {
224 auto State = C.getState();
225
226 auto Value = RHS;
227 if (auto ValAsLoc = RHS.getAs<Loc>()) {
228 Value = State->getRawSVal(*ValAsLoc);
229 }
230
231 if (Value.isUnknownOrUndef() || !isa<NonLoc>(Value))
232 return;
233
234 // Incremention or decremention by 0 is never a bug.
235 if (isZero(State, Value.castAs<NonLoc>()))
236 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 auto StateAfter = advancePosition(State, LHS, Op, Value);
241 if (!StateAfter)
242 return;
243
244 const auto *PosAfter = getIteratorPosition(StateAfter, LHS);
245 assert(PosAfter &&
246 "Iterator should have position after successful advancement");
247 if (isAheadOfRange(State, *PosAfter)) {
248 auto *N = C.generateErrorNode(State);
249 if (!N)
250 return;
251 reportBug("Iterator decremented ahead of its valid range.", LHS,
252 C, N);
253 }
254 if (isBehindPastTheEnd(State, *PosAfter)) {
255 auto *N = C.generateErrorNode(State);
256 if (!N)
257 return;
258 reportBug("Iterator incremented behind the past-the-end "
259 "iterator.", LHS, C, N);
260 }
261}
262
263void IteratorRangeChecker::verifyAdvance(CheckerContext &C, SVal LHS,
264 SVal RHS) const {
265 verifyRandomIncrOrDecr(C, OO_PlusEqual, LHS, RHS);
266}
267
268void IteratorRangeChecker::verifyPrev(CheckerContext &C, SVal LHS,
269 SVal RHS) const {
270 verifyRandomIncrOrDecr(C, OO_Minus, LHS, RHS);
271}
272
273void IteratorRangeChecker::verifyNext(CheckerContext &C, SVal LHS,
274 SVal RHS) const {
275 verifyRandomIncrOrDecr(C, OO_Plus, LHS, RHS);
276}
277
278void IteratorRangeChecker::reportBug(const StringRef &Message, SVal Val,
280 ExplodedNode *ErrNode) const {
281 auto R = std::make_unique<PathSensitiveBugReport>(*OutOfRangeBugType, Message,
282 ErrNode);
283
284 const auto *Pos = getIteratorPosition(C.getState(), Val);
285 assert(Pos && "Iterator without known position cannot be out-of-range.");
286
287 R->markInteresting(Val);
288 R->markInteresting(Pos->getContainer());
289 C.emitReport(std::move(R));
290}
291
292namespace {
293
294bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
295bool isGreater(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
296bool isEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
297
298bool isZero(ProgramStateRef State, const NonLoc &Val) {
299 auto &BVF = State->getBasicVals();
300 return compare(State, Val,
301 nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(0))),
302 BO_EQ);
303}
304
305bool isPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos) {
306 const auto *Cont = Pos.getContainer();
307 const auto *CData = getContainerData(State, Cont);
308 if (!CData)
309 return false;
310
311 const auto End = CData->getEnd();
312 if (End) {
313 if (isEqual(State, Pos.getOffset(), End)) {
314 return true;
315 }
316 }
317
318 return false;
319}
320
321bool isAheadOfRange(ProgramStateRef State, const IteratorPosition &Pos) {
322 const auto *Cont = Pos.getContainer();
323 const auto *CData = getContainerData(State, Cont);
324 if (!CData)
325 return false;
326
327 const auto Beg = CData->getBegin();
328 if (Beg) {
329 if (isLess(State, Pos.getOffset(), Beg)) {
330 return true;
331 }
332 }
333
334 return false;
335}
336
337bool isBehindPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos) {
338 const auto *Cont = Pos.getContainer();
339 const auto *CData = getContainerData(State, Cont);
340 if (!CData)
341 return false;
342
343 const auto End = CData->getEnd();
344 if (End) {
345 if (isGreater(State, Pos.getOffset(), End)) {
346 return true;
347 }
348 }
349
350 return false;
351}
352
353bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
354 return compare(State, Sym1, Sym2, BO_LT);
355}
356
357bool isGreater(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
358 return compare(State, Sym1, Sym2, BO_GT);
359}
360
361bool isEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
362 return compare(State, Sym1, Sym2, BO_EQ);
363}
364
365} // namespace
366
367void ento::registerIteratorRangeChecker(CheckerManager &mgr) {
368 mgr.registerChecker<IteratorRangeChecker>();
369}
370
371bool ento::shouldRegisterIteratorRangeChecker(const CheckerManager &mgr) {
372 return true;
373}
unsigned Iter
Definition: HTMLLogger.cpp:154
static bool compare(const PathDiagnostic &X, const PathDiagnostic &Y)
ArraySubscriptExpr - [C99 6.5.2.1] Array Subscripting.
Definition: Expr.h:2691
Expr * getLHS()
An array access can be written A[4] or 4[A] (both are equivalent).
Definition: Expr.h:2720
A builtin binary operation expression such as "x + y" or "x <= y".
Definition: Expr.h:3862
Expr * getLHS() const
Definition: Expr.h:3911
static OverloadedOperatorKind getOverloadedOperator(Opcode Opc)
Retrieve the overloaded operator kind that corresponds to the given binary opcode.
Definition: Expr.cpp:2156
Expr * getRHS() const
Definition: Expr.h:3913
Opcode getOpcode() const
Definition: Expr.h:3906
QualType getType() const
Definition: Expr.h:142
MemberExpr - [C99 6.5.2.3] Structure and Union Members.
Definition: Expr.h:3210
bool isImplicitAccess() const
Determine whether the base of this explicit is implicit.
Definition: Expr.h:3404
Expr * getBase() const
Definition: Expr.h:3283
bool isArrow() const
Definition: Expr.h:3390
bool isIntegralOrEnumerationType() const
Determine whether this type is an integral or enumeration type.
Definition: Type.h:7455
UnaryOperator - This represents the unary-expression's (except sizeof and alignof),...
Definition: Expr.h:2210
Expr * getSubExpr() const
Definition: Expr.h:2255
Opcode getOpcode() const
Definition: Expr.h:2250
An immutable map from CallDescriptions to arbitrary data.
Represents an abstract call to a function or method along a particular path.
Definition: CallEvent.h:152
CHECKER * registerChecker(AT &&... Args)
Used to register checkers.
SVal - This represents a symbolic expression, which can be either an L-value or an R-value.
Definition: SVals.h:55
std::optional< T > getAs() const
Convert to the specified SVal type, returning std::nullopt if this SVal is not of the desired type.
Definition: SVals.h:86
Symbolic value.
Definition: SymExpr.h:30
Value representing integer constant.
Definition: SVals.h:305
ProgramStateRef advancePosition(ProgramStateRef State, const SVal &Iter, OverloadedOperatorKind Op, const SVal &Distance)
Definition: Iterator.cpp:224
const IteratorPosition * getIteratorPosition(ProgramStateRef State, const SVal &Val)
Definition: Iterator.cpp:184
bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK)
Definition: Iterator.cpp:169
const ContainerData * getContainerData(ProgramStateRef State, const MemRegion *Cont)
Definition: Iterator.cpp:179
bool isDecrementOperator(OverloadedOperatorKind OK)
Definition: Iterator.cpp:161
bool isDereferenceOperator(OverloadedOperatorKind OK)
Definition: Iterator.cpp:140
bool isIncrementOperator(OverloadedOperatorKind OK)
Definition: Iterator.cpp:153
OverloadedOperatorKind
Enumeration specifying the different kinds of C++ overloaded operators.
Definition: OperatorKinds.h:21
BinaryOperatorKind
UnaryOperatorKind
const MemRegion * getContainer() const
Definition: Iterator.h:42