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