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