<div dir="ltr"><div dir="ltr"><br></div><div dir="ltr"></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">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">dkszelethus@gmail.com</a> <br>
> <mailto:<a href="mailto:dkszelethus@gmail.com" target="_blank">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">noqnoqneo@gmail.com</a><br>
>     <mailto:<a href="mailto:noqnoqneo@gmail.com" target="_blank">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">dkszelethus@gmail.com</a> <mailto:<a href="mailto:dkszelethus@gmail.com" target="_blank">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">noqnoqneo@gmail.com</a> <mailto:<a href="mailto:noqnoqneo@gmail.com" target="_blank">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">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">https://docs.google.com/document/d/1ci1BCAKojPlqIxIw1J_K2dnATA3z01PuwR_vHJS55TI/edit</a><br>
>>><br>
>><br>
><br>
<br>
</blockquote></div>
</div>