<div dir="ltr"><div>I just realized after reading your answer how ambiguous my email was. When I said it is possible to trick the NoStoreFuncVisitor what I meant was to prevent it from emitting notes and thus pruning interesting parts of the bug path. But I am glad that we are actually on the same page regarding the value of detecting control dependencies. The example 4 you provided is a very compelling one :)</div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, 3 Apr 2019 at 23:16, Artem Dergachev <<a href="mailto:noqnoqneo@gmail.com">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">
  
    
  
  <div bgcolor="#FFFFFF">
    The thing in NoStoreFuncVisitor for IVars looks like it's just
    saying "let's see if there's a data dependency on at least one
    statement in this call". Given that the statement found by such AST
    matcher was not executed on the bug's execution path, there must be
    at least one control flow dependency in this function as well.<br>
    <br>
    I think this pattern-matching may only have false negatives, i.e.
    it's possible to write into a variable/field/ivar without producing
    an assignement-operator to a DeclRefExpr for that
    variable/field/ivar, but it's not possible to write an assignment
    into a DeclRefExpr for that variable/field/ivar without modifying
    the variable/field/ivar in the process. A more sophisticated
    analysis may find situations when such write is always done via an
    aliasing pointer, but i cannot think of anything else. Well, there's
    also the self-assignment cornercase, i.e. `x = x`, but that's
    esoteric.<br>
    <br>
    ------------------------<br>
    <br>
    Ok, i think i understand: one of the great goals for this project
    would be to correctly highlight control flow dependencies, which we
    currently don't do. I.e.:<br>
    <br>
    <b>Example 4.</b><br>
    <br>
    01  int flag;<br>
    02  <br>
    03  bool coin();<br>
    04  <br>
    05  void foo() {<br>
    06    flag = coin();<br>
    07  }<br>
    08  <br>
    09  void bar() {<br>
    10    int *x = 0;<br>
    11    // Set the flag to true.<br>
    12    flag = true;<br>
    13    foo();<br>
    14    if (flag) { // Taking false branch... wait, what?<br>
    15      x = new int;<br>
    16    }<br>
    17    foo();<br>
    18    if (flag) { // Now it's taking true branch again?!<br>
    19      *x = 1; // Null dereference.<br>
    20    }<br>
    21  }<br>
    <br>
    Because we wouldn't highlight the data dependency on line 06 of the
    control flow dependency on lines 14 and 18, the positive may be
    incomprehensible.<br>
    <br>
    This one's tricky to do with a visitor because it's hard to figure
    out that the true-branch of the if-statement on line 14 would have
    updated `x`, given that we didn't execute it.<br>
    <br>
    (1) Again, we can do a syntactic match over the true-branch, like we
    did in NoStoreFuncVisitor, to see if there are any data depenencies
    within it (there are, line 15). Again, this may fail to cover the
    tricky cases (what if this branch instead calls a function that
    initializes `x`?). <br>
    <br>
    (2) Instead we can also have a look at the execution path on the
    ExplodedGraph that goes through the true-branch and see if the value
    remains null when it exits the if-branch. Kristof, you're saying
    that you plan to do the slicing over the ExplodedGraph - is that
    what you mean? This could work as long as the other branch is
    actually *explored* by the analyzer. If it isn't, it'll be almost
    impossible to detect, and i don't know how often would this happen,
    but there's a good chance it's going to be much more rare than us
    having problems with such highlighting right now.<br>
    <br>
    (3) We can also come up with a completely separate CFG-based
    analysis for this purpose. This is probably the most precise thing
    to do, because the problem is essentially an all-paths problem
    (which is why loss of coverage in the ExplodedGraph would bite us).
    I cannot estimate how difficult such analysis would be to implement
    (probably pretty scary), but i think Kristof wasn't looking in this
    direction.<br>
    <br>
    Yay, i finally understand how to solve these problems we have!<br>
    <br>
    I'd suggest first starting with a syntax-based approach (1) because
    it sounds to me that the approach that we chose for identifying
    dependencies on paths that aren't part of the bug path is orthogonal
    to actually making use of that information to produce notes. Once we
    learn how to make use of this information, we'll have a taste of
    this medicine and see if it works. Then we'll see if we need to
    transition to (2) or (3) depending on such evaluation.<br>
    <br>
    What i just described sounds like a fairly realistic plan to me. Of
    course, the question still remains about how checker-specific would
    the analysis be. If i learned anything, it's "don't estimate the
    power of the esoteric checker contracts". But the idea that we can
    often get away with just tracking interesting regions and symbols
    and consuming trackExpressionValue() hints sounds like a good thing
    to try.<br>
    <br>
    <br>
    <br>
    <div class="gmail-m_3651988806800932803moz-cite-prefix">On 4/2/19 11:23 PM, Gábor Horváth
      wrote:<br>
    </div>
    <blockquote type="cite">
      
      <div dir="ltr">
        <div>Yeah, this particular example would be fixed, but we do not
          know how noisy it would be in general. One way to make it a
          bit less noisy could be something like what the
          NoStoreFuncVisitor already does for IVars. We could also add
          some syntactic checks to see if the method/function actually
          has the possibility to escape the region. <br>
        </div>
        <div><br>
        </div>
        <div>I am not familiar with Obj-C, but I suspect it would be
          possible to trick NoStoreFuncVisitor, or at least the
          syntactic checks in `<span class="gmail-m_3651988806800932803gmail-pl-en">potentiallyWritesIntoIvar</span>
          `.</div>
        <div>I think the main value of slicing here could be to get rid
          of those fully syntactic heuristics and replace them by
          something smarter. Does this make sense?<br>
        </div>
        <br>
        <div class="gmail_quote">
          <div dir="ltr" class="gmail_attr">On Wed, 3 Apr 2019 at 02:25,
            Artem Dergachev <<a href="mailto:noqnoqneo@gmail.com" target="_blank">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">
            <div bgcolor="#FFFFFF"> One more question about Example 1.
              Do you think this particular example could be solved by
              developing some sort of NoStoreFuncVisitor but for
              MallocChecker? I.e., in addition to emitting notes like
              "returning without initializing variable `x`", it could
              emit notes like "returning without escaping pointer `p`".
              If such visitor is developed, what would be the
              differences between your proposal and whatever behavior
              we'll get with such visitor? In other words, is it
              possible to construct an example with the "use of
              uninitialized variable" checker that, like Example 1, has
              vital pieces of information missing, given that this
              checker already uses NoStoreFuncVisitor?<br>
              <br>
              I mean, it's most likely a terrible idea to develop such
              visitor for MallocChecker, because the only reason this
              visitor works more or less reliably is the existence of
              const-qualifiers. For MallocChecker they don't exist, so
              it's going to be hard to figure out if a function was
              *supposed* to escape the pointer.<br>
              <br>
              <div class="gmail-m_3651988806800932803gmail-m_444863209060437944moz-cite-prefix">On
                4/2/19 5:14 PM, Artem Dergachev wrote:<br>
              </div>
              <blockquote type="cite"> Ahaaaaa, ooooookkkkk, iiiiiiii
                seeeeeeeeee!<br>
                <br>
                Sounds fascinating, must-have and hard.<br>
                <br>
                My primary question is how much do you think this will
                put stress on the checkers. Like, how much more
                difficult would it be to write checkers when we require
                them to include the slicing criterion with their bug
                reports? How much of it would we (i.e., BugReporter) be
                able to infer ourselves?<br>
                <br>
                ------------------------<br>
                <br>
                Say, let's take Example 1. You describe the slicing
                criterion as:<br>
                <br>
                    (13, <dynamically allocated int object>)<br>
                <br>
                The value of the dynamically allocated into object
                remains the same regardless of whether the object is
                stored in global_ptr or not, so the slice doesn't need
                to include line 5 or 6. Therefore i think that the
                slicing criterion you proposed is not what we're looking
                for, and the real slicing criterion we're looking for
                is:<br>
                <br>
                    (13, <liveness of <dynamically allocated int
                object>>)<br>
                <br>
                Like, we're mapping every dynamically allocated object
                to an imaginary heap location that represents its
                current liveness, and include that imaginary variable,
                rather than the object itself, in the slicing criterion.
                Line 6 would affect liveness of the object on line 13
                (if it's stored into a global, it's alive; otherwise
                it's not), therefore it'll be part of the slice. So, am
                i understanding correctly that you're proposing a
                checker API that'll look like this:<br>
                <br>
                  BugReport *R = new BugReport(Node, ...);<br>
                  R->addLivenessBasedSlicingCriterion(HeapSym);<br>
                <br>
                ?<br>
                <br>
                I guess we can infer the statement of the slicing
                criterion from the Node, but i'm not entirely sure; see
                also below.<br>
                <br>
                I'd actually love it if you elaborate this example
                further because it's fairly interesting. Like, we know
                that the assignment affects the liveness information,
                but how would the slicing algorithm figure this out? Do
                you have a step-by-step description of how the algorithm
                behaves in this case?<br>
                <br>
                ------------------------<br>
                <br>
                Let's take another example i just came up with. Consider
                alpha.unix.PthreadLock - a checker that finds various
                bugs with mutexes, such as double locks or double
                unlocks. Consider code:<br>
                <br>
                1  pthread_mutex_t mtx1, mtx2;<br>
                2<br>
                3  void foo(bool x1, bool x2) {<br>
                4    if (x1)<br>
                5      pthread_mutex_lock(&mtx1);<br>
                6    if (x2)<br>
                7      pthread_mutex_lock(&mtx1);<br>
                8    // ...<br>
                9  }<br>
                <br>
                In this example we'll report a double lock bug due to a
                copy-paste error: line 7 should probably lock &mtx2
                rather than &mtx1.<br>
                <br>
                The whole program is relevant to the report. Without
                line 5, there would only be a single lock. It
                transitions the mutex object from state "unknown" to
                state "locked".<br>
                <br>
                I don't think the Analyzer would currently do a bad job
                at explaining the bug; it's pretty straightforward.<br>
                <br>
                What would be the slicing criterion in this case? As far
                as i understand, it'll be<br>
                <br>
                    (7, <locked-ness of mtx1>)<br>
                <br>
                In this case "lockedness" is, again, an "imaginary heap
                location" that contains metadata for the mutex. More
                specifically, it is a GDM map value. How would a checker
                API look in this case? How would it even describe to the
                BugReporter what to look at, given that currently only
                the checker understands how to read its GDM values?<br>
                <br>
                My random guess is:<br>
                <br>
                  BugReport *R = new BugReport(Node, ...);<br>
                 
                R->addGDMBasedSlicingCriterion<MutexState>(MutexMR);<br>
                <br>
                ------------------------<br>
                <br>
                So it sounds to me that your project is, like many other
                awesome projects, brings in, as a dependency, replacing
                GDM with a better, smarter data map that the analyzer
                core *can* introspect and manipulate without the direct
                help from the checkers. It might be that your project
                actually requires relatively little amounts of such
                introspection - i.e., you might be able to get away with
                "it's some GDM map and the value for this key has
                changed, therefore this statement is a relevant data
                dependency" for quite a lot of checkers.<br>
                <br>
                That's the subject i was also bringing up as part of <a class="gmail-m_3651988806800932803gmail-m_444863209060437944moz-txt-link-freetext" href="https://reviews.llvm.org/D59861" target="_blank">https://reviews.llvm.org/D59861</a>
                - "this was the plan that is part of the
                even-more-long-term plan of completely deprecating the
                void*-based Generic Data Map...". This was also
                something that became a blocker on my old attempt to
                introduce summary-based analysis. It required stuffing
                fairly large chunks of code into every checker that
                would teach the checker how to collect summary
                information and apply it when the summary is applied,
                and this new boilerplate was fairly brain-damaging to
                implement and hard to get right or even to explain. This
                problem also blocks other projects, such as state
                merging / loop widening (on one branch the mutex is
                locked, on the other branch it is unlocked, hey checker
                please teach me how to merge this).<br>
                <br>
                The variety of slicing criteria (that is a consequence
                of the variety of checkers that we have) sounds pretty
                scary to me. Some of them are really complicated, eg.
                the liveness criterion. Making sure that the generic
                algorithm works correctly with at least a significant
                chunk of them is going to be fun. Making sure it can
                actually handle arbitrary criterions required by the
                checkers without having every checker come with its own
                boilerplate for slicing also sounds hard. And it'll be
                very bad if we have to tell our checker developers "hey,
                by the way, you also need to know what backward slicing
                is and write down part of the algorithm in order to ever
                get your checker enabled by default" - i'm already
                feeling pretty bad explaining dead symbols and pointer
                escapes (which are pretty much must-have in most
                checkers), these are definitely examples of a
                boilerplate that a smarter version of GDM could handle
                automatically. In order to conquer the world, i think we
                should stick to our "writing a checker in 24 hours"
                utopia: writing a checker should be as easy as writing
                down the transfer functions for relevant statements. In
                my opinion, we should take it as an important
                constraint.<br>
                <br>
                <br>
                <br>
                <br>
                <div class="gmail-m_3651988806800932803gmail-m_444863209060437944moz-cite-prefix">On
                  4/2/19 12:21 PM, Kristóf Umann wrote:<br>
                </div>
                <blockquote type="cite">
                  <div dir="ltr">
                    <div dir="ltr">Somehow the images and the attached
                      files were left out, please find them here:</div>
                    <br>
                    <div class="gmail_quote">
                      <div dir="ltr" class="gmail_attr">On Tue, 2 Apr
                        2019 at 21:16, Kristóf Umann <<a href="mailto:dkszelethus@gmail.com" target="_blank">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 class="gmail_quote">
                            <div dir="ltr">
                              <div dir="ltr">
                                <div dir="ltr">
                                  <div dir="ltr"><span style="background-color:rgb(255,255,255)"><font color="#000000">Hi!<br>
                                        <br>
                                      </font></span>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000">In this
                                          letter, I'd like to describe a
                                          particular problem in the
                                          Clang StaticAnalyzer's <font face="monospace, monospace">BugReporter
                                          </font>class that I'd like to
                                          tackle in a Google Summer of
                                          Code project this summer. I'll
                                          show real-world examples on
                                          some of its shortcomings, and
                                          propose a potential solution
                                          using static backward program
                                          slicing. At last, I'll ask
                                          some specific questions. I'd
                                          love to hear any and all
                                          feedback on this!</font></span></div>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000"><br>
                                        </font></span></div>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000">This is a <i>problem
                                            statement, </i>not a <i>proposal</i>.
                                          I plan to send out a formal
                                          proposal by Friday (but not
                                          later then Saturday), that
                                          will contain more details on
                                          both the problem and the
                                          solution. I don't introduce
                                          myself or my previous works
                                          within the project, that will
                                          also be detailed in my
                                          upcoming letter. I also plan
                                          to incorporate the feedback
                                          I'll receive to this letter.</font></span></div>
                                  </div>
                                  <div dir="ltr"><span style="background-color:rgb(255,255,255)"><font color="#000000"><br>
                                      </font></span></div>
                                  <div><b><font style="background-color:rgb(255,255,255)" size="4" color="#000000">---===
                                        BugReporter constructs bad
                                        reports ===---</font></b></div>
                                  <div><b><font style="background-color:rgb(255,255,255)" size="4" color="#000000"><br>
                                      </font></b></div>
                                  <div><span style="background-color:rgb(255,255,255)"><font color="#000000"><b>What does the
                                          BugReporter do?</b><br>
                                        <br>
                                        After the Static Analyzer found
                                        an error, the <font face="monospace, monospace">BugReporter
                                        </font>receives an <font face="monospace, monospace">ExplodedNode</font>,
                                        which, accompanied by its
                                        predecessors, contains all the
                                        information needed to reproduce
                                        that error. This <i>bugpath </i>is
                                        then shortened with a variety of
                                        heuristics, such as removing
                                        unrelated function calls,
                                        unrelated branches and so on. <font face="monospace, monospace">BugReporter
                                        </font>by the end of this
                                        process will construct a <font face="monospace, monospace">PathDiagnostic
                                        </font>object for each report,
                                        that is, ideally, minimal.</font></span></div>
                                  <div><b style="background-color:rgb(255,255,255)"><font color="#000000"><br>
                                      </font></b></div>
                                  <div><b style="background-color:rgb(255,255,255)"><font color="#000000">Example 1.</font></b></div>
                                  <div><span style="background-color:rgb(255,255,255)"><font color="#000000"><br>
                                      </font></span></div>
                                  <div><span style="background-color:rgb(255,255,255)"><font color="#000000">Consider the
                                        following code example:<br>
                                        <br>
                                      </font></span>
                                    <div><font style="background-color:rgb(255,255,255)" face="monospace, monospace" color="#000000">1  // leak.cpp</font></div>
                                    <div><font style="background-color:rgb(255,255,255)" face="monospace, monospace" color="#000000">2  int
                                        *global_ptr;</font></div>
                                    <div><font style="background-color:rgb(255,255,255)" face="monospace, monospace" color="#000000">3  </font></div>
                                    <div><font style="background-color:rgb(255,255,255)" face="monospace, monospace" color="#000000">4  void
                                        save_ext(int storeIt, int *ptr)
                                        {</font></div>
                                    <div><font style="background-color:rgb(255,255,255)" face="monospace, monospace" color="#000000">5    if
                                        (storeIt)</font></div>
                                    <div><font style="background-color:rgb(255,255,255)" face="monospace, monospace" color="#000000">6     
                                        global_ptr = ptr;</font></div>
                                    <div><font style="background-color:rgb(255,255,255)" face="monospace, monospace" color="#000000">7  }</font></div>
                                    <div><font style="background-color:rgb(255,255,255)" face="monospace, monospace" color="#000000">8</font></div>
                                    <div><font style="background-color:rgb(255,255,255)" face="monospace, monospace" color="#000000">9  void test(int
                                        b) {</font></div>
                                    <div><font style="background-color:rgb(255,255,255)" face="monospace, monospace" color="#000000">10   int *myptr
                                        = new int;</font></div>
                                    <div><font style="background-color:rgb(255,255,255)" face="monospace, monospace" color="#000000">11   save_ext(b,
                                        myptr);</font></div>
                                    <div><font style="background-color:rgb(255,255,255)" face="monospace, monospace" color="#000000">12   delete
                                        global_ptr;</font></div>
                                    <div><font style="background-color:rgb(255,255,255)" face="monospace, monospace" color="#000000">13 }</font></div>
                                  </div>
                                  <div><span style="background-color:rgb(255,255,255)"><font color="#000000"><br>
                                      </font></span></div>
                                  <div dir="ltr">
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000">It's clear
                                          that if test is invoked with <font face="monospace, monospace">b</font>'s
                                          value set to true, there is no
                                          error in the program. However,
                                          should b be false, we'll leak
                                          memory.</font></span></div>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000"><br>
                                        </font></span></div>
                                    <span style="font-family:monospace,monospace;background-color:rgb(255,255,255)"><font color="#000000">$ clang -cc1
                                        -analyze
                                        -analyzer-checker=core,cplusplus
                                        leak.cpp</font></span></div>
                                  <div dir="ltr">
                                    <div><img src="cid:169e5205a23cb971f161" alt="image.png" width="472" height="168"><br>
                                    </div>
                                  </div>
                                  <div dir="ltr"><font style="background-color:rgb(255,255,255)" face="monospace, monospace" color="#000000"><br>
                                    </font>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000">The Static
                                          Analyzer is able to catch this
                                          error, but fails to mention
                                          the call to <font face="monospace, monospace">save_ext</font> entirely,
                                          despite the error only
                                          occurring because the analyzer
                                          assumed that <font face="monospace, monospace">storeIt</font> is
                                          false. I've also attached the
                                          exploded graph <font face="monospace, monospace">leak.svg </font><font face="arial, helvetica,
                                            sans-serif">that
                                            demonstrates this.</font></font></span></div>
                                    <div><font style="background-color:rgb(255,255,255)" face="arial, helvetica,
                                        sans-serif" color="#000000"><br>
                                      </font></div>
                                    <div>
                                      <div><b style="background-color:rgb(255,255,255)"><font color="#000000">Example 2.</font></b></div>
                                    </div>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000"><br>
                                        </font></span></div>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000">Consider the
                                          following code example:<br>
                                          <br>
                                          <font face="monospace,
                                            monospace">1  //
                                            divbyzero.cpp</font><br>
                                        </font></span>
                                      <div><font style="background-color:rgb(255,255,255)" face="monospace, monospace" color="#000000">2  void f() {</font></div>
                                      <div><font style="background-color:rgb(255,255,255)" face="monospace, monospace" color="#000000">3    int i =
                                          0;</font></div>
                                      <div><font style="background-color:rgb(255,255,255)" face="monospace, monospace" color="#000000">4    (void)
                                          (10 / i);</font></div>
                                      <div><font style="background-color:rgb(255,255,255)" face="monospace, monospace" color="#000000">5  }</font></div>
                                      <div><font style="background-color:rgb(255,255,255)" face="monospace, monospace" color="#000000">6</font></div>
                                      <div><font style="background-color:rgb(255,255,255)" face="monospace, monospace" color="#000000">7  void g() {
                                          f(); }</font></div>
                                      <div><font style="background-color:rgb(255,255,255)" face="monospace, monospace" color="#000000">8  void h() {
                                          g(); }</font></div>
                                      <div><font style="background-color:rgb(255,255,255)" face="monospace, monospace" color="#000000">9  void j() {
                                          h(); }</font></div>
                                      <div><font style="background-color:rgb(255,255,255)" face="monospace, monospace" color="#000000">10 void k() {
                                          j(); }</font></div>
                                      <div><span style="background-color:rgb(255,255,255)"><font color="#000000"><br class="gmail-m_3651988806800932803gmail-m_444863209060437944m_6421736142923902491gmail-m_-3454961580602141710gmail-m_-6979117027997739172gmail-m_4426039388547674777gmail-m_5439174890474816058gmail-m_6038659214782379119gmail-Apple-interchange-newline">
                                            Its clear that a call to f
                                            will result in a division by
                                            zero error.</font></span></div>
                                      <div><span style="background-color:rgb(255,255,255)"><font color="#000000"><br>
                                          </font></span></div>
                                      <span style="background-color:rgb(255,255,255)"><font color="#000000"><span style="font-family:monospace,monospace">$
                                            clang -cc1 -analyze
                                            -analyzer-checker=core </span><span style="font-family:monospace,monospace">divbyzero.cpp</span></font></span></div>
                                    <div><img src="cid:169e5205a24cb971f162" alt="image.png" width="334" height="472"><br>
                                    </div>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000">Again, the
                                          Static Analyzer is plenty
                                          smart enough to catch this,
                                          but the constructed bug report
                                          is littered with a lot of
                                          useless information -- it
                                          would be enough to only show
                                          the body of f, and, optionally
                                          where f itself was called. For
                                          the sake of completeness, I've
                                          attached <font face="monospace, monospace">divbyzero.svg</font> that
                                          contains the exploded graph
                                          for the above code snippet.<br>
                                        </font></span></div>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000"><br>
                                        </font></span></div>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000">The above
                                          examples demonstrate that <font face="monospace, monospace">BugReporter
                                          </font>sometimes reduces the
                                          bugpath too much or too
                                          little.</font></span></div>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000"><br>
                                        </font></span></div>
                                    <div><b><font style="background-color:rgb(255,255,255)" size="4" color="#000000">---===
                                          Solving the above problem with
                                          static backward program
                                          slicing ===---</font></b></div>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000"><br>
                                        </font></span></div>
                                    <div><b style="background-color:rgb(255,255,255)"><font color="#000000">What is static
                                          backward program slicing?</font></b></div>
                                    <div>
                                      <div><span style="background-color:rgb(255,255,255)"><font color="#000000"><br>
                                          </font></span></div>
                                      <div><span style="background-color:rgb(255,255,255)"><font color="#000000">A <i>program
                                              slice</i> consists of the
                                            parts of a program that
                                            (potentially) affect the
                                            values computed at some
                                            point of interest, called
                                            the slicing criterion. <i><b>Program
                                                slicing</b></i> is a
                                            decomposition technique that
                                            elides program components
                                            not relevant to the slicing
                                            criterion (which is a pair
                                            of (statement, set of
                                            variables)), creating a
                                            program slice[1][2]. <b>Static </b>slicing
                                            preserves the meaning of the
                                            variable(s) in the slicing
                                            criterion for all possible
                                            inputs[1]. <b>Backward </b>slices
                                            answer the question “what
                                            program components might
                                            affect a selected
                                            computation?”[1]</font></span></div>
                                    </div>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000"><br>
                                        </font></span></div>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000">While
                                          statement-minimal slices are
                                          not necessarily unique[3],
                                          Weisel developed a popular
                                          algorithm that constructs one.
                                          In essence, his fix-point
                                          algorithm constructs sets of <i>relevant
                                            variables</i><i> </i>for
                                          each edge in between node <i>i</i> and
                                          node <i>j</i> in a CFG graph,
                                          from which he constructs <i>relevant
                                            statements</i>. The
                                          fix-point of the relevant
                                          statements set is the slice
                                          itself.</font></span></div>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000"><br>
                                        </font></span></div>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000">One of the
                                          characteristic of his
                                          algorithm is that the
                                          resulting program slice will
                                          be executable. However, our
                                          problem doesn't require the
                                          code to be executable, so we
                                          could use a more "aggressive"
                                          approach that creates a
                                          smaller slice. An improvement
                                          to his algorithm is presented
                                          in [4].</font></span></div>
                                    <div>
                                      <div><b style="background-color:rgb(255,255,255)"><font color="#000000"><br>
                                          </font></b></div>
                                      <div><b style="background-color:rgb(255,255,255)"><font color="#000000">How does
                                            this relate to BugReporter?</font></b></div>
                                    </div>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000"><br>
                                        </font></span></div>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000">We can show
                                          that using Weiser's algorithm,
                                          issues raised in Example 1.
                                          and Example 2. can be improved
                                          upon.</font></span></div>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000"><br>
                                        </font></span></div>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000">For example
                                          1., the statement-minimal
                                          program slice with the
                                          criterion (13, <font face="monospace, monospace"><dynamically
                                            allocated int object></font>)
                                          will contain the statements 5
                                          and 6, and for example 2., the
                                          statement-minimal program
                                          slice with the criterion (4,<font face="monospace, monospace">
                                            i</font>) won't contain
                                          anything but statements 3 and
                                          4. For the latter, we can even
                                          improve the algorithm to also
                                          contain statement 7, where a
                                          call to f is made.</font></span></div>
                                    <span style="background-color:rgb(255,255,255)"><font color="#000000"><br class="gmail-m_3651988806800932803gmail-m_444863209060437944m_6421736142923902491gmail-m_-3454961580602141710gmail-m_-6979117027997739172gmail-m_4426039388547674777gmail-Apple-interchange-newline">
                                        The analyzer, as stated earlier,
                                        gives <font face="monospace,
                                          monospace">BugReporter </font>an
                                        <font face="monospace,
                                          monospace">ExplodedNode</font>,
                                        from which the slicing criterion
                                        must be constructed. The
                                        statement corresponding to this
                                        node, coupled with the
                                        interesting regions the checker
                                        itself marked could be used to
                                        construct this slicing
                                        criterion.</font></span>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000"><br>
                                        </font></span></div>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000"><b>Challenges</b><br>
                                        </font></span></div>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000"><br>
                                        </font></span></div>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000">While the
                                          algorithm Weiser developed
                                          along with the improvements
                                          made by others are
                                          interprocedural, I would
                                          imagine that in
                                          implementation, it would be a
                                          challenging step from an
                                          intraprocedural prototype.</font></span></div>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000"><br>
                                        </font></span></div>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000">Several
                                          articles also describe
                                          pointers, references, and
                                          dynamically allocated regions,
                                          as well as gotos and other
                                          tricky parts of the language,
                                          but I still expect to see some
                                          skeletons falling out of the
                                          closet when implementing this
                                          for C++, not only C.</font></span></div>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000"><br>
                                        </font></span></div>
                                    <div><b style="background-color:rgb(255,255,255)"><font color="#000000">Drawbacks</font></b></div>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000"><br>
                                        </font></span></div>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000">Static
                                          slicing, as an algorithm that
                                          doesn't know anything about
                                          input values, suffers from the
                                          same issues that all static
                                          techniques do, meaning that
                                          without heuristics, it'll have
                                          to do very rough guesses,
                                          possibly leaving a far too big
                                          program slice. However, with
                                          the symbolic values the
                                          analyzer holds, this could be
                                          improved, turning this into <i>conditioned
                                            slicing, </i>as described in
                                          [1]. This however is only
                                          planned as a followup work
                                          after GSoC.</font></span></div>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000"><br>
                                        </font></span></div>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000">For this
                                          reason, this project would be
                                          developed as an alternative
                                          approach to some of the
                                          techniques used in <font face="monospace, monospace">BugReporter</font>,
                                          as an optional off-by-default
                                          analyzer feature.</font></span></div>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000"><br>
                                        </font></span></div>
                                    <div><font size="4" color="#000000"><b style="background-color:rgb(255,255,255)">---=== Questions ===---</b></font></div>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000"><br>
                                        </font></span></div>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000">What do you
                                          think of this approach?</font></span></div>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000">Do you think
                                          that implementing this
                                          algorithm is achievable, but
                                          tough enough task for GSoC?</font></span></div>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000">Would you
                                          prefer to see a general
                                          program slicing library, or an
                                          analyzer-specific
                                          implementation? Traversing the
                                          <font face="monospace,
                                            monospace">ExplodedGraph </font>would
                                          be far easier in terms of what
                                          I want to achieve, but a more
                                          general approach that
                                          traverses the CFG (like <font face="monospace, monospace">llvm::DominatorTree</font><font face="arial, helvetica,
                                            sans-serif">[5]) could be
                                            beneficial to more
                                            developers, but possibly at
                                            the cost of not being able
                                            to improve the prototype
                                            with the symbolic value
                                            information the analyzer
                                            holds.</font></font></span></div>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000"><br>
                                        </font></span></div>
                                    <div><b><i style="background-color:rgb(255,255,255)"><font color="#000000">References,
                                            links</font></i></b></div>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000"><br>
                                        </font></span></div>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000">[1] <span style="font-size:13px;font-family:Arial,sans-serif">Gallagher,
                                            Keith, and David Binkley.
                                            "Program slicing." </span><i style="font-size:13px;font-family:Arial,sans-serif">2008 Frontiers of
                                            Software Maintenance</i><span style="font-size:13px;font-family:Arial,sans-serif">.</span></font></span></div>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000"><span style="font-size:13px;font-family:Arial,sans-serif">[2] </span><span style="font-size:13px;font-family:Arial,sans-serif">Tip, Frank. </span><i style="font-size:13px;font-family:Arial,sans-serif">A survey of program
                                            slicing techniques</i><span style="font-size:13px;font-family:Arial,sans-serif">. Centrum voor
                                            Wiskunde en Informatica,
                                            1994.</span></font></span></div>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000"><span style="font-size:13px;font-family:Arial,sans-serif">[3] </span><span style="font-size:13px;font-family:Arial,sans-serif">Weiser, Mark.
                                            "Program slicing." </span><i style="font-size:13px;font-family:Arial,sans-serif">Proceedings of the
                                            5th international conference
                                            on Software engineering</i><span style="font-size:13px;font-family:Arial,sans-serif">. IEEE Press, 1981.</span></font></span></div>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000"><span style="font-size:13px;font-family:Arial,sans-serif">[4] </span><span style="font-size:13px;font-family:Arial,sans-serif">Binkley, David.
                                            "Precise executable
                                            interprocedural slices." </span><i style="font-size:13px;font-family:Arial,sans-serif">ACM Letters on
                                            Programming Languages and
                                            Systems (LOPLAS)</i><span style="font-size:13px;font-family:Arial,sans-serif"> 2.1-4
                                            (1993): 31-45.</span></font></span></div>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000"><span style="font-size:13px;font-family:Arial,sans-serif">[5] </span><font face="Arial, sans-serif"><a href="http://llvm.org/doxygen/classllvm_1_1DominatorTree.html" target="_blank">http://llvm.org/doxygen/classllvm_1_1DominatorTree.html</a></font></font></span></div>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000"><br>
                                        </font></span></div>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000">Link to
                                          previous GSoC related letter I
                                          sent: <a href="http://lists.llvm.org/pipermail/cfe-dev/2019-February/061464.html" target="_blank">http://lists.llvm.org/pipermail/cfe-dev/2019-February/061464.html</a></font></span></div>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000"><br>
                                        </font></span></div>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000">Cheers,</font></span></div>
                                    <div><span style="background-color:rgb(255,255,255)"><font color="#000000">Kristóf Umann</font></span></div>
                                  </div>
                                </div>
                              </div>
                            </div>
                          </div>
                        </div>
                      </blockquote>
                    </div>
                  </div>
                </blockquote>
                <br>
              </blockquote>
              <br>
            </div>
          </blockquote>
        </div>
      </div>
    </blockquote>
    <br>
  </div>

</blockquote></div></div>