[Analyzer] Crash fix for FindLastStoreBRVisitor

[baloghadamsoftware]

Summary

This patch is a fix for bug 40625.

FindLastStoreBRVisitor tries to find the first node in the exploded graph where the current value was assigned to a region. This node is called the "store site". It is identified by a pair of Pred and Succ nodes where Succ already has the binding for the value while Pred does not have it. However the visitor mistakenly identifies a node pair as the store site where the value is a LazyCompoundVal and Pred does not have a store yet but Succ has it. In this case the LazyCompoundVal is different in the Pred node because it also contains the store which is different in the two nodes. This error may lead to crashes (a declaration is cast to a parameter declaration without check) or misleading bug path notes.

In this patch we fix this problem by checking for unequal LazyCompoundVals: if their region is equal, and their store is the same as the store of their nodes we consider them as equal when looking for the store site.

[baloghadamsoftware]

I tried very hard to create a test case where we are crashing on a true positive but I did not succeed. I am not sure whether it is possible so fixing the false positive in CallAndMessageUnInitRefArg also fixes the crash without this patch. However I am confident the bug is still a bug in the visitor and maybe in the future it will be used for complex values as well which could be LazyCompoundVals. Also you can see in the test case uninit-vals.m that even if it does not crash it prints nonsense bug path notes caused by this same bug which is fixed by this patch.

lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

159

Maybe we should find a better name. Even better we could place this function into LazyCompoundVal but with 'Store` or ProgramStateRef parameters instead of ExplodedNode*.

test/Analysis/uninit-vals.m

401

What was this nonsense?

418

This one too...

[NoQ]

Aha, right, indeed, thanks, nice!

We should eventually remove operator==() from the SVal class because it doesn't do anything you'd possibly imagine it to do. However we do need to come up with adequate alternatives. And by looking at this patch, it seems that we actually need two alternatives:

1. An attempt to figure out that two SVals are equal. The result of such comparison is state-specific - eg., ($a == $b) may be true in states that follow the true-branch of "if (a == b)" and false otherwise. This is how evalBinOp(BO_EQ) should behave. And this sounds impossible to implement without a perfect constraint solver, so the user should always be prepared to receive an unknown answer in some cases.
2. An attempt to figure out if two SVals are representing the same value, that is, you cannot replace one value with another without an assignment. This is what we need in this patch. Eg., in

int a;
int b;

void foo() {
  if (a == b) {
    b = a;
  } 
}

we don't mind* noticing that an assignment has happened by noticing that $b was replaced with $a. I guess the author suspected that SVal::operator==() does exactly that; however, as you point out, for lazy compound values this is not the case because they're "not normalized", i.e. contain more information than necessary. And in fact it's not really possible to compare two lazy compound values (even for "sameness") without a perfect constraint solver (consider a symbolic-offset binding that would or would not overlap with the parent region of the LCV, depending on constraint offsets).

