[Analyzer] IteratorRangeChecker verify `std::advance()`, `std::prev()` and `std::next()`

[baloghadamsoftware]

Summary

Upon calling one of the functions std::advance(), std::prev() and std::next() iterators could get out of their valid range which leads to undefined behavior. If all these funcions are inlined together with the functions they call internally (e.g. __advance() called by std::advance() in some implementations) the error is detected by IteratorRangeChecker but the bug location is inside the STL implementation. Even worse, if the budget runs out and one of the calls is not inlined the bug remains undetected. This patch fixes this behavior: all the bugs are detected at the point of the STL function invocation.

[baloghadamsoftware]

This patch replaces the verification part of D62895.

[Szelethus]

The patch looks great, though I'd kindly ask you to wait a bit for someone with a bit more experience on SVal-smithing ;)

Generally speaking, I think the word you are looking for is "validate", not "verify", is that right, @whisperity?

clang/lib/StaticAnalyzer/Checkers/IteratorRangeChecker.cpp

49–50

Prefer using.

[baloghadamsoftware]

Updated according to the comments and automatic formatting suggestions.

[baloghadamsoftware]

In D76379#1929698, @Szelethus wrote:

The patch looks great, though I'd kindly ask you to wait a bit for someone with a bit more experience on SVal-smithing ;)

Do you mean the change from const SVal & to SVal? It was done according to this comment.

Generally speaking, I think the word you are looking for is "validate", not "verify", is that right, @whisperity?

We always used the word "verify" in the iterator checkers for checking for bugs. The word "check" is reserved for the hooks, "handle" is used in the modeling. This is an internal concept for the container-iterator ecosystem, I do not know about common Clang Static Analyzer coding standard here.

[NoQ]

In D76379#1930917, @baloghadamsoftware wrote:

In D76379#1929698, @Szelethus wrote:

The patch looks great, though I'd kindly ask you to wait a bit for someone with a bit more experience on SVal-smithing ;)

Do you mean the change from const SVal & to SVal? It was done according to this comment.

I think @Szelethus means my inline comment.

clang/lib/StaticAnalyzer/Checkers/IteratorRangeChecker.cpp

133

Please think about the type of the integer. You most likely want SValBuilder::makeArrayIndex(). There's also SValBuilder::makeIntVal() with a bunch of handy overloads. You almost never need to access BasicValueFactory directly.

clang/lib/StaticAnalyzer/Checkers/IteratorRangeChecker.cpp

 
 namespace {
 
 class IteratorRangeChecker
   : public Checker<check::PreCall> {
 
   std::unique_ptr<BugType> OutOfRangeBugType;
 
-  void verifyDereference(CheckerContext &C, const SVal &Val) const;
-  void verifyIncrement(CheckerContext &C, const SVal &Iter) const;
-  void verifyDecrement(CheckerContext &C, const SVal &Iter) const;
+  void verifyDereference(CheckerContext &C, SVal Val) const;
+  void verifyIncrement(CheckerContext &C, SVal Iter) const;
+  void verifyDecrement(CheckerContext &C, SVal Iter) const;
   void verifyRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op,
-                              const SVal &LHS, const SVal &RHS) const;
-  void reportBug(const StringRef &Message, const SVal &Val,
-                 CheckerContext &C, ExplodedNode *ErrNode) const;
+                              SVal LHS, SVal RHS) const;
+  void verifyAdvance(CheckerContext &C, SVal LHS, SVal RHS) const;
+  void verifyPrev(CheckerContext &C, SVal LHS, SVal RHS) const;
+  void verifyNext(CheckerContext &C, SVal LHS, SVal RHS) const;
+  void reportBug(const StringRef &Message, SVal Val, CheckerContext &C,
+                 ExplodedNode *ErrNode) const;
 public:
   IteratorRangeChecker();
 
   void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
 
