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