[analyzer] A fix for symbolic element region index lifetime.

[NoQ]

Summary

In Clang Static Analyzer, when the symbol is referenced by an index value of an element region, it does not prevent garbage collection (reaping) of that symbol. Hence, if the element index value is the only place where the symbol is stored, the symbol gets reaped, and range information is removed from the constraint manager.

This time, i'm not sure if it's the right place to put the fix; probably markLive() itself should handle it transparently, or something like that.

I managed to construct a regression test with the ReturnPtrRange checker. The second test shows that not only the store, but also the environment needs to be fixed.

[jordan_rose]

Hm, interesting. I'm not sure this is even sufficient, though: what if I have a FieldRegion that's a sub-region of an ElementRegion with a symbolic index? RegionStore does everything by base regions, so we won't ever see that intermediate region with the symbolic index.

[NoQ]

Thanks for the quick reply, sorry for the delay! Was afk for a couple of days.

Yeah, right, in fact i didn't even fix the issue for store keys at all; only for store values and environment values.

It also seems much harder to test store keys, because it's quite a problem to guess the symbolic key once the symbol is not present anywhere else, though i can imagine an artificial checker that would rely on that. A test like...

int a[1];
{
  int x = conjure_index();
  a[x] = 0;
  if (x != 0)
    return;
  clang_analyzer_eval(a[0] == 0); // expected-warning{{TRUE}}
}
clang_analyzer_eval(a[0] == 0); // expected-warning{{TRUE}}

...should have exposed such problem, but this kind of lookup doesn't seem to be supported by the store yet (that is, the first expected-warning{{TRUE}} fails as well).

Hmm, what if i expand the debug.ExprInspection checker to allow testing SymbolReaper directly? Updated the diff with a proof of concept, which fixes the issue for the store keys and adds a test. I can split the ExprInspection change into a separate commit/review if necessary. It might be useful for testing other SymbolReaper-related patches as well.

[zaks.anna]

Now that we have a way to test symbol reaper, please, add more coverage to the symbol-reaper.c test, including the test that Jordan mentioned. Even if it is not fixed, it's good to include it with a FIXME note.

What is the performance impact of this change?

The changes to the RegionStore and Environment seem inconsistent and repetitive.. For example, we can remove a lot of this just by changing SymbolReaper::markLive(const MemRegion *region), see below. How is this patch different from your solution? Can it be generalized to handle more cases?

diff --git a/lib/StaticAnalyzer/Core/RegionStore.cpp b/lib/StaticAnalyzer/Core/RegionStore.cpp
index 49b5ac3..55db545 100644
--- a/lib/StaticAnalyzer/Core/RegionStore.cpp
+++ b/lib/StaticAnalyzer/Core/RegionStore.cpp
@@ -2320,8 +2320,14 @@ void removeDeadBindingsWorker::VisitCluster(const MemRegion *baseR,
   if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(baseR))
     SymReaper.markLive(SymR->getSymbol());
 
