[cfe-dev] [analyzer] Tracking values for generating bug reports
Artem Dergachev via cfe-dev
cfe-dev at lists.llvm.org
Tue Jun 18 16:14:27 PDT 2019
On 6/18/19 3:44 PM, Gábor Horváth wrote:
> Hi Kristóf,
>
> Thanks for the report. I have been thinking about what kind of user
> experience should we pursue. While my ideas might be a bit
> opinionated, see my comments inline.
>
> On Tue, 18 Jun 2019 at 20:47, Kristóf Umann <dkszelethus at gmail.com
> <mailto:dkszelethus at gmail.com>> wrote:
>
> Hi!
>
> This is an update on my GSoC project, "Enhancing bug reports in
> the Clang Static Analyzer". We had some discussions on
> phabricator, and some in private meetings, and I think it's due to
> share how things are looking right now.
>
> In my previous mail [1], I detailed the two distinct categories we
> defined, the "must-have-happened" case where every information is
> already in the bug path, and the "should-not-have-happened" case
> when the information isn't found in the bugpath. I divided the
> latter into two subcategories, the "Inlined category" (initially
> referred to as "category 1"), and the "Not inlined category"
> (initally referred to as "category 2").
>
> These categorizations are used to teach the analyzer incrementally
> about which nodes in the bugpath deserve special attention. For
> now, I plan to use this information exclusively for finding
> control dependencies to these nodes, and tracking their condition.
> Now, what we mean under "tracking an expression value", is that to
> add notes to the bug report relevant to that expression value.
>
> Ultimately, this means that my project depends greatly on
> condition tracking yielding meaningful addition of notes to the
> bug report, without adding unimportant ones. Since I more-or-less
> finished my work on the must-have-happened case (meaning that the
> analyzer can now figure out control dependencies to nodes
> contained in the bugpath), I'd like to detail how I plan to work
> on this.
>
> While evaluating an early prototype solution to the
> "must-have-happened" case where the same expression value tracking
> was used for both the bug-causing variable and for the conditions,
> I found that in many cases, the growth of bug length was
> intolerable. This is, in part, caused by conditions being tracked
> to a condition recursively, the conditions of asserts being
> tracked, and that notes about a condition are not as interesting
> as notes about the bug causing variable (calls to operator bool
> for instance).
>
> Fixing any of these requires me to teach the analyzer the
> difference in between "THE value" and "just a condition". The
> details are a little more complicated, so I'll show some examples
> that point out certain cases:
> *
> *
> *Example 1.:*
>
> 01 int flag;
>
> 02 bool coin();
>
> 03
>
> 04 void foo() {
>
> 05 flag = coin();
>
> 06 }
>
> 07
>
> 08 int main() {
>
> 09 int *x = 0;
>
> 10 foo();
>
> 11 if (flag) // assumed true
>
> 12 *x = 5; // warn
>
> 13 }
>
> *
> *
> In this example, it'd be great to see notes placed on line 10 and
> 5, because if flag wasn't invalidated, the bug would not have
> occurred (since flag is global, and is initialized to 0). The
> analyzer normally wouldn't place notes there, so we definitely
> should track flag up to line 5.
> *
> *
> *Example 2.:*
> *
> *
> 01 int flag;
>
> 02 bool coin();
>
> 03
>
> 04 void foo() {
>
> 05 coin();
>
> 06 }
>
> 07
>
> 08 int main() {
>
> 09 int *x = 0;
>
> 10 foo();
>
> 11 if (flag)// assumed true
>
> 12 *x = 5;// warn
>
> 13 }
>
>
> This case is very similar, with the only difference being that the
> analyzer conservatively assumed that coin may have written flag
> (as it's a global variable). We should track until line 5.
>
>
> I am not sure about this example. While the invalidation of the global
> flag is definitely playing a role in this bug report the point where
> the flag is actually invalidated could seem quite arbitrary for the
> user. We might get the invalidation when we first see a function that
> is not defined in this TU, when we reach the maximum call stack depth
> and so on. My point is, I am not sure if we actually help the user by
> pinpointing the first function call where the invalidation happens. A
> more user friendly way to think about this problem is how could the
> user solve this false positive? As far as I understand the cannonical
> solution would be to add an assertion, so it would be better to put a
> node close to the place where the user would change the code, so I
> would put it in the stack frame of the bug. For example we could
> generate a note for the call foo(), that somewhere in that call stack
> the analyzer could no longer track the value of flag, thus invalidated
> its contents. @Artem Dergachev <mailto:adergachev at apple.com> what do
> you think?
This is definitely one of the most annoying kinds of false positives we
have due to infeasible paths and over-eager assumption chains. Like, you
can add an assertion here, but it's going to look super ugly:
bool tmp_flag = flag;
coin(); // why would anybody believe it touches flag in the first
place???
assert(flag == tmp_flag && "sanity check");
And even if the user would actually like to add something like that to
his code, it would require a powerful constraint solver to even handle
this assertion correctly.
These are not very common, but they're so annoying that i probably
wouldn't be against marking reports as invalid immediately when we see
that an important control dependency relies on such invalidation (we'll
have to gather experimental data on that, of course).
>
> *Example 3.:*
> *
> *
>
> 01 void f(int flag) {
>
> 02 int *x = 0;
>
> 03 if (flag)// assumed true
>
> 04 *x = 5;// warn
>
> 05 }
>
>
> Here, the user could simply follow the arrows that shows the path
> of execution: it isn't really important what flag was initialized
> on the first line.
>
> *Example 4.:*
> *
> *
>
> 01 int flag;
>
> 02
>
> 03 int getInt();
>
> 04
>
> 05 int main() {
>
> 06 int *x = 0;
>
> 07 int y = getInt();
>
> 08 flag = y;
>
> 09 if (flag)// assumed true
>
> 10 *x = 5;// warn
>
> 11 }
>
>
> Again, the user could see there was a write made to flag on line 8
> -- the question is, whether we should explain y better. Right now,
> we're thinking that we shouldn't, leading to the conclusion that
> flag here shouldn't be tracked at all.
>
>
> Finding the place where flag was modified in a really big function can
> still be challenging. While generating a note would be an overkill I
> wonder if some middle ground like highlighting the statement without
> additional text would actually make sense for this case.
When it's in the same function, you can simply search for the variable
name to see all writes into it. It's not that hard. Even if the variable
is written into by pointer, you can see that its address is taken and
search for the pointer variable as well (though annoying if there are
too many levels of indirection).
But, hmm, if the address is taken in a different stack frame, this
becomes much harder. I guess, writes that are made through pointers
should be highlighted, and we should also do our tracking to explain why
do we think that this pointer points to that variable.
>
> *Example 5.:*
> *
> *
>
> 01 int flag;
>
> 02
>
> 03 int getInt();
>
> 04
>
> 05 void foo() {
>
> 06 int y = getInt();
>
> 07 flag = y;
>
> 08 }
>
> 09
>
> 10 int main() {
>
> 11 int *x = 0;
>
> 12 foo();
>
> 13 if (flag)// assumed true
>
> 14 *x = 5;// warn
>
> 15 }
>
> Like Example 1-2, we should explain that flag was written on line
> 7, but like in Example 4., we shouldn't track y.
>
>
> Again, from the user's point of view, I think the ultimate solution
> would be to have an interface, where we does not present the part
> where y was tracked by default, but the user could click on a button
> to actually expand that part of the path in case she consider it
> interesting. This, of course, is not part of you GSoC, I am just
> wondering what is the ideal that we would like to pursue in the long run.
A more powerful UI could have indeed solved a lot of these problems by
telling users to do our work. But given that it comes with a fairly
large cost of developing such UIs for every tool that integrates the
Static Analyzer, i'd definitely try to push our own effort of stuffing
exactly as much information as necessary into the report as far as possible.
> *
> Example 6.:*
>
> 01 void f(int flag) {
>
> 02 int *x = 0;
>
> 03 assert(flag);
>
> 04 if (flag)// assumed true
>
> 05 *x = 5;// warn
>
> 06 }
>
>
> Currently, we mention nothing about line 3, yet we say "Taking the
> true branch" on line 4, rather then "Assuming the condition is
> true". This is because the collapse point (point at which we
> constrain flag's value to be true or false) isn't on line 4: the
> analysis only continued past the assert since the analyzer assumed
> flag to be non-zero. In this case, we would like to track flag to
> the assert to explain why we are so confident on line 5 that flag
> is non-zero.
>
>
> What do you mean by tracking tha flag back to the assert? The reason
> why a note is useful because in this case either the assert is wrong
> or the bug is a true positive. But again, when the assert is in the
> same function we might not want to generate additional note for this
> as this info might easily be inferred by following the arrows in the
> report (but we might highlight the assertion line, see my previous
> comments). In case the assert is in a separate (inlined) function it
> would make much more sense to generate a note.
Wouldn't the assert already contain a (prunable) note saying "Assuming
'flag' is true"? I guess the only problem here is that the note is
prunable, so it won't be shown if the assert is wrapped into a nested
function call.
> *
> Example 7.:*
>
> 01 int getInt();
>
> 02 03 void f(int flag) {
>
> 04 int *x = 0;
>
> 05 flag = getInt();
>
> 06 assert(flag);
>
> 07 if (flag)// assumed true
>
> 08 *x = 5;// warn
>
> 09 }
>
>
> Like Example 6, we should explain why know that flag is non-zero
> on line 7 by tracking it back to line 6. Like in the case of
> Example 4., the user could see where flag was written, so we
> wouldn't like to see a note on line 5.
>
> So what's the takeaway?
>
> After teaching the analyzer the difference in between a condition
> and a "regularly tracked expression", I plan to implement the
> following two rules:
>
> Track a condition only if
> a.) The collapse point doesn't coincide with the condition point
> b.) It was written in a nested stack frame.
>
>
> Do you mane a) or b), or a) and b)? Also, what to do with "multiple
> collapse point" events like:
>
> if ( a < 10 ) ;
> if ( a < 5) // Here we do add new constraints to a, but we also had
> other constraints before. Do you consider this to coincide or not?
> ...
I'd rather track the condition *until* we cover those points (which
implies not tracking it at all when there are no b.)-points and the
a.)-point coincide with the current terminator), rather than track it
forever if we have those points.
By collapse point i meant the point where the (bool)condition collapses
to a constant-false or a constant-true (in the true case the condition
itself doesn't necessarily collapse to a constant 1). It doesn't happen
every time we introduce a constraint.
>
> We hope that by implementing this, tracking conditions to
> conditions would be kept at bay without a counter to limit the
> depth of recursion, and the intolerable growth of bug length with
> drastically shorten. I do expect skeletons to fall out of the
> closet, but I am confident that this is a good initial approach.
>
> As explained earlier, this is mission number one, so I'll
> prioritize getting it right before pursuing the
> "should-not-have-happened" case.
>
> One thing I did not touch on just yet, is the case where an assert
> was (correctly, by the way) regarded as a control dependency, and
> it's condition was tracked. This is undoubtedly undesirable, but
> figuring out whether the condition is found in an assert is rather
> difficult. Asserts are often implemented as a macro, and could
> have a very, for a lack of a better word, esoteric implementations
> on certain platforms. We discussed trying to tinker with the
> control dependency calculator, namely skipping over nodes that
> have two successors and one of them leads to noreturn node, but I
> still need time to figure out something reliable.
>
>
> Some asserts consists of more basic blocks. Having two successors
> where one of them is a noreturn block is not a sufficient condition.
> Consider for example assert(a && b); Here the basic block for
> evaluating a will either go to the next line after assertion or to the
> evaluation ofb which is not a noreturn block. While it is true that
> from node a we will either go to the next non-assert block or end up
> in a noreturn block, the noreturn block might not be an immediate
> successor of node a.
Forgot to mention, i have a history with the CFG for asserts that's
mostly contained in https://reviews.llvm.org/D28023 and
https://reviews.llvm.org/D35673. This is the reason why i believe that
some implementation of assert() have a lot of CFG blocks on their own,
regardless of how many CFG blocks does it take to evaluate the assert
condition.
>
> Regards,
> Gabor
>
>
> Thanks to everyone who helped me along: Artem Dergachev, Gábor
> Horváth, Ádám Balogh, Jakub Kuderski, and Zoltán Porkoláb!
>
> Cheers,
> Kristóf
>
> [1] http://lists.llvm.org/pipermail/cfe-dev/2019-June/062535.html
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20190618/c363c5cf/attachment.html>
More information about the cfe-dev
mailing list