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