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