[analyzer] Tracking values for generating bug reports

classic Classic list List threaded Threaded
14 messages Options
Reply | Threaded
Open this post in threaded view
|

[analyzer] Tracking values for generating bug reports

Nathan Ridge via cfe-dev
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.

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.

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.


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.

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.

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.

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


_______________________________________________
cfe-dev mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: [analyzer] Tracking values for generating bug reports

Nathan Ridge via cfe-dev
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 <[hidden email]> 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. [hidden email] what do you think?
 

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.
 

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.
 

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.
 

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

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 of b 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.

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


_______________________________________________
cfe-dev mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: [analyzer] Tracking values for generating bug reports

Nathan Ridge via cfe-dev
Sorry for the amount of mails. I just wanted to share a random idea. What if you cut every (inbound) edge of all noreturn basic blocks temporarily before calculating the control dependencies and restore the edges afterwards. I did not work through any examples as it is 1 am here, nevertheless, this might worth exploring. 

Gábor Horváth <[hidden email]> ezt írta (időpont: 2019. jún. 19., Sze 0:44):
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 <[hidden email]> 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. [hidden email] what do you think?
 

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.
 

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.
 

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.
 

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

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 of b 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.

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


_______________________________________________
cfe-dev mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: [analyzer] Tracking values for generating bug reports

Nathan Ridge via cfe-dev
In reply to this post by Nathan Ridge via cfe-dev


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 <[hidden email]> 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. [hidden email] 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 of b 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



_______________________________________________
cfe-dev mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: [analyzer] Tracking values for generating bug reports

Nathan Ridge via cfe-dev


On Wed, 19 Jun 2019 at 01:14, Artem Dergachev <[hidden email]> 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 <[hidden email]> 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. [hidden email] 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.
 

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.

 

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 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 of b 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.

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



_______________________________________________
cfe-dev mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: [analyzer] Tracking values for generating bug reports

Nathan Ridge via cfe-dev


On Jun 18, 2019, at 5:02 PM, Kristóf Umann <[hidden email]> wrote:



On Wed, 19 Jun 2019 at 01:14, Artem Dergachev <[hidden email]> 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 <[hidden email]> 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. [hidden email] 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 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 of b 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.

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



_______________________________________________
cfe-dev mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: [analyzer] Tracking values for generating bug reports

Nathan Ridge via cfe-dev
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:


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.


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 <[hidden email]> wrote:


On Jun 18, 2019, at 5:02 PM, Kristóf Umann <[hidden email]> wrote:



On Wed, 19 Jun 2019 at 01:14, Artem Dergachev <[hidden email]> 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 <[hidden email]> 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. [hidden email] 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 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 of b 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.

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



_______________________________________________
cfe-dev mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: [analyzer] Tracking values for generating bug reports

Nathan Ridge via cfe-dev
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:


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.


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 <[hidden email]> wrote:


On Jun 18, 2019, at 5:02 PM, Kristóf Umann <[hidden email]> wrote:



On Wed, 19 Jun 2019 at 01:14, Artem Dergachev <[hidden email]> 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 <[hidden email]> 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. [hidden email] 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 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 of b 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.

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




_______________________________________________
cfe-dev mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: [analyzer] Tracking values for generating bug reports

Nathan Ridge via cfe-dev
I'm happy to delight you all with some more results! I was far more strict on my judgement this time around, marking a report good when I genuinely believed that the note made the report better.

All the runs were made on monorepo commit  db4e335b8643056f5afa2a0d8d175d95b1fb7e28  with the following patches applied:

