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