+  typedef void (IteratorRangeChecker::*AdvanceFn)(CheckerContext &, SVal,
+                                                  SVal) const;
+
+  CallDescriptionMap<AdvanceFn> AdvanceFunctions = {
+    {{{"std", "advance"}, 2},
+     &IteratorRangeChecker::verifyAdvance},
+    {{{"std", "prev"}, 2},
+     &IteratorRangeChecker::verifyPrev},
+    {{{"std", "next"}, 2},
+     &IteratorRangeChecker::verifyNext},
+  };
 };
 
 bool isPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos);
 bool isAheadOfRange(ProgramStateRef State, const IteratorPosition &Pos);
 bool isBehindPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos);
 bool isZero(ProgramStateRef State, const NonLoc &Val);
 
 } //namespace
if (Func->isOverloadedOperator()) {
     } else if (isDereferenceOperator(Func->getOverloadedOperator())) {
       // Check for dereference of out-of-range iterators
       if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
         verifyDereference(C, InstCall->getCXXThisVal());
       } else {
         verifyDereference(C, Call.getArgSVal(0));
       }
     }
+  } else {
+    const AdvanceFn *Verifier = AdvanceFunctions.lookup(Call);
+    if (Verifier) {
+      if (Call.getNumArgs() > 1) {
+        (this->**Verifier)(C, Call.getArgSVal(0), Call.getArgSVal(1));
+      } else {
+        auto &BVF = C.getSValBuilder().getBasicValueFactory();
+        (this->**Verifier)(C, Call.getArgSVal(0),
+                       nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
+      }
+    }
   }
 }
 
 void IteratorRangeChecker::verifyDereference(CheckerContext &C,
-                                             const SVal &Val) const {
+                                             SVal Val) const {
   auto State = C.getState();
   const auto *Pos = getIteratorPosition(State, Val);
   if (Pos && isPastTheEnd(State, *Pos)) {
     auto *N = C.generateErrorNode(State);
     if (!N)
       return;
     reportBug("Past-the-end iterator dereferenced.", Val, C, N);
     return;
   }
 }
 
