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/CallEvent.h" 18 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" 19 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> { 31 32 std::unique_ptr<BugType> OutOfRangeBugType; 33 34 void verifyDereference(CheckerContext &C, const SVal &Val) const; 35 void verifyIncrement(CheckerContext &C, const SVal &Iter) const; 36 void verifyDecrement(CheckerContext &C, const SVal &Iter) const; 37 void verifyRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op, 38 const SVal &LHS, const SVal &RHS) const; 39 void reportBug(const StringRef &Message, const SVal &Val, 40 CheckerContext &C, ExplodedNode *ErrNode) const; 41 public: 42 IteratorRangeChecker(); 43 44 void checkPreCall(const CallEvent &Call, CheckerContext &C) const; 45 46 }; 47 48 bool isPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos); 49 bool isAheadOfRange(ProgramStateRef State, const IteratorPosition &Pos); 50 bool isBehindPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos); 51 bool isZero(ProgramStateRef State, const NonLoc &Val); 52 53 } //namespace 54 55 IteratorRangeChecker::IteratorRangeChecker() { 56 OutOfRangeBugType.reset( 57 new BugType(this, "Iterator out of range", "Misuse of STL APIs")); 58 } 59 60 void IteratorRangeChecker::checkPreCall(const CallEvent &Call, 61 CheckerContext &C) const { 62 // Check for out of range access 63 const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl()); 64 if (!Func) 65 return; 66 67 if (Func->isOverloadedOperator()) { 68 if (isIncrementOperator(Func->getOverloadedOperator())) { 69 // Check for out-of-range incrementions 70 if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) { 71 verifyIncrement(C, InstCall->getCXXThisVal()); 72 } else { 73 if (Call.getNumArgs() >= 1) { 74 verifyIncrement(C, Call.getArgSVal(0)); 75 } 76 } 77 } else if (isDecrementOperator(Func->getOverloadedOperator())) { 78 // Check for out-of-range decrementions 79 if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) { 80 verifyDecrement(C, InstCall->getCXXThisVal()); 81 } else { 82 if (Call.getNumArgs() >= 1) { 83 verifyDecrement(C, Call.getArgSVal(0)); 84 } 85 } 86 } else if (isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) { 87 if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) { 88 // Check for out-of-range incrementions and decrementions 89 if (Call.getNumArgs() >= 1 && 90 Call.getArgExpr(0)->getType()->isIntegralOrEnumerationType()) { 91 verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(), 92 InstCall->getCXXThisVal(), 93 Call.getArgSVal(0)); 94 } 95 } else { 96 if (Call.getNumArgs() >= 2 && 97 Call.getArgExpr(1)->getType()->isIntegralOrEnumerationType()) { 98 verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(), 99 Call.getArgSVal(0), Call.getArgSVal(1)); 100 } 101 } 102 } else if (isDereferenceOperator(Func->getOverloadedOperator())) { 103 // Check for dereference of out-of-range iterators 104 if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) { 105 verifyDereference(C, InstCall->getCXXThisVal()); 106 } else { 107 verifyDereference(C, Call.getArgSVal(0)); 108 } 109 } 110 } 111 } 112 113 void IteratorRangeChecker::verifyDereference(CheckerContext &C, 114 const SVal &Val) const { 115 auto State = C.getState(); 116 const auto *Pos = getIteratorPosition(State, Val); 117 if (Pos && isPastTheEnd(State, *Pos)) { 118 auto *N = C.generateErrorNode(State); 119 if (!N) 120 return; 121 reportBug("Past-the-end iterator dereferenced.", Val, C, N); 122 return; 123 } 124 } 125 126 void IteratorRangeChecker::verifyIncrement(CheckerContext &C, 127 const SVal &Iter) const { 128 auto &BVF = C.getSValBuilder().getBasicValueFactory(); 129 verifyRandomIncrOrDecr(C, OO_Plus, Iter, 130 nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1)))); 131 } 132 133 void IteratorRangeChecker::verifyDecrement(CheckerContext &C, 134 const SVal &Iter) const { 135 auto &BVF = C.getSValBuilder().getBasicValueFactory(); 136 verifyRandomIncrOrDecr(C, OO_Minus, Iter, 137 nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1)))); 138 } 139 140 void IteratorRangeChecker::verifyRandomIncrOrDecr(CheckerContext &C, 141 OverloadedOperatorKind Op, 142 const SVal &LHS, 143 const SVal &RHS) const { 144 auto State = C.getState(); 145 146 auto Value = RHS; 147 if (auto ValAsLoc = RHS.getAs<Loc>()) { 148 Value = State->getRawSVal(*ValAsLoc); 149 } 150 151 if (Value.isUnknown()) 152 return; 153 154 // Incremention or decremention by 0 is never a bug. 155 if (isZero(State, Value.castAs<NonLoc>())) 156 return; 157 158 // The result may be the past-end iterator of the container, but any other 159 // out of range position is undefined behaviour 160 auto StateAfter = advancePosition(State, LHS, Op, Value); 161 if (!StateAfter) 162 return; 163 164 const auto *PosAfter = getIteratorPosition(StateAfter, LHS); 165 assert(PosAfter && 166 "Iterator should have position after successful advancement"); 167 if (isAheadOfRange(State, *PosAfter)) { 168 auto *N = C.generateErrorNode(State); 169 if (!N) 170 return; 171 reportBug("Iterator decremented ahead of its valid range.", LHS, 172 C, N); 173 } 174 if (isBehindPastTheEnd(State, *PosAfter)) { 175 auto *N = C.generateErrorNode(State); 176 if (!N) 177 return; 178 reportBug("Iterator incremented behind the past-the-end " 179 "iterator.", LHS, C, N); 180 } 181 } 182 183 void IteratorRangeChecker::reportBug(const StringRef &Message, 184 const SVal &Val, CheckerContext &C, 185 ExplodedNode *ErrNode) const { 186 auto R = std::make_unique<PathSensitiveBugReport>(*OutOfRangeBugType, Message, 187 ErrNode); 188 R->markInteresting(Val); 189 C.emitReport(std::move(R)); 190 } 191 192 namespace { 193 194 bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2); 195 bool isGreater(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2); 196 bool isEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2); 197 198 bool isZero(ProgramStateRef State, const NonLoc &Val) { 199 auto &BVF = State->getBasicVals(); 200 return compare(State, Val, 201 nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(0))), 202 BO_EQ); 203 } 204 205 bool isPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos) { 206 const auto *Cont = Pos.getContainer(); 207 const auto *CData = getContainerData(State, Cont); 208 if (!CData) 209 return false; 210 211 const auto End = CData->getEnd(); 212 if (End) { 213 if (isEqual(State, Pos.getOffset(), End)) { 214 return true; 215 } 216 } 217 218 return false; 219 } 220 221 bool isAheadOfRange(ProgramStateRef State, const IteratorPosition &Pos) { 222 const auto *Cont = Pos.getContainer(); 223 const auto *CData = getContainerData(State, Cont); 224 if (!CData) 225 return false; 226 227 const auto Beg = CData->getBegin(); 228 if (Beg) { 229 if (isLess(State, Pos.getOffset(), Beg)) { 230 return true; 231 } 232 } 233 234 return false; 235 } 236 237 bool isBehindPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos) { 238 const auto *Cont = Pos.getContainer(); 239 const auto *CData = getContainerData(State, Cont); 240 if (!CData) 241 return false; 242 243 const auto End = CData->getEnd(); 244 if (End) { 245 if (isGreater(State, Pos.getOffset(), End)) { 246 return true; 247 } 248 } 249 250 return false; 251 } 252 253 bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) { 254 return compare(State, Sym1, Sym2, BO_LT); 255 } 256 257 bool isGreater(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) { 258 return compare(State, Sym1, Sym2, BO_GT); 259 } 260 261 bool isEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) { 262 return compare(State, Sym1, Sym2, BO_EQ); 263 } 264 265 } // namespace 266 267 void ento::registerIteratorRangeChecker(CheckerManager &mgr) { 268 mgr.registerChecker<IteratorRangeChecker>(); 269 } 270 271 bool ento::shouldRegisterIteratorRangeChecker(const LangOptions &LO) { 272 return true; 273 } 274