<html><head><meta http-equiv="Content-Type" content="text/html; charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class="">After fixing a few bugs, another evaluation of the approach shows considerably better results.<div class=""><br class=""></div><div class="">On <b class="">openssl</b>:</div><div class=""><br class=""></div><div class=""> - 9 reports added</div><div class=""> - 1 report removed</div><div class=""><br class=""></div><div class="">Note on histograms (here and below)</div><div class=""><br class=""></div><div class=""> -> Histograms only show the ratio <b class="">for same bugs</b> (compared using issue hash),</div><div class="">that is, if the histogram says “decrease by a factor of three”, it means the new approach finds the *same* bug</div><div class="">with a path size 1/3d of the original</div><div class=""> -> Histograms omit data points where the path length has remained the same</div><div class=""> (as otherwise they completely dominate the histogram)</div><div class=""> -> Relative histograms are provided as both ratio and logarithm of the ratio.</div><div class="">Logarithms of the ratio are convenient as they are symmetric in case changes balance out</div><div class="">(e.g. log(1/2) = -log(2/1))</div><div class=""><br class=""></div><div class=""><div class="">Relative path length change for same bugs (path size before / path size after):</div></div><div class=""><br class=""></div><div class=""><img apple-inline="yes" id="531FEA82-6947-4BF0-9F25-6E53033F8332" width="562" height="431" src="cid:968D7632-4E55-4335-8AED-6D6C2B1EADD9" class=""></div><div class=""><br class=""></div><div class=""><div class="">Log of relative path length change (log(path size before/ path size after)):</div></div><div class=""><br class=""></div><div class=""><img apple-inline="yes" id="450C2A08-C4C1-4A84-8708-F57E298FFCBE" width="582" height="442" src="cid:84C3C074-6C8D-4A18-8A53-1B62243A3E92" class=""></div><div class=""><br class=""></div><div class=""><div class="">Absolute change in path length (path size before - path size after)</div></div><div class=""><br class=""></div><div class=""><img apple-inline="yes" id="19912813-5A8A-4072-AD21-902BCD04C1E9" width="540" height="423" src="cid:2F5835B7-F216-4782-98BB-9A5B3B14F848" class=""></div><div class=""><br class=""></div><div class="">On <b class="">postgresql</b>:</div><div class=""><br class=""></div><div class=""> - 377 reports added</div><div class=""> - 43 reports removed</div><div class=""><br class=""></div><div class=""><span style="caret-color: rgb(0, 249, 0);" class="">Relative path length change (path size before / path size after):</span></div><div class=""><span style="caret-color: rgb(0, 249, 0);" class=""><br class=""></span></div><div class=""><img apple-inline="yes" id="8962D494-EFD5-4C76-B70E-8CCB69496653" width="554" height="428" src="cid:0872DFC4-2C65-459F-B66C-05CB25FD3EAD" class=""></div><div class=""><br class=""></div><div class="">Log of relative path length change (log(path size before / path size after))</div><div class=""><br class=""></div><div class=""><img apple-inline="yes" id="79C7F77E-B39E-4019-858E-DEBCE2C814F4" width="555" height="424" src="cid:B1E8CB16-92DC-471A-8804-B3B656FA8524" class=""></div><div class=""><br class=""></div><div class="">Absolute change in path length (path size before - path size after)</div><div class=""><br class=""></div><div class=""><img apple-inline="yes" id="1053F80F-A373-4EC3-B951-8D7458641EDD" width="557" height="431" src="cid:8206EFE5-306D-4B72-94EB-08EE322B901A" class=""></div><div class=""><br class=""></div><div class=""><br class=""></div><div class="">On <b class="">sqlite3 + a few other misc files</b>:</div><div class=""><br class=""></div><div class=""> - 239 reports added</div><div class=""> - 1 report removed</div><div class=""><br class=""></div><div class="">Relative path length change (path size before / path size after):</div><div class=""><br class=""></div><div class=""><img apple-inline="yes" id="4B5A0633-9F80-4E5A-B214-373B8D63A59E" width="562" height="444" src="cid:F83AB10E-6B45-44D6-A6F2-B31367C97987" class=""></div><div class=""><br class=""></div><div class=""><div class="">Log of relative path length change (log(path size before / path size after)):</div></div><div class=""><br class=""></div><div class=""><br class=""></div><div class=""><img apple-inline="yes" id="A7BDF3E2-BEF0-4A84-B3CC-F7C4A8491E49" width="577" height="435" src="cid:7A908C96-2D35-46ED-B28D-25813C74DAA4" class=""></div><div class=""><br class=""></div><div class="">Absolute path length change (path size before - path size after):</div><div class=""><br class=""></div><div class=""><img apple-inline="yes" id="02B71C4D-EF96-4BA9-A719-D5686044AA87" width="570" height="440" src="cid:53BC5D4C-D242-4ADB-80DA-E7A1A38F2C66" class=""></div><div class=""><br class=""></div><div class=""><div><br class=""></div><div><blockquote type="cite" class=""><div class="">On Jan 30, 2018, at 4:23 PM, George Karpenkov <<a href="mailto:ekarpenkov@apple.com" class="">ekarpenkov@apple.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><meta http-equiv="Content-Type" content="text/html; charset=utf-8" class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div class="">Preliminary evaluation of a patch which prefers exploring nodes associated with statements which weren’t seen before first:</div><div class=""><br class=""></div>On openssl:<div class=""><br class=""></div><div class=""> - Adds four reports</div><div class=""> - Removes four reports </div><div class=""> - Path lengths before: 317, 75, 75, 72, 70, 58, 50, 50, 44, 36, 23, 23, 21, 21, 20, 20, 19, 19, 19, 19, 18, 18, 18, 16, 15, 15, 15, 14, 13, 13, 12, 11, 11, 9, 7, 7, 6, 4</div><div class=""> - Path lengths after: 72, 60, 59, 53, 53, 52, 46, 38, 37, 30, 29, 28, 23, 21, 20, 19, 19, 19, 19, 19, 18, 16, 15, 15, 15, 15, 13, 13, 12, 12, 11, 9, 8, 7, 7, 7, 6, 4</div><div class=""><br class=""></div><div class="">The quality of the added reports seems higher, mainly due to the fact that report length is shorter.</div><div class=""><br class=""></div><div class="">On postgresql:</div><div class=""><br class=""></div><div class=""> - Added 80 reports</div><div class=""> - Removed 154 reports</div><div class=""> -> Out of those, 72 are reports on the yacc/bison autogenerated files, so whatever the cause is, good thing they are gone</div><div class=""> - The overall number of reports is 1188</div><div class=""> - Path lengths are lower on overall, but not in such a dramatic way</div><div class=""> - For many reports, I am quite confused as to why they got removed</div><div class=""><br class=""></div><div class="">On sqlite:</div><div class=""><br class=""></div><div class=""> - 7 inserted, 7 removed</div><div class=""><br class=""></div><div class=""><div class=""><div class=""><blockquote type="cite" class=""><div class="">On Jan 30, 2018, at 1:10 PM, Artem Dergachev <<a href="mailto:noqnoqneo@gmail.com" class="">noqnoqneo@gmail.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class=""><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class=""><span style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; float: none; display: inline !important;" class="">On 30/01/2018 12:40 PM, Gábor Horváth via cfe-dev wrote:</span><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class=""><blockquote type="cite" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; text-decoration: none;" class="">Hi George, Artem,<br class=""><br class="">I am glad that you are looking into this problem!<br class=""><br class="">On 30 January 2018 at 01:12, George Karpenkov via cfe-dev <<a href="mailto:cfe-dev@lists.llvm.org" class="">cfe-dev@lists.llvm.org</a><span class="Apple-converted-space"> </span><<a href="mailto:cfe-dev@lists.llvm.org" class="">mailto:cfe-dev@lists.llvm.org</a>>> wrote:<br class=""><br class=""> Hi All,<br class=""><br class=""> I was investigating recently bug reports with very long analyzer<br class=""> paths (more than a few hundred nodes).<br class=""> In many of such cases the path is long for no good reason: namely,<br class=""> the analyzer would go 3 times around the loop before<br class=""> going further.<br class=""> The issue is surprisingly common, and it was exacerbated with a<br class=""> recent bump of analyzer thresholds.<br class=""><br class=""> The problem is reproduced on the following file:<br class=""><br class=""> ```<br class=""> extern int coin();<br class=""><br class=""> int foo() {<br class=""> int *x = 0;<br class=""> while (coin()) {<br class=""> if (coin())<br class=""> return *x;<br class=""> }<br class=""> return 0;<br class=""> }<br class=""><br class=""> void bar() {<br class=""> while(coin())<br class=""> if (coin())<br class=""> foo();<br class=""> }<br class=""> ```<br class=""><br class=""> While a shortest path to the error does not loop around, the<br class=""> current version of the analyzer<br class=""> will go around the loop three times before going further.<br class=""> (and we are quite fortunate that the unrolling limit for loops is<br class=""> three, otherwise it would keep going<br class=""> until the unrolling limit is reached).<br class=""><br class=""> Multiple issues were discovered during the investigation.<br class=""><br class=""> 1. Analyzer queue does not have a concept of priority, and<br class=""> performs a simple DFS by default.<br class=""> Thus if the successor of the if-branch under the loop in “bar"<br class=""> containing the desired destination is generated second,<br class=""> it will never be evaluated until the loop exploration limit is<br class=""> exhausted.<br class=""><br class=""> 2. The previous issue slows down the exploration, but is not<br class=""> enough to get a pathological behavior of ultra-long paths.<br class=""> The second problem is a combination of:<br class=""> a) Block counter is not a part of a node's identity, and node A<br class=""> with a small block counter can be merged into a node B with a<br class=""> large block counter,<br class=""> and the resulting node will have a block counter associated with B.<br class=""><br class=""><br class="">Sorry for the questions, just wanted to clarify some things. You mean ExplodedNodes? By merge, you mean the same thing as "caching-out"?<br class=""></blockquote><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class=""><span style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; float: none; display: inline !important;" class="">Yeah, George notices that if we construct the same ExplodedNode on two different paths that have different block counts, we'd cache-out on the latter path, while the worklist element of the first path would still possess the original block count.</span><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class=""><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class=""><span style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; float: none; display: inline !important;" class="">Which happens a lot when we're evaluating foo() conservatively in this example.</span><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class=""><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class=""><span style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; float: none; display: inline !important;" class="">This isn't directly related to our problem though, as i noticed in<span class="Apple-converted-space"> </span></span><a href="http://lists.llvm.org/pipermail/cfe-dev/2018-January/056719.html" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px;" class="">http://lists.llvm.org/pipermail/cfe-dev/2018-January/056719.html</a><span style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none; float: none; display: inline !important;" class=""><span class="Apple-converted-space"> </span>.</span><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class=""><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class=""><br style="caret-color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration: none;" class=""><blockquote type="cite" style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; text-decoration: none;" class=""> b) The issue in (a) is triggered due to our heuristic to abandon<br class=""> the function’s exploration and switch to conservative evaluation<br class=""> if we are already *inside* the function and the block limit has<br class=""> been reached.<br class=""><br class=""> Issue (1) combined with (2-b) causes the problematic behavior: the<br class=""> issue is discovered on the longest path first,<br class=""> and by the time the shortest path gets to “bar”, the block limit<br class=""> is already reached, and the switch to conservative evaluation is<br class=""> performed.<br class=""><br class=""> Thus there are two mitigation strategies currently being evaluated:<br class=""><br class=""> i) Remove the heuristic in (2-b)<br class=""> ii) Use a priority queue to hold nodes which should be explored;<br class=""> prefer nodes which give new source code coverage over others<br class=""> (or alternatively prefer nodes with least depth of loop stack)<br class=""><br class=""> Me and Artem have evaluated the option (i) and the results were<br class=""> surprisingly good: some reports disappear, and slightly more<br class=""> reports reappear.<br class=""> The quality of the new reports seems to be slightly better, and I<br class=""> am still trying to figure out exact reasons.<br class=""> I suspect merges resulting from heuristic (2-b) cause us to lose<br class=""> some actually valid reports.<br class=""><br class=""><br class="">I also find the results surprising. If you have more information about the reasons please do not forget to follow up this thread. We are curious :)<br class=""><br class=""><br class=""> Option (ii) has not been evaluated fully yet, but current<br class=""> experiments show slightly more reports (5-10%), and a radical<br class=""> decline in report lengths<br class=""> (e.g. from 400+ to <100 for largest reports)<br class=""><br class=""> Are there any thoughts on the matter?<br class=""><br class=""> Personally I think we should do both (i) and (ii), even if they<br class=""> would shake up the results.<br class=""> - The original idea for heuristics (2-b) was to be able to produce<br class=""> a report even if we are out of budget, but since it actually<br class=""> results in less reports,<br class=""> I think the data does not validate the approach.<br class=""><br class=""> - Option (ii) is AFAIK how most similar engines work, and should<br class=""> get us much larger coverage (and shorter paths) for the same node<br class=""> budget,<br class=""> even at the cost of log(N) overhead of the priority queue.<br class=""> Moreover, not having the priority queue will bite us later if we<br class=""> ever decide to further<br class=""> increase the analyzer budget or to increase the unroll limit.<br class=""><br class=""><br class="">I wonder what will the performance implication be. But I also like the idea of having a priority queue. If we find that we get more and better report<br class="">but also have worse performance, we can also consider reducing the analysis budget slightly.<br class=""><br class="">Regards,<br class="">Gábor<br class=""><br class=""><br class=""> George<br class=""><br class=""><br class=""><br class=""> _______________________________________________<br class=""> cfe-dev mailing list<br class=""> <a href="mailto:cfe-dev@lists.llvm.org" class="">cfe-dev@lists.llvm.org</a><span class="Apple-converted-space"> </span><<a href="mailto:cfe-dev@lists.llvm.org" class="">mailto:cfe-dev@lists.llvm.org</a>><br class=""> <a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" class="">http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev</a><br class=""> <<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" class="">http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev</a>><br class=""><br class=""><br class=""><br class=""><br class="">_______________________________________________<br class="">cfe-dev mailing list<br class=""><a href="mailto:cfe-dev@lists.llvm.org" class="">cfe-dev@lists.llvm.org</a><br class=""><a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" class="">http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev</a></blockquote></div></blockquote></div><br class=""></div></div></div></div></blockquote></div><br class=""></div></body></html>