[analyzer] symbol_iterator must iterate through the symbolic base.

[NoQ]

Summary

I've been investigating a false positive that had a pointer-type symbol with a non-zero range which had its range forgotten and later assumed to be zero. The big test that i added (test_region_referenced_only_through_field_in_store_value()) roughly re-creates the infeasible path that was taken. A bit simplified, it looks like this:

 1 int *p;
 2
 3 struct S {
 4   int field;
 5 };
 6
 7 struct S *conjure();
 8
 9 void foo() {
10   struct S *s = conjure();
11   p = &s->field;
12   if (!s) {
13     exit(0);
14   }
15   if (!p) {
16     clang_analyzer_warnIfReached(); // no-warning
17   }
18 }

It is easy to see that the path with clang_analyzer_warnIfReached() is infeasible. The bug that causes us to explore that infeasible path is in the RegionStore's dead symbol removal algorithm that didn't realize that the symbol is live. Recall that RegionStore scans itself with the help of a worklist algorithm - it enforces the invariant of "if a binding key is live, then the respective binding value is also live" (and a few other similar invariants) and marks symbols and regions as live until the live set reaches a fixed point (i.e. the worklist runs dry).

In our example the symbol in question is the return value of conjure_S1(). We'd still refer to it as $x.

1. $x is present in the Store as a binding value of form &SymRegion{$x}->field (which is equivalent to $x + offsetof(field), i.e. it's possible to easily recover $x from it).
2. Symbol $x is not mentioned anywhere else in the program state.
3. Additionally, there are no store bindings anywhere within region SymRegion{$x}.
4. When &SymRegion{$x}->field is found as a binding value in removeDeadBindingsWorker::VisitBinding(), symbolic base SymRegion{$x} of region SymRegion{$x}->field is put into the worklist (removeDeadBindingsWorker::AddToWorkList() descends to the base region automatically).
5. However, $x is not added to the live set yet, because the loop through sub-symbols (from symbol_begin() to symbol_end()) doesn't descend to from SymRegion{$x}->field to its symbolic base SymRegion{$x} in order to find $x.
6. In most cases $x will be found anyway when later processing the worklist. Indeed, removeDeadBindingsWorker::VisitCluster() would take SymRegion{$x} from the worklist and immediately find $x within it. This is actually one of the "other similar invariants": "if a binding key is live and is a symbolic region, its parent symbol is live".
7. In our case, however, this will not happen, because SymRegion{$x} has no bindings and therefore its cluster is empty and removeDeadBindingsWorker::VisitCluster() will bail out early.

Essentially, it worked most of the time because most regions have bindings. But normally it is not a responsibility of removeDeadBindingsWorker::VisitCluster() to find symbol $x within binding value SymRegion{$x}->field - it should definitely not try to care about the liveness of stuff in empty clusters, those should only be live if there are other reasons to believe they're alive. Being a binding value is one such "other reason", which means that on step 5 we should have added $x to the live set.

I believe that this is exactly how step 5 was intended to work. However, the undocumented behavior of symbol_begin() that consists in not descending to the base region was unexpected.

---

In order to confirm my understanding, i tried to see what other users of symbol_begin() expect. It turns out that three other users made the same mistake, and in two of these three cases it led to keeping the symbol around longer (instead of shorter) than necessary (i.e. zombie symbols), while the third case is similar to the original example albeit more exotic. In all other cases users of symbol_begin() did not care if it descends to the base region or not.

Namely:

• CStringChecker::checkLiveSymbols() iterates over sub-symbols of string length to mark string lengths as live. Because string length is for now only composed of CStringChecker-tagged metadata symbols and constants, and therefore it is a NonLoc that isn't a nonloc::LocAsInteger, it is irrelevant whether symbol_begin descends to the symbolic base.
• Environment::removeDeadBindings() marks symbols within a value of a dead expression as maybeDead(). I added a test case, test_region_referenced_only_through_field_in_environment_value(), to demonstrate that we indeed produce a zombie symbol due to symbol_begin() here not descending to the symbolic base.
• ScanReachableSymbols::scan(Sym) scans sub-symbols of a raw symbol, not of an SVal. Therefore it is not a region and there is no need to descend to the symbolic base.
• ProgramState::isTainted(Sym, Kind) scans a raw symbol as well.
• removeDeadBindingsWorker::VisitBinding() the test case we've just discussed.
• RegionStoreManager::removeDeadBindings() also has a bug similar to the one in Environment::removeDeadBindings(), which is demonstrated by test case test_zombie_referenced_only_through_field_in_store_value().
• SymExpr::computeComplexity() scans a raw symbol.
• SymbolReaper::markElementIndicesLive() scans an array symbol, which is always a NonLoc. However, it may still be a nonloc::LocAsInteger, and in this case descend to the symbolic base would be necessary, as demonstrated by test_loc_as_integer_element_index_lifetime(). This test, however, is not fixed by the current patch, due to getAsLocSymbol() incorrectly failing to pass its IncludeBaseRegions argument into the recursive call. But i decided not to investigate it further today, because, well, enough is enough.

[NoQ]

Leak false-negatives that result from bugs in Environment::removeDeadBindings() and RegionStoreManager::removeDeadBindings() are also only appearing due to the overall zombie symbol problem we have (D18860). The bugs are in the code that populates the dead set, however the dead set shouldn't have existed in the first place.

Also the if (s) {} part of the test_loc_as_integer_element_index_lifetime() test case is vital because otherwise the symbol would turn into a zombie and there'd be no leak false positive. But by saying if (s) {} we're declaring that it is the constraint manager who is responsible for putting the symbol into the dead set. The same is true for the original test case (test_region_referenced_only_through_field_in_store_value()) but there we'd have the branching anyway because the test is also designed to show the infeasible path.

[NoQ]

Slightly simplify one of the tests.

[NoQ]

Because string length is for now only composed of CStringChecker-tagged metadata symbols and constants...

Even if this was not the case, it is stil certain that string length is a NonLoc. And as such it is either a plain nonloc::SymbolVal that is unaffected or a nonloc::LocAsInteger that is affected but isn't going to work, for a reason described in the SymbolReaper::markElementIndicesLive() section. This is a much more obvious way to demonstrate that CStringChecker is not affected by this patch.

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

public:
   const SymExpr *getAsSymExpr() const;
 
   const MemRegion *getAsRegion() const;
 
   void dumpToStream(raw_ostream &OS) const;
   void dump() const;
 
   SymExpr::symbol_iterator symbol_begin() const {
-    const SymExpr *SE = getAsSymbolicExpression();
+    const SymExpr *SE = getAsSymbol(/*IncludeBaseRegions=*/true);
     if (SE)
       return SE->symbol_begin();
     else
       return SymExpr::symbol_iterator();
   }
 
   SymExpr::symbol_iterator symbol_end() const { 
     return SymExpr::symbol_end();

test/Analysis/symbol-reaper.c

 // RUN: %clang_analyze_cc1 -analyzer-checker=debug.ExprInspection -verify %s
 
 void clang_analyzer_eval(int);
 void clang_analyzer_warnOnDeadSymbol(int);
 void clang_analyzer_numTimesReached();
+void clang_analyzer_warnIfReached();
+
+void exit(int);
 
 int conjure_index();
 
 void test_that_expr_inspection_works() {
   do {
     int x = conjure_index();
     clang_analyzer_warnOnDeadSymbol(x);
   } while(0); // expected-warning{{SYMBOL DEAD}}

 }
 
 struct S1 {
   int field;
 };
 struct S2 {
   struct S1 array[5];
 } s2;
+struct S3 {
+  void *field;
+};
+
+struct S1 *conjure_S1();
+struct S3 *conjure_S3();
 
 void test_element_index_lifetime_with_complicated_hierarchy_of_regions() {
   do {
     int x = conjure_index();
     clang_analyzer_warnOnDeadSymbol(x);
     s2.array[x].field = 1;
     if (x) {}
   } while (0); // no-warning
 }
 
+void test_loc_as_integer_element_index_lifetime() {
+  do {
+    int x;
+    struct S3 *s = conjure_S3();
+    clang_analyzer_warnOnDeadSymbol((int)s);
+    x = (int)&(s->field);
+    ptr = &arr[x];
+    if (s) {}
+  // FIXME: Should not warn. The symbol is still alive within the ptr's index.
+  } while (0); // expected-warning{{SYMBOL DEAD}}
+}
+
 // Test below checks lifetime of SymbolRegionValue in certain conditions.
 
 int **ptrptr;
 void test_region_lifetime_as_store_value(int *x) {
   clang_analyzer_warnOnDeadSymbol((int) x);
   *x = 1;
   ptrptr = &x;
   (void)0; // No-op; make sure the environment forgets things and the GC runs.
   clang_analyzer_eval(**ptrptr); // expected-warning{{TRUE}}
 } // no-warning
+
+int *produce_region_referenced_only_through_field_in_environment_value() {
+  struct S1 *s = conjure_S1();
+  clang_analyzer_warnOnDeadSymbol((int) s);
+  int *x = &s->field;
+  return x;
+}
+
+void test_region_referenced_only_through_field_in_environment_value() {
+  produce_region_referenced_only_through_field_in_environment_value();
+} // expected-warning{{SYMBOL DEAD}}
+
+void test_region_referenced_only_through_field_in_store_value() {
+  struct S1 *s = conjure_S1();
+  clang_analyzer_warnOnDeadSymbol((int) s);
+  ptr = &s->field; // Write the symbol into a global. It should live forever.
+  if (!s) {
+    exit(0); // no-warning (symbol should not die here)
+    // exit() is noreturn.
+    clang_analyzer_warnIfReached(); // no-warning
+  }
+  if (!ptr) { // no-warning (symbol should not die here)
+    // We exit()ed under these constraints earlier.
+    clang_analyzer_warnIfReached(); // no-warning
+  }
+  // The exit() call invalidates globals. The symbol will die here because
+  // the exit() statement itself is already over and there's no better statement
+  // to put the diagnostic on.
+} // expected-warning{{SYMBOL DEAD}}
+
+void test_zombie_referenced_only_through_field_in_store_value() {
+  struct S1 *s = conjure_S1();
+  clang_analyzer_warnOnDeadSymbol((int) s);
+  int *x = &s->field;
+} // expected-warning{{SYMBOL DEAD}}