As far as i understand, your approach now misses assignments to fields within the lazy compound value (because you're not checking that the corresponding stores are actually equal when restricted to the given parent region), which may probably still lead to confusing diagnostics, but that's definitely better than before.

__
*Though ideally i'd definitely prefer noticing that an assignment has happened simply by realizing that there's an assignment operator at this program point. But that's a bigger question of why is our whole visitor infrastructure so inside-out. I mean, why does it have to reverse-engineer ExprEngine's logic instead of simply communicating with it somehow?...

lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

156–158

I think it's more important for a comment to explain *why* exactly does the code do whatever it does, than *what* specifically does it do. I.e., could you say something about how comparing internal representations of symbolic values (via SVal::operator==()) is a valid way to check if the value was updated (even if the new value is in fact equal to the old value), unless it's a LazyCompoundValue that may have a different internal representation every time it is loaded from the state? ...Which is why you do an approximate comparison for lazy compound values, checking that they are the immediate snapshots of the tracked region's bindings within the node's respective states but not really checking that these snapshots actually contain the same set of bindings.

Also, is it possible that these values both have the same region that is different from the region R we're tracking? I suspect that it isn't possible with immediate loads from the RegionStore as it currently is, but i wouldn't expect this to happen in the general case or be future-proof. Maybe we should assert that - either within this function or immediately after this function.

159

Hmm, dunno. "hasVisibleUpdate()"?

[baloghadamsoftware]

Function renamed, comment updated.

lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

const Expr *bugreporter::getDerefExpr(const Stmt *S) {
   // our pointer rvalue was loaded.
   if (const auto *CE = dyn_cast<ImplicitCastExpr>(E))
     if (CE->getCastKind() == CK_LValueToRValue)
       E = CE->getSubExpr();
 
   return E;
 }
 
+/// Comparing internal representations of symbolic values (via
+/// SVal::operator==()) is a valid way to check if the value was updated,
+/// unless it's a LazyCompoundVal that may have a different internal
+/// representation every time it is loaded from the state. In this function we
+/// do an approximate comparison for lazy compound values, checking that they
+/// are the immediate snapshots of the tracked region's bindings within the
+/// node's respective states but not really checking that these snapshots
+/// actually contain the same set of bindings.
+bool hasVisibleUpdate(const ExplodedNode *LeftNode, SVal LeftVal,
+                      const ExplodedNode *RightNode, SVal RightVal) {
+  if (LeftVal == RightVal)
+    return true;
+
+  const auto LLCV = LeftVal.getAs<nonloc::LazyCompoundVal>();
+  if (!LLCV)
+    return false;
+
+  const auto RLCV = RightVal.getAs<nonloc::LazyCompoundVal>();
+  if (!RLCV)
+    return false;
+
+  return LLCV->getRegion() == RLCV->getRegion() &&
+    LLCV->getStore() == LeftNode->getState()->getStore() &&
+    RLCV->getStore() == RightNode->getState()->getStore();
+}
+
 //===----------------------------------------------------------------------===//
 // Definitions for bug reporter visitors.
 //===----------------------------------------------------------------------===//
 
 std::shared_ptr<PathDiagnosticPiece>
 BugReporterVisitor::getEndPath(BugReporterContext &,
                                const ExplodedNode *, BugReport &) {
   return nullptr;
FindLastStoreBRVisitor::VisitNode(const ExplodedNode *Succ,
   // (1) Succ has this binding and Pred does not, i.e. this is
   //     where the binding first occurred.
   // (2) Succ has this binding and is a PostStore node for this region, i.e.
   //     the same binding was re-assigned here.
   if (!StoreSite) {
     if (Succ->getState()->getSVal(R) != V)
       return nullptr;
 
-    if (Pred->getState()->getSVal(R) == V) {
+    if (hasVisibleUpdate(Pred, Pred->getState()->getSVal(R), Succ, V)) {
       Optional<PostStore> PS = Succ->getLocationAs<PostStore>();
       if (!PS || PS->getLocationValue() != R)
         return nullptr;
     }
 
     StoreSite = Succ;
 
     // If this is an assignment expression, we can track the value
     // being assigned.
     if (Optional<PostStmt> P = Succ->getLocationAs<PostStmt>())
       if (const BinaryOperator *BO = P->getStmtAs<BinaryOperator>())
         if (BO->isAssignmentOp())
           InitE = BO->getRHS();
 
     // If this is a call entry, the variable should be a parameter.
     // FIXME: Handle CXXThisRegion as well. (This is not a priority because
     // 'this' should never be NULL, but this visitor isn't just for NULL and
     // UndefinedVal.)
     if (Optional<CallEnter> CE = Succ->getLocationAs<CallEnter>()) {
       if (const auto *VR = dyn_cast<VarRegion>(R)) {
+
         const auto *Param = cast<ParmVarDecl>(VR->getDecl());
 
         ProgramStateManager &StateMgr = BRC.getStateManager();
         CallEventManager &CallMgr = StateMgr.getCallEventManager();
 
         CallEventRef<> Call = CallMgr.getCaller(CE->getCalleeContext(),
                                                 Succ->getState());
         InitE = Call->getArgExpr(Param->getFunctionScopeIndex());

test/Analysis/PR40625.cpp

+// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,alpha.core.CallAndMessageUnInitRefArg  %s -verify
+
+void f(const int *end);
+
+void g(const int (&arrr)[10]) {
+  f(arrr+sizeof(arrr)); // expected-warning{{1st function call argument is a pointer to uninitialized value}}
+  // FIXME: This is a false positive that should be fixed. Until then this
+  //        tests the crash fix in FindLastStoreBRVisitor (beside
+  //        uninit-vals.m).
+}
+
+void h() {
+  int arr[10];
+
+  g(arr);
+}

test/Analysis/const_array.cpp

-// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,alpha.core.CallAndMessageUnInitRefArg  %s -verify
-
-// expect-no-diagnostics
-
-const int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
-
-void f(const int *begin, const int *end) {
-  int sum = 0;
-  for (const int *p = begin; p != end; ++p) {
-    sum += *p;
-  }
-}
-
-typedef const int intarray[10];
-
-void g(const intarray &arrr) {
-  f(arrr, arrr+sizeof(arrr));
-}
-
-void h() {
-  g(arr);
-}

test/Analysis/uninit-vals.m

void testSmallStructBitfieldsSecondUndef() {
   clang_analyzer_eval(b.y == 2); // expected-warning{{garbage}}
                                  // expected-note@-1{{garbage}}
 }
 
 void testSmallStructBitfieldsFirstUnnamed() {
   struct {
     int : 4;
     int y : 4;
-  } a, b, c;
+  } a, b, c; // expected-note{{'c' initialized here}}
 
   a.y = 2;
 
-  b = a; // expected-note{{Value assigned to 'c'}}
+  b = a;
   clang_analyzer_eval(b.y == 2); // expected-warning{{TRUE}}
                                  // expected-note@-1{{TRUE}}
 
   b = c; // expected-note{{Uninitialized value stored to 'b.y'}}
   clang_analyzer_eval(b.y == 2); // expected-warning{{garbage}}
                                  // expected-note@-1{{garbage}}
 }
 
 void testSmallStructBitfieldsSecondUnnamed() {
   struct {
     int x : 4;
     int : 4;
-  } a, b, c;
+  } a, b, c; // expected-note{{'c' initialized here}}
 
   a.x = 1;
 
-  b = a; // expected-note{{Value assigned to 'c'}}
+  b = a;
   clang_analyzer_eval(b.x == 1); // expected-warning{{TRUE}}
                                  // expected-note@-1{{TRUE}}
 
   b = c; // expected-note{{Uninitialized value stored to 'b.x'}}
   clang_analyzer_eval(b.x == 1); // expected-warning{{garbage}}
                                  // expected-note@-1{{garbage}}
 }