-  for (ClusterBindings::iterator I = C->begin(), E = C->end(); I != E; ++I)
+  for (ClusterBindings::iterator I = C->begin(), E = C->end(); I != E; ++I) {
+    // Mark the key of each binding as live.
+    const BindingKey &K = I.getKey();
+    if (auto subR = dyn_cast<SubRegion>(K.getRegion()))
+      SymReaper.markLive(subR);
+
     VisitBinding(I.getData());
+  }
 }
 
 void removeDeadBindingsWorker::VisitBinding(SVal V) {
@@ -2342,6 +2348,7 @@ void removeDeadBindingsWorker::VisitBinding(SVal V) {
   // If V is a region, then add it to the worklist.
   if (const MemRegion *R = V.getAsRegion()) {
     AddToWorkList(R);
+    SymReaper.markLive(R);
 
     // All regions captured by a block are also live.
     if (const BlockDataRegion *BR = dyn_cast<BlockDataRegion>(R)) {
diff --git a/lib/StaticAnalyzer/Core/SymbolManager.cpp b/lib/StaticAnalyzer/Core/SymbolManager.cpp
index df4d22a..793f53e 100644
--- a/lib/StaticAnalyzer/Core/SymbolManager.cpp
+++ b/lib/StaticAnalyzer/Core/SymbolManager.cpp
@@ -391,6 +391,16 @@ void SymbolReaper::markLive(SymbolRef sym) {
 
 void SymbolReaper::markLive(const MemRegion *region) {
   RegionRoots.insert(region);
+  
+  // Mark the element index as live.
+  if (const ElementRegion *ER = dyn_cast<ElementRegion>(region)) {
+    SVal Idx = ER->getIndex();
+    for (SymExpr::symbol_iterator SI = Idx.symbol_begin(),
+         SE = Idx.symbol_end();
+         SI != SE; ++SI) {
+      markLive(*SI);
+    }
+  }
 }

lib/StaticAnalyzer/Checkers/ExprInspectionChecker.cpp

177

Thank you for adding this!!! This can be part of this commit or separate; up to you.

Please, update the debugger checkers document in the docs folder with information on how this should be used.

lib/StaticAnalyzer/Core/RegionStore.cpp

2241

Please, remove unnecessary spacing here and in a couple of other places.

2247

Why symbol_iterator is not used here?

2249

Could you add test cases that explain why we need the while loop here?

[NoQ]

Thanks for the review! Fixed all comments. I don't notice any significant performance hit with this patch (+/- 2% on the whole Android codebase runs).

I guess i won't break this into separate reviews, because less work =)

The loop through super-regions is necessary for supporting the test proposed by Jordan Rose, which is now added. Not sure what other tests are worth adding; together with specific tests on ReturnPtrRange, we're covering all three places that were patched; maybe i could move these tests to symbol-reaper.c as well, but i guess it's more worth it to test the actual analyzer output than artificially dumped internals(?) Not sure.

The change in Environment.cpp was removed because it's now handled automatically by markLive().

[zaks.anna]

I don't notice any significant performance hit with this
patch (+/- 2% on the whole Android codebase runs).

What did you test it on?

we're covering all three places that were patched; maybe i could move these tests
to symbol-reaper.c as well, but i guess it's more worth it to test the actual analyzer output than
artificially dumped internals(?) Not sure.

I'd add all necessary tests to the symbol-reaper.c and duplicate one of them in return-ptr-range.cpp to see that it has an effect on bug reporting.

The change in Environment.cpp was removed because it's now handled automatically by markLive().

This patch is different from what I sent. In my patch, I was marking the region as live and your latest patch is marking the indexes live without marking the region in some cases. What are the implications in each case?

docs/analyzer/DebugChecks.rst

143 ↗

(On Diff #36946)

What does subscribe mean? How do you decide when to subscribe/start tracking the symbol? Are you supposed to do that when you know the symbol is live?

[NoQ]

What are the implications in each case?

Uhm, sorry, right, I guess i have to admit i don't quite understand what exactly is going on, so it'd take more time for me to conduct a deeper audit of the reaping code to answer this question. In fact, right now i'm not even sure that

// If the block expr's value is a memory region, then mark that region.
if (Optional<loc::MemRegionVal> R = X.getAs<loc::MemRegionVal>())
  SymReaper.markLive(R->getRegion());

in EnvironmentManager::removeDeadBindings() does anything at all (at least, it's not covered by tests).

For now i just leave the patch here that fixes the tests with minimal intrusion (instead of patching markLive(), this diff patches only specific places), other issues you pointed out are fixed as well. Hopefully, will have time to dig into this in the nearest future :)

I don't notice any significant performance hit with this
patch (+/- 2% on the whole Android codebase runs).

What did you test it on?

On the source code of the whole Android Open Source Project (version 5); i record analyzer commands after the first scan-build, so that not to rebuild Android for every analysis (and only substitute clang executable and set of checkers), and the observed time of analysis is 1 hour 6 minutes (expensive hardware...) both before and after the patch is applied, so the difference in time seems to be less than one minute, i.e. less than 2%. And i guess it should be large and varied enough(?)

[zaks.anna]

so it'd take more time for me to conduct a deeper audit of the reaping code to answer this question

That would be great, thanks!

And i guess it should be large and varied enough(?)

Yes.

[NoQ]

Hmm, i think i'm ready to explain most of the stuff.

• First of all, the piece of code in EnvironmentManager::removeDeadBindings() i mentioned above is truly useless; everything would be marked as live anyway on the next line.

• Then, in RegionStore, in VisitBinding(), markLive() of the whole region value inside the binding is indeed correct, and i provide a pretty straightforward test;

• Finally, in VisitCluster(), it's a bit more complicated, and i suggest that markLive() is unnecessary here, and in fact does very little if anything, so it's hard to test even with stuff we have now:
  • i guess we shouldn't think of a region as live, simply because it has bindings, in a procedure designed for removing bindings;
  • however, marking the region as live here wouldn't save the bindings; they would later be removed simply because they weren't visited;
  • liveness of the region would also extend lifetime of a few symbols that depend on it, such as its SymbolRegionValue, SymbolExtent, and SymbolMetadata, however because the binding would be dead anyway, these symbols would die on the next pass;
    • note that SymbolRegionValue should explicitly be dead when the region has other bindings, so we certainly shouldn't try to preserve the region only to save SymbolRegionValue;
      • see also http://reviews.llvm.org/D5104 ; i also think i accidentally wrote the missing test for this ticket, will put it there;
  • another place that relies on region liveness information collected on these passes is Dynamic Type Propagation, however the same arguments apply; it would only delay the inevitable.

So the real question is whether (or rather how) the Store should maintain correct region liveness information after completing its internal garbage collection pass, because there are, in fact, other users of this information later in the chain, but this seems to be a larger problem without instantly noticeable effects.

The new diff removes dead code in Environment and tests and fixes the separate bug in the Store that caused reaping of constraints on SymbolRegionValue (and a few other kinds of SymbolData) too early when the only place where the related region is stored is a store value.

[NoQ]

Whoops accidentally left out a dead code line in tests.

[NoQ]

Awwww, another mis-submit. Sorry for the noise.

[zaks.anna]

LGTM.

(Feel free to add comments to the existing code!)

So the real question is whether (or rather how) the Store should maintain correct region liveness information
after completing its internal garbage collection pass, because there are, in fact, other users of
this information later in the chain, but this seems to be a larger problem without instantly noticeable effects.

Could you give specific (possibly potential) examples of this problem?

We assume that the symbols that are collected do not need to stick around, so no-one "later in the chain" should need them. Except for the cases where we artificially extend liveness by calling addSymbolDependency().

[NoQ]

In D12726#303122, @zaks.anna wrote:

So the real question is whether (or rather how) the Store should maintain correct region liveness information
after completing its internal garbage collection pass, because there are, in fact, other users of
this information later in the chain, but this seems to be a larger problem without instantly noticeable effects.

Could you give specific (possibly potential) examples of this problem?

We assume that the symbols that are collected do not need to stick around, so no-one "later in the chain" should need them. Except for the cases where we artificially extend liveness by calling addSymbolDependency().

What I was trying to say is that after StoreManager iterates over the Store, there are also checkers that may want to make decisions on liveness of their symbols based on liveness of certain regions, by checking SymbolReaper::isLiveRegion(), but currently such behavior is very rare, and thus barely tested. But eventually, with more checkers and further development, we'd need to figure out how this should work (eg. http://reviews.llvm.org/D14277 is a step in this direction - this patch can only work as long as isLiveRegion() is reliable after GC'ing the Store). Theoretically, it still makes sense to me to say that, for example, the Store shouldn't hold its keys as live - for the reasons stated above.

So this is mostly a hand-waving thing, and i think the patch is not immediately affected by this potential debate, and it should be OK to commit it.

lib/StaticAnalyzer/Checkers/ExprInspectionChecker.cpp

 #include "clang/StaticAnalyzer/Core/Checker.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
 #include "llvm/ADT/StringSwitch.h"
 
 using namespace clang;
 using namespace ento;
 
 namespace {
-class ExprInspectionChecker : public Checker< eval::Call > {
+class ExprInspectionChecker : public Checker<eval::Call, check::DeadSymbols> {
   mutable std::unique_ptr<BugType> BT;
 
   void analyzerEval(const CallExpr *CE, CheckerContext &C) const;
   void analyzerCheckInlined(const CallExpr *CE, CheckerContext &C) const;
   void analyzerWarnIfReached(const CallExpr *CE, CheckerContext &C) const;
   void analyzerCrash(const CallExpr *CE, CheckerContext &C) const;
+  void analyzerWarnOnDeadSymbol(const CallExpr *CE, CheckerContext &C) const;
 
   typedef void (ExprInspectionChecker::*FnCheck)(const CallExpr *,
                                                  CheckerContext &C) const;
 
 public:
   bool evalCall(const CallExpr *CE, CheckerContext &C) const;
+  void checkDeadSymbols(SymbolReaper &SymReaper, CheckerContext &C) const;
 };
 }
 
+REGISTER_SET_WITH_PROGRAMSTATE(MarkedSymbols, const void *)
+
 bool ExprInspectionChecker::evalCall(const CallExpr *CE,
                                      CheckerContext &C) const {
   // These checks should have no effect on the surrounding environment
   // (globals should not be invalidated, etc), hence the use of evalCall.
   FnCheck Handler = llvm::StringSwitch<FnCheck>(C.getCalleeName(CE))
     .Case("clang_analyzer_eval", &ExprInspectionChecker::analyzerEval)
     .Case("clang_analyzer_checkInlined",
           &ExprInspectionChecker::analyzerCheckInlined)
     .Case("clang_analyzer_crash", &ExprInspectionChecker::analyzerCrash)
-    .Case("clang_analyzer_warnIfReached", &ExprInspectionChecker::analyzerWarnIfReached)
+    .Case("clang_analyzer_warnIfReached",
+          &ExprInspectionChecker::analyzerWarnIfReached)
+    .Case("clang_analyzer_warnOnDeadSymbol",
+          &ExprInspectionChecker::analyzerWarnOnDeadSymbol)
     .Default(nullptr);
 
   if (!Handler)
     return false;
 
   (this->*Handler)(CE, C);
   return true;
 }
void ExprInspectionChecker::analyzerCheckInlined(const CallExpr *CE,
 
   ExplodedNode *N = C.generateNonFatalErrorNode();
   if (!N)
     return;
   C.emitReport(
       llvm::make_unique<BugReport>(*BT, getArgumentValueString(CE, C), N));
 }
 
+void ExprInspectionChecker::analyzerWarnOnDeadSymbol(const CallExpr *CE,
+                                                     CheckerContext &C) const {
+  if (CE->getNumArgs() == 0)
+    return;
+  SVal Val = C.getSVal(CE->getArg(0));
+  SymbolRef Sym = Val.getAsSymbol();
+  if (!Sym)
+    return;
+
+  ProgramStateRef State = C.getState();
+  State = State->add<MarkedSymbols>(Sym);
+  C.addTransition(State);
+}
+
+void ExprInspectionChecker::checkDeadSymbols(SymbolReaper &SymReaper,
+                                             CheckerContext &C) const {
+  ProgramStateRef State = C.getState();
+  const MarkedSymbolsTy &Syms = State->get<MarkedSymbols>();
+  for (auto I = Syms.begin(), E = Syms.end(); I != E; ++I) {
+    SymbolRef Sym = static_cast<SymbolRef>(*I);
+    if (!SymReaper.isDead(Sym))
+      continue;
+
+    if (!BT)
+      BT.reset(new BugType(this, "Checking analyzer assumptions", "debug"));
+
+    ExplodedNode *N = C.generateNonFatalErrorNode();
+    if (!N)
+      return;
+
+    C.emitReport(llvm::make_unique<BugReport>(*BT, "SYMBOL DEAD", N));
+  }
+}
+
 void ExprInspectionChecker::analyzerCrash(const CallExpr *CE,
                                           CheckerContext &C) const {
   LLVM_BUILTIN_TRAP;
 }
 
 void ento::registerExprInspectionChecker(CheckerManager &Mgr) {
   Mgr.registerChecker<ExprInspectionChecker>();
 }
 

lib/StaticAnalyzer/Core/Environment.cpp

for (Environment::iterator I = Env.begin(), E = Env.end();
     const EnvironmentEntry &BlkExpr = I.getKey();
     const SVal &X = I.getData();
 
     if (SymReaper.isLive(BlkExpr.getStmt(), BlkExpr.getLocationContext())) {
       // Copy the binding to the new map.
       EBMapRef = EBMapRef.add(BlkExpr, X);
 
       // If the block expr's value is a memory region, then mark that region.
-      if (Optional<loc::MemRegionVal> R = X.getAs<loc::MemRegionVal>())
-        SymReaper.markLive(R->getRegion());
+      if (Optional<loc::MemRegionVal> R = X.getAs<loc::MemRegionVal>()) {
+        const MemRegion *MR = R->getRegion();
+        SymReaper.markLive(MR);
+
+        // Mark the element index as live.
+        if (const ElementRegion *ER = dyn_cast<ElementRegion>(MR))
+          if (SymbolRef Sym = ER->getIndex().getAsSymbol())
+            SymReaper.markLive(Sym);
+      }
 
       // Mark all symbols in the block expr's value live.
       RSScaner.scan(X);
       continue;
     } else {
       SymExpr::symbol_iterator SI = X.symbol_begin(), SE = X.symbol_end();
       for (; SI != SE; ++SI)
         SymReaper.maybeDead(*SI);

lib/StaticAnalyzer/Core/RegionStore.cpp

void removeDeadBindingsWorker::VisitCluster(const MemRegion *baseR,
   if (!C)
     return;
 
   // Mark the symbol for any SymbolicRegion with live bindings as live itself.
   // This means we should continue to track that symbol.
   if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(baseR))
     SymReaper.markLive(SymR->getSymbol());
 
-  for (ClusterBindings::iterator I = C->begin(), E = C->end(); I != E; ++I)
+  for (ClusterBindings::iterator I = C->begin(), E = C->end(); I != E; ++I) {
+
+    // Mark the index symbol of any ElementRegion key as live.
+    const BindingKey &K = I.getKey();
+    auto subR = dyn_cast<SubRegion>(K.getRegion());
+    while (subR) {
+      if (auto elemR = dyn_cast<ElementRegion>(subR))
+        if (SymbolRef Sym = elemR->getIndex().getAsSymbol())
+          SymReaper.markLive(Sym);
+      subR = dyn_cast<SubRegion>(subR->getSuperRegion());
+    }
+
     VisitBinding(I.getData());
   }
+}
 
 void removeDeadBindingsWorker::VisitBinding(SVal V) {
   // Is it a LazyCompoundVal?  All referenced regions are live as well.
   if (Optional<nonloc::LazyCompoundVal> LCS =
           V.getAs<nonloc::LazyCompoundVal>()) {
 
     const RegionStoreManager::SValListTy &Vals = RM.getInterestingValues(*LCS);
 
     for (RegionStoreManager::SValListTy::const_iterator I = Vals.begin(),
                                                         E = Vals.end();
          I != E; ++I)
       VisitBinding(*I);
 
     return;
   }
 
   // If V is a region, then add it to the worklist.
   if (const MemRegion *R = V.getAsRegion()) {
     AddToWorkList(R);
 
+    // Element index of an element region is live.
+    if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
+      SVal Idx = ER->getIndex();
+      for (SymExpr::symbol_iterator SI = Idx.symbol_begin(),
+                                    SE = Idx.symbol_end();
+           SI != SE; ++SI) {
+        SymReaper.markLive(*SI);
+      }
+    }
+
     // All regions captured by a block are also live.
     if (const BlockDataRegion *BR = dyn_cast<BlockDataRegion>(R)) {
       BlockDataRegion::referenced_vars_iterator I = BR->referenced_vars_begin(),
                                                 E = BR->referenced_vars_end();
       for ( ; I != E; ++I)
         AddToWorkList(I.getCapturedRegion());
     }
   }

test/Analysis/return-ptr-range.cpp

+// RUN: %clang_cc1 -analyze -analyzer-checker=alpha.security.ReturnPtrRange -verify %s
+
+int arr[10];
+int *ptr;
+
+int conjure_index();
+
+int *test_element_index_lifetime() {
+  do {
+    int x = conjure_index();
+    ptr = arr + x;
+    if (x != 20)
+      return arr; // no-warning
+  } while (0);
+  return ptr; // expected-warning{{Returned pointer value points outside the original object (potential buffer overflow)}}
+}
+
+int *test_element_index_lifetime_with_local_ptr() {
+  int *local_ptr;
+  do {
+    int x = conjure_index();
+    local_ptr = arr + x;
+    if (x != 20)
+      return arr; // no-warning
+  } while (0);
+  return local_ptr; // expected-warning{{Returned pointer value points outside the original object (potential buffer overflow)}}
+}

test/Analysis/symbol-reaper.c

+// RUN: %clang_cc1 -analyze -analyzer-checker=debug.ExprInspection -verify %s
+
+void clang_analyzer_warnOnDeadSymbol(int);
+
+int arr[3];
+
+int conjure_index();
+
+void test_that_expr_inspection_works() {
+  do {
+    int x = conjure_index();
+    clang_analyzer_warnOnDeadSymbol(x);
+  } while(0); // expected-warning{{SYMBOL DEAD}}
+}
+
+void test_element_index_lifetime() {
+  do {
+    int x = conjure_index();
+    clang_analyzer_warnOnDeadSymbol(x);
+    arr[x] = 1;
+    if (x) {}
+  } while(0); // no-warning
+}