[cfe-dev] [analyzer] Tracking values for generating bug reports
Artem Dergachev via cfe-dev
cfe-dev at lists.llvm.org
Mon Jun 24 18:59:09 PDT 2019
Yup, looks much better! Let's actually dig through other projects a bit,
but results on LLVM look fairly perfect to me.
> ASTDiagnostic.cpp
Why wasn't the extra tracking removed in the moderate mode? There
doesn't seem to be an obvious overwrite for `kind`. Is it reacting to an
invalidation?
> DominanceFrontierImpl.h
Why does it track so much more expressions in the moderate mode (even if
not producing any actual nodes for them)? Is it because you changed the
de-duplication method from by-expr to by-node in between?
> CGObjCGNU.cpp
I'd like to think more about this one. It doesn't look to me that the
new notes are helpful here, for the reason that the problem is pretty
much entirely between the definition of OID and the use, while all of
the notes are outside that range. The report wouldn't become less valid
(for a certain definition of valid) if we simply omit everything except
the last three notes:
- 'OID' is initialized to a null pointer value
- Loop body skipped when range is empty
- Called ++ object pointer is null
I don't see any immediate solutions here; i guess the right thing to do
would be to simply learn how to chop off the irrelevant beginning of the
path.
On 6/24/19 4:48 PM, Kristóf Umann wrote:
> I went ahead and (although admittedly with a very crude
> implementation) I enhanced condition tracking with the following:
>
> * All notes about their initialization are discarded
> * No longer tracking the right hand side of the last store
> * Last stores are discarded unless it happened in another stack frame
>
> I evaluated the prototype solution on LLVM+Clang+Clang-tools-extra,
> Xerces and Bitcoin. I might add rtags and YouCompleteMe later, but I
> think this is sufficient for now:
>
> http://cc.elte.hu:15001/Default/#
>
> Due to the lack of better categorization, I used the following (so
> this has in fact no relation to whether the report is correct or not):
> * Intentional reports (green x) are the ones where the bugreport got
> unquestionably worse.
> * Confirmed reports (red check mark) got definitely better
> * False positives (grey line) are in between.
>
> I didn't have time to look at them all, but here are some reports I
> found interesting on LLVM:
>
> http://cc.elte.hu:15001/Default/#is-unique=on&run=LLVM%2FClang%2FClang-tools-extra%20AFTER%20tracking%20conditions&review-status=Confirmed&review-status=False%20positive&review-status=Intentional&detection-status=New&detection-status=Reopened&detection-status=Unresolved&tab=LLVM%2FClang%2FClang-tools-extra%20AFTER%20tracking%20conditions
>
> By clicking on a bug report, and changing the run with the dropdown
> menu found in the upper right corner (next to "Also found in:"), you
> can see that in some cases these enhancements kept the amount of extra
> notes at bay quite well.
>
> .* BEFORE condition tracking: Analysis made on LLVM monorepo commit
> 4cc6d72bb4d
> .* AFTER condition tracking: With https://reviews.llvm.org/D62883
> applied and condition tracking enabled.
> .* AFTER condition tracking + DEBUG notes: With
> https://reviews.llvm.org/D63642 applied and condition tracking with
> debug notes enabled.
> .* AFTER condition tracking WITH moderate tracking: With the above
> mentioned additions applied on top of https://reviews.llvm.org/D62883
> and condition tracking enabled.
> .* AFTER condition tracking WITH moderate tracking + DEBUG notes: With
> the above mentioned additions applied on top of
> https://reviews.llvm.org/D63642 and condition tracking with debug
> notes enabled.
>
> On Wed, 19 Jun 2019 at 02:08, Artem Dergachev <adergachev at apple.com
> <mailto:adergachev at apple.com>> wrote:
>
>
>
>> On Jun 18, 2019, at 5:02 PM, Kristóf Umann <dkszelethus at gmail.com
>> <mailto:dkszelethus at gmail.com>> wrote:
>>
>>
>>
>> On Wed, 19 Jun 2019 at 01:14, Artem Dergachev
>> <noqnoqneo at gmail.com <mailto:noqnoqneo at gmail.com>> wrote:
>>
>>
>>
>> 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).
>>
>>
>> Hmm, yea, good point. But if I coin were to take flag as a
>> non-const reference (other than the fact that flag is global) I
>> guess we would like to keep the report and place notes all the
>> way there? I agree with Artem, we really need to see the real
>> world impact of this.
>
> Yup.
>
>
>>>
>>> *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.
>>
>> I think its a matter of a simple comparison of the stack frames
>> that would decide whether we only want to track the condition if
>> it was in between the collapse point and the initialization in a
>> nested stack frame, or regardless of the stack frame. Let's see
>> just see which yields the better result!
>>
>>
>> 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.
>>
>>
>> Ah yes, our arch enemy, pointer analysis showed up again. I guess
>> I agree with you, but I plan on approaching aliasing related
>> issues when I got most of the other stuff working.
>
> In this case it's much more trivial because you're simply relying
> on the information about pointers that's already contained in the
> graph.
>
>>
>>>
>>> *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.
>>
>>
>> I actually had a number of discussions with Dániel Krupp about
>> this, and folks in Ericsson seem to be very interested in this
>> direction. This could be a great compliment to my GSoC as a
>> followup project.
>>
>>> *
>>> 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.
>>
>> Yup, with-analyzer-config prune-paths=false, you get the
>> following report, but it's still not explained well why flag is
>> non-zero (the thing that I'm missing is the connection in between
>> b and flag):
>>
>> $ cat example_6.cpp
>>
>> [[noreturn]] void halt();
>>
>> void assert(int b) {
>> if (!b)
>> halt();
>> }
>>
>> void f(int flag) {
>> int *x = 0;
>> assert(flag);
>> if (flag) // assumed true
>> *x = 5; // warn
>> }
>>
>> $ clang -cc1 -analyze -analyzer-output=text
>> -analyzer-checker=core example_6.cpp -analyzer-config
>> prune-paths=false
>>
>> example_6.cpp:10:3: note: 'x' initialized to a null pointer value
>> int *x = 0;
>> ^~~~~~
>> example_6.cpp:11:3: note: Calling 'assert'
>> assert(flag);
>> ^~~~~~~~~~~~
>> example_6.cpp:5:7: note: Assuming 'b' is not equal to 0
>> if (!b)
>> ^~
>> example_6.cpp:5:3: note: Taking false branch
>> if (!b)
>> ^
>> example_6.cpp:11:3: note: Returning from 'assert'
>> assert(flag);
>> ^~~~~~~~~~~~
>> example_6.cpp:12:7: note: 'flag' is not equal to 0
>> if (flag) // assumed true
>> ^~~~
>> example_6.cpp:12:3: note: Taking true branch
>> if (flag) // assumed true
>> ^
>> example_6.cpp:13:8: note: Dereference of null pointer (loaded
>> from variable 'x')
>> *x = 5; // warn
>> ~ ^
>>
>> As you said, this example is interesting because assert isn't a
>> macro here, and flag's collapse point really happens in a nested
>> stack frame. Am I understanding correctly that maybe we shouldn't
>> pursue tracking a variable if the collapse point happened in the
>> same stack frame?
>>
>>> *
>>> 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 either happens.
>>
>>>
>>> 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.
>>
>> Yup, that's what I was planning to go for.
>>
>>
>>>
>>> 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 anoreturnblock is not a
>>> sufficient condition. Consider for exampleassert(a &&
>>> b);Here the basic block for evaluatingawill either go to the
>>> next line after assertion or to the evaluation ofbwhich is
>>> not anoreturnblock. While it is true that from node a we
>>> will either go to the next non-assert block or end up in
>>> anoreturnblock, thenoreturnblock might not be an immediate
>>> successor of nodea.
>>
>> Forgot to mention, i have a history with the CFG for asserts
>> that's mostly contained
>> inhttps://reviews.llvm.org/D28023andhttps://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.
>>
>> Thanks! :D Right now, incorrect tracking of assert conditions
>> isn't on the top of my priority list, but I'll think about this
>> when I'm sitting on the bus or watering the garden.
>>
>>>
>>> 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/20190624/93c72bf5/attachment.html>
More information about the cfe-dev
mailing list