BEFORE tracking condition:  Without any changes being made, default CodeChecker settings.
AFTER tracking conditions: Without any changes being made, track-conditions set to true.
AFTER tracking conditions + DEBUG notes:  Without any changes being made, track-conditions and track-conditions-debug set to true.
AFTER linear pruning (or similar run name): [1] applied, track-conditions set to true
AFTER tracking conditions WITH improved moderation: [1, 2, 3, 4] applied, track-conditions set to true (stupid name but it's gonna stay like this for now :) )
AFTER tracking conditions WITH improved moderation: [1, 2, 3, 4] applied, track-conditions and track-conditions-debug  set to true

[1]
https://reviews.llvm.org/D64232 [analyzer] Prune calls to functions with linear CFGs that return a non-zero constrained value 
[2] https://reviews.llvm.org/D64287 [analyzer] Track the right hand side of the last store regardless of its value

[3] https://reviews.llvm.org/D64270 [analyzer][NFC] Prepare visitors for different tracking kinds

[4] https://reviews.llvm.org/D64272 [analyzer] Note last writes to a condition only in a nested stackframe



Some conclusions:
  • [4] Actually notes last writes in different, not nested stack frames. Gotta fix that.
  • [1] Returning an unconstrained value when the function is linear is never meaningful. Not for conditions, not for anything else. Gotta fix that too. It's worth talking about whether we should prune these for conditions even if the function isn't linear.
  • [1] This one gets rid of almost all the operator bool calls. Maybe in the rare case it doesn't, we should preserve them? I always planned to get rid of calls to operator bool, but now I'm hesitant.
  • Assert conditions are not yet ignored, I have a neat solution locally, but I haven't published or tested it yet.
There honestly isn't that much I have on my mind, I think after the next round of analyses we should be good! I really should've made an analysis with all the non-condition tracking changes to get an even better perspective, so I'll do that next time.

On Tue, 25 Jun 2019 at 04:00, Artem Dergachev <[hidden email]> wrote:
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?
 
The report is now untouched! 

> 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?
 
I'll make a testcase for that. Honestly, I'm thinking of reimplementing the visitor as well, so that I'll collect the control dependencies in a set when the visitor object is created, and track them at BlockExit locations, that should limit it, because yeah, I believe they originate from the de-duplication.

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

This time around, BodyFarm.cpp is in the same boat. I really just made a fundamentally bad (like, really bad) report even worse. 
 
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:


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.


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 <[hidden email]> wrote:


On Jun 18, 2019, at 5:02 PM, Kristóf Umann <[hidden email]> wrote:



On Wed, 19 Jun 2019 at 01:14, Artem Dergachev <[hidden email]> 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 <[hidden email]> 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. [hidden email] 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 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 of b 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.

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




_______________________________________________
cfe-dev mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: [analyzer] Tracking values for generating bug reports

Nathan Ridge via cfe-dev
*repeats without overquoting in order to avoid hitting the mailing list message length limit*

On 7/23/19 7:29 PM, Artem Dergachev wrote:
Xerces - DOMRangeImpl.cpp: Ugh, are those "Value assigned to..." notes triggered by invalidation? I have a plan of my own to wipe such notes out (or at least formulate them more carefully), so i guess it's not an action item for you (nor much of a regression), but still ugh. Another thing to think about for those is to suppress the warning entirely when a region that stores is important condition is first assumed to contain false, then invalidated, then assumed to contain true.

Xerces - XMLString.hpp: Mmm, i guess passing unconstrained values as parameters is also not very meaningful. It doesn't look like it's a *big* problem, but i guess it's worth considering fixing eventually.


> Assert conditions are not yet ignored, I have a neat solution locally

Just to make sure - do you have a test case with control flow within the condition, eg. `assert((a || b) && "the universe is collapsing")`?


On 7/23/19 12:49 PM, Kristóf Umann wrote:
I'm happy to delight you all with some more results! I was far more strict on my judgement this time around, marking a report good when I genuinely believed that the note made the report better.

All the runs were made on monorepo commit  db4e335b8643056f5afa2a0d8d175d95b1fb7e28  with the following patches applied:

BEFORE tracking condition:  Without any changes being made, default CodeChecker settings.
AFTER tracking conditions: Without any changes being made, track-conditions set to true.
AFTER tracking conditions + DEBUG notes:  Without any changes being made, track-conditions and track-conditions-debug set to true.
AFTER linear pruning (or similar run name): [1] applied, track-conditions set to true
AFTER tracking conditions WITH improved moderation: [1, 2, 3, 4] applied, track-conditions set to true (stupid name but it's gonna stay like this for now :) )
AFTER tracking conditions WITH improved moderation: [1, 2, 3, 4] applied, track-conditions and track-conditions-debug  set to true
[1] https://reviews.llvm.org/D64232 [analyzer] Prune calls to functions with linear CFGs that return a non-zero constrained value 
[2] https://reviews.llvm.org/D64287 [analyzer] Track the right hand side of the last store regardless of its value

[3] https://reviews.llvm.org/D64270 [analyzer][NFC] Prepare visitors for different tracking kinds

[4] https://reviews.llvm.org/D64272 [analyzer] Note last writes to a condition only in a nested stackframe



Some conclusions:
  • [4] Actually notes last writes in different, not nested stack frames. Gotta fix that.
  • [1] Returning an unconstrained value when the function is linear is never meaningful. Not for conditions, not for anything else. Gotta fix that too. It's worth talking about whether we should prune these for conditions even if the function isn't linear.
  • [1] This one gets rid of almost all the operator bool calls. Maybe in the rare case it doesn't, we should preserve them? I always planned to get rid of calls to operator bool, but now I'm hesitant.
  • Assert conditions are not yet ignored, I have a neat solution locally, but I haven't published or tested it yet.
There honestly isn't that much I have on my mind, I think after the next round of analyses we should be good! I really should've made an analysis with all the non-condition tracking changes to get an even better perspective, so I'll do that next time.



_______________________________________________
cfe-dev mailing list
[hidden email]
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
Reply | Threaded
Open this post in threaded view
|

Re: [analyzer] Tracking values for generating bug reports

Nathan Ridge via cfe-dev
I got another round! The following new run names were added:

.* + all non-control dependency changes: [1, 2] applied
.*AFTER tracking conditions + all non-control dependency changes: [1, 2] applied, "track-conditions" enabled
.*AFTER tracking conditions FINAL: "track-conditions" enabled, [1-8] applied (also with ~10 or so NFC patches)
.*AFTER tracking conditions FINAL + DEBUG notes: "track-conditions" and "track-conditions-debug" enabled, [1-8] applied (also with ~10 or so NFC patches)

[1] https://reviews.llvm.org/D64232 [analyzer] Prune calls to functions with linear CFGs that return a non-zero constrained value 
[2] https://reviews.llvm.org/D64287 [analyzer] Track the right hand side of the last store regardless of its value
[3] https://reviews.llvm.org/D64270 [analyzer][NFC] Prepare visitors for different tracking kinds

[4] https://reviews.llvm.org/D64272 [analyzer] Note last writes to a condition only in a nested stackframe

[5] https://reviews.llvm.org/D65287 [analyzer][CFG] Don't track the condition of asserts
[6] https://reviews.llvm.org/D65575 [analyzer] Mention whether an event is about a condition in a bug report part 1
[7] https://reviews.llvm.org/D65724 [analyzer] Don't make ConditionBRVisitor events prunable when the condition is an interesting field
[8] https://reviews.llvm.org/D65725 [analyzer] Mention whether an event is about a condition in a bug report part 2

Conclusions:

Shockingly, no condition tracking related changes were made in the FINAL run for either Bitcoin or Xerces, so we only have LLVM/Clang to talk about. This time, I added comments, which, after clicking on a report, can be retrieved by clicking on 'Comments' in the upper right corner. These comments are far more precise than the notes I left previously.


The negatives:
1. Extra notes to functions following this pattern were very-very common:

bool a(int b) {
  return b == 0;
  // Assuming 'b' is equal to 0
  // Returning the value 1, which will be (a part of a) condition
}

void f(int b) {
  int *x = 0;
  if (a(b)) // call to 'a', returning from 'a'
    *x = 5; // nullptr dereference
}

These notes are totally meaningless, and they aren't pruned out by [1] because the assumption notes are non-prunable (they explain a variable, b in this case, that is marked as interesting, as the return value is tracked by ReturnVisitor). A possible solution would be to prune linear functions in ConditionBRVisitor as well similarly to [1], but then we'd lose the assumption note. Instead, moving the non-prunable assumption note to the actual collapse point would be better, but a quick look at the generated ExplodedGraph reveals that this no longer an bug report construction issue: the collapse point is in fact at the return statement, rather then the condition.

So, I think the bug report should always explain how the analyzer thinks. Ideally, this should be identical to how the bug could be reproduced, but if it is not (in this case the assumption should be made when a(b) is the condition), maybe the logic of the analysis should be changed instead.


2. I didn't come across this too often, but it happened:

int getInt(); int getInt2();

bool a() {
  return getInt2() && getInt();
  // Returning value, which will be (a part of a) condition
}

void f() {
  int *x = 0;

  if (a()) // call to 'a', returning from 'a'
    *x = 5; // nullptr dereference
}


This note wasn't pruned because a() has in fact more than 3 basic blocks, but it really doesn't change anything. I guess we *could* prune it, but I'm leaning on accepting it as a sacrifice.


3. Some function calls are lost due to retrieving information from nested stack frames only, rather than different stack frames. I only encountered this when the condition variable was invalidated: The "AFTER tracking conditions WITH improved moderation" runs display the path to the invalidation point, yet the FINAL runs do not.


4. Calls to operator!= in foreach loops -- Are these necessary? Is there any, even articial cases where this is actually meaningful? This is pretty much the only non-constructive addition of notes that are introduced only because of condition tracking.


Positives:

In general, the wording as the analyses were run may be imperfect, but they indicate what the message is about very precisely. The path of execution is much better explained, and even if the extra function call isn't meaningful, the note messages state clearly that we're only talking about a condition, I can skip them without being bothered by it too much. I am given extra information without the cost of polluting the rest of the report.

Here is a collection of my favorites, though I found most of the extra notes nice:

1. Here, we encounter a nullpointer dereference issue. Op0 is assumed to be equal to Op1, but only due to condition tracking do we explain that Op1 is believed to be null, and THAT is why this assumption (Op1 == Op0) is so important!


2. The seldom addition of extra "Returning value, which will be (a part of a) condition" notes, love them!


3. This one is weird, I'm not yet sure how this note came about, but yet again, it isn't clear AT ALL in the original report why CountS will be a source of a null dereference error. The extra note tells us that CountS is non-null, but its pointee is.


Also, adding the actual mail that was lost ;)

On Wed, 24 Jul 2019 at 13:57, Kristóf Umann <[hidden email]> wrote:


On Wed, 24 Jul 2019 at 04:29, Artem Dergachev <[hidden email]> wrote:
Xerces - DOMRangeImpl.cpp: Ugh, are those "Value assigned to..." notes triggered by invalidation? I have a plan of my own to wipe such notes out (or at least formulate them more carefully), so i guess it's not an action item for you (nor much of a regression), but still ugh. Another thing to think about for those is to suppress the warning entirely when a region that stores is important condition is first assumed to contain false, then invalidated, then assumed to contain true.

Totally agreed.
 
Xerces - XMLString.hpp: Mmm, i guess passing unconstrained values as parameters is also not very meaningful. It doesn't look like it's a *big* problem, but i guess it's worth considering fixing eventually.

In this particular case, partly due to me not being familiar with the code, I found the note helpful, but in LLVM there were plenty of reports where I didn't feel this way, so I'll get that fixed.
 
> Assert conditions are not yet ignored, I have a neat solution locally

Just to make sure - do you have a test case with control flow within the condition, eg. `assert((a || b) && "the universe is collapsing")`?

I don't :) Thanks!
 
On 7/23/19 12:49 PM, Kristóf Umann wrote:
I'm happy to delight you all with some more results! I was far more strict on my judgement this time around, marking a report good when I genuinely believed that the note made the report better.

All the runs were made on monorepo commit  db4e335b8643056f5afa2a0d8d175d95b1fb7e28  with the following patches applied:

BEFORE tracking condition:  Without any changes being made, default CodeChecker settings.
AFTER tracking conditions: Without any changes being made, track-conditions set to true.
AFTER tracking conditions + DEBUG notes:  Without any changes being made, track-conditions and track-conditions-debug set to true.
AFTER linear pruning (or similar run name): [1] applied, track-conditions set to true
AFTER tracking conditions WITH improved moderation: [1, 2, 3, 4] applied, track-conditions set to true (stupid name but it's gonna stay like this for now :) )
AFTER tracking conditions WITH improved moderation: [1, 2, 3, 4] applied, track-conditions and track-conditions-debug  set to true
[1] https://reviews.llvm.org/D64232 [analyzer] Prune calls to functions with linear CFGs that return a non-zero constrained value 
[2] https://reviews.llvm.org/D64287 [analyzer] Track the right hand side of the last store regardless of its value

[3] https://reviews.llvm.org/D64270 [analyzer][NFC] Prepare visitors for different tracking kinds

[4] https://reviews.llvm.org/D64272 [analyzer] Note last writes to a condition only in a nested stackframe



Some conclusions:
  • [4] Actually notes last writes in different, not nested stack frames. Gotta fix that.
  • [1] Returning an unconstrained value when the function is linear is never meaningful. Not for conditions, not for anything else. Gotta fix that too. It's worth talking about whether we should prune these for conditions even if the function isn't linear.
  • [1] This one gets rid of almost all the operator bool calls. Maybe in the rare case it doesn't, we should preserve them? I always planned to get rid of calls to operator bool, but now I'm hesitant.
  • Assert conditions are not yet ignored, I have a neat solution locally, but I haven't published or tested it yet.

One more thing: If the condition is a binary operator, like (B || A) is assumed true because A is true, or (A && B) is assumed false because A is false, we should only track A.
 
    There honestly isn't that much I have on my mind, I think after the next round of analyses we should be good! I really should've made an analysis with all the non-condition tracking changes to get an even better perspective, so I'll do that next time.

    On Tue, 25 Jun 2019 at 04:00, Artem Dergachev <[hidden email]> wrote:
    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?
     
    The report is now untouched! 

    > 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?
     
    I'll make a testcase for that. Honestly, I'm thinking of reimplementing the visitor as well, so that I'll collect the control dependencies in a set when the visitor object is created, and track them at BlockExit locations, that should limit it, because yeah, I believe they originate from the de-duplication.

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

    This time around, BodyFarm.cpp is in the same boat. I really just made a fundamentally bad (like, really bad) report even worse.

    _______________________________________________
    cfe-dev mailing list
    [hidden email]
    https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
    Reply | Threaded
    Open this post in threaded view
    |

    Re: [analyzer] Tracking values for generating bug reports

    Nathan Ridge via cfe-dev


    On 8/8/19 2:05 PM, Kristóf Umann wrote:
    I got another round! The following new run names were added:

    .* + all non-control dependency changes: [1, 2] applied
    .*AFTER tracking conditions + all non-control dependency changes: [1, 2] applied, "track-conditions" enabled
    .*AFTER tracking conditions FINAL: "track-conditions" enabled, [1-8] applied (also with ~10 or so NFC patches)
    .*AFTER tracking conditions FINAL + DEBUG notes: "track-conditions" and "track-conditions-debug" enabled, [1-8] applied (also with ~10 or so NFC patches)
    [1] https://reviews.llvm.org/D64232 [analyzer] Prune calls to functions with linear CFGs that return a non-zero constrained value 
    [2] https://reviews.llvm.org/D64287 [analyzer] Track the right hand side of the last store regardless of its value
    [3] https://reviews.llvm.org/D64270 [analyzer][NFC] Prepare visitors for different tracking kinds

    [4] https://reviews.llvm.org/D64272 [analyzer] Note last writes to a condition only in a nested stackframe

    [5] https://reviews.llvm.org/D65287 [analyzer][CFG] Don't track the condition of asserts
    [6] https://reviews.llvm.org/D65575 [analyzer] Mention whether an event is about a condition in a bug report part 1
    [7] https://reviews.llvm.org/D65724 [analyzer] Don't make ConditionBRVisitor events prunable when the condition is an interesting field
    [8] https://reviews.llvm.org/D65725 [analyzer] Mention whether an event is about a condition in a bug report part 2

    Conclusions:

    Shockingly, no condition tracking related changes were made in the FINAL run for either Bitcoin or Xerces, so we only have LLVM/Clang to talk about. This time, I added comments, which, after clicking on a report, can be retrieved by clicking on 'Comments' in the upper right corner. These comments are far more precise than the notes I left previously.


    The negatives:
    1. Extra notes to functions following this pattern were very-very common:

    bool a(int b) {
      return b == 0;
      // Assuming 'b' is equal to 0
      // Returning the value 1, which will be (a part of a) condition
    }

    void f(int b) {
      int *x = 0;
      if (a(b)) // call to 'a', returning from 'a'
        *x = 5; // nullptr dereference
    }

    These notes are totally meaningless, and they aren't pruned out by [1] because the assumption notes are non-prunable (they explain a variable, b in this case, that is marked as interesting, as the return value is tracked by ReturnVisitor). A possible solution would be to prune linear functions in ConditionBRVisitor as well similarly to [1], but then we'd lose the assumption note. Instead, moving the non-prunable assumption note to the actual collapse point would be better, but a quick look at the generated ExplodedGraph reveals that this no longer an bug report construction issue: the collapse point is in fact at the return statement, rather then the condition.

    So, I think the bug report should always explain how the analyzer thinks. Ideally, this should be identical to how the bug could be reproduced, but if it is not (in this case the assumption should be made when a(b) is the condition), maybe the logic of the analysis should be changed instead.


    This is due to the eagerly-assume behavior. The state split does actually happen at == or ! rather than at the if-statement.

    I guess you could check if the node is wearing an "ExprEngine: Eagerly Assume" tag.


    2. I didn't come across this too often, but it happened:

    int getInt(); int getInt2();

    bool a() {
      return getInt2() && getInt();
      // Returning value, which will be (a part of a) condition
    }

    void f() {
      int *x = 0;

      if (a()) // call to 'a', returning from 'a'
        *x = 5; // nullptr dereference
    }


    This note wasn't pruned because a() has in fact more than 3 basic blocks, but it really doesn't change anything. I guess we *could* prune it, but I'm leaning on accepting it as a sacrifice.


    I guess it depends:

    - If we're assuming that the condition is true, and the function returns A && B, the note is indeed redundant.
    - If we're assuming that the condition is true, and the function returns A || B, it's worth mentioning whether we think that A is true or we think that B is true.
    - If we're assuming that the condition is false, and the function returns A && B, it's worth mentioning whether we think that A is false or we think that B is false.
    - If we're assuming that the condition is false, and the function returns A || B, the note is indeed redundant.


    3. Some function calls are lost due to retrieving information from nested stack frames only, rather than different stack frames. I only encountered this when the condition variable was invalidated: The "AFTER tracking conditions WITH improved moderation" runs display the path to the invalidation point, yet the FINAL runs do not.


    4. Calls to operator!= in foreach loops -- Are these necessary? Is there any, even articial cases where this is actually meaningful? This is pretty much the only non-constructive addition of notes that are introduced only because of condition tracking.


    Mmm, yeah, i'd rather skip them. We don't make much sense out of iterators anyway. I wish IteratorChecker could provide us with better notes.

    Positives:

    In general, the wording as the analyses were run may be imperfect, but they indicate what the message is about very precisely. The path of execution is much better explained, and even if the extra function call isn't meaningful, the note messages state clearly that we're only talking about a condition, I can skip them without being bothered by it too much. I am given extra information without the cost of polluting the rest of the report.

    Here is a collection of my favorites, though I found most of the extra notes nice:

    1. Here, we encounter a nullpointer dereference issue. Op0 is assumed to be equal to Op1, but only due to condition tracking do we explain that Op1 is believed to be null, and THAT is why this assumption (Op1 == Op0) is so important!



    The note is indeed extremely helpful, but the warning itself should have been suppressed by the "inlined defensive check" heuristic. I guess the heuristic doesn't know how to carry over to the other side of the `==`.


    2. The seldom addition of extra "Returning value, which will be (a part of a) condition" notes, love them!


    3. This one is weird, I'm not yet sure how this note came about, but yet again, it isn't clear AT ALL in the original report why CountS will be a source of a null dereference error. The extra note tells us that CountS is non-null, but its pointee is.


    You're talking about the "Assuming pointer value is null" thingy? I suspect that it's a bug and the note is in fact meaningless. See also https://reviews.llvm.org/D65889?id=214186#inline-590619 - i've seen them before but i suspect that i suddenly see more of them these days. Generally, i still don't understand the report after seeing these notes. Even if the notes tell anything about the pointee, the code they're attached to doesn't.

    I also don't understand why did we bring in the copy-constructor. Was there an invalidation of all heap going on that also touched *CountS?

    Also, adding the actual mail that was lost ;)

    On Wed, 24 Jul 2019 at 13:57, Kristóf Umann <[hidden email]> wrote:


    On Wed, 24 Jul 2019 at 04:29, Artem Dergachev <[hidden email]> wrote:
    Xerces - DOMRangeImpl.cpp: Ugh, are those "Value assigned to..." notes triggered by invalidation? I have a plan of my own to wipe such notes out (or at least formulate them more carefully), so i guess it's not an action item for you (nor much of a regression), but still ugh. Another thing to think about for those is to suppress the warning entirely when a region that stores is important condition is first assumed to contain false, then invalidated, then assumed to contain true.

    Totally agreed.
     
    Xerces - XMLString.hpp: Mmm, i guess passing unconstrained values as parameters is also not very meaningful. It doesn't look like it's a *big* problem, but i guess it's worth considering fixing eventually.

    In this particular case, partly due to me not being familiar with the code, I found the note helpful, but in LLVM there were plenty of reports where I didn't feel this way, so I'll get that fixed.
     
    > Assert conditions are not yet ignored, I have a neat solution locally

    Just to make sure - do you have a test case with control flow within the condition, eg. `assert((a || b) && "the universe is collapsing")`?

    I don't :) Thanks!
     
    On 7/23/19 12:49 PM, Kristóf Umann wrote:
    I'm happy to delight you all with some more results! I was far more strict on my judgement this time around, marking a report good when I genuinely believed that the note made the report better.

    All the runs were made on monorepo commit  db4e335b8643056f5afa2a0d8d175d95b1fb7e28  with the following patches applied:

    BEFORE tracking condition:  Without any changes being made, default CodeChecker settings.
    AFTER tracking conditions: Without any changes being made, track-conditions set to true.
    AFTER tracking conditions + DEBUG notes:  Without any changes being made, track-conditions and track-conditions-debug set to true.
    AFTER linear pruning (or similar run name): [1] applied, track-conditions set to true
    AFTER tracking conditions WITH improved moderation: [1, 2, 3, 4] applied, track-conditions set to true (stupid name but it's gonna stay like this for now :) )
    AFTER tracking conditions WITH improved moderation: [1, 2, 3, 4] applied, track-conditions and track-conditions-debug  set to true
    [1] https://reviews.llvm.org/D64232 [analyzer] Prune calls to functions with linear CFGs that return a non-zero constrained value 
    [2] https://reviews.llvm.org/D64287 [analyzer] Track the right hand side of the last store regardless of its value

    [3] https://reviews.llvm.org/D64270 [analyzer][NFC] Prepare visitors for different tracking kinds

    [4] https://reviews.llvm.org/D64272 [analyzer] Note last writes to a condition only in a nested stackframe



    Some conclusions:
    • [4] Actually notes last writes in different, not nested stack frames. Gotta fix that.
    • [1] Returning an unconstrained value when the function is linear is never meaningful. Not for conditions, not for anything else. Gotta fix that too. It's worth talking about whether we should prune these for conditions even if the function isn't linear.
    • [1] This one gets rid of almost all the operator bool calls. Maybe in the rare case it doesn't, we should preserve them? I always planned to get rid of calls to operator bool, but now I'm hesitant.
    • Assert conditions are not yet ignored, I have a neat solution locally, but I haven't published or tested it yet.

    One more thing: If the condition is a binary operator, like (B || A) is assumed true because A is true, or (A && B) is assumed false because A is false, we should only track A.
     
    There honestly isn't that much I have on my mind, I think after the next round of analyses we should be good! I really should've made an analysis with all the non-condition tracking changes to get an even better perspective, so I'll do that next time.

    On Tue, 25 Jun 2019 at 04:00, Artem Dergachev <[hidden email]> wrote:
    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?
     
    The report is now untouched! 

    > 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?
     
    I'll make a testcase for that. Honestly, I'm thinking of reimplementing the visitor as well, so that I'll collect the control dependencies in a set when the visitor object is created, and track them at BlockExit locations, that should limit it, because yeah, I believe they originate from the de-duplication.

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

    This time around, BodyFarm.cpp is in the same boat. I really just made a fundamentally bad (like, really bad) report even worse.


    _______________________________________________
    cfe-dev mailing list
    [hidden email]
    https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
    Reply | Threaded
    Open this post in threaded view
    |

    Re: [analyzer] Tracking values for generating bug reports

    Nathan Ridge via cfe-dev
    What are your feelings on this run? I'm personally pleased with how things look like, and the only thing I'd like to add is pruning operator!=, though I do not plan on doing any more analyses.

    On Sat, 10 Aug 2019 at 03:48, Artem Dergachev <[hidden email]> wrote:


    On 8/8/19 2:05 PM, Kristóf Umann wrote:

    The negatives:
    1. Extra notes to functions following this pattern were very-very common:

    bool a(int b) {
      return b == 0;
      // Assuming 'b' is equal to 0
      // Returning the value 1, which will be (a part of a) condition
    }

    void f(int b) {
      int *x = 0;
      if (a(b)) // call to 'a', returning from 'a'
        *x = 5; // nullptr dereference
    }

    These notes are totally meaningless, and they aren't pruned out by [1] because the assumption notes are non-prunable (they explain a variable, b in this case, that is marked as interesting, as the return value is tracked by ReturnVisitor). A possible solution would be to prune linear functions in ConditionBRVisitor as well similarly to [1], but then we'd lose the assumption note. Instead, moving the non-prunable assumption note to the actual collapse point would be better, but a quick look at the generated ExplodedGraph reveals that this no longer an bug report construction issue: the collapse point is in fact at the return statement, rather then the condition.

    So, I think the bug report should always explain how the analyzer thinks. Ideally, this should be identical to how the bug could be reproduced, but if it is not (in this case the assumption should be made when a(b) is the condition), maybe the logic of the analysis should be changed instead.


    This is due to the eagerly-assume behavior. The state split does actually happen at == or ! rather than at the if-statement.

    I guess you could check if the node is wearing an "ExprEngine: Eagerly Assume" tag.


    Then I guess we should leave this as-is.
    2. I didn't come across this too often, but it happened:

    int getInt(); int getInt2();

    bool a() {
      return getInt2() && getInt();
      // Returning value, which will be (a part of a) condition
    }

    void f() {
      int *x = 0;

      if (a()) // call to 'a', returning from 'a'
        *x = 5; // nullptr dereference
    }


    This note wasn't pruned because a() has in fact more than 3 basic blocks, but it really doesn't change anything. I guess we *could* prune it, but I'm leaning on accepting it as a sacrifice.


    I guess it depends:

    - If we're assuming that the condition is true, and the function returns A && B, the note is indeed redundant.
    - If we're assuming that the condition is true, and the function returns A || B, it's worth mentioning whether we think that A is true or we think that B is true.
    - If we're assuming that the condition is false, and the function returns A && B, it's worth mentioning whether we think that A is false or we think that B is false.
    - If we're assuming that the condition is false, and the function returns A || B, the note is indeed redundant.

    Yea, I may fix it up later, though I'm not *immediately* worried about it since this problem isn't condition tracking specific. 

    4. Calls to operator!= in foreach loops -- Are these necessary? Is there any, even articial cases where this is actually meaningful? This is pretty much the only non-constructive addition of notes that are introduced only because of condition tracking.


    Mmm, yeah, i'd rather skip them. We don't make much sense out of iterators anyway. I wish IteratorChecker could provide us with better notes.


    I guess I'll fix this up quickly before making this on-by-default. 
    Positives:

    In general, the wording as the analyses were run may be imperfect, but they indicate what the message is about very precisely. The path of execution is much better explained, and even if the extra function call isn't meaningful, the note messages state clearly that we're only talking about a condition, I can skip them without being bothered by it too much. I am given extra information without the cost of polluting the rest of the report.

    Here is a collection of my favorites, though I found most of the extra notes nice:

    1. Here, we encounter a nullpointer dereference issue. Op0 is assumed to be equal to Op1, but only due to condition tracking do we explain that Op1 is believed to be null, and THAT is why this assumption (Op1 == Op0) is so important!



    The note is indeed extremely helpful, but the warning itself should have been suppressed by the "inlined defensive check" heuristic. I guess the heuristic doesn't know how to carry over to the other side of the `==`.

    You're talking about the "Assuming pointer value is null" thingy? I suspect that it's a bug and the note is in fact meaningless. See also https://reviews.llvm.org/D65889?id=214186#inline-590619 - i've seen them before but i suspect that i suddenly see more of them these days. Generally, i still don't understand the report after seeing these notes. Even if the notes tell anything about the pointee, the code they're attached to doesn't.

    I also don't understand why did we bring in the copy-constructor. Was there an invalidation of all heap going on that also touched *CountS?

    The answer lies in the DEBUG notes run: We already track CollectionS to the point where it was initialized, and FindLastStoreBRVisitor tracks the right hand side of it. This will trigger control dependency calculation again, resulting in State being tracked, which leads to that monster of a copy constructor call, where we explain why we believed State to be null. The call to IntrusiveRefCntPtr::operator bool was pruned, but it explains why we placed a note about Obj, because thats what it returns. I do wonder however why it wasn't accompanied with ", which will be (a part of a) condition", I'll take a look.
     

    _______________________________________________
    cfe-dev mailing list
    [hidden email]
    https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
    Reply | Threaded
    Open this post in threaded view
    |

    Re: [analyzer] Tracking values for generating bug reports

    Nathan Ridge via cfe-dev
    4. Calls to operator!= in foreach loops -- Are these necessary? Is there any, even articial cases where this is actually meaningful? This is pretty much the only non-constructive addition of notes that are introduced only because of condition tracking.


    Mmm, yeah, i'd rather skip them. We don't make much sense out of iterators anyway. I wish IteratorChecker could provide us with better notes.


    I guess I'll fix this up quickly before making this on-by-default. 

    That was easier then expected :)

    You're talking about the "Assuming pointer value is null" thingy? I suspect that it's a bug and the note is in fact meaningless. See also https://reviews.llvm.org/D65889?id=214186#inline-590619 - i've seen them before but i suspect that i suddenly see more of them these days. Generally, i still don't understand the report after seeing these notes. Even if the notes tell anything about the pointee, the code they're attached to doesn't.

    I also don't understand why did we bring in the copy-constructor. Was there an invalidation of all heap going on that also touched *CountS?

    The answer lies in the DEBUG notes run: We already track CollectionS to the point where it was initialized, and FindLastStoreBRVisitor tracks the right hand side of it. This will trigger control dependency calculation again, resulting in State being tracked, which leads to that monster of a copy constructor call, where we explain why we believed State to be null. The call to IntrusiveRefCntPtr::operator bool was pruned, but it explains why we placed a note about Obj, because thats what it returns. I do wonder however why it wasn't accompanied with ", which will be (a part of a) condition", I'll take a look.

    This took an unbelievable amount headaches to track (haha) down, but I don't really understand what's happening. I originally thought the that it would help if the debug notes the non-prunable, but the extra information I got didn't help much. It should state that 'Obj' is a condition, and nothing screams from the code as an explanation why it doesn't. I'll try to creduce this little more later on, but its difficult to make an interestingness script for, and since this is the one and only case where this occurred, I'll prioritize more pressing matters for now.


    _______________________________________________
    cfe-dev mailing list
    [hidden email]
    https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev