xref: /freebsd/contrib/llvm-project/clang/lib/StaticAnalyzer/Checkers/IteratorRangeChecker.cpp (revision b64c5a0ace59af62eff52bfe110a521dc73c937b) 
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   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 
49 public:
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 
71 bool isPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos);
72 bool isAheadOfRange(ProgramStateRef State, const IteratorPosition &Pos);
73 bool isBehindPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos);
74 bool isZero(ProgramStateRef State, NonLoc Val);
75 
76 } // namespace
77 
78 void IteratorRangeChecker::checkPreCall(const CallEvent &Call,
79                                         CheckerContext &C) const {
80   // Check for out of range access
81   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 incrementions
88       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 decrementions
97       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 decrementions
107         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 iterators
122       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 
143 void 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 
161 void 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 
178 void 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 
185 void 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 
195 void 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 
208 void 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 
214 void 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 
220 void 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 other
238   // out of range position is undefined behaviour
239   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 
262 void IteratorRangeChecker::verifyAdvance(CheckerContext &C, SVal LHS,
263                                          SVal RHS) const {
264   verifyRandomIncrOrDecr(C, OO_PlusEqual, LHS, RHS);
265 }
266 
267 void IteratorRangeChecker::verifyPrev(CheckerContext &C, SVal LHS,
268                                       SVal RHS) const {
269   verifyRandomIncrOrDecr(C, OO_Minus, LHS, RHS);
270 }
271 
272 void IteratorRangeChecker::verifyNext(CheckerContext &C, SVal LHS,
273                                       SVal RHS) const {
274   verifyRandomIncrOrDecr(C, OO_Plus, LHS, RHS);
275 }
276 
277 void 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 
291 namespace {
292 
293 bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
294 bool isGreater(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
295 bool isEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
296 
297 bool 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 
304 bool 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 
320 bool 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 
336 bool 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 
352 bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
353   return compare(State, Sym1, Sym2, BO_LT);
354 }
355 
356 bool isGreater(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
357   return compare(State, Sym1, Sym2, BO_GT);
358 }
359 
360 bool isEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
361   return compare(State, Sym1, Sym2, BO_EQ);
362 }
363 
364 } // namespace
365 
366 void ento::registerIteratorRangeChecker(CheckerManager &mgr) {
367   mgr.registerChecker<IteratorRangeChecker>();
368 }
369 
370 bool ento::shouldRegisterIteratorRangeChecker(const CheckerManager &mgr) {
371   return true;
372 }
373