<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
</head>
<body text="#000000" bgcolor="#FFFFFF">
Interesting.<br>
<br>
Condition on line 12 would not be our control dependency - neither
in example 1 nor in example 2, simply because there's nothing
interesting within either branches of that if-statement. The 'new
int' assignment would have been interesting if we solved the
should-not-have-happened problem of "x should not have been
overwritten", but for now we don't do that.<br>
<br>
At the same time, condition on line 16 would still be a control
dependency of our report in both examples, because this is where the
actual crash happens. So we will have a note on line 05 in both
cases, even if it's completely unnecessary in the second example.<br>
<br>
We would indeed never have a note on line 10. This is, in fact, a
dead store, this value is never used, so we wouldn't be able to
track anything back to it.<br>
<br>
<div class="moz-cite-prefix">On 5/30/19 4:48 PM, Kristóf Umann
wrote:<br>
</div>
<blockquote type="cite"
cite="mid:CAGcXOD45pbWdQGmSdUtiMMNNNGfSo1=kqjBiTBZXPybcCM=v6w@mail.gmail.com">
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<div dir="ltr">
<div>Allow me to elaborate.</div>
<div><span><br>
</span></div>
<div><span><b><font size="4">Example 1.:</font></b></span></div>
<div>
<p dir="ltr"
style="font-family:Roboto,RobotoDraft,Helvetica,Arial,sans-serif;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">01 int flag;</span></p>
<p dir="ltr"
style="font-family:Roboto,RobotoDraft,Helvetica,Arial,sans-serif;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">02 bool coin();</span></p>
<p dir="ltr"
style="font-family:Roboto,RobotoDraft,Helvetica,Arial,sans-serif;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">03 </span></p>
<p dir="ltr"
style="font-family:Roboto,RobotoDraft,Helvetica,Arial,sans-serif;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">04 void foo() {</span></p>
<p dir="ltr"
style="font-family:Roboto,RobotoDraft,Helvetica,Arial,sans-serif;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">05 flag = coin(); // no note</span></p>
<p dir="ltr"
style="font-family:Roboto,RobotoDraft,Helvetica,Arial,sans-serif;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">06 }</span></p>
<p dir="ltr"
style="font-family:Roboto,RobotoDraft,Helvetica,Arial,sans-serif;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">07 </span></p>
<p dir="ltr"
style="font-family:Roboto,RobotoDraft,Helvetica,Arial,sans-serif;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">08 int main() {</span></p>
<p dir="ltr"
style="font-family:Roboto,RobotoDraft,Helvetica,Arial,sans-serif;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">09 int *x = 0; // x initialized to 0</span></p>
<p dir="ltr"
style="font-family:Roboto,RobotoDraft,Helvetica,Arial,sans-serif;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">10 flag = 1;</span></p>
<p dir="ltr"
style="font-family:Roboto,RobotoDraft,Helvetica,Arial,sans-serif;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">11 foo();</span></p>
<p dir="ltr"
style="font-family:Roboto,RobotoDraft,Helvetica,Arial,sans-serif;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">12 if (flag) // assumed false</span></p>
<p dir="ltr"
style="font-family:Roboto,RobotoDraft,Helvetica,Arial,sans-serif;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">13 x = new int;</span></p>
<p dir="ltr"
style="font-family:Roboto,RobotoDraft,Helvetica,Arial,sans-serif;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">14 foo();</span></p>
<p dir="ltr"
style="font-family:Roboto,RobotoDraft,Helvetica,Arial,sans-serif;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">15 </span></p>
<p dir="ltr"
style="font-family:Roboto,RobotoDraft,Helvetica,Arial,sans-serif;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">16 if (flag) // assumed true</span></p>
<p dir="ltr"
style="font-family:Roboto,RobotoDraft,Helvetica,Arial,sans-serif;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">17 *x = 5; // warn</span></p>
<p dir="ltr"
style="font-family:Roboto,RobotoDraft,Helvetica,Arial,sans-serif;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">18 }</span></p>
</div>
<div><span><br>
</span></div>
<div><span><b><font size="4">Example 2.: (note the change on
line 15)</font></b></span></div>
<div>
<p dir="ltr"
style="font-family:Roboto,RobotoDraft,Helvetica,Arial,sans-serif;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">01 int flag;</span></p>
<p dir="ltr"
style="font-family:Roboto,RobotoDraft,Helvetica,Arial,sans-serif;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">02 bool coin();</span></p>
<p dir="ltr"
style="font-family:Roboto,RobotoDraft,Helvetica,Arial,sans-serif;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">03 </span></p>
<p dir="ltr"
style="font-family:Roboto,RobotoDraft,Helvetica,Arial,sans-serif;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">04 void foo() {</span></p>
<p dir="ltr"
style="font-family:Roboto,RobotoDraft,Helvetica,Arial,sans-serif;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">05 flag = coin(); // no note</span></p>
<p dir="ltr"
style="font-family:Roboto,RobotoDraft,Helvetica,Arial,sans-serif;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">06 }</span></p>
<p dir="ltr"
style="font-family:Roboto,RobotoDraft,Helvetica,Arial,sans-serif;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">07 </span></p>
<p dir="ltr"
style="font-family:Roboto,RobotoDraft,Helvetica,Arial,sans-serif;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">08 int main() {</span></p>
<p dir="ltr"
style="font-family:Roboto,RobotoDraft,Helvetica,Arial,sans-serif;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">09 int *x = 0;</span></p>
<p dir="ltr"
style="font-family:Roboto,RobotoDraft,Helvetica,Arial,sans-serif;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">10 flag = 1;</span></p>
<p dir="ltr"
style="font-family:Roboto,RobotoDraft,Helvetica,Arial,sans-serif;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">11 foo();</span></p>
<p dir="ltr"
style="font-family:Roboto,RobotoDraft,Helvetica,Arial,sans-serif;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">12 if (flag) // assumed false</span></p>
<p dir="ltr"
style="font-family:Roboto,RobotoDraft,Helvetica,Arial,sans-serif;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">13 x = new int;</span></p>
<p dir="ltr"
style="font-family:Roboto,RobotoDraft,Helvetica,Arial,sans-serif;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">14 foo();</span></p>
<p dir="ltr"
style="font-family:Roboto,RobotoDraft,Helvetica,Arial,sans-serif;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">15 x = 0; // x set to 0</span></p>
<p dir="ltr"
style="font-family:Roboto,RobotoDraft,Helvetica,Arial,sans-serif;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">16 if (flag) // assumed true</span></p>
<p dir="ltr"
style="font-family:Roboto,RobotoDraft,Helvetica,Arial,sans-serif;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">17 *x = 5; // warn</span></p>
<p dir="ltr"
style="font-family:Roboto,RobotoDraft,Helvetica,Arial,sans-serif;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">18 }</span></p>
</div>
<div><span
id="gmail-docs-internal-guid-4afc448c-7fff-3e2d-c87d-f55781fa8e89">
<div dir="ltr" style="margin-left:0pt"><br>
</div>
<div style="margin-left:0pt">By tweaking <font
face="courier new, monospace">trackExpressionValue</font>
a bit:</div>
<div dir="ltr" style="margin-left:0pt"><br>
</div>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">bool trackExpressionValue(const ExplodedNode *N,</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap"> const Stmt *S, BugReport &R,</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap"> bool IsArg=false,</span></p>
<p dir="ltr"
style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:9pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap"> bool EnableNullFPSuppression=true);</span></p>
<br>
<span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">Should a block </span><span style="font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">B</span><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap"> in the bug path be a control dependency of </span><span style="font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">N</span><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">, track the expression value in the condition of </span><span style="font-size:11pt;font-family:"Courier New";color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">B</span><span style="font-size:11pt;font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">. With that, I believe we should get a note for statement 14. For statement 10, we still wouldn’t get a note saying that flag’s value was invalidated (I fear), but it’s more of a should-not-have-happened case. For Example 2 however, we’d get a pretty much perfect bug report.</span></span><br>
</div>
<br>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">On Fri, 31 May 2019 at
00:16, Kristóf Umann <<a
href="mailto:dkszelethus@gmail.com" moz-do-not-send="true">dkszelethus@gmail.com</a>>
wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px
0.8ex;border-left:1px solid
rgb(204,204,204);padding-left:1ex">
<div dir="ltr">
<div dir="ltr"><br>
</div>
<br>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">On Mon, 27 May 2019 at
19:48, Artem Dergachev <<a
href="mailto:noqnoqneo@gmail.com" target="_blank"
moz-do-not-send="true">noqnoqneo@gmail.com</a>>
wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px
0px 0.8ex;border-left:1px solid
rgb(204,204,204);padding-left:1ex"><br>
<br>
On 5/27/19 10:12 AM, Gábor Horváth wrote:<br>
> Hi!<br>
><br>
> I wanted to share some of my points as well but
had little time to do so.<br>
><br>
> Artem identified two kinds of issues. One of
which has all the <br>
> information available in the bug path (in his
terminology: <br>
> must-have-happened) and the other which has not (
<br>
> should-not-have-happened). The goal is the same
in both of the cases, <br>
> identify all dependencies including control and
data dependencies. The <br>
> main difference is that in one case we could use
all the information <br>
> available in the bug path while in the other we
cannot.<br>
><br>
> 1. must-have-happened:<br>
> Since the bug-path contains all the information
we need, I do agree <br>
> with Artem using bug path visitors might be
sufficient. I do not know <br>
> how reliable `trackExpressionValue` is in
identifying data <br>
> dependencies, but revising it could be one step
in GSoC. For example, <br>
> after quickly skimming through the implementation
I am not sure if it <br>
> is able to track the source of a constant value
that was constant <br>
> folded during the symbolic execution from
different values.<br>
<br>
It should be able to, because that's how inlined
defensive check <br>
suppressions work.<br>
</blockquote>
<div><br>
</div>
<div>I recently finished (not yet published) my work on
implementing control dependencies for clang's CFG via
LLVM's <font face="courier new, monospace">IDFCalculator</font>.
Theoretically speaking, by simply tracking the
variables in the block that is a control dependency of
the block that is being tracked, we should be able to
get a proper bug report for Example 1? From afar, it
seems reasonable.</div>
<div> </div>
<blockquote class="gmail_quote" style="margin:0px 0px
0px 0.8ex;border-left:1px solid
rgb(204,204,204);padding-left:1ex">
> Only if we had a way to test this functionality
in isolation quickly <br>
> :) I think making that possible would also be a
valuable addition.<br>
><br>
> For control dependencies, it is great that LLVM
already has some <br>
> algorithms to calculate dominator sets and it
might be possible to <br>
> make that work for the Clang CFG.<br>
><br>
> In my opinion, if you only tackle these problems
by the end of the <br>
> summer your project already brought great value
to the community.<br>
><br>
> 2. should-not-have-happened<br>
> This category cannot be solved only using
visitors for sure. So we <br>
> might end up with an implementation for this
problem that is <br>
> completely separate from the previous one (maybe
except for getting <br>
> control dependencies?). As Artem pointed out, we
might query some <br>
> information from the analyzer e.g. which
functions were inlined. One <br>
> option is to use a slicing algorithm here.
However, we should make <br>
> sure that the way a function is conservatively
evaluated by the <br>
> slicing algorithm and the analyzer is compatible.
E.g.: if the <br>
> analyzer does not invalidate a memory region
during evaluating the <br>
> call, the statement should not be considered as
relevant for the <br>
> variable in question. We have several challenges
here, the analyzer <br>
> reasons about memory regions while the slicing
algorithm will probably <br>
> not. Also, we need to do something with pointers,
since we do not want <br>
> to implement a full-fledged pointer analysis. We
also need to decide <br>
> how to represent arrays, structures etc.<br>
><br>
> I skimmed through the algorithm in the google
docs, and I think there <br>
> are some other details we need to work out. For
example, you never <br>
> remove anything from the set of relevant
variables. Consider the <br>
> following example:<br>
> x = 5;<br>
> y = x + 2;<br>
> y = 2;<br>
> z = y + 3;<br>
><br>
> Whit the slicing criterion (z = y + 3). Here,
once y is overwritten <br>
> with 2, it is no longer relevant, sox should not
end up in the slice. <br>
> The algorithm you proposed will not handle this
correctly (yet). Also <br>
> I am not sure if we actually need
therelevant_variable_map or having a <br>
> set will be sufficient.<br>
><br>
> Regards,<br>
> Gabor<br>
><br>
> On Mon, 27 May 2019 at 12:52, Kristóf Umann <<a
href="mailto:dkszelethus@gmail.com" target="_blank"
moz-do-not-send="true">dkszelethus@gmail.com</a> <br>
> <mailto:<a href="mailto:dkszelethus@gmail.com"
target="_blank" moz-do-not-send="true">dkszelethus@gmail.com</a>>>
wrote:<br>
><br>
> + Ádám Balogh<br>
><br>
> On Fri, 24 May 2019 at 23:31, Artem Dergachev
<<a href="mailto:noqnoqneo@gmail.com"
target="_blank" moz-do-not-send="true">noqnoqneo@gmail.com</a><br>
> <mailto:<a
href="mailto:noqnoqneo@gmail.com" target="_blank"
moz-do-not-send="true">noqnoqneo@gmail.com</a>>>
wrote:<br>
><br>
> Ok, i think i have a little bit of
clarity.<br>
><br>
> Let's first talk about must-have-happened
problems. For instance,<br>
><br>
> int *foo() {<br>
> return coin() ? new int : nullptr;
// needs note<br>
> }<br>
> void bar() {<br>
> int *x = foo();<br>
> *x = 1; // warning: null dereference<br>
> }<br>
><br>
> In this case trackExpressionValue solves
the<br>
> "must-have-happened" problem of "x
must-have been assigned a<br>
> null pointer value" by displaying a note
when foo() returns<br>
> nullptr. This currently more or less
works correctly - there<br>
> are a lot of bugs but the overall idea
behind<br>
> trackExpressionValue is correct.<br>
><br>
> Example 1 in your document is another
example of a<br>
> must-have-happened problem: in order for
the report to be<br>
> valid, we need to show that 'flag'
must-have-changed between<br>
> line 17 and line 13. That's something
that the Static Analyzer<br>
> currently cannot handle and you plan to
improve upon it.<br>
><br>
> Hʏᴘᴏᴛʜᴇsɪs1. All "must-have-happened"
problems should be<br>
> solved with a bug visitor. We don't need
any new analysis<br>
> algorithm for that.<br>
><br>
> In particular, i believe that Example 1
can be solved by<br>
> extending trackExpressionValue() with a
bug visitor that<br>
> detects control-flow-dependencies via
this approach of yours:<br>
><br>
> > "Check whether the statement is a
control dependency of<br>
> Statement 18 with dominator sets: 18
doesn't post dominate 17,<br>
> but every statement in between them does,
meaning that 17 is a<br>
> control dependency of 18."<br>
><br>
> I.e., while ascending through
ExplodedGraph, we pick<br>
> interesting statements and perform this
domination check on<br>
> their predecessor nodes until we reach
the control dependency,<br>
> then we track the control dependency
recursively by adding<br>
> more visitors.<br>
><br>
> I think this is the first thing we should
try on our GSoC.<br>
><br>
> The reason why i believe that Hypothesis
1 is true is that all<br>
> the information that we need is fully
contained in the bug<br>
> path. If something must have happened on
the path, then it's<br>
> probably in the path and we can figure it
out by looking at<br>
> the path. If something must have happened
on the path and it's<br>
> not in the path, then why did we emit a
warning in the first<br>
> place?<br>
><br>
> ==============<br>
><br>
> Now, to should-not-have-happened
problems. The main motivating<br>
> example is:<br>
><br>
> void foo(int *y) {<br>
> if (coin()) // needs note<br>
> *y = 1;<br>
> }<br>
> void bar() {<br>
> int x;<br>
> foo(&x);<br>
> use(x); // warning: use of
uninitialized value<br>
> }<br>
><br>
> In order to make the warning
comprehensible, we have to<br>
> explain to the user why do we think that
'x' is uninitialized,<br>
> as it clearly "should-not-have-been"
initialized for the<br>
> warning to be correct. For that purpose
it is absolutely<br>
> essential to display the execution path
within the inlined<br>
> call to foo().<br>
><br>
> One way to achieve that would be to
display *all* execution<br>
> path and leave it up to the user to see
that the event that<br>
> should-not-have-happened has indeed never
happened.<br>
><br>
> That, however, would be overwhelming, so
we use "path pruning"<br>
> that cuts away execution paths in inlined
calls that are known<br>
> to have no interesting events happening.
Which, in turn, makes<br>
> us incapable of solving
should-not-have-happened problems, as<br>
> it's the whole point of the problem to
display execution path<br>
> in inlined functions in which nothing has
happened.<br>
><br>
> In order to figure this out, we need to
learn how to<br>
> discriminate between inlined calls in
which nothing<br>
> interesting *could* have happened in the
first place and<br>
> inlined calls in which something
interesting could have<br>
> happened but *didn't*.<br>
><br>
> NoStoreFuncVisitor solves this problem
for the example above.<br>
> The visitor notices that the local
variable is passed by<br>
> non-const pointer into the inlined call
and the call<br>
> syntactically contains assignments
through this pointer,<br>
> therefore this call *could* have
initialized the value. The<br>
> visitor then suppresses pruning of this
call by emitting an<br>
> interesting note within the call
("returning without<br>
> initializing '*y'"...).<br>
><br>
> However, AST-based analysis in
NoStoreFuncVisitor is very<br>
> primitive and easy to trick. A more
sophisticated analysis is<br>
> clearly necessary.<br>
><br>
> The second thing we can try in our GSoC
is to come up with a<br>
> better analysis specifically for the
uninitialized value<br>
> checker, because we already have a place
to stick it into and<br>
> we know how exactly do we want to consume
the result of such<br>
> analysis and evaluate it.<br>
><br>
> The third thing we can try in our GSoC is
to come up with more<br>
> such analysis for other checkers and
other<br>
> should-have-happened problems and see if
a reusable framework<br>
> for creating such analyses can be
implemented.<br>
><br>
><br>
> On 5/23/19 1:25 PM, Kristóf Umann wrote:<br>
>><br>
>><br>
>> On Thu, 23 May 2019 at 21:58, Kristóf
Umann<br>
>> <<a
href="mailto:dkszelethus@gmail.com" target="_blank"
moz-do-not-send="true">dkszelethus@gmail.com</a>
<mailto:<a href="mailto:dkszelethus@gmail.com"
target="_blank" moz-do-not-send="true">dkszelethus@gmail.com</a>>>
wrote:<br>
>><br>
>> Please let me know if I didn't
address something you<br>
>> mentioned!<br>
>><br>
>> On Thu, 23 May 2019 at 02:29,
Artem Dergachev<br>
>> <<a
href="mailto:noqnoqneo@gmail.com" target="_blank"
moz-do-not-send="true">noqnoqneo@gmail.com</a>
<mailto:<a href="mailto:noqnoqneo@gmail.com"
target="_blank" moz-do-not-send="true">noqnoqneo@gmail.com</a>>>
wrote:<br>
>><br>
>> My primary question is, how
do you plan to use the<br>
>> data that you obtain via your
analysis?<br>
>><br>
>><br>
>> Gather relevant statements. Keep
ExplodedNodes in the<br>
>> bugpath for which
PathDiagnosticLocation::getStmt() is in<br>
>> the set (or, something like that
at least). But honestly,<br>
>> I didn't think too much about
that yet :^) I guess we<br>
>> could just gather ExplodedNodes
rather than statements,<br>
>> we'll see.<br>
>><br>
>> Like, do you plan to
backtrack the value of all<br>
>> relevant variables and/or
expressions in the final<br>
>> bug report that were also
encountered along the bug<br>
>> path? If yes, then is it
possible that the slicing<br>
>> criterion gets updated in the
process and you'll have<br>
>> to re-run the CFG-based
analysis to take it into account?<br>
>><br>
>><br>
>> No, the slicing criterion is what
it is, and will not<br>
>> change. The set of relevant
statements to the slicing<br>
>> criterion define the actual
program slice, which is<br>
>> basically the thing we're going
for in this project. When<br>
>> it turns out that a value of a
variable directly affects<br>
>> a variable in the slicing
criterion (either through data<br>
>> or control dependency), we just
add it to the set of<br>
>> relevant variables, and then if
something in the set of<br>
>> relevant variables is affected
(some statements or<br>
>> variables turn out to be a
control/data dependencies to<br>
>> them), then it's added to the
respective relevancy sets.<br>
>> Should we only traverse the basic
blocks the analyzer<br>
>> visited, I think we can pull off
the slicing with a<br>
>> single pass.<br>
>><br>
>><br>
>> We'll see about that single pass
thing though. I'm gathering<br>
>> some tricky examples in the document
I shared and working on<br>
>> a neat algorithm.<br>
>><br>
>> > What would also be
really great is to assist this<br>
>> traversal with the
information the analyzer already<br>
>> has, essentially only
inspecting basic blocks the<br>
>> analyzer actually visits.<br>
>><br>
>> You mean visits on the
current bug path or visits on<br>
>> the equivalence class of bugs
or visits in general<br>
>> during analysis?<br>
>><br>
>> Regardless, for many problems
ideally we should<br>
>> traverse basic blocks that
the analyzer *didn't*<br>
>> visit (eg., if the function
didn't initialize the<br>
>> variable on the current path,
we're interested in<br>
>> parts of the code in which it
*did* initialize the<br>
>> variable, even though we
didn't necessarily have time<br>
>> to visit them).<br>
>><br>
>><br>
>> Well I mean slicing by definition
isn't intended to do<br>
>> that. The entire point of it is
to gather the smallest<br>
>> slice related to the slicing
criterion, and my project<br>
>> aims to fill in the gaps where we
don't provide enough<br>
>> information.<br>
>><br>
>> It actually sounds as if all
problems that we're<br>
>> trying to solve here can be
classified into<br>
>> "must-have-happened" problems
(eg., "variable<br>
>> must-have been declared
without initialization",<br>
>> "variable must-have been set
to nullptr", "memory<br>
>> must-have been allocated")
and<br>
>> "should-not-have-happened"
problems (eg., "variable<br>
>> should-not-have been
initialized", "null value<br>
>> should-not-have been
overwritten", "pointer<br>
>> should-not-have escaped").<br>
>><br>
>> For must-have-happened
problems, i'm recently under<br>
>> an impression that we should
suppress the bug report<br>
>> entirely when we fail to
solve them (i.e., if fail to<br>
>> explain to the user where
exactly does this happen,<br>
>> then the report is impossible
to understand anyway).<br>
>> This is currently a very big
problem for our null<br>
>> dereference checker on some
codebases, especially<br>
>> because it uses this tracking
for suppressions as<br>
>> well (aka inlined defensive
checks), so when it fails<br>
>> to track the variable it's
likely a legit false<br>
>> positive as well, not simply
a hard-to-understand report.<br>
>><br>
>><br>
>> I think this set calculating
approach inherently gathers<br>
>> far more information, allowing us
to make better<br>
>> judgement on whether we should
suppress the report.<br>
>><br>
>> For should-not-have-happened
problems i'm much more<br>
>> confused. We're talking about
looking for places<br>
>> where it *could* have
happened and then trying to<br>
>> explain to the user why none
of them have actually<br>
>> happened. I'm not sure what
are the consequences of<br>
>> failing to explain to the
user why didn't a<br>
>> particular piece of code do
something, because i've<br>
>> no idea how do users
intuitively figure out which<br>
>> code *could* have done these
things and which clearly<br>
>> couldn't.<br>
>><br>
>><br>
>> Im really at a loss here :) Can
you provide some example<br>
>> as to what a problematic
"must-have-happened" bug report<br>
>> would look like, and how would
you like to see it<br>
>> improved? Same for
"should-not-have-happened". Because as<br>
>> I understand it, and I might be
wrong, you have problems<br>
>> with this:<br>
>><br>
>> int a; // declaring a without
initializing<br>
>><br>
>> if (rand()) // assuming that the
condition is false<br>
>> a = 5;<br>
>><br>
>> print(a); // a is undef<br>
>><br>
>> And prefer to see this:<br>
>><br>
>> int a; // declaring a without
initializing<br>
>><br>
>> if (rand()) // should this
condition be false, a's value<br>
>> will be indeterministic<br>
>> a = 5; // writing to a skipped<br>
>><br>
>> print(a); // a is undef<br>
>><br>
>> and I just don't see how this
would be possible with<br>
>> slicing at all. Also, I can't see
how this would scale to<br>
>> real-world production code.<br>
>><br>
>><br>
>> On 5/22/19 4:11 PM, Kristóf
Umann wrote:<br>
>>><br>
>>> Hi!<br>
>>><br>
>>><br>
>>> I'd like to share some
thoughts about my GSoC<br>
>>> project, "Enhancing bug
reporting with static<br>
>>> backward program
slicing"[1].<br>
>>><br>
>>><br>
>>> My proposal is very
specific about whatI'm aiming to<br>
>>> improve on, but vague on
the howpart of it. This<br>
>>> mail aims to add clarify
some of this.<br>
>>><br>
>>><br>
>>> Program slicing is
essentially a technique of<br>
>>> discovering data and
control dependencies to the<br>
>>> slicing criterion, which
is a (statement, {set of<br>
>>> variables}) pair.
Fortunately, tools for control<br>
>>> dependencies, namely,
dominator set calculations are<br>
>>> already implemented, but
seems to be unstable with<br>
>>> clang's CFG. It would be
a great tool if I were able<br>
>>> to fix it.<br>
>>><br>
>>><br>
>>> While my proposal states
that I plan to implement an<br>
>>> AST-based solution, I'm
actually not sure that this<br>
>>> is the optimal approach.
We could instead inspect<br>
>>> CFG blocks in a backwards
manner (coupled with the<br>
>>> analyzer's call stack),
and gather relevant variable<br>
>>> in the meanwhile.<br>
>>><br>
>>><br>
>>> What would also be really
great is to assist this<br>
>>> traversal with the
information the analyzer already<br>
>>> has, essentially only
inspecting basic blocks the<br>
>>> analyzer actually visits.<br>
>>><br>
>>><br>
>>> Here’s my idea for an
algorithm (from the point of<br>
>>> the slicing criterion
already being constructed):<br>
>>><br>
>>> <a
href="https://docs.google.com/document/d/1Lx867o3meyQsj0WKOSWMdosSBdw2MUq1aIxyPJM6iLU/edit?usp=sharing"
rel="noreferrer" target="_blank"
moz-do-not-send="true">https://docs.google.com/document/d/1Lx867o3meyQsj0WKOSWMdosSBdw2MUq1aIxyPJM6iLU/edit?usp=sharing</a><br>
>>><br>
>>><br>
>>><br>
>>> Please note that this is
a veeery rough sketch, I<br>
>>> didn't think about every
edge case that exists, but<br>
>>> I think it's an okay
start.<br>
>>><br>
>>><br>
>>> [1]<br>
>>> <a
href="https://docs.google.com/document/d/1ci1BCAKojPlqIxIw1J_K2dnATA3z01PuwR_vHJS55TI/edit"
rel="noreferrer" target="_blank"
moz-do-not-send="true">https://docs.google.com/document/d/1ci1BCAKojPlqIxIw1J_K2dnATA3z01PuwR_vHJS55TI/edit</a><br>
>>><br>
>><br>
><br>
<br>
</blockquote>
</div>
</div>
</blockquote>
</div>
</div>
</blockquote>
<br>
</body>
</html>