[analyzer] Consider array subscripts to be interesting lvalues

[vsavchenko]

Summary

Static analyzer has a mechanism of clearing redundant nodes when
analysis hits a certain threshold with a number of nodes in exploded
graph (default is 1000). It is similar to GC and aims removing nodes
not useful for analysis. Unfortunately nodes corresponding to array
subscript expressions (that actively participate in data propagation)
get removed during the cleanup. This might prevent the analyzer from
generating useful notes about where it thinks the data came from.

This fix is pretty much consistent with the way analysis works
already. Lvalue "interestingness" stands for the analyzer's
possibility of tracking values through them.

rdar://problem/53280338

[martong]

clang/test/Analysis/PR53280338.cpp

1 ↗

(On Diff #259283)

AFAIK rdar is not accessible outside Apple. So, for the rest of the open source developers any rdar info is totally useless. Thus, could you please copy the relevant parts of the bug description from there into the test file? Would be even better if we could just mention the rdar link in the test file and the filename itself was better explaining the nature of the bug.

[vsavchenko]

clang/test/Analysis/PR53280338.cpp

1 ↗

(On Diff #259283)

It is a fair point, I'll make it more clear what exactly we are testing here.

[vsavchenko]

Add more clarity on what we test

[Szelethus]

How come rGe20b388e2f923bfc98f63a13fea9fc19aeaec425 doesn't solve this? Or, rather, how come it even worked if this patch is needed? Is the index being a global variable the issue? The change looks great, but I'm a bit confused.

[vsavchenko]

In D78638#1997576, @Szelethus wrote:

How come rGe20b388e2f923bfc98f63a13fea9fc19aeaec425 doesn't solve this? Or, rather, how come it even worked if this patch is needed? Is the index being a global variable the issue? The change looks great, but I'm a bit confused.

Hey, thanks! So, I've tried to cover it in the comment and in the commit message.

In this test, both do while and the global index help to reproduce the erroneous behaviour. Usually, the analyzer tracks through array subscript expressions and it adds notes like expected in the test ("Assuming pointer value is null"). But in the test snippet, it was not adding those. The main reason is not in trackExpressionValue, it works fine! trackExpressionValue starts with finding an exploded node, where the lvalue is defined, and such node was not found. A little bit of digging later I found out that the node collector (aka garbage collector) threw those nodes away (check ExplodedGraph::shouldCollect and ExplodedGraph::reclaimRecentlyAllocatedNodes)! Because of the do while loop and the global index, the number of exploded nodes is pretty large. This fact causes GC to kick in and remove the nodes that we need for trackExpressionValue to work. Interesting nodes are on the other hand not deleted and this what helped with the problem.

I hope this clears it a bit!

[Szelethus]

Everything's clear! Nice detective work!

[NoQ]

Yup. Yet another epic bug!

clang/test/Analysis/CheckThatArraySubsciptNodeIsNotCollected.cpp

19–20

I'm still curious why index being global actually matters here. Like, how does it increase the number of nodes in the graph?

[vsavchenko]

clang/test/Analysis/CheckThatArraySubsciptNodeIsNotCollected.cpp

19–20

It does not simply increase the number of nodes, it increases it by thousands!

clang/lib/StaticAnalyzer/Core/ExplodedGraph.cpp

 
 //===----------------------------------------------------------------------===//
 // Node reclamation.
 //===----------------------------------------------------------------------===//
 
 bool ExplodedGraph::isInterestingLValueExpr(const Expr *Ex) {
   if (!Ex->isLValue())
     return false;
-  return isa<DeclRefExpr>(Ex) ||
-         isa<MemberExpr>(Ex) ||
-         isa<ObjCIvarRefExpr>(Ex);
+  return isa<DeclRefExpr>(Ex) || isa<MemberExpr>(Ex) ||
+         isa<ObjCIvarRefExpr>(Ex) || isa<ArraySubscriptExpr>(Ex);
 }
 
 bool ExplodedGraph::shouldCollect(const ExplodedNode *node) {
   // First, we only consider nodes for reclamation of the following
   // conditions apply:
   //
   // (1) 1 predecessor (that has one successor)
   // (2) 1 successor (that has one predecessor)

clang/test/Analysis/CheckThatArraySubsciptNodeIsNotCollected.cpp

+// RUN: %clang_analyze_cc1 -analyzer-checker=core -analyzer-output=text -verify %s
+
+class A {
+public:
+  int method();
+};
+
+A *foo();
+void bar(A *);
+
+int index;
+
+// We want to check here that the notes about the origins of the null pointer
+// (array[index] = foo()) will get to the final report.
+//
+// The analyzer used to drop exploded nodes for array subscripts when it was
+// time to collect redundant nodes. This GC-like mechanism kicks in only when
+// the exploded graph is large enough (>1K nodes). For this reason, 'index'
+// is a global variable, and the sink point is inside of a loop.
+
+void test() {
+  A *array[42];
+  A *found;
+
+  for (index = 0; (array[index] = foo()); ++index) { // expected-note {{Loop condition is false. Execution continues on line 34}}
+    // expected-note@-1 {{Value assigned to 'index'}}
+    // expected-note@-2 {{Assigning value}}
+    // expected-note@-3 {{Assuming pointer value is null}}
+    if (array[0])
+      break;
+  }
+
+  do {
+    found = array[index]; // expected-note {{Null pointer value stored to 'found'}}
+
+    if (found->method()) // expected-warning {{Called C++ object pointer is null [core.CallAndMessage]}}
+      // expected-note@-1 {{Called C++ object pointer is null}}
+      bar(found);
+  } while (--index);
+}