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 
52 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 
184 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 
195 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 
231 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 
269 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 
279 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 
290 void ento::registerMismatchedIteratorChecker(CheckerManager &mgr) {
291   mgr.registerChecker<MismatchedIteratorChecker>();
292 }
293 
294 bool ento::shouldRegisterMismatchedIteratorChecker(const CheckerManager &mgr) {
295   return true;
296 }
297