[Analyzer] Iterator Checkers - Use the region of the topmost base class for iterators stored in a region

[baloghadamsoftware]

Summary

If an iterator is represented by a derived C++ class but its comparison operator is for its base the iterator checkers cannot recognize the iterators compared. This results in false positives in very straightforward cases (range error when dereferencing an iterator after disclosing that it is equal to the past-end iterator).

To overcome this problem we always use the region of the topmost base class for iterators stored in a region. A new method called getMostDerivedObjectRegion() was added to the MemRegion class to get this region.

[baloghadamsoftware]

I marked this patch as WIP because I could not create a test-case for it. However in real projects this patch seems to reduce false positives significantly.

The member function getBaseRegion() of MemRegion does not work here because it recursively retrieves the base region of multiple kinds of SubRegion.

[Szelethus]

Hmmm, shouldn't we add this to MemRegion's interface instead?

[NoQ]

I marked this patch as WIP because I could not create a test-case for it. However in real projects this patch seems to reduce false positives significantly.

False positives are hard to reduce via delta-debugging because they can be accidentally reduced into true positives, because the distinction between true positives and false positives cannot be tested automatically. But once you fix the false positive, creduce can be used to reduce them by writing down the condition as "the positive is there on the original clang but not on the modified clang". Strongly recommended :)

Hmmm, shouldn't we add this to MemRegion's interface instead?

I wouldn't insist, but this does indeed sound useful. I suggest MemRegion::getMostDerivedObjectRegion() or something like that.

The member function getBaseRegion() of MemRegion does not work here because it recursively retrieves the base region of multiple kinds of SubRegion.

Also, ugh, that nomenclature: the base region of CXXBaseObjectRegion in fact represents the derived object.

[baloghadamsoftware]

In D54466#1297887, @NoQ wrote:

I marked this patch as WIP because I could not create a test-case for it. However in real projects this patch seems to reduce false positives significantly.

False positives are hard to reduce via delta-debugging because they can be accidentally reduced into true positives, because the distinction between true positives and false positives cannot be tested automatically. But once you fix the false positive, creduce can be used to reduce them by writing down the condition as "the positive is there on the original clang but not on the modified clang". Strongly recommended :)

creduce did not work (continous clang_delta crash) but somehow I managed to create tests.

Hmmm, shouldn't we add this to MemRegion's interface instead?

This:

I wouldn't insist, but this does indeed sound useful. I suggest MemRegion::getMostDerivedObjectRegion() or something like that.

vs

Also, ugh, that nomenclature: the base region of CXXBaseObjectRegion in fact represents the derived object.

So if CXXBaseObjectRegion is the derived object, then MemRegion::getMostDerivedObjectRegion() gets the least derived object region now?

[Szelethus]

In D54466#1305305, @baloghadamsoftware wrote:

In D54466#1297887, @NoQ wrote:

Hmmm, shouldn't we add this to MemRegion's interface instead?

This:

I wouldn't insist, but this does indeed sound useful. I suggest MemRegion::getMostDerivedObjectRegion() or something like that.

vs

Also, ugh, that nomenclature: the base region of CXXBaseObjectRegion in fact represents the derived object.

So if CXXBaseObjectRegion is the derived object, then MemRegion::getMostDerivedObjectRegion() gets the least derived object region now?

Hmm, are there any particular reasons against renaming it to CXXDerivedRegion?

[baloghadamsoftware]

