<div dir="ltr"><p class="MsoNormal"><span lang="EN-US">Hello,<br></span></p><p class="MsoNormal"><span lang="EN-US">
<br>
thank you for your replies!<br></span></p><p class="MsoNormal"><span lang="EN-US">I
collected my ideas about it but at the end of the email I put my
concerns in perspective which dependency would be important and maybe it should be done first. I would gladly
take it for the summer since it was mentioned in the GSoC project page earlier.<br></span></p><p class="MsoNormal"><span lang="EN-US"><br></span></p>
<p class="MsoNormal"><span lang="EN-US">My initial thoughts
in details about handling loops in a better way:<br>
First, we have a control number N which determines how many steps to unroll during the analysis of a loop. Instead of this, in my
opinion it would be better to have a number M which determines the maximum times a loop can branch the ExplodedGraph. In this case simulating a simple (non-branching) loop to the end would not be too complex. This means we could analyze the following example without a problem:<br></span></p><p class="MsoNormal"><span lang="EN-US"><br></span></p>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><p class="MsoNormal"><span lang="EN-US">vector<int>
v;</span></p>
<p class="MsoNormal"><span lang="EN-US">for(int i =
1; i<SIZE;++i)</span></p>
<p class="MsoNormal"><span lang="EN-US">{</span></p>
<p class="MsoNormal"><span lang="EN-US"><span> </span>v[i] = f(i);</span></p>
<p class="MsoNormal"><span lang="EN-US">}</span></p></blockquote><div> </div>
<p class="MsoNormal"><span lang="EN-US">But we
would not waste much time to analyze a complex loop for „nothing”:<br></span></p><p class="MsoNormal"><span lang="EN-US"><br></span></p><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span lang="EN-US">
for(auto it = begin();it!=end();it++</span> <span lang="EN-US">)</span> </blockquote><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span lang="EN-US">{</span>
<p class="MsoNormal"><span lang="EN-US"><span> </span>if(it->complexfun1()) …<br>
<span> </span>if(it->complexfun2()) …<br>
<span> </span>else …</span></p>
<p class="MsoNormal"><span lang="EN-US">}</span></p></blockquote><div> </div>
<p class="MsoNormal"><span lang="EN-US">And this
could be <b>Milestone1</b>. (That is quite optional but I think this would be a great
improvement.)</span></p><p class="MsoNormal"><span lang="EN-US"><br></span></p>
<p class="MsoNormal"><span lang="EN-US">The next
step is the LoopWidening so whenever we stop the simulation - since the loop would
result in a too complex/huge ExplodedGraph - we would continue the analysis
and invalidate only the MemRegions of which binded values can be changed in the loop.
I</span><span lang="EN-US"><span lang="EN-US"><span lang="EN-US"></span>n order to avoid false positives<span class="">, </span>h</span>owever, an important restriction would be </span><span lang="EN-US"><span lang="EN-US">that whenever we would invalidate too much MemRegions then it is just better to
stop the analyzing process</span>. It can be tricky to say when exactly it is too much but
determining it would be part of the project.</span></p><p class="MsoNormal"><span lang="EN-US"><br></span></p><p class="MsoNormal"><span lang="EN-US">
So how the invalidation should work? I believe a great approch would be the following: we would iterate over
the statements of the loop's body and they would be handled one by one. Implementing
an ASTVisitor could solve this and the statements which are not handled at the
moment would result in the „conservative analysis” so it would cut the processing of the
given path.</span></p>
<p class="MsoNormal"><span lang="EN-US">This way it
can be an extensible and incremental solution since new callbacks can be implemented in an
easy way to cover new statements. (It could work like in the ASTImporter.)</span></p>
<p class="MsoNormal"><span lang="EN-US"><b>Milestone2
</b>could be implementing the ASTVisitor described above.</span></p>
<p class="MsoNormal"><span lang="EN-US">The next step could be implementing the following nodes: function calls (CallExpr) of which parameters are const or
passed by value, and <i>the assignement
operator</i> in some trivial cases (no pointer/reference/array on the left side).<br>So whenever we stop the analysis of a loop which contains only those nodes, we have the
information which regions to invalidate. This way the analysis can be continued
safely.</span></p>
<p class="MsoNormal"><span lang="EN-US">For example:</span></p><p class="MsoNormal"><span lang="EN-US"><br></span></p>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><p class="MsoNormal"><span lang="EN-US">int f(int);<br>
int h(int,int);<br>
int a,b,c = 0;<br>
for(int i =0;i<100;i++)</span></p>
<p class="MsoNormal"><span lang="EN-US">{</span></p>
<p class="MsoNormal"><span lang="EN-US"><span> </span>a = f(i);<br>
<span> </span>b = h(a,i);</span></p>
<p class="MsoNormal"><span lang="EN-US">}</span></p><p class="MsoNormal"><span lang="EN-US"><br></span></p>
<p class="MsoNormal"><span lang="EN-US">int d = 12/c;
// The analyzer should be able to find this and report the divByZero bug
since the foor loop contains only those statements which are implemented.</span></p></blockquote><p class="MsoNormal"><span lang="EN-US"><br></span></p><p class="MsoNormal"><span lang="EN-US">
However, in the next example:</span></p><p class="MsoNormal"><span lang="EN-US"><br></span></p>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><p class="MsoNormal"><span lang="EN-US">int f(int);<br>
int h(int*,int);<br>
int a,b,c = 0;<br>
for(int i =0;i<100;i++)</span></p>
<p class="MsoNormal"><span lang="EN-US">{</span></p>
<p class="MsoNormal"><span lang="EN-US"><span> </span>a = f(i);<br>
<span> </span>b = h(&a,i);</span></p>
<p class="MsoNormal"><span lang="EN-US">}</span></p>
<p class="MsoNormal"><span lang="EN-US">int d = 12/c;</span></p></blockquote><div> </div>
<p class="MsoNormal"><span lang="EN-US">Here we
have a function call which is not implemented (pointer parameter) so we just end this path’s
analysis and not spot the bug after the loop.<br>
This would be <b>Milestone3</b>.</span></p>
<p class="MsoNormal"><span lang="EN-US">After these
fundamentals I would investigate which statements are commonly used in a loop,
testing this feature on open source projects and I would aim to implement these visitor
callbacks which are important according to these tests.</span></p><p class="MsoNormal"><span lang="EN-US"><br></span></p><p class="MsoNormal"><span lang="EN-US">
AAAAnd that is the point where I think we have a problem because usage of
pointers and function calls by reference is quite common in a loop. In the naive
and conservative way all of the <i>typeT </i>variable’s
regions should be invalidated whenever we visit an assignment of which left hand
side variable is <i>typeT*. </i>Moreover it
could be casted to another type so maybe it should result invalidating all MemRegions.
That is why I think that a points-to analysis would be critical in order to
make this whole approach work on analysis of real projects. Because of that I am
considering to apply for the project “Implement points-to analysis” which I
have seen it on <a href="http://llvm.org/OpenProjects.html" target="_blank">http://llvm.org/OpenProjects.<wbr>html</a>
2 weeks ago but it mysteriously disappeared.</span></p><p class="MsoNormal"><span lang="EN-US"><br></span></p>
<p class="MsoNormal"><span lang="EN-US">My
questions:<br>
1. What do you think of this whole approach? (Please let me know if the whole idea is broken because I missed something.)<br>
2. Do you agree that arguing about pointer's possible values is important for achieving this?<br>
3. If that is the case could I still apply for that project or is it removed
because of good reasons?</span></p><p class="MsoNormal"><b><span lang="EN-US"><br></span></b></p><p class="MsoNormal"><span lang="EN-US">Cheers,<br></span></p><span lang="EN-US">Peter</span></div><div class="gmail_extra"><br><div class="gmail_quote">2017-03-16 13:25 GMT+01:00 Sean Eveson <span dir="ltr"><<a href="mailto:eveson.sean@gmail.com" target="_blank">eveson.sean@gmail.com</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Hello Péter,<div><br></div><div>Sounds good to me. I'd also be interested in knowing the specifics of what you are planning to do.</div><div><br></div><div>Very happy to help at any point.</div><div><br></div><div>Thanks,</div><div class="gmail_extra"><br clear="all"><div><div class="m_5146538026118419111gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><span style="color:rgb(0,0,0);font-family:'Segoe UI','Segoe UI Web Regular','Segoe UI Symbol','Helvetica Neue',Helvetica,Arial,sans-serif;font-size:13px;line-height:18.85px">Sean Eveson</span><br style="color:rgb(0,0,0);font-family:'Segoe UI','Segoe UI Web Regular','Segoe UI Symbol','Helvetica Neue',Helvetica,Arial,sans-serif;font-size:13px;line-height:18.85px"><span style="color:rgb(0,0,0);font-family:'Segoe UI','Segoe UI Web Regular','Segoe UI Symbol','Helvetica Neue',Helvetica,Arial,sans-serif;font-size:13px;line-height:18.85px">SN Systems - Sony Interactive Entertainment Group</span><br></div></div></div><div><div class="h5">
<br><div class="gmail_quote">On Thu, Mar 16, 2017 at 12:49 AM, Anna Zaks <span dir="ltr"><<a href="mailto:ganna@apple.com" target="_blank">ganna@apple.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word">Hi Péter,<br><div><br></div><div>Better modeling of loops is definitely an interesting topic. My main concern would be having a specific proposal on what improvements you could complete in the GSoC timeframe. The next step here is to write down more specifics about what you intend to work on. Please, let me, Devin, and Artem know if you’d like to talk to us while figuring this out.</div><div><br></div><div>Cheers!</div><span class="m_5146538026118419111HOEnZb"><font color="#888888"><div>Anna.</div></font></span><div><div class="m_5146538026118419111h5"><div><br></div><div><br><div><blockquote type="cite"><div>On Mar 13, 2017, at 9:43 AM, Péter Szécsi <<a href="mailto:peterszecsi95@gmail.com" target="_blank">peterszecsi95@gmail.com</a>> wrote:</div><br class="m_5146538026118419111m_-1237608075928966407Apple-interchange-newline"><div><div dir="ltr">Hello,<span class="m_5146538026118419111m_-1237608075928966407gmail-gI"><span></span></span><span class="m_5146538026118419111m_-1237608075928966407gmail-gI"><span> </span></span><br><br>I would love to work on a Clang Static Analyzer project during the summer by joining GSoC.<br>Let me introduce myself:<br>I'm Peter Szecsi, a third-year BSc student at Eötvös Loránd University, Budapest. It would be my first Summer of Code project but I have already contributed to clang:<br>During the last summer I have uploaded 2 patches:<br>- An accepted and merged clang-tidy checker [1] <br>- An accepted Clang SA checker [2]<br>Since then I am working on cross translational unit analysis as a university project (and because of that I`ve send some patches about the ASTImporter [3]). Furthermore I participated in the preparations of a talk that was accepted at the EuroLLVM conference. [4]<br>I found SA interesting since I like to work on algorithmic challenges and enjoy participating in programming competitions and there is a lot of algorithms in the Static Analyzer which could be optimized/made more precise by heuristics.<br><br>That is the reason why I would be most interested in project "Implement generalized loop execution modeling" from the Clang SA Open Projects page [5]. Hopefully it is a suitable project for GSoC and it is possible to achieve useful improvements during this time frame. <br>I have read the discussion at the "loop widening" patch [6] and the most important enhancements (and milestones in the project) would be invalidating only the possible modified values. In addition to that I was thinking to have some heuristics which would approximate if a loop is too complex to even use this kind of strategy because it would still lead to invalidate most of the values and result in a lot of false positives. Another small heuristic could be: when we already reached the maximum loop unroll number then in case we are sure that there is only a few loopsteps ahead we could unroll it to the end since probably this algorithm will not consume too much time/memory and the result state will not be much more complex. <br><br>What do you think about these ideas?<br><br>(I have CC'd everyone from the "loop widening" patch discussion.)<br><br>Best regards,<br>Peter<br><br>[1] <a href="https://reviews.llvm.org/D22507" target="_blank">https://reviews.llvm.org/D2250<wbr>7</a><br>[2] <a href="https://reviews.llvm.org/D24246" target="_blank">https://reviews.llvm.org/D2424<wbr>6</a><br>[3] <a href="https://reviews.llvm.org/D29612" target="_blank">https://reviews.llvm.org/D2961<wbr>2</a>, <a href="https://reviews.llvm.org/D30876" target="_blank">https://reviews.llvm.org/D3087<wbr>6</a>, <a href="https://reviews.llvm.org/D30877" target="_blank">https://reviews.llvm.org/D3087<wbr>7</a><br>[4] <a href="http://llvm.org/devmtg/2017-03//2017/02/20/accepted-sessions.html#7" target="_blank">http://llvm.org/devmtg/2017-03<wbr>//2017/02/20/accepted-sessions<wbr>.html#7</a><br>[5] <a href="http://clang-analyzer.llvm.org/open_projects.html" target="_blank">http://clang-analyzer.llvm.org<wbr>/open_projects.html</a><br>[6] <a href="https://reviews.llvm.org/D12358" target="_blank">https://reviews.llvm.org/D1235<wbr>8</a><br></div>
</div></blockquote></div><br></div></div></div></div></blockquote></div><br></div></div></div></div>
</blockquote></div><br></div>