| 1 |
//===-- IteratorRangeChecker.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 dereference of the past-the-end iterator and |
| 10 |
// out-of-range increments and decrements. |
| 11 |
// |
| 12 |
//===----------------------------------------------------------------------===// |
| 13 |
|
| 14 |
#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h" |
| 15 |
#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" |
| 16 |
#include "clang/StaticAnalyzer/Core/Checker.h" |
| 17 |
#include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h" |
| 18 |
#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" |
| 19 |
#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" |
| 20 |
|
| 21 |
#include "Iterator.h" |
| 22 |
|
| 23 |
using namespace clang; |
| 24 |
using namespace ento; |
| 25 |
using namespace iterator; |
| 26 |
|
| 27 |
namespace { |
| 28 |
|
| 29 |
class IteratorRangeChecker |
| 30 |
: public Checker<check::PreCall, check::PreStmt<UnaryOperator>, |
| 31 |
check::PreStmt<BinaryOperator>, |
| 32 |
check::PreStmt<ArraySubscriptExpr>, |
| 33 |
check::PreStmt<MemberExpr>> { |
| 34 |
|
| 35 |
std::unique_ptr<BugType> OutOfRangeBugType; |
| 36 |
|
| 37 |
void verifyDereference(CheckerContext &C, SVal Val) const; |
| 38 |
void verifyIncrement(CheckerContext &C, SVal Iter) const; |
| 39 |
void verifyDecrement(CheckerContext &C, SVal Iter) const; |
| 40 |
void verifyRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op, |
| 41 |
SVal LHS, SVal RHS) const; |
| 42 |
void verifyAdvance(CheckerContext &C, SVal LHS, SVal RHS) const; |
| 43 |
void verifyPrev(CheckerContext &C, SVal LHS, SVal RHS) const; |
| 44 |
void verifyNext(CheckerContext &C, SVal LHS, SVal RHS) const; |
| 45 |
void reportBug(const StringRef &Message, SVal Val, CheckerContext &C, |
| 46 |
ExplodedNode *ErrNode) const; |
| 47 |
|
| 48 |
public: |
| 49 |
IteratorRangeChecker(); |
| 50 |
|
| 51 |
void checkPreCall(const CallEvent &Call, CheckerContext &C) const; |
| 52 |
void checkPreStmt(const UnaryOperator *UO, CheckerContext &C) const; |
| 53 |
void checkPreStmt(const BinaryOperator *BO, CheckerContext &C) const; |
| 54 |
void checkPreStmt(const ArraySubscriptExpr *ASE, CheckerContext &C) const; |
| 55 |
void checkPreStmt(const MemberExpr *ME, CheckerContext &C) const; |
| 56 |
|
| 57 |
using AdvanceFn = void (IteratorRangeChecker::*)(CheckerContext &, SVal, |
| 58 |
SVal) const; |
| 59 |
|
| 60 |
CallDescriptionMap<AdvanceFn> AdvanceFunctions = { |
| 61 |
{{{"std", "advance"}, 2}, &IteratorRangeChecker::verifyAdvance}, |
| 62 |
{{{"std", "prev"}, 2}, &IteratorRangeChecker::verifyPrev}, |
| 63 |
{{{"std", "next"}, 2}, &IteratorRangeChecker::verifyNext}, |
| 64 |
}; |
| 65 |
}; |
| 66 |
|
| 67 |
bool isPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos); |
| 68 |
bool isAheadOfRange(ProgramStateRef State, const IteratorPosition &Pos); |
| 69 |
bool isBehindPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos); |
| 70 |
bool isZero(ProgramStateRef State, const NonLoc &Val); |
| 71 |
|
| 72 |
} //namespace |
| 73 |
|
| 74 |
IteratorRangeChecker::IteratorRangeChecker() { |
| 75 |
OutOfRangeBugType.reset( |
| 76 |
new BugType(this, "Iterator out of range", "Misuse of STL APIs")); |
| 77 |
} |
| 78 |
|
| 79 |
void IteratorRangeChecker::checkPreCall(const CallEvent &Call, |
| 80 |
CheckerContext &C) const { |
| 81 |
// Check for out of range access |
| 82 |
const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl()); |
| 83 |
if (!Func) |
| 84 |
return; |
| 85 |
|
| 86 |
if (Func->isOverloadedOperator()) { |
| 87 |
if (isIncrementOperator(Func->getOverloadedOperator())) { |
| 88 |
// Check for out-of-range incrementions |
| 89 |
if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) { |
| 90 |
verifyIncrement(C, InstCall->getCXXThisVal()); |
| 91 |
} else { |
| 92 |
if (Call.getNumArgs() >= 1) { |
| 93 |
verifyIncrement(C, Call.getArgSVal(0)); |
| 94 |
} |
| 95 |
} |
| 96 |
} else if (isDecrementOperator(Func->getOverloadedOperator())) { |
| 97 |
// Check for out-of-range decrementions |
| 98 |
if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) { |
| 99 |
verifyDecrement(C, InstCall->getCXXThisVal()); |
| 100 |
} else { |
| 101 |
if (Call.getNumArgs() >= 1) { |
| 102 |
verifyDecrement(C, Call.getArgSVal(0)); |
| 103 |
} |
| 104 |
} |
| 105 |
} else if (isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) { |
| 106 |
if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) { |
| 107 |
// Check for out-of-range incrementions and decrementions |
| 108 |
if (Call.getNumArgs() >= 1 && |
| 109 |
Call.getArgExpr(0)->getType()->isIntegralOrEnumerationType()) { |
| 110 |
verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(), |
| 111 |
InstCall->getCXXThisVal(), |
| 112 |
Call.getArgSVal(0)); |
| 113 |
} |
| 114 |
} else { |
| 115 |
if (Call.getNumArgs() >= 2 && |
| 116 |
Call.getArgExpr(1)->getType()->isIntegralOrEnumerationType()) { |
| 117 |
verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(), |
| 118 |
Call.getArgSVal(0), Call.getArgSVal(1)); |
| 119 |
} |
| 120 |
} |
| 121 |
} else if (isDereferenceOperator(Func->getOverloadedOperator())) { |
| 122 |
// Check for dereference of out-of-range iterators |
| 123 |
if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) { |
| 124 |
verifyDereference(C, InstCall->getCXXThisVal()); |
| 125 |
} else { |
| 126 |
verifyDereference(C, Call.getArgSVal(0)); |
| 127 |
} |
| 128 |
} |
| 129 |
} else { |
| 130 |
const AdvanceFn *Verifier = AdvanceFunctions.lookup(Call); |
| 131 |
if (Verifier) { |
| 132 |
if (Call.getNumArgs() > 1) { |
| 133 |
(this->**Verifier)(C, Call.getArgSVal(0), Call.getArgSVal(1)); |
| 134 |
} else { |
| 135 |
auto &BVF = C.getSValBuilder().getBasicValueFactory(); |
| 136 |
(this->**Verifier)( |
| 137 |
C, Call.getArgSVal(0), |
| 138 |
nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1)))); |
| 139 |
} |
| 140 |
} |
| 141 |
} |
| 142 |
} |
| 143 |
|
| 144 |
void IteratorRangeChecker::checkPreStmt(const UnaryOperator *UO, |
| 145 |
CheckerContext &C) const { |
| 146 |
if (isa<CXXThisExpr>(UO->getSubExpr())) |
| 147 |
return; |
| 148 |
|
| 149 |
ProgramStateRef State = C.getState(); |
| 150 |
UnaryOperatorKind OK = UO->getOpcode(); |
| 151 |
SVal SubVal = State->getSVal(UO->getSubExpr(), C.getLocationContext()); |
| 152 |
|
| 153 |
if (isDereferenceOperator(OK)) { |
| 154 |
verifyDereference(C, SubVal); |
| 155 |
} else if (isIncrementOperator(OK)) { |
| 156 |
verifyIncrement(C, SubVal); |
| 157 |
} else if (isDecrementOperator(OK)) { |
| 158 |
verifyDecrement(C, SubVal); |
| 159 |
} |
| 160 |
} |
| 161 |
|
| 162 |
void IteratorRangeChecker::checkPreStmt(const BinaryOperator *BO, |
| 163 |
CheckerContext &C) const { |
| 164 |
ProgramStateRef State = C.getState(); |
| 165 |
BinaryOperatorKind OK = BO->getOpcode(); |
| 166 |
SVal LVal = State->getSVal(BO->getLHS(), C.getLocationContext()); |
| 167 |
|
| 168 |
if (isDereferenceOperator(OK)) { |
| 169 |
verifyDereference(C, LVal); |
| 170 |
} else if (isRandomIncrOrDecrOperator(OK)) { |
| 171 |
SVal RVal = State->getSVal(BO->getRHS(), C.getLocationContext()); |
| 172 |
if (!BO->getRHS()->getType()->isIntegralOrEnumerationType()) |
| 173 |
return; |
| 174 |
verifyRandomIncrOrDecr(C, BinaryOperator::getOverloadedOperator(OK), LVal, |
| 175 |
RVal); |
| 176 |
} |
| 177 |
} |
| 178 |
|
| 179 |
void IteratorRangeChecker::checkPreStmt(const ArraySubscriptExpr *ASE, |
| 180 |
CheckerContext &C) const { |
| 181 |
ProgramStateRef State = C.getState(); |
| 182 |
SVal LVal = State->getSVal(ASE->getLHS(), C.getLocationContext()); |
| 183 |
verifyDereference(C, LVal); |
| 184 |
} |
| 185 |
|
| 186 |
void IteratorRangeChecker::checkPreStmt(const MemberExpr *ME, |
| 187 |
CheckerContext &C) const { |
| 188 |
if (!ME->isArrow() || ME->isImplicitAccess()) |
| 189 |
return; |
| 190 |
|
| 191 |
ProgramStateRef State = C.getState(); |
| 192 |
SVal BaseVal = State->getSVal(ME->getBase(), C.getLocationContext()); |
| 193 |
verifyDereference(C, BaseVal); |
| 194 |
} |
| 195 |
|
| 196 |
void IteratorRangeChecker::verifyDereference(CheckerContext &C, |
| 197 |
SVal Val) const { |
| 198 |
auto State = C.getState(); |
| 199 |
const auto *Pos = getIteratorPosition(State, Val); |
| 200 |
if (Pos && isPastTheEnd(State, *Pos)) { |
| 201 |
auto *N = C.generateErrorNode(State); |
| 202 |
if (!N) |
| 203 |
return; |
| 204 |
reportBug("Past-the-end iterator dereferenced.", Val, C, N); |
| 205 |
return; |
| 206 |
} |
| 207 |
} |
| 208 |
|
| 209 |
void IteratorRangeChecker::verifyIncrement(CheckerContext &C, SVal Iter) const { |
| 210 |
auto &BVF = C.getSValBuilder().getBasicValueFactory(); |
| 211 |
verifyRandomIncrOrDecr(C, OO_Plus, Iter, |
| 212 |
nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1)))); |
| 213 |
} |
| 214 |
|
| 215 |
void IteratorRangeChecker::verifyDecrement(CheckerContext &C, SVal Iter) const { |
| 216 |
auto &BVF = C.getSValBuilder().getBasicValueFactory(); |
| 217 |
verifyRandomIncrOrDecr(C, OO_Minus, Iter, |
| 218 |
nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1)))); |
| 219 |
} |
| 220 |
|
| 221 |
void IteratorRangeChecker::verifyRandomIncrOrDecr(CheckerContext &C, |
| 222 |
OverloadedOperatorKind Op, |
| 223 |
SVal LHS, SVal RHS) const { |
| 224 |
auto State = C.getState(); |
| 225 |
|
| 226 |
auto Value = RHS; |
| 227 |
if (auto ValAsLoc = RHS.getAs<Loc>()) { |
| 228 |
Value = State->getRawSVal(*ValAsLoc); |
| 229 |
} |
| 230 |
|
| 231 |
if (Value.isUnknownOrUndef()) |
| 232 |
return; |
| 233 |
|
| 234 |
// Incremention or decremention by 0 is never a bug. |
| 235 |
if (isZero(State, Value.castAs<NonLoc>())) |
| 236 |
return; |
| 237 |
|
| 238 |
// The result may be the past-end iterator of the container, but any other |
| 239 |
// out of range position is undefined behaviour |
| 240 |
auto StateAfter = advancePosition(State, LHS, Op, Value); |
| 241 |
if (!StateAfter) |
| 242 |
return; |
| 243 |
|
| 244 |
const auto *PosAfter = getIteratorPosition(StateAfter, LHS); |
| 245 |
assert(PosAfter && |
| 246 |
"Iterator should have position after successful advancement"); |
| 247 |
if (isAheadOfRange(State, *PosAfter)) { |
| 248 |
auto *N = C.generateErrorNode(State); |
| 249 |
if (!N) |
| 250 |
return; |
| 251 |
reportBug("Iterator decremented ahead of its valid range.", LHS, |
| 252 |
C, N); |
| 253 |
} |
| 254 |
if (isBehindPastTheEnd(State, *PosAfter)) { |
| 255 |
auto *N = C.generateErrorNode(State); |
| 256 |
if (!N) |
| 257 |
return; |
| 258 |
reportBug("Iterator incremented behind the past-the-end " |
| 259 |
"iterator.", LHS, C, N); |
| 260 |
} |
| 261 |
} |
| 262 |
|
| 263 |
void IteratorRangeChecker::verifyAdvance(CheckerContext &C, SVal LHS, |
| 264 |
SVal RHS) const { |
| 265 |
verifyRandomIncrOrDecr(C, OO_PlusEqual, LHS, RHS); |
| 266 |
} |
| 267 |
|
| 268 |
void IteratorRangeChecker::verifyPrev(CheckerContext &C, SVal LHS, |
| 269 |
SVal RHS) const { |
| 270 |
verifyRandomIncrOrDecr(C, OO_Minus, LHS, RHS); |
| 271 |
} |
| 272 |
|
| 273 |
void IteratorRangeChecker::verifyNext(CheckerContext &C, SVal LHS, |
| 274 |
SVal RHS) const { |
| 275 |
verifyRandomIncrOrDecr(C, OO_Plus, LHS, RHS); |
| 276 |
} |
| 277 |
|
| 278 |
void IteratorRangeChecker::reportBug(const StringRef &Message, SVal Val, |
| 279 |
CheckerContext &C, |
| 280 |
ExplodedNode *ErrNode) const { |
| 281 |
auto R = std::make_unique<PathSensitiveBugReport>(*OutOfRangeBugType, Message, |
| 282 |
ErrNode); |
| 283 |
|
| 284 |
const auto *Pos = getIteratorPosition(C.getState(), Val); |
| 285 |
assert(Pos && "Iterator without known position cannot be out-of-range."); |
| 286 |
|
| 287 |
R->markInteresting(Val); |
| 288 |
R->markInteresting(Pos->getContainer()); |
| 289 |
C.emitReport(std::move(R)); |
| 290 |
} |
| 291 |
|
| 292 |
namespace { |
| 293 |
|
| 294 |
bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2); |
| 295 |
bool isGreater(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2); |
| 296 |
bool isEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2); |
| 297 |
|
| 298 |
bool isZero(ProgramStateRef State, const NonLoc &Val) { |
| 299 |
auto &BVF = State->getBasicVals(); |
| 300 |
return compare(State, Val, |
| 301 |
nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(0))), |
| 302 |
BO_EQ); |
| 303 |
} |
| 304 |
|
| 305 |
bool isPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos) { |
| 306 |
const auto *Cont = Pos.getContainer(); |
| 307 |
const auto *CData = getContainerData(State, Cont); |
| 308 |
if (!CData) |
| 309 |
return false; |
| 310 |
|
| 311 |
const auto End = CData->getEnd(); |
| 312 |
if (End) { |
| 313 |
if (isEqual(State, Pos.getOffset(), End)) { |
| 314 |
return true; |
| 315 |
} |
| 316 |
} |
| 317 |
|
| 318 |
return false; |
| 319 |
} |
| 320 |
|
| 321 |
bool isAheadOfRange(ProgramStateRef State, const IteratorPosition &Pos) { |
| 322 |
const auto *Cont = Pos.getContainer(); |
| 323 |
const auto *CData = getContainerData(State, Cont); |
| 324 |
if (!CData) |
| 325 |
return false; |
| 326 |
|
| 327 |
const auto Beg = CData->getBegin(); |
| 328 |
if (Beg) { |
| 329 |
if (isLess(State, Pos.getOffset(), Beg)) { |
| 330 |
return true; |
| 331 |
} |
| 332 |
} |
| 333 |
|
| 334 |
return false; |
| 335 |
} |
| 336 |
|
| 337 |
bool isBehindPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos) { |
| 338 |
const auto *Cont = Pos.getContainer(); |
| 339 |
const auto *CData = getContainerData(State, Cont); |
| 340 |
if (!CData) |
| 341 |
return false; |
| 342 |
|
| 343 |
const auto End = CData->getEnd(); |
| 344 |
if (End) { |
| 345 |
if (isGreater(State, Pos.getOffset(), End)) { |
| 346 |
return true; |
| 347 |
} |
| 348 |
} |
| 349 |
|
| 350 |
return false; |
| 351 |
} |
| 352 |
|
| 353 |
bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) { |
| 354 |
return compare(State, Sym1, Sym2, BO_LT); |
| 355 |
} |
| 356 |
|
| 357 |
bool isGreater(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) { |
| 358 |
return compare(State, Sym1, Sym2, BO_GT); |
| 359 |
} |
| 360 |
|
| 361 |
bool isEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) { |
| 362 |
return compare(State, Sym1, Sym2, BO_EQ); |
| 363 |
} |
| 364 |
|
| 365 |
} // namespace |
| 366 |
|
| 367 |
void ento::registerIteratorRangeChecker(CheckerManager &mgr) { |
| 368 |
mgr.registerChecker<IteratorRangeChecker>(); |
| 369 |
} |
| 370 |
|
| 371 |
bool ento::shouldRegisterIteratorRangeChecker(const CheckerManager &mgr) { |
| 372 |
return true; |
| 373 |
} |