There is [[ https://clang.llvm.org/doxygen/classclang_1_1ento_1_1CXXDerivedObjectRegion.html | CXXDerivedObjectRegion ]] as well. I am totally confused about the terminology now. Is there somewhere a documentation that explains all these things? If I make a class hierarchy, then the region of derived objects are CXXBaseObjectRegion. I did not meet CXXDerivedObjectRegion yet.

[baloghadamsoftware]

More standard-like tests.

[NoQ]

Huh, gotcha :) The nomenclature is mostly correct, just feels weird.

Super-region of a region is a larger region. Sub-region is a smaller region. Base region is the largest non-memspace superregion, so it's a larger region.

Derived class object is a large object. Base class object is a small object within the derived class object, so it should be represented by a smaller region.

Hence we have CXXBaseObjectRegion which is a small sub-region that corresponds to the object of the base class within the object of a derived class. Which means that yes, you obtain the base region by removing CXXBaseObjectRegion layers (i.e., making the region larger), and that is fine because "base region" in our terminology means a completely different thing.

Now, right, there's the CXXDerivedObjectRegion that i added recently. It represents the region of a derived object if its super-object isn't a CXXBaseObjectRegion (otherwise we can just unwrap the CXXBaseObjectRegion). So it kinda sounds like a sub-region that is larger than its superregion, which contradicts the tradition. But this is fine because if the program under analysis is valid (which we assume unless we can prove the opposite), the only valid use case for CXXDerivedObjectRegion is to place it on top of a SymbolicRegion which points to an object of unknown size. So we kinda don't really know what's larger here. Also, that's not the only example of the situation when a sub-region is not a sub-segment of its super-region. We can always add an ElementRegion with an arbitrary offset over almost any other region and it'll be equally wonky (i.e., a valid program shouldn't make us do that, but if it does, then, well, it's not surprising that weird things are happening).

include/clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h

121 ↗

(On Diff #175125)

Let's start writing doxygen thingies!

lib/StaticAnalyzer/Core/MemRegion.cpp

1182–1188 ↗

(On Diff #175125)

My attempt:

while (const auto *BR = dyn_cast<CXXBaseObjectRegion>(R))
  R = BR->getSuperRegion();

[baloghadamsoftware]

Now I think I understand the terminology and the concept so I could add Doxygen comment. I also refactored the code as you suggested, original code was based on getBaseRegion().

[NoQ]

Looks great, thanks!

cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h

public:
   virtual void Profile(llvm::FoldingSetNodeID& ID) const = 0;
 
   virtual MemRegionManager* getMemRegionManager() const = 0;
 
   const MemSpaceRegion *getMemorySpace() const;
 
   const MemRegion *getBaseRegion() const;
 
+  /// Recursively retrieve the region of the most derived class instance of
+  /// regions of C++ base class instances.
+  const MemRegion *getMostDerivedObjectRegion() const;
+
   /// Check if the region is a subregion of the given region.
   /// Each region is a subregion of itself.
   virtual bool isSubRegionOf(const MemRegion *R) const;
 
   const MemRegion *StripCasts(bool StripBaseAndDerivedCasts = true) const;
 
   /// If this is a symbolic region, returns the region. Otherwise,
   /// goes up the base chain looking for the first symbolic base region.

cfe/trunk/lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

if (!N)
       return;
     reportOutOfRangeBug("Iterator accessed past its end.", LHS, C, N);
   }
 }
 
 void IteratorChecker::verifyMatch(CheckerContext &C, const SVal &Iter,
                                   const MemRegion *Cont) const {
   // Verify match between a container and the container of an iterator
-  while (const auto *CBOR = Cont->getAs<CXXBaseObjectRegion>()) {
-    Cont = CBOR->getSuperRegion();
-  }
+  Cont = Cont->getMostDerivedObjectRegion();
 
   auto State = C.getState();
   const auto *Pos = getIteratorPosition(State, Iter);
   if (Pos && Pos->getContainer() != Cont) {
     auto *N = C.generateNonFatalErrorNode(State);
     if (!N) {
       return;
     }

 }
 
 void IteratorChecker::handleBegin(CheckerContext &C, const Expr *CE,
                                   const SVal &RetVal, const SVal &Cont) const {
   const auto *ContReg = Cont.getAsRegion();
   if (!ContReg)
     return;
 
-  while (const auto *CBOR = ContReg->getAs<CXXBaseObjectRegion>()) {
-    ContReg = CBOR->getSuperRegion();
-  }
+  ContReg = ContReg->getMostDerivedObjectRegion();
 
   // If the container already has a begin symbol then use it. Otherwise first
   // create a new one.
   auto State = C.getState();
   auto BeginSym = getContainerBegin(State, ContReg);
   if (!BeginSym) {
     auto &SymMgr = C.getSymbolManager();
     BeginSym = SymMgr.conjureSymbol(CE, C.getLocationContext(),
                                     C.getASTContext().LongTy, C.blockCount());
     State = assumeNoOverflow(State, BeginSym, 4);
     State = createContainerBegin(State, ContReg, BeginSym);
   }
   State = setIteratorPosition(State, RetVal,
                               IteratorPosition::getPosition(ContReg, BeginSym));
   C.addTransition(State);
 }
 
 void IteratorChecker::handleEnd(CheckerContext &C, const Expr *CE,
                                 const SVal &RetVal, const SVal &Cont) const {
   const auto *ContReg = Cont.getAsRegion();
   if (!ContReg)
     return;
 
-  while (const auto *CBOR = ContReg->getAs<CXXBaseObjectRegion>()) {
-    ContReg = CBOR->getSuperRegion();
-  }
+  ContReg = ContReg->getMostDerivedObjectRegion();
 
   // If the container already has an end symbol then use it. Otherwise first
   // create a new one.
   auto State = C.getState();
   auto EndSym = getContainerEnd(State, ContReg);
   if (!EndSym) {
     auto &SymMgr = C.getSymbolManager();
     EndSym = SymMgr.conjureSymbol(CE, C.getLocationContext(),
                                   C.getASTContext().LongTy, C.blockCount());
     State = assumeNoOverflow(State, EndSym, 4);
     State = createContainerEnd(State, ContReg, EndSym);
   }
   State = setIteratorPosition(State, RetVal,
                               IteratorPosition::getPosition(ContReg, EndSym));
   C.addTransition(State);
 }
 
 void IteratorChecker::assignToContainer(CheckerContext &C, const Expr *CE,
                                         const SVal &RetVal,
                                         const MemRegion *Cont) const {
-  while (const auto *CBOR = Cont->getAs<CXXBaseObjectRegion>()) {
-    Cont = CBOR->getSuperRegion();
-  }
+  Cont = Cont->getMostDerivedObjectRegion();
 
   auto State = C.getState();
   auto &SymMgr = C.getSymbolManager();
   auto Sym = SymMgr.conjureSymbol(CE, C.getLocationContext(),
                                   C.getASTContext().LongTy, C.blockCount());
   State = assumeNoOverflow(State, Sym, 4);
   State = setIteratorPosition(State, RetVal,
                               IteratorPosition::getPosition(Cont, Sym));
   C.addTransition(State);
 }
 
 void IteratorChecker::handleAssign(CheckerContext &C, const SVal &Cont,
                                    const Expr *CE, const SVal &OldCont) const {
   const auto *ContReg = Cont.getAsRegion();
   if (!ContReg)
     return;
 
-  while (const auto *CBOR = ContReg->getAs<CXXBaseObjectRegion>()) {
-    ContReg = CBOR->getSuperRegion();
-  }
+  ContReg = ContReg->getMostDerivedObjectRegion();
 
   // Assignment of a new value to a container always invalidates all its
   // iterators
   auto State = C.getState();
   const auto CData = getContainerData(State, ContReg);
   if (CData) {
     State = invalidateAllIteratorPositions(State, ContReg);
   }
 
   // In case of move, iterators of the old container (except the past-end
   // iterators) remain valid but refer to the new container
   if (!OldCont.isUndef()) {
     const auto *OldContReg = OldCont.getAsRegion();
     if (OldContReg) {
-      while (const auto *CBOR = OldContReg->getAs<CXXBaseObjectRegion>()) {
-        OldContReg = CBOR->getSuperRegion();
-      }
+      OldContReg = OldContReg->getMostDerivedObjectRegion();
       const auto OldCData = getContainerData(State, OldContReg);
       if (OldCData) {
         if (const auto OldEndSym = OldCData->getEnd()) {
           // If we already assigned an "end" symbol to the old conainer, then
           // first reassign all iterator positions to the new container which
           // are not past the container (thus not greater or equal to the
           // current "end" symbol).
           State = reassignAllIteratorPositionsUnless(State, OldContReg, ContReg,
void IteratorChecker::handleAssign(CheckerContext &C, const SVal &Cont,
   C.addTransition(State);
 }
 
 void IteratorChecker::handleClear(CheckerContext &C, const SVal &Cont) const {
   const auto *ContReg = Cont.getAsRegion();
   if (!ContReg)
     return;
 
-  while (const auto *CBOR = ContReg->getAs<CXXBaseObjectRegion>()) {
-    ContReg = CBOR->getSuperRegion();
-  }
+  ContReg = ContReg->getMostDerivedObjectRegion();
 
   // The clear() operation invalidates all the iterators, except the past-end
   // iterators of list-like containers
   auto State = C.getState();
   if (!hasSubscriptOperator(State, ContReg) ||
       !backModifiable(State, ContReg)) {
     const auto CData = getContainerData(State, ContReg);
     if (CData) {

 }
 
 void IteratorChecker::handlePushBack(CheckerContext &C,
                                      const SVal &Cont) const {
   const auto *ContReg = Cont.getAsRegion();
   if (!ContReg)
     return;
 
-  while (const auto *CBOR = ContReg->getAs<CXXBaseObjectRegion>()) {
-    ContReg = CBOR->getSuperRegion();
-  }
+  ContReg = ContReg->getMostDerivedObjectRegion();
 
   // For deque-like containers invalidate all iterator positions
   auto State = C.getState();
   if (hasSubscriptOperator(State, ContReg) && frontModifiable(State, ContReg)) {
     State = invalidateAllIteratorPositions(State, ContReg);
     C.addTransition(State);
     return;
   }
void IteratorChecker::handlePushBack(CheckerContext &C,
   C.addTransition(State);
 }
 
 void IteratorChecker::handlePopBack(CheckerContext &C, const SVal &Cont) const {
   const auto *ContReg = Cont.getAsRegion();
   if (!ContReg)
     return;
 
-  while (const auto *CBOR = ContReg->getAs<CXXBaseObjectRegion>()) {
-    ContReg = CBOR->getSuperRegion();
-  }
+  ContReg = ContReg->getMostDerivedObjectRegion();
 
   auto State = C.getState();
   const auto CData = getContainerData(State, ContReg);
   if (!CData)
     return;
 
   if (const auto EndSym = CData->getEnd()) {
     auto &SymMgr = C.getSymbolManager();

 }
 
 void IteratorChecker::handlePushFront(CheckerContext &C,
                                       const SVal &Cont) const {
   const auto *ContReg = Cont.getAsRegion();
   if (!ContReg)
     return;
 
-  while (const auto *CBOR = ContReg->getAs<CXXBaseObjectRegion>()) {
-    ContReg = CBOR->getSuperRegion();
-  }
+  ContReg = ContReg->getMostDerivedObjectRegion();
 
   // For deque-like containers invalidate all iterator positions
   auto State = C.getState();
   if (hasSubscriptOperator(State, ContReg)) {
     State = invalidateAllIteratorPositions(State, ContReg);
     C.addTransition(State);
   } else {
     const auto CData = getContainerData(State, ContReg);

 }
 
 void IteratorChecker::handlePopFront(CheckerContext &C,
                                      const SVal &Cont) const {
   const auto *ContReg = Cont.getAsRegion();
   if (!ContReg)
     return;
 
-  while (const auto *CBOR = ContReg->getAs<CXXBaseObjectRegion>()) {
-    ContReg = CBOR->getSuperRegion();
-  }
+  ContReg = ContReg->getMostDerivedObjectRegion();
 
   auto State = C.getState();
   const auto CData = getContainerData(State, ContReg);
   if (!CData)
     return;
 
   // For deque-like containers invalidate all iterator positions. For list-like
   // iterators only invalidate the first position

 
 ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont,
                                  const ContainerData &CData) {
   return State->set<ContainerMap>(Cont, CData);
 }
 
 const IteratorPosition *getIteratorPosition(ProgramStateRef State,
                                             const SVal &Val) {
-  if (const auto Reg = Val.getAsRegion()) {
+  if (auto Reg = Val.getAsRegion()) {
+    Reg = Reg->getMostDerivedObjectRegion();
     return State->get<IteratorRegionMap>(Reg);
   } else if (const auto Sym = Val.getAsSymbol()) {
     return State->get<IteratorSymbolMap>(Sym);
   } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
     return State->get<IteratorRegionMap>(LCVal->getRegion());
   }
   return nullptr;
 }
 
 const IteratorPosition *getIteratorPosition(ProgramStateRef State,
                                             RegionOrSymbol RegOrSym) {
   if (RegOrSym.is<const MemRegion *>()) {
-    return State->get<IteratorRegionMap>(RegOrSym.get<const MemRegion *>());
+    auto Reg = RegOrSym.get<const MemRegion *>()->getMostDerivedObjectRegion();
+    return State->get<IteratorRegionMap>(Reg);
   } else if (RegOrSym.is<SymbolRef>()) {
     return State->get<IteratorSymbolMap>(RegOrSym.get<SymbolRef>());
   }
   return nullptr;
 }
 
 ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val,
                                     const IteratorPosition &Pos) {
-  if (const auto Reg = Val.getAsRegion()) {
+  if (auto Reg = Val.getAsRegion()) {
+    Reg = Reg->getMostDerivedObjectRegion();
     return State->set<IteratorRegionMap>(Reg, Pos);
   } else if (const auto Sym = Val.getAsSymbol()) {
     return State->set<IteratorSymbolMap>(Sym, Pos);
   } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
     return State->set<IteratorRegionMap>(LCVal->getRegion(), Pos);
   }
   return nullptr;
 }
 
 ProgramStateRef setIteratorPosition(ProgramStateRef State,
                                     RegionOrSymbol RegOrSym,
                                     const IteratorPosition &Pos) {
   if (RegOrSym.is<const MemRegion *>()) {
-    return State->set<IteratorRegionMap>(RegOrSym.get<const MemRegion *>(),
-                                         Pos);
+    auto Reg = RegOrSym.get<const MemRegion *>()->getMostDerivedObjectRegion();
+    return State->set<IteratorRegionMap>(Reg, Pos);
   } else if (RegOrSym.is<SymbolRef>()) {
     return State->set<IteratorSymbolMap>(RegOrSym.get<SymbolRef>(), Pos);
   }
   return nullptr;
 }
 
 ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val) {
-  if (const auto Reg = Val.getAsRegion()) {
+  if (auto Reg = Val.getAsRegion()) {
+    Reg = Reg->getMostDerivedObjectRegion();
     return State->remove<IteratorRegionMap>(Reg);
   } else if (const auto Sym = Val.getAsSymbol()) {
     return State->remove<IteratorSymbolMap>(Sym);
   } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
     return State->remove<IteratorRegionMap>(LCVal->getRegion());
   }
   return nullptr;
 }

cfe/trunk/lib/StaticAnalyzer/Core/MemRegion.cpp

switch (R->getKind()) {
       default:
         break;
     }
     break;
   }
   return R;
 }
 
+// getgetMostDerivedObjectRegion gets the region of the root class of a C++
+// class hierarchy.
+const MemRegion *MemRegion::getMostDerivedObjectRegion() const {
+  const MemRegion *R = this;
+  while (const auto *BR = dyn_cast<CXXBaseObjectRegion>(R))
+    R = BR->getSuperRegion();
+  return R;
+}
+
 bool MemRegion::isSubRegionOf(const MemRegion *) const {
   return false;
 }
 
 //===----------------------------------------------------------------------===//
 // View handling.
 //===----------------------------------------------------------------------===//
 

cfe/trunk/test/Analysis/iterator-range.cpp

 
 void bad_move_push_back(std::list<int> &L1, std::list<int> &L2, int n) {
   auto i0 = --L2.cend();
   L2.push_back(n);
   L1 = std::move(L2);
   ++i0;
   *++i0; // expected-warning{{Iterator accessed outside of its range}}
 }
+
+struct simple_iterator_base {
+  simple_iterator_base();
+  simple_iterator_base(const simple_iterator_base& rhs);
+  simple_iterator_base &operator=(const simple_iterator_base& rhs);
+  virtual ~simple_iterator_base();
+  bool friend operator==(const simple_iterator_base &lhs,
+                         const simple_iterator_base &rhs);
+  bool friend operator!=(const simple_iterator_base &lhs,
+                         const simple_iterator_base &rhs);
+private:
+  int *ptr;
+};
+
+struct simple_derived_iterator: public simple_iterator_base {
+  int& operator*();
+  int* operator->();
+  simple_iterator_base &operator++();
+  simple_iterator_base operator++(int);
+  simple_iterator_base &operator--();
+  simple_iterator_base operator--(int);
+};
+
+struct simple_container {
+  typedef simple_derived_iterator iterator;
+
+  iterator begin();
+  iterator end();
+};
+
+void good_derived(simple_container c) {
+  auto i0 = c.end();
+  if (i0 != c.end()) {
+    clang_analyzer_warnIfReached();
+    *i0; // no-warning
+  }
+}