1 //===-- MismatchedIteratorChecker.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 mistakenly applying a foreign iterator on a container
10 // and for using iterators of two different containers in a context where
11 // iterators of the same container should be used.
12 //
13 //===----------------------------------------------------------------------===//
14
15 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
16 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
17 #include "clang/StaticAnalyzer/Core/Checker.h"
18 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
19 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
20
21
22 #include "Iterator.h"
23
24 using namespace clang;
25 using namespace ento;
26 using namespace iterator;
27
28 namespace {
29
30 class MismatchedIteratorChecker
31 : public Checker<check::PreCall, check::PreStmt<BinaryOperator>> {
32
33 const BugType MismatchedBugType{this, "Iterator(s) mismatched",
34 "Misuse of STL APIs",
35 /*SuppressOnSink=*/true};
36
37 void verifyMatch(CheckerContext &C, SVal Iter, const MemRegion *Cont) const;
38 void verifyMatch(CheckerContext &C, SVal Iter1, SVal Iter2) const;
39 void reportBug(StringRef Message, SVal Val1, SVal Val2, CheckerContext &C,
40 ExplodedNode *ErrNode) const;
41 void reportBug(StringRef Message, SVal Val, const MemRegion *Reg,
42 CheckerContext &C, ExplodedNode *ErrNode) const;
43
44 public:
45 void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
46 void checkPreStmt(const BinaryOperator *BO, CheckerContext &C) const;
47
48 };
49
50 } // namespace
51
checkPreCall(const CallEvent & Call,CheckerContext & C) const52 void MismatchedIteratorChecker::checkPreCall(const CallEvent &Call,
53 CheckerContext &C) const {
54 // Check for iterator mismatches
55 const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
56 if (!Func)
57 return;
58
59 if (Func->isOverloadedOperator() &&
60 isComparisonOperator(Func->getOverloadedOperator())) {
61 // Check for comparisons of iterators of different containers
62 if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
63 if (Call.getNumArgs() < 1)
64 return;
65
66 if (!isIteratorType(InstCall->getCXXThisExpr()->getType()) ||
67 !isIteratorType(Call.getArgExpr(0)->getType()))
68 return;
69
70 verifyMatch(C, InstCall->getCXXThisVal(), Call.getArgSVal(0));
71 } else {
72 if (Call.getNumArgs() < 2)
73 return;
74
75 if (!isIteratorType(Call.getArgExpr(0)->getType()) ||
76 !isIteratorType(Call.getArgExpr(1)->getType()))
77 return;
78
79 verifyMatch(C, Call.getArgSVal(0), Call.getArgSVal(1));
80 }
81 } else if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
82 const auto *ContReg = InstCall->getCXXThisVal().getAsRegion();
83 if (!ContReg)
84 return;
85 // Check for erase, insert and emplace using iterator of another container
86 if (isEraseCall(Func) || isEraseAfterCall(Func)) {
87 verifyMatch(C, Call.getArgSVal(0),
88 InstCall->getCXXThisVal().getAsRegion());
89 if (Call.getNumArgs() == 2) {
90 verifyMatch(C, Call.getArgSVal(1),
91 InstCall->getCXXThisVal().getAsRegion());
92 }
93 } else if (isInsertCall(Func)) {
94 verifyMatch(C, Call.getArgSVal(0),
95 InstCall->getCXXThisVal().getAsRegion());
96 if (Call.getNumArgs() == 3 &&
97 isIteratorType(Call.getArgExpr(1)->getType()) &&
98 isIteratorType(Call.getArgExpr(2)->getType())) {
99 verifyMatch(C, Call.getArgSVal(1), Call.getArgSVal(2));
100 }
101 } else if (isEmplaceCall(Func)) {
102 verifyMatch(C, Call.getArgSVal(0),
103 InstCall->getCXXThisVal().getAsRegion());
104 }
105 } else if (isa<CXXConstructorCall>(&Call)) {
106 // Check match of first-last iterator pair in a constructor of a container
107 if (Call.getNumArgs() < 2)
108 return;
109
110 const auto *Ctr = cast<CXXConstructorDecl>(Call.getDecl());
111 if (Ctr->getNumParams() < 2)
112 return;
113
114 if (Ctr->getParamDecl(0)->getName() != "first" ||
115 Ctr->getParamDecl(1)->getName() != "last")
116 return;
117
118 if (!isIteratorType(Call.getArgExpr(0)->getType()) ||
119 !isIteratorType(Call.getArgExpr(1)->getType()))
120 return;
121
122 verifyMatch(C, Call.getArgSVal(0), Call.getArgSVal(1));
123 } else {
124 // The main purpose of iterators is to abstract away from different
125 // containers and provide a (maybe limited) uniform access to them.
126 // This implies that any correctly written template function that
127 // works on multiple containers using iterators takes different
128 // template parameters for different containers. So we can safely
129 // assume that passing iterators of different containers as arguments
130 // whose type replaces the same template parameter is a bug.
131 //
132 // Example:
133 // template<typename I1, typename I2>
134 // void f(I1 first1, I1 last1, I2 first2, I2 last2);
135 //
136 // In this case the first two arguments to f() must be iterators must belong
137 // to the same container and the last to also to the same container but
138 // not necessarily to the same as the first two.
139
140 const auto *Templ = Func->getPrimaryTemplate();
141 if (!Templ)
142 return;
143
144 const auto *TParams = Templ->getTemplateParameters();
145 const auto *TArgs = Func->getTemplateSpecializationArgs();
146
147 // Iterate over all the template parameters
148 for (size_t I = 0; I < TParams->size(); ++I) {
149 const auto *TPDecl = dyn_cast<TemplateTypeParmDecl>(TParams->getParam(I));
150 if (!TPDecl)
151 continue;
152
153 if (TPDecl->isParameterPack())
154 continue;
155
156 const auto TAType = TArgs->get(I).getAsType();
157 if (!isIteratorType(TAType))
158 continue;
159
160 SVal LHS = UndefinedVal();
161
162 // For every template parameter which is an iterator type in the
163 // instantiation look for all functions' parameters' type by it and
164 // check whether they belong to the same container
165 for (auto J = 0U; J < Func->getNumParams(); ++J) {
166 const auto *Param = Func->getParamDecl(J);
167 const auto *ParamType =
168 Param->getType()->getAs<SubstTemplateTypeParmType>();
169 if (!ParamType)
170 continue;
171 const TemplateTypeParmDecl *D = ParamType->getReplacedParameter();
172 if (D != TPDecl)
173 continue;
174 if (LHS.isUndef()) {
175 LHS = Call.getArgSVal(J);
176 } else {
177 verifyMatch(C, LHS, Call.getArgSVal(J));
178 }
179 }
180 }
181 }
182 }
183
checkPreStmt(const BinaryOperator * BO,CheckerContext & C) const184 void MismatchedIteratorChecker::checkPreStmt(const BinaryOperator *BO,
185 CheckerContext &C) const {
186 if (!BO->isComparisonOp())
187 return;
188
189 ProgramStateRef State = C.getState();
190 SVal LVal = State->getSVal(BO->getLHS(), C.getLocationContext());
191 SVal RVal = State->getSVal(BO->getRHS(), C.getLocationContext());
192 verifyMatch(C, LVal, RVal);
193 }
194
verifyMatch(CheckerContext & C,SVal Iter,const MemRegion * Cont) const195 void MismatchedIteratorChecker::verifyMatch(CheckerContext &C, SVal Iter,
196 const MemRegion *Cont) const {
197 // Verify match between a container and the container of an iterator
198 Cont = Cont->getMostDerivedObjectRegion();
199
200 if (const auto *ContSym = Cont->getSymbolicBase()) {
201 if (isa<SymbolConjured>(ContSym->getSymbol()))
202 return;
203 }
204
205 auto State = C.getState();
206 const auto *Pos = getIteratorPosition(State, Iter);
207 if (!Pos)
208 return;
209
210 const auto *IterCont = Pos->getContainer();
211
212 // Skip symbolic regions based on conjured symbols. Two conjured symbols
213 // may or may not be the same. For example, the same function can return
214 // the same or a different container but we get different conjured symbols
215 // for each call. This may cause false positives so omit them from the check.
216 if (const auto *ContSym = IterCont->getSymbolicBase()) {
217 if (isa<SymbolConjured>(ContSym->getSymbol()))
218 return;
219 }
220
221 if (IterCont != Cont) {
222 auto *N = C.generateNonFatalErrorNode(State);
223 if (!N) {
224 return;
225 }
226 reportBug("Container accessed using foreign iterator argument.",
227 Iter, Cont, C, N);
228 }
229 }
230
verifyMatch(CheckerContext & C,SVal Iter1,SVal Iter2) const231 void MismatchedIteratorChecker::verifyMatch(CheckerContext &C, SVal Iter1,
232 SVal Iter2) const {
233 // Verify match between the containers of two iterators
234 auto State = C.getState();
235 const auto *Pos1 = getIteratorPosition(State, Iter1);
236 if (!Pos1)
237 return;
238
239 const auto *IterCont1 = Pos1->getContainer();
240
241 // Skip symbolic regions based on conjured symbols. Two conjured symbols
242 // may or may not be the same. For example, the same function can return
243 // the same or a different container but we get different conjured symbols
244 // for each call. This may cause false positives so omit them from the check.
245 if (const auto *ContSym = IterCont1->getSymbolicBase()) {
246 if (isa<SymbolConjured>(ContSym->getSymbol()))
247 return;
248 }
249
250 const auto *Pos2 = getIteratorPosition(State, Iter2);
251 if (!Pos2)
252 return;
253
254 const auto *IterCont2 = Pos2->getContainer();
255 if (const auto *ContSym = IterCont2->getSymbolicBase()) {
256 if (isa<SymbolConjured>(ContSym->getSymbol()))
257 return;
258 }
259
260 if (IterCont1 != IterCont2) {
261 auto *N = C.generateNonFatalErrorNode(State);
262 if (!N)
263 return;
264 reportBug("Iterators of different containers used where the "
265 "same container is expected.", Iter1, Iter2, C, N);
266 }
267 }
268
reportBug(StringRef Message,SVal Val1,SVal Val2,CheckerContext & C,ExplodedNode * ErrNode) const269 void MismatchedIteratorChecker::reportBug(StringRef Message, SVal Val1,
270 SVal Val2, CheckerContext &C,
271 ExplodedNode *ErrNode) const {
272 auto R = std::make_unique<PathSensitiveBugReport>(MismatchedBugType, Message,
273 ErrNode);
274 R->markInteresting(Val1);
275 R->markInteresting(Val2);
276 C.emitReport(std::move(R));
277 }
278
reportBug(StringRef Message,SVal Val,const MemRegion * Reg,CheckerContext & C,ExplodedNode * ErrNode) const279 void MismatchedIteratorChecker::reportBug(StringRef Message, SVal Val,
280 const MemRegion *Reg,
281 CheckerContext &C,
282 ExplodedNode *ErrNode) const {
283 auto R = std::make_unique<PathSensitiveBugReport>(MismatchedBugType, Message,
284 ErrNode);
285 R->markInteresting(Val);
286 R->markInteresting(Reg);
287 C.emitReport(std::move(R));
288 }
289
registerMismatchedIteratorChecker(CheckerManager & mgr)290 void ento::registerMismatchedIteratorChecker(CheckerManager &mgr) {
291 mgr.registerChecker<MismatchedIteratorChecker>();
292 }
293
shouldRegisterMismatchedIteratorChecker(const CheckerManager & mgr)294 bool ento::shouldRegisterMismatchedIteratorChecker(const CheckerManager &mgr) {
295 return true;
296 }
297