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