-void IteratorRangeChecker::verifyIncrement(CheckerContext &C,
-                                          const SVal &Iter) const {
+void IteratorRangeChecker::verifyIncrement(CheckerContext &C, SVal Iter) const {
   auto &BVF = C.getSValBuilder().getBasicValueFactory();
   verifyRandomIncrOrDecr(C, OO_Plus, Iter,
                      nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
 }
 
-void IteratorRangeChecker::verifyDecrement(CheckerContext &C,
-                                          const SVal &Iter) const {
+void IteratorRangeChecker::verifyDecrement(CheckerContext &C, SVal Iter) const {
   auto &BVF = C.getSValBuilder().getBasicValueFactory();
   verifyRandomIncrOrDecr(C, OO_Minus, Iter,
                      nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
 }
 
 void IteratorRangeChecker::verifyRandomIncrOrDecr(CheckerContext &C,
                                                  OverloadedOperatorKind Op,
-                                                 const SVal &LHS,
-                                                 const SVal &RHS) const {
+                                                 SVal LHS, SVal RHS) const {
   auto State = C.getState();
 
   auto Value = RHS;
   if (auto ValAsLoc = RHS.getAs<Loc>()) {
     Value = State->getRawSVal(*ValAsLoc);
   }
 
   if (Value.isUnknown())
if (isBehindPastTheEnd(State, *PosAfter)) {
     auto *N = C.generateErrorNode(State);
     if (!N)
       return;
     reportBug("Iterator incremented behind the past-the-end "
                         "iterator.", LHS, C, N);
   }
 }
 
-void IteratorRangeChecker::reportBug(const StringRef &Message,
-                                    const SVal &Val, CheckerContext &C,
+void IteratorRangeChecker::verifyAdvance(CheckerContext &C, SVal LHS,
+                                         SVal RHS) const {
+  verifyRandomIncrOrDecr(C, OO_PlusEqual, LHS, RHS);
+}
+
+void IteratorRangeChecker::verifyPrev(CheckerContext &C, SVal LHS,
+                                      SVal RHS) const {
+  verifyRandomIncrOrDecr(C, OO_Minus, LHS, RHS);
+}
+
+void IteratorRangeChecker::verifyNext(CheckerContext &C, SVal LHS,
+                                         SVal RHS) const {
+  verifyRandomIncrOrDecr(C, OO_Plus, LHS, RHS);
+}
+
+void IteratorRangeChecker::reportBug(const StringRef &Message, SVal Val,
+                                     CheckerContext &C,
                                      ExplodedNode *ErrNode) const {
   auto R = std::make_unique<PathSensitiveBugReport>(*OutOfRangeBugType, Message,
                                                     ErrNode);
   R->markInteresting(Val);
   C.emitReport(std::move(R));
 }
 
 namespace {
 

clang/test/Analysis/Inputs/system-header-simulator-cxx.h

namespace std {
   BidirectionalIterator
   prev (BidirectionalIterator it,
         typename iterator_traits<BidirectionalIterator>::difference_type n =
         1) {
     advance(it, -n);
     return it;
   }
 
+  template <class ForwardIterator>
+  ForwardIterator
+  next (ForwardIterator it,
+        typename iterator_traits<ForwardIterator>::difference_type n = 1) {
+    advance(it, n);
+    return it;
+  }
+
   template <class InputIt, class T>
   InputIt find(InputIt first, InputIt last, const T& value);
 
   template <class ExecutionPolicy, class ForwardIt, class T>
   ForwardIt find(ExecutionPolicy&& policy, ForwardIt first, ForwardIt last,
                  const T& value);
 
   template <class InputIt, class UnaryPredicate>

clang/test/Analysis/iterator-range.cpp

 }
 
 void subscript_positive_end(const std::vector<int> &V) {
   auto i = V.end();
   auto j = i[1]; // expected-warning{{Past-the-end iterator dereferenced}} FIXME: expect warning Iterator incremented behind the past-the-end iterator
 }
 
 //
+// std::advance()
+//
+
+// std::advance() by +1
+
+void advance_plus_1_begin(const std::vector<int> &V) {
+  auto i = V.begin();
+  std::advance(i, 1); // no-warning
+}
+
+void advance_plus_1_behind_begin(const std::vector<int> &V) {
+  auto i = ++V.begin();
+  std::advance(i, 1); // no-warning
+}
+
+void advance_plus_1_unknown(const std::vector<int> &V) {
+  auto i = return_any_iterator(V.begin());
+  std::advance(i, 1); // no-warning
+}
+
+void advance_plus_1_ahead_of_end(const std::vector<int> &V) {
+  auto i = --V.end();
+  std::advance(i, 1); // no-warning
+}
+
+void advance_plus_1_end(const std::vector<int> &V) {
+  auto i = V.end();
+  std::advance(i, 1); // expected-warning{{Iterator incremented behind the past-the-end iterator}}
+}
+
+// std::advance() by -1
+
+void advance_minus_1_begin(const std::vector<int> &V) {
+  auto i = V.begin();
+  std::advance(i, -1); // expected-warning{{Iterator decremented ahead of its valid range}}
+}
+
+void advance_minus_1_behind_begin(const std::vector<int> &V) {
+  auto i = ++V.begin();
+  std::advance(i, -1); // no-warning
+}
+
+void advance_minus_1_unknown(const std::vector<int> &V) {
+  auto i = return_any_iterator(V.begin());
+  std::advance(i, -1); // no-warning
+}
+
+void advance_minus_1_ahead_of_end(const std::vector<int> &V) {
+  auto i = --V.end();
+  std::advance(i, -1); // no-warning
+}
+
+void advance_minus_1_end(const std::vector<int> &V) {
+  auto i = V.end();
+  std::advance(i, -1); // no-warning
+}
+
+// std::advance() by +2
+
+void advance_plus_2_begin(const std::vector<int> &V) {
+  auto i = V.begin();
+  std::advance(i, 2); // no-warning
+}
+
+void advance_plus_2_behind_begin(const std::vector<int> &V) {
+  auto i = ++V.begin();
+  std::advance(i, 2); // no-warning
+}
+
+void advance_plus_2_unknown(const std::vector<int> &V) {
+  auto i = return_any_iterator(V.begin());
+  std::advance(i, 2); // no-warning
+}
+
+void advance_plus_2_ahead_of_end(const std::vector<int> &V) {
+  auto i = --V.end();
+  std::advance(i, 2); // expected-warning{{Iterator incremented behind the past-the-end iterator}}
+}
+
+void advance_plus_2_end(const std::vector<int> &V) {
+  auto i = V.end();
+  std::advance(i, 2); // expected-warning{{Iterator incremented behind the past-the-end iterator}}
+}
+
+// std::advance() by -2
+
+void advance_minus_2_begin(const std::vector<int> &V) {
+  auto i = V.begin();
+  std::advance(i, -2); // expected-warning{{Iterator decremented ahead of its valid range}}
+}
+
+void advance_minus_2_behind_begin(const std::vector<int> &V) {
+  auto i = ++V.begin();
+  std::advance(i, -2); // expected-warning{{Iterator decremented ahead of its valid range}}
+}
+
+void advance_minus_2_unknown(const std::vector<int> &V) {
+  auto i = return_any_iterator(V.begin());
+  std::advance(i, -2); // no-warning
+}
+
+void advance_minus_2_ahead_of_end(const std::vector<int> &V) {
+  auto i = --V.end();
+  std::advance(i, -2); // no-warning
+}
+
+void advance_minus_2_end(const std::vector<int> &V) {
+  auto i = V.end();
+  std::advance(i, -2); // no-warning
+}
+
+// std::advance() by 0
+
+void advance_0_begin(const std::vector<int> &V) {
+  auto i = V.begin();
+  std::advance(i, 0); // no-warning
+}
+
+void advance_0_behind_begin(const std::vector<int> &V) {
+  auto i = ++V.begin();
+  std::advance(i, 0); // no-warning
+}
+
+void advance_0_unknown(const std::vector<int> &V) {
+  auto i = return_any_iterator(V.begin());
+  std::advance(i, 0); // no-warning
+}
+
+void advance_0_ahead_of_end(const std::vector<int> &V) {
+  auto i = --V.end();
+  std::advance(i, 0); // no-warning
+}
+
+void advance_0_end(const std::vector<int> &V) {
+  auto i = V.end();
+  std::advance(i, 0); // no-warning
+}
+
+//
+// std::next()
+//
+
+// std::next() by +1 (default)
+
+void next_plus_1_begin(const std::vector<int> &V) {
+  auto i = V.begin();
+  auto j = std::next(i); // no-warning
+}
+
+void next_plus_1_behind_begin(const std::vector<int> &V) {
+  auto i = ++V.begin();
+  auto j = std::next(i); // no-warning
+}
+
+void next_plus_1_unknown(const std::vector<int> &V) {
+  auto i = return_any_iterator(V.begin());
+  auto j = std::next(i); // no-warning
+}
+
+void next_plus_1_ahead_of_end(const std::vector<int> &V) {
+  auto i = --V.end();
+  auto j = std::next(i); // no-warning
+}
+
+void next_plus_1_end(const std::vector<int> &V) {
+  auto i = V.end();
+  auto j = std::next(i); // expected-warning{{Iterator incremented behind the past-the-end iterator}}
+}
+
+// std::next() by -1
+
+void next_minus_1_begin(const std::vector<int> &V) {
+  auto i = V.begin();
+  auto j = std::next(i, -1); // expected-warning{{Iterator decremented ahead of its valid range}}
+}
+
+void next_minus_1_behind_begin(const std::vector<int> &V) {
+  auto i = ++V.begin();
+  auto j = std::next(i, -1); // no-warning
+}
+
+void next_minus_1_unknown(const std::vector<int> &V) {
+  auto i = return_any_iterator(V.begin());
+  auto j = std::next(i, -1); // no-warning
+}
+
+void next_minus_1_ahead_of_end(const std::vector<int> &V) {
+  auto i = --V.end();
+  auto j = std::next(i, -1); // no-warning
+}
+
+void next_minus_1_end(const std::vector<int> &V) {
+  auto i = V.end();
+  auto j = std::next(i, -1); // no-warning
+}
+
+// std::next() by +2
+
+void next_plus_2_begin(const std::vector<int> &V) {
+  auto i = V.begin();
+  auto j = std::next(i, 2); // no-warning
+}
+
+void next_plus_2_behind_begin(const std::vector<int> &V) {
+  auto i = ++V.begin();
+  auto j = std::next(i, 2); // no-warning
+}
+
+void next_plus_2_unknown(const std::vector<int> &V) {
+  auto i = return_any_iterator(V.begin());
+  auto j = std::next(i, 2); // no-warning
+}
+
+void next_plus_2_ahead_of_end(const std::vector<int> &V) {
+  auto i = --V.end();
+  auto j = std::next(i, 2); // expected-warning{{Iterator incremented behind the past-the-end iterator}}
+}
+
+void next_plus_2_end(const std::vector<int> &V) {
+  auto i = V.end();
+  auto j = std::next(i, 2); // expected-warning{{Iterator incremented behind the past-the-end iterator}}
+}
+
+// std::next() by -2
+
+void next_minus_2_begin(const std::vector<int> &V) {
+  auto i = V.begin();
+  auto j = std::next(i, -2); // expected-warning{{Iterator decremented ahead of its valid range}}
+}
+
+void next_minus_2_behind_begin(const std::vector<int> &V) {
+  auto i = ++V.begin();
+  auto j = std::next(i, -2); // expected-warning{{Iterator decremented ahead of its valid range}}
+}
+
+void next_minus_2_unknown(const std::vector<int> &V) {
+  auto i = return_any_iterator(V.begin());
+  auto j = std::next(i, -2); // no-warning
+}
+
+void next_minus_2_ahead_of_end(const std::vector<int> &V) {
+  auto i = --V.end();
+  auto j = std::next(i, -2); // no-warning
+}
+
+void next_minus_2_end(const std::vector<int> &V) {
+  auto i = V.end();
+  auto j = std::next(i, -2); // no-warning
+}
+
+// std::next() by 0
+
+void next_0_begin(const std::vector<int> &V) {
+  auto i = V.begin();
+  auto j = std::next(i, 0); // no-warning
+}
+
+void next_0_behind_begin(const std::vector<int> &V) {
+  auto i = ++V.begin();
+  auto j = std::next(i, 0); // no-warning
+}
+
+void next_0_unknown(const std::vector<int> &V) {
+  auto i = return_any_iterator(V.begin());
+  auto j = std::next(i, 0); // no-warning
+}
+
+void next_0_ahead_of_end(const std::vector<int> &V) {
+  auto i = --V.end();
+  auto j = std::next(i, 0); // no-warning
+}
+
+void next_0_end(const std::vector<int> &V) {
+  auto i = V.end();
+  auto j = std::next(i, 0); // no-warning
+}
+
+//
+// std::prev()
+//
+
+// std::prev() by +1 (default)
+
+void prev_plus_1_begin(const std::vector<int> &V) {
+  auto i = V.begin();
+  auto j = std::prev(i); // expected-warning{{Iterator decremented ahead of its valid range}}
+}
+
+void prev_plus_1_behind_begin(const std::vector<int> &V) {
+  auto i = ++V.begin();
+  auto j = std::prev(i); // no-warning
+}
+
+void prev_plus_1_unknown(const std::vector<int> &V) {
+  auto i = return_any_iterator(V.begin());
+  auto j = std::prev(i); // no-warning
+}
+
+void prev_plus_1_ahead_of_end(const std::vector<int> &V) {
+  auto i = --V.end();
+  auto j = std::prev(i); // no-warning
+}
+
+void prev_plus_1_end(const std::vector<int> &V) {
+  auto i = V.end();
+  auto j = std::prev(i); // no-warning
+}
+
+// std::prev() by -1
+
+void prev_minus_1_begin(const std::vector<int> &V) {
+  auto i = V.begin();
+  auto j = std::prev(i, -1); // no-warning
+}
+
+void prev_minus_1_behind_begin(const std::vector<int> &V) {
+  auto i = ++V.begin();
+  auto j = std::prev(i, -1); // no-warning
+}
+
+void prev_minus_1_unknown(const std::vector<int> &V) {
+  auto i = return_any_iterator(V.begin());
+  auto j = std::prev(i, -1); // no-warning
+}
+
+void prev_minus_1_ahead_of_end(const std::vector<int> &V) {
+  auto i = --V.end();
+  auto j = std::prev(i, -1); // no-warning
+}
+
+void prev_minus_1_end(const std::vector<int> &V) {
+  auto i = V.end();
+  auto j = std::prev(i, -1); // expected-warning{{Iterator incremented behind the past-the-end iterator}}
+}
+
+// std::prev() by +2
+
+void prev_plus_2_begin(const std::vector<int> &V) {
+  auto i = V.begin();
+  auto j = std::prev(i, 2); // expected-warning{{Iterator decremented ahead of its valid range}}
+}
+
+void prev_plus_2_behind_begin(const std::vector<int> &V) {
+  auto i = ++V.begin();
+  auto j = std::prev(i, 2); // expected-warning{{Iterator decremented ahead of its valid range}}
+}
+
+void prev_plus_2_unknown(const std::vector<int> &V) {
+  auto i = return_any_iterator(V.begin());
+  auto j = std::prev(i, 2); // no-warning
+}
+
+void prev_plus_2_ahead_of_end(const std::vector<int> &V) {
+  auto i = --V.end();
+  auto j = std::prev(i, 2); // no-warning
+}
+
+void prev_plus_2_end(const std::vector<int> &V) {
+  auto i = V.end();
+  auto j = std::prev(i, 2); // no-warning
+}
+
+// std::prev() by -2
+
+void prev_minus_2_begin(const std::vector<int> &V) {
+  auto i = V.begin();
+  auto j = std::prev(i, -2); // no-warning
+}
+
+void prev_minus_2_behind_begin(const std::vector<int> &V) {
+  auto i = ++V.begin();
+  auto j = std::prev(i, -2); // no-warning
+}
+
+void prev_minus_2_unknown(const std::vector<int> &V) {
+  auto i = return_any_iterator(V.begin());
+  auto j = std::prev(i, -2); // no-warning
+}
+
+void prev_minus_2_ahead_of_end(const std::vector<int> &V) {
+  auto i = --V.end();
+  auto j = std::prev(i, -2); // expected-warning{{Iterator incremented behind the past-the-end iterator}}
+}
+
+void prev_minus_2_end(const std::vector<int> &V) {
+  auto i = V.end();
+  auto j = std::prev(i, -2); // expected-warning{{Iterator incremented behind the past-the-end iterator}}
+}
+
+// std::prev() by 0
+
+void prev_0_begin(const std::vector<int> &V) {
+  auto i = V.begin();
+  auto j = std::prev(i, 0); // no-warning
+}
+
+void prev_0_behind_begin(const std::vector<int> &V) {
+  auto i = ++V.begin();
+  auto j = std::prev(i, 0); // no-warning
+}
+
+void prev_0_unknown(const std::vector<int> &V) {
+  auto i = return_any_iterator(V.begin());
+  auto j = std::prev(i, 0); // no-warning
+}
+
+void prev_0_ahead_of_end(const std::vector<int> &V) {
+  auto i = --V.end();
+  auto j = std::prev(i, 0); // no-warning
+}
+
+void prev_0_end(const std::vector<int> &V) {
+  auto i = V.end();
+  auto j = std::prev(i, 0); // no-warning
+}
+
+//
 // Structure member dereference operators
 //
 
 struct S {
   int n;
 };
 
 // Member dereference - operator->()