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
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 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
49 public:
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
71 bool isPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos);
72 bool isAheadOfRange(ProgramStateRef State, const IteratorPosition &Pos);
73 bool isBehindPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos);
74 bool isZero(ProgramStateRef State, NonLoc Val);
75
76 } // namespace
77
checkPreCall(const CallEvent & Call,CheckerContext & C) const78 void 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>(Call.getDecl());
82 if (!Func)
83 return;
84
85 if (Func->isOverloadedOperator()) {
86 if (isIncrementOperator(Func->getOverloadedOperator())) {
87 // Check for out-of-range incrementions
88 if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
89 verifyIncrement(C, InstCall->getCXXThisVal());
90 } else {
91 if (Call.getNumArgs() >= 1) {
92 verifyIncrement(C, Call.getArgSVal(0));
93 }
94 }
95 } else if (isDecrementOperator(Func->getOverloadedOperator())) {
96 // Check for out-of-range decrementions
97 if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
98 verifyDecrement(C, InstCall->getCXXThisVal());
99 } else {
100 if (Call.getNumArgs() >= 1) {
101 verifyDecrement(C, Call.getArgSVal(0));
102 }
103 }
104 } else if (isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) {
105 if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
106 // Check for out-of-range incrementions and decrementions
107 if (Call.getNumArgs() >= 1 &&
108 Call.getArgExpr(0)->getType()->isIntegralOrEnumerationType()) {
109 verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(),
110 InstCall->getCXXThisVal(),
111 Call.getArgSVal(0));
112 }
113 } else {
114 if (Call.getNumArgs() >= 2 &&
115 Call.getArgExpr(1)->getType()->isIntegralOrEnumerationType()) {
116 verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(),
117 Call.getArgSVal(0), Call.getArgSVal(1));
118 }
119 }
120 } else if (isDereferenceOperator(Func->getOverloadedOperator())) {
121 // Check for dereference of out-of-range iterators
122 if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
123 verifyDereference(C, InstCall->getCXXThisVal());
124 } else {
125 verifyDereference(C, Call.getArgSVal(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(0), Call.getArgSVal(1));
133 } else {
134 auto &BVF = C.getSValBuilder().getBasicValueFactory();
135 (this->**Verifier)(
136 C, Call.getArgSVal(0),
137 nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
138 }
139 }
140 }
141 }
142
checkPreStmt(const UnaryOperator * UO,CheckerContext & C) const143 void IteratorRangeChecker::checkPreStmt(const UnaryOperator *UO,
144 CheckerContext &C) const {
145 if (isa<CXXThisExpr>(UO->getSubExpr()))
146 return;
147
148 ProgramStateRef State = C.getState();
149 UnaryOperatorKind OK = UO->getOpcode();
150 SVal SubVal = State->getSVal(UO->getSubExpr(), C.getLocationContext());
151
152 if (isDereferenceOperator(OK)) {
153 verifyDereference(C, SubVal);
154 } else if (isIncrementOperator(OK)) {
155 verifyIncrement(C, SubVal);
156 } else if (isDecrementOperator(OK)) {
157 verifyDecrement(C, SubVal);
158 }
159 }
160
checkPreStmt(const BinaryOperator * BO,CheckerContext & C) const161 void IteratorRangeChecker::checkPreStmt(const BinaryOperator *BO,
162 CheckerContext &C) const {
163 ProgramStateRef State = C.getState();
164 BinaryOperatorKind OK = BO->getOpcode();
165 SVal LVal = State->getSVal(BO->getLHS(), C.getLocationContext());
166
167 if (isDereferenceOperator(OK)) {
168 verifyDereference(C, LVal);
169 } else if (isRandomIncrOrDecrOperator(OK)) {
170 SVal RVal = State->getSVal(BO->getRHS(), C.getLocationContext());
171 if (!BO->getRHS()->getType()->isIntegralOrEnumerationType())
172 return;
173 verifyRandomIncrOrDecr(C, BinaryOperator::getOverloadedOperator(OK), LVal,
174 RVal);
175 }
176 }
177
checkPreStmt(const ArraySubscriptExpr * ASE,CheckerContext & C) const178 void IteratorRangeChecker::checkPreStmt(const ArraySubscriptExpr *ASE,
179 CheckerContext &C) const {
180 ProgramStateRef State = C.getState();
181 SVal LVal = State->getSVal(ASE->getLHS(), C.getLocationContext());
182 verifyDereference(C, LVal);
183 }
184
checkPreStmt(const MemberExpr * ME,CheckerContext & C) const185 void 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(ME->getBase(), C.getLocationContext());
192 verifyDereference(C, BaseVal);
193 }
194
verifyDereference(CheckerContext & C,SVal Val) const195 void 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)) {
200 auto *N = C.generateErrorNode(State);
201 if (!N)
202 return;
203 reportBug("Past-the-end iterator dereferenced.", Val, C, N);
204 return;
205 }
206 }
207
verifyIncrement(CheckerContext & C,SVal Iter) const208 void IteratorRangeChecker::verifyIncrement(CheckerContext &C, SVal Iter) const {
209 auto &BVF = C.getSValBuilder().getBasicValueFactory();
210 verifyRandomIncrOrDecr(C, OO_Plus, Iter,
211 nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
212 }
213
verifyDecrement(CheckerContext & C,SVal Iter) const214 void IteratorRangeChecker::verifyDecrement(CheckerContext &C, SVal Iter) const {
215 auto &BVF = C.getSValBuilder().getBasicValueFactory();
216 verifyRandomIncrOrDecr(C, OO_Minus, Iter,
217 nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
218 }
219
verifyRandomIncrOrDecr(CheckerContext & C,OverloadedOperatorKind Op,SVal LHS,SVal RHS) const220 void 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(*ValAsLoc);
228 }
229
230 if (Value.isUnknownOrUndef() || !isa<NonLoc>(Value))
231 return;
232
233 // Incremention or decremention by 0 is never a bug.
234 if (isZero(State, 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, LHS, Op, Value);
240 if (!StateAfter)
241 return;
242
243 const auto *PosAfter = getIteratorPosition(StateAfter, LHS);
244 assert(PosAfter &&
245 "Iterator should have position after successful advancement");
246 if (isAheadOfRange(State, *PosAfter)) {
247 auto *N = C.generateErrorNode(State);
248 if (!N)
249 return;
250 reportBug("Iterator decremented ahead of its valid range.", LHS,
251 C, N);
252 }
253 if (isBehindPastTheEnd(State, *PosAfter)) {
254 auto *N = C.generateErrorNode(State);
255 if (!N)
256 return;
257 reportBug("Iterator incremented behind the past-the-end "
258 "iterator.", LHS, C, N);
259 }
260 }
261
verifyAdvance(CheckerContext & C,SVal LHS,SVal RHS) const262 void IteratorRangeChecker::verifyAdvance(CheckerContext &C, SVal LHS,
263 SVal RHS) const {
264 verifyRandomIncrOrDecr(C, OO_PlusEqual, LHS, RHS);
265 }
266
verifyPrev(CheckerContext & C,SVal LHS,SVal RHS) const267 void IteratorRangeChecker::verifyPrev(CheckerContext &C, SVal LHS,
268 SVal RHS) const {
269 verifyRandomIncrOrDecr(C, OO_Minus, LHS, RHS);
270 }
271
verifyNext(CheckerContext & C,SVal LHS,SVal RHS) const272 void IteratorRangeChecker::verifyNext(CheckerContext &C, SVal LHS,
273 SVal RHS) const {
274 verifyRandomIncrOrDecr(C, OO_Plus, LHS, RHS);
275 }
276
reportBug(StringRef Message,SVal Val,CheckerContext & C,ExplodedNode * ErrNode) const277 void IteratorRangeChecker::reportBug(StringRef Message, SVal Val,
278 CheckerContext &C,
279 ExplodedNode *ErrNode) const {
280 auto R = std::make_unique<PathSensitiveBugReport>(OutOfRangeBugType, Message,
281 ErrNode);
282
283 const auto *Pos = getIteratorPosition(C.getState(), Val);
284 assert(Pos && "Iterator without known position cannot be out-of-range.");
285
286 R->markInteresting(Val);
287 R->markInteresting(Pos->getContainer());
288 C.emitReport(std::move(R));
289 }
290
291 namespace {
292
293 bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
294 bool isGreater(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
295 bool isEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
296
isZero(ProgramStateRef State,NonLoc Val)297 bool isZero(ProgramStateRef State, NonLoc Val) {
298 auto &BVF = State->getBasicVals();
299 return compare(State, Val,
300 nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(0))),
301 BO_EQ);
302 }
303
isPastTheEnd(ProgramStateRef State,const IteratorPosition & Pos)304 bool 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, Pos.getOffset(), End)) {
313 return true;
314 }
315 }
316
317 return false;
318 }
319
isAheadOfRange(ProgramStateRef State,const IteratorPosition & Pos)320 bool 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, Pos.getOffset(), Beg)) {
329 return true;
330 }
331 }
332
333 return false;
334 }
335
isBehindPastTheEnd(ProgramStateRef State,const IteratorPosition & Pos)336 bool 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, Pos.getOffset(), End)) {
345 return true;
346 }
347 }
348
349 return false;
350 }
351
isLess(ProgramStateRef State,SymbolRef Sym1,SymbolRef Sym2)352 bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
353 return compare(State, Sym1, Sym2, BO_LT);
354 }
355
isGreater(ProgramStateRef State,SymbolRef Sym1,SymbolRef Sym2)356 bool isGreater(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
357 return compare(State, Sym1, Sym2, BO_GT);
358 }
359
isEqual(ProgramStateRef State,SymbolRef Sym1,SymbolRef Sym2)360 bool isEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
361 return compare(State, Sym1, Sym2, BO_EQ);
362 }
363
364 } // namespace
365
registerIteratorRangeChecker(CheckerManager & mgr)366 void ento::registerIteratorRangeChecker(CheckerManager &mgr) {
367 mgr.registerChecker<IteratorRangeChecker>();
368 }
369
shouldRegisterIteratorRangeChecker(const CheckerManager & mgr)370 bool ento::shouldRegisterIteratorRangeChecker(const CheckerManager &mgr) {
371 return true;
372 }
373