[Analyzer] Debug Checkers for Container and Iterator Inspection

[baloghadamsoftware]

Summary

For white-box testing correct container and iterator modelling it is essential to access the internal data structures stored for container and iterators. This patch introduces two simple debug checkers called debug.ContainerInspection and debug.IteratorInspection to achieve this.

[baloghadamsoftware]

I did not add debug calls to the tests of the existing iterator checkers yet, they will come in the next patch. After that I think the next step is to refactor the monolithic checker class into smaller ones: the iterator modelling into one file, and all the other checkers in small separate files. The modelling checker may also be split into two: container modelling and iterator modelling. Of course the is a connection between them, but they can be separated logically. All the common function must go into a library "module" (header and body file). However, the prerequisite for such a huge refactoring is a thorough whitebox testing.

[Szelethus]

Niiiiice! Thank you so much for sorting this out! I think this will make reviewing far more accessible for newcomers to the IteratorChecker family. I have a couple nits to comment on, but I won't clutter the code just yet. @NoQ, do you have any high level objections to this?

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

1703

Ah, right, so this would fire for clang_analyzer_iterator_position()?

[NoQ]

Yup, thanks, this is really nice!

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

243–244

We usually define such getters for stuff that the programmer cannot obtain otherwise during normal program execution. These two functions look like they're probably equivalent to normal .begin() and .end() calls. I don't really object but do we really ever need them other than for testing the trivial implementations of .begin() and .end()?

1673–1674

CallDescriptionMap please? ^.^

test/Analysis/iterator-inspection.cpp

41–42 ↗

(On Diff #218657)

Slightly more robust: clang_analyzer_eval(clang_analyzer_iterator_container(b0) == &v0); // expected-warning{{TRUE}}?

[NoQ]

include/clang/StaticAnalyzer/Checkers/Checkers.td

1346–1355

Dunno, i would keep it all in one checker, just to save a few // RUN: lines :)

[Szelethus]

I'm sadly not knowledgeable enough with CallDescriptionMap, so let's have another round of review on this, otherwise, its perfect.

We talked about dividing this checker into multiple files, which would also make reviewing a bit easier. With that done, combined with this patch, I am very confident that we could enable parts of this checker by default by, well, you know, soon enough :^)

include/clang/StaticAnalyzer/Checkers/Checkers.td

1346–1355

I agree. Let's combine these into DebugIteratorModeling, because, as I understand it, that is what we're doing!

test/Analysis/iterator-inspection.cpp

1–2 ↗

