<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
</head>
<body text="#000000" bgcolor="#FFFFFF">
I kinda gathered some understanding of the problem and the solution
and trying to come up with some sort of a plan, and for that purpose
i'm trying to step back from "we should totally do this cool
technique" towards a more "adult", "boring" point of view that
consists in asking, "what *do* we need to do?".<br>
<br>
For now i'm seeing that the work on this problem can be decomposed
into three chunks:<br>
<br>
(1) Collect slicing criteria from various sources,<br>
(2) Perform slicing to discover data and control dependencies,<br>
(3) Use information about dependencies to improve the bug report.<br>
<br>
Chunk (3) sounds straightforward: we just enable or disable path
pieces based on information we already have. I don't fully
understand how it'll go, but i don't see any unknowns here.<br>
<br>
Chunk (1) sounds like a large amount of routine, repetitive work:
convert sources of slicing criteria, such as checkers, to the new
system one-by-one. There is certain amount of known unknowns here:
some sources may be tricky to take advantage of (eg.,
liveness-related sources), some may put stress on the checkers.<br>
<br>
Chunk (2) is the research-intensive part: it has an easy 80%
solution (AST matching based detection that has already been
implemented and proved useful for one of the checkers) and an idea
to improve upon it by implementing a more sophisticated analysis.<br>
<br>
Because chunk (2) is research-intensive, we need experimental data
that we currently don't have. In order to avoid spending a lot of
time on something that isn't going to work, we should try to gather
that data as soon as possible in our plan.<br>
<br>
Because chunk (1) is repetitive, we don't need to implement it
completely; we can pick one or two sources and get them right.<br>
<br>
Therefore here's the plan that emerges:<br>
i. Pick one or two slicing criteria sources and implement them.<br>
ii. Implement a simple AST-based algorithm for discovering
dependencies.<br>
iii. Apply the information produced by that algorithm to the bug
report.<br>
iv. Run the updated analyzer on real-world codebases and see what
problems remain.<br>
v. Implement solutions to these problems.<br>
<br>
Solutions on step v. may or may not be about coding a more
sophisticated slicing algorithm. They might as well be improvements
in chunk (1), i.e. discovering more slicing criteria, or they may be
about a "horizontal" improvement in the existing primitive algorithm
(eg., cover more forms of control flow or different variants of data
dependencies, which should have been a separate chunk).<br>
<br>
That's roughly how i imagine it. <br>
<br>
<br>
<div class="moz-cite-prefix">On 4/4/19 10:32 AM, Kristóf Umann
wrote:<br>
</div>
<blockquote type="cite"
cite="mid:CAGcXOD6Ym7xKfj7kpDGD-U2zf6sM22bSQ5uYEKnovRUfD0dBpA@mail.gmail.com">
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<div dir="ltr">
<div>> 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>
</div>
><br>
> 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>
I guess it depends on what we want to do.
<div><br>
<div>Static slicing isn't defined for the ExplodedGraph, I'll
have show that we can transform an ExplodedGraph into a CFG,
or define the algorithm on it. From afar, it's very hard to
tell how difficult this would be. When looking for a
long-term solution, I think it would be better to find an
approach where we won't have to worry about whether the
analyzer explored everything or not. On the other hand, we
could eventually turn this backward static slicing into a
backward <i>conditional</i> slicing with the constraints
the analyzer gathered, should we chose to go with an
ExplodedGraph based algorithm.</div>
<div><br>
</div>
<div>So we'll have to balance these two. Greater accuracy with
a chance that the slice will be too big (CFG), or not as
accurate but resulting in a smaller slice (ExplodedGraph). I
am not yet sure which one I'd like to pursue, but the latter
would probably fit our needs better.<br>
<br>
> Id 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>
</div>
</div>
<div><br>
</div>
<div>I'll be honest, I don't really understand what you mean
here. Would you like to see a more down-to-earth syntax-based
solution as an exercise "for the big thing"? If so, I'm not
sure what you mean specifically.</div>
<div><br>
</div>
</div>
<br>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">On Thu, 4 Apr 2019 at 01:06,
Artem Dergachev <<a href="mailto:noqnoqneo@gmail.com"
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">
<div bgcolor="#FFFFFF"> I mean, assigning 3 to 'n' :)<br>
<br>
<div class="gmail-m_7103518053654994422moz-cite-prefix">On
4/3/19 4:05 PM, Artem Dergachev wrote:<br>
</div>
<blockquote type="cite"><font face="monospace, monospace"><b>Assigning
'n' to '3'</b></font></blockquote>
<br>
</div>
</blockquote>
</div>
</blockquote>
<br>
</body>
</html>