Page MenuHomePhabricator

[Analyzer] Crash fix for FindLastStoreBRVisitor

Authored by baloghadamsoftware on Feb 11 2019, 11:48 AM.



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.

Diff Detail

rC Clang

Event Timeline

baloghadamsoftware marked 3 inline comments as done.Feb 11 2019, 11:55 AM

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.


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*.


What was this nonsense?


This one too...

NoQ accepted this revision.Feb 11 2019, 1:53 PM

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?...


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.


Hmm, dunno. "hasVisibleUpdate()"?

This revision is now accepted and ready to land.Feb 11 2019, 1:53 PM
baloghadamsoftware marked 3 inline comments as not done.

Function renamed, comment updated.

This revision was automatically updated to reflect the committed changes.