Page MenuHomePhabricator

[analyzer] symbol_iterator must iterate through the symbolic base.
ClosedPublic

Authored by NoQ on Mar 9 2018, 7:05 PM.

Details

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.

Diff Detail

Repository
rC Clang

Event Timeline

NoQ created this revision.Mar 9 2018, 7:05 PM
NoQ added a comment.Mar 9 2018, 7:14 PM

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 updated this revision to Diff 137892.Mar 9 2018, 7:15 PM

Slightly simplify one of the tests.

NoQ edited the summary of this revision. (Show Details)Mar 9 2018, 7:15 PM
NoQ added a comment.Mar 9 2018, 8:02 PM

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.

MTC added a subscriber: MTC.Mar 11 2018, 7:18 PM
NoQ edited the summary of this revision. (Show Details)Mar 12 2018, 4:58 PM
This revision was not accepted when it landed; it landed in state Needs Review.Mar 22 2018, 2:33 PM
Closed by commit rC328247: [analyzer] Make symbol_iterator iterate over SVal's symbolic base. (authored by dergachev, committed by ). · Explain Why
This revision was automatically updated to reflect the committed changes.