(On Diff #218657)

Could you please format these? c:

38–43 ↗

(On Diff #218657)

Yea, I agree, let's add a testcase with a little more substance.

[NoQ]

In D67156#1661881, @Szelethus wrote:

I'm sadly not knowledgeable enough with CallDescriptionMap

D62557 contains a basic example.

[baloghadamsoftware]

Updated according to the comments.

[baloghadamsoftware]

include/clang/StaticAnalyzer/Checkers/Checkers.td

1346–1355

I did it on the short term, but on the long term iterator and container modelling are planned to be two different things, where iterator modelling depends on container modelling, but the latter works alone as well to support container checkers, such as e.g. copying data into a container with insufficient size. Furthermore I do not really like the name debug.DebugIteratorModeling.

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

243–244

Not exactly. These functions return the internal representation of their .begin() and .end(). These symbols are conjured by the iterator checker and are bound to the return value of .begin() and .end() in the container data map. It is an extra check to check whether they return the same internal symbol as clang_analyzer_iterator_position() for the return value of .begin() and .end().

1703

Yes, and also for the other two.

[Szelethus]

This is amazing, thanks!! LGTM.

include/clang/StaticAnalyzer/Checkers/Checkers.td

 def ExplodedGraphViewer : Checker<"ViewExplodedGraph">,
   HelpText<"View Exploded Graphs using GraphViz">,
   Documentation<NotDocumented>;
 
 def ReportStmts : Checker<"ReportStmts">,
   HelpText<"Emits a warning for every statement.">,
   Documentation<NotDocumented>;
 
+def DebugIteratorModeling : Checker<"DebugIteratorModeling">,
+  HelpText<"Check the analyzer's understanding of C++ iterators">,
+  Dependencies<[IteratorModeling]>,
+  Documentation<NotDocumented>;
+
 } // end "debug"
 
 
 //===----------------------------------------------------------------------===//
 // Clone Detection
 //===----------------------------------------------------------------------===//
 
 let ParentPackage = CloneDetectionAlpha in {
 
 def CloneChecker : Checker<"CloneChecker">,
   HelpText<"Reports similar pieces of code.">,
   CheckerOptions<[
     CmdLineOption<Integer,

lib/StaticAnalyzer/Checkers/IteratorChecker.cpp

void Profile(llvm::FoldingSetNodeID &ID) const {
     ID.Add(Begin);
     ID.Add(End);
   }
 };
 
 class IteratorChecker
     : public Checker<check::PreCall, check::PostCall,
                      check::PostStmt<MaterializeTemporaryExpr>, check::Bind,
-                     check::LiveSymbols, check::DeadSymbols> {
+                     check::LiveSymbols, check::DeadSymbols, eval::Call> {
 
   std::unique_ptr<BugType> OutOfRangeBugType;
   std::unique_ptr<BugType> MismatchedBugType;
   std::unique_ptr<BugType> InvalidatedBugType;
+  std::unique_ptr<BugType> DebugMsgBugType;
 
   void handleComparison(CheckerContext &C, const Expr *CE, const SVal &RetVal,
                         const SVal &LVal, const SVal &RVal,
                         OverloadedOperatorKind Op) const;
   void processComparison(CheckerContext &C, ProgramStateRef State,
                          SymbolRef Sym1, SymbolRef Sym2, const SVal &RetVal,
                          OverloadedOperatorKind Op) const;
   void verifyAccess(CheckerContext &C, const SVal &Val) const;
class IteratorChecker
   void reportMismatchedBug(const StringRef &Message, const SVal &Val1,
                            const SVal &Val2, CheckerContext &C,
                            ExplodedNode *ErrNode) const;
   void reportMismatchedBug(const StringRef &Message, const SVal &Val,
                            const MemRegion *Reg, CheckerContext &C,
                            ExplodedNode *ErrNode) const;
   void reportInvalidatedBug(const StringRef &Message, const SVal &Val,
                             CheckerContext &C, ExplodedNode *ErrNode) const;
+  template <typename Getter>
+  void analyzerContainerDataField(const CallExpr *CE, CheckerContext &C,
+                                  Getter get) const;
+  void analyzerContainerBegin(const CallExpr *CE, CheckerContext &C) const;
+  void analyzerContainerEnd(const CallExpr *CE, CheckerContext &C) const;
+  template <typename Getter>
+  void analyzerIteratorDataField(const CallExpr *CE, CheckerContext &C,
+                                 Getter get, SVal Default) const;
+  void analyzerIteratorPosition(const CallExpr *CE, CheckerContext &C) const;
+  void analyzerIteratorContainer(const CallExpr *CE, CheckerContext &C) const;
+  void analyzerIteratorValidity(const CallExpr *CE, CheckerContext &C) const;
+  ExplodedNode *reportDebugMsg(llvm::StringRef Msg, CheckerContext &C) const;
+
+  typedef void (IteratorChecker::*FnCheck)(const CallExpr *,
+                                           CheckerContext &) const;
+
+  CallDescriptionMap<FnCheck> Callbacks = {
+    {{0, "clang_analyzer_container_begin", 1},
+     &IteratorChecker::analyzerContainerBegin},
+    {{0, "clang_analyzer_container_end", 1},
+     &IteratorChecker::analyzerContainerEnd},
+    {{0, "clang_analyzer_iterator_position", 1},
+     &IteratorChecker::analyzerIteratorPosition},
+    {{0, "clang_analyzer_iterator_container", 1},
+     &IteratorChecker::analyzerIteratorContainer},
+    {{0, "clang_analyzer_iterator_validity", 1},
+     &IteratorChecker::analyzerIteratorValidity},
+  };
   
 public:
   IteratorChecker();
 
   enum CheckKind {
     CK_IteratorRangeChecker,
     CK_MismatchedIteratorChecker,
     CK_InvalidatedIteratorChecker,
+    CK_DebugIteratorModeling,
     CK_NumCheckKinds
   };
 
   DefaultBool ChecksEnabled[CK_NumCheckKinds];
   CheckerNameRef CheckNames[CK_NumCheckKinds];
 
   void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
   void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
   void checkBind(SVal Loc, SVal Val, const Stmt *S, CheckerContext &C) const;
   void checkPostStmt(const CXXConstructExpr *CCE, CheckerContext &C) const;
   void checkPostStmt(const DeclStmt *DS, CheckerContext &C) const;
   void checkPostStmt(const MaterializeTemporaryExpr *MTE,
                      CheckerContext &C) const;
   void checkLiveSymbols(ProgramStateRef State, SymbolReaper &SR) const;
   void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
+  bool evalCall(const CallEvent &Call, CheckerContext &C) const;
 };
 } // namespace
 
 REGISTER_MAP_WITH_PROGRAMSTATE(IteratorSymbolMap, SymbolRef, IteratorPosition)
 REGISTER_MAP_WITH_PROGRAMSTATE(IteratorRegionMap, const MemRegion *,
                                IteratorPosition)
 
 REGISTER_MAP_WITH_PROGRAMSTATE(ContainerMap, const MemRegion *, ContainerData)

 IteratorChecker::IteratorChecker() {
   OutOfRangeBugType.reset(
       new BugType(this, "Iterator out of range", "Misuse of STL APIs"));
   MismatchedBugType.reset(
       new BugType(this, "Iterator(s) mismatched", "Misuse of STL APIs",
                   /*SuppressOnSink=*/true));
   InvalidatedBugType.reset(
       new BugType(this, "Iterator invalidated", "Misuse of STL APIs"));
+  DebugMsgBugType.reset(
+      new BugType(this, "Checking analyzer assumptions", "debug",
+                  /*SuppressOnSink=*/true));
 }
 
 void IteratorChecker::checkPreCall(const CallEvent &Call,
                                    CheckerContext &C) const {
   // Check for out of range access or access of invalidated position and
   // iterator mismatches
   const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
   if (!Func)
void IteratorChecker::reportInvalidatedBug(const StringRef &Message,
                                            const SVal &Val, CheckerContext &C,
                                            ExplodedNode *ErrNode) const {
   auto R = std::make_unique<PathSensitiveBugReport>(*InvalidatedBugType,
                                                     Message, ErrNode);
   R->markInteresting(Val);
   C.emitReport(std::move(R));
 }
 
+bool IteratorChecker::evalCall(const CallEvent &Call,
+                                     CheckerContext &C) const {
+  if (!ChecksEnabled[CK_DebugIteratorModeling])
+    return false;
+
+  const auto *CE = dyn_cast_or_null<CallExpr>(Call.getOriginExpr());
+  if (!CE)
+    return false;
+
+  const FnCheck *Handler = Callbacks.lookup(Call);
+  if (!Handler)
+    return false;
+
+  (this->**Handler)(CE, C);
+  return true;
+}
+
+template <typename Getter>
+void IteratorChecker::analyzerContainerDataField(const CallExpr *CE,
+                                                 CheckerContext &C,
+                                                 Getter get) const {
+  if (CE->getNumArgs() == 0) {
+    reportDebugMsg("Missing container argument", C);
+    return;
+  }
+
+  auto State = C.getState();
+  const MemRegion *Cont = C.getSVal(CE->getArg(0)).getAsRegion();
+  if (Cont) {
+    const auto *Data = getContainerData(State, Cont);
+    if (Data) {
+      SymbolRef Field = get(Data);
+      if (Field) {
+        State = State->BindExpr(CE, C.getLocationContext(),
+                                nonloc::SymbolVal(Field));
+        C.addTransition(State);
+        return;
+      }
+    }
+  }
+
+  auto &BVF = C.getSValBuilder().getBasicValueFactory();
+  State = State->BindExpr(CE, C.getLocationContext(),
+                   nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(0))));
+}
+
+void IteratorChecker::analyzerContainerBegin(const CallExpr *CE,
+                                             CheckerContext &C) const {
+  analyzerContainerDataField(CE, C, [](const ContainerData *D) {
+      return D->getBegin();
+    });
+}
+
+void IteratorChecker::analyzerContainerEnd(const CallExpr *CE,
+                                             CheckerContext &C) const {
+  analyzerContainerDataField(CE, C, [](const ContainerData *D) {
+      return D->getEnd();
+    });
+}
+
+template <typename Getter>
+void IteratorChecker::analyzerIteratorDataField(const CallExpr *CE,
+                                                CheckerContext &C,
+                                                Getter get,
+                                                SVal Default) const {
+  if (CE->getNumArgs() == 0) {
+    reportDebugMsg("Missing iterator argument", C);
+    return;
+  }
+
+  auto State = C.getState();
+  SVal V = C.getSVal(CE->getArg(0));
+  const auto *Pos = getIteratorPosition(State, V);
+  if (Pos) {
+    State = State->BindExpr(CE, C.getLocationContext(), get(Pos));
+  } else {
+    State = State->BindExpr(CE, C.getLocationContext(), Default);
+  }
+  C.addTransition(State);
+}
+
+void IteratorChecker::analyzerIteratorPosition(const CallExpr *CE,
+                                               CheckerContext &C) const {
+  auto &BVF = C.getSValBuilder().getBasicValueFactory();
+  analyzerIteratorDataField(CE, C, [](const IteratorPosition *P) {
+      return nonloc::SymbolVal(P->getOffset());
+    }, nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(0))));
+}
+
+void IteratorChecker::analyzerIteratorContainer(const CallExpr *CE,
+                                               CheckerContext &C) const {
+  auto &BVF = C.getSValBuilder().getBasicValueFactory();
+  analyzerIteratorDataField(CE, C, [](const IteratorPosition *P) {
+      return loc::MemRegionVal(P->getContainer());
+    }, loc::ConcreteInt(BVF.getValue(llvm::APSInt::get(0))));
+}
+
+void IteratorChecker::analyzerIteratorValidity(const CallExpr *CE,
+                                               CheckerContext &C) const {
+  auto &BVF = C.getSValBuilder().getBasicValueFactory();
+  analyzerIteratorDataField(CE, C, [&BVF](const IteratorPosition *P) {
+      return
+        nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get((P->isValid()))));
+    }, nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(0))));
+}
+
+ExplodedNode *IteratorChecker::reportDebugMsg(llvm::StringRef Msg,
+                                              CheckerContext &C) const {
+  ExplodedNode *N = C.generateNonFatalErrorNode();
+  if (!N)
+    return nullptr;
+
+  auto &BR = C.getBugReporter();
+  BR.emitReport(std::make_unique<PathSensitiveBugReport>(*DebugMsgBugType,
+                                                         Msg, N));
+  return N;
+}
+
 namespace {
 
 bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
 bool isGreater(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
 bool isEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
 bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
              BinaryOperator::Opcode Opc);
 bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2,
checker->CheckNames[IteratorChecker::CK_##name] =                          \
         Mgr.getCurrentCheckerName();                                           \
   }                                                                            \
                                                                                \
   bool ento::shouldRegister##name(const LangOptions &LO) { return true; }
 
 REGISTER_CHECKER(IteratorRangeChecker)
 REGISTER_CHECKER(MismatchedIteratorChecker)
 REGISTER_CHECKER(InvalidatedIteratorChecker)
+REGISTER_CHECKER(DebugIteratorModeling)

test/Analysis/debug-iterator-modeling.cpp

+// RUN: %clang_analyze_cc1 -std=c++11\
+// RUN: -analyzer-checker=core,cplusplus\
+// RUN: -analyzer-checker=debug.DebugIteratorModeling,debug.ExprInspection\
+// RUN: -analyzer-config aggressive-binary-operation-simplification=true\
+// RUN: -analyzer-config c++-container-inlining=false %s -verify
+
+// RUN: %clang_analyze_cc1 -std=c++11\
+// RUN: -analyzer-checker=core,cplusplus\
+// RUN: -analyzer-checker=debug.DebugIteratorModeling,debug.ExprInspection\
+// RUN: -analyzer-config aggressive-binary-operation-simplification=true\
+// RUN: -analyzer-config c++-container-inlining=true -DINLINE=1 %s -verify
+
+#include "Inputs/system-header-simulator-cxx.h"
+
+template <typename Container>
+long clang_analyzer_container_begin(const Container&);
+template <typename Container>
+long clang_analyzer_container_end(const Container&);
+template <typename Iterator>
+long clang_analyzer_iterator_position(const Iterator&);
+template <typename Iterator>
+void* clang_analyzer_iterator_container(const Iterator&);
+template <typename Iterator>
+bool clang_analyzer_iterator_validity(const Iterator&);
+void clang_analyzer_denote(long, const char*);
+void clang_analyzer_express(long);
+void clang_analyzer_dump(const void*);
+void clang_analyzer_eval(bool);
+
+void iterator_position(const std::vector<int> v0) {
+  auto b0 = v0.begin(), e0 = v0.end();
+
+  clang_analyzer_denote(clang_analyzer_iterator_position(b0), "$b0");
+  clang_analyzer_denote(clang_analyzer_iterator_position(e0), "$e0");
+
+  clang_analyzer_express(clang_analyzer_iterator_position(b0)); // expected-warning{{$b0}}
+  clang_analyzer_express(clang_analyzer_iterator_position(e0)); // expected-warning{{$e0}}
+
+  clang_analyzer_express(clang_analyzer_container_begin(v0)); // expected-warning{{$b0}}
+  clang_analyzer_express(clang_analyzer_container_end(v0)); // expected-warning{{$e0}}
+
+  ++b0;
+
+  clang_analyzer_express(clang_analyzer_iterator_position(b0)); // expected-warning{{$b0 + 1}}
+}
+
+void iterator_container(const std::vector<int> v0) {
+  auto b0 = v0.begin();
+
+  clang_analyzer_dump(&v0); //expected-warning{{&v0}}
+  clang_analyzer_eval(clang_analyzer_iterator_container(b0) == &v0); // expected-warning{{TRUE}}
+}
+
+void iterator_validity(std::vector<int> v0) {
+  auto b0 = v0.begin();
+  clang_analyzer_eval(clang_analyzer_iterator_validity(b0)); //expected-warning{{TRUE}}
+
+  v0.clear();
+
+  clang_analyzer_eval(clang_analyzer_iterator_validity(b0)); //expected-warning{{FALSE}}
+}