[cfe-dev] [analyzer] exploration strategies and paths

[Gábor Horváth via cfe-dev]

Hi George, Artem,

I am glad that you are looking into this problem!

On 30 January 2018 at 01:12, George Karpenkov via cfe-dev <
cfe-dev at lists.llvm.org> wrote:

> Hi All,
>
> I was investigating recently bug reports with very long analyzer paths
> (more than a few hundred nodes).
> In many of such cases the path is long for no good reason: namely, the
> analyzer would go 3 times around the loop before
> going further.
> The issue is surprisingly common, and it was exacerbated with a recent
> bump of analyzer thresholds.
>
> The problem is reproduced on the following file:
>
> ```
> extern int coin();
>
> int foo() {
>     int *x = 0;
>     while (coin()) {
>         if (coin())
>             return *x;
>     }
>     return 0;
> }
>
> void bar() {
>     while(coin())
>         if (coin())
>             foo();
> }
> ```
>
> While a shortest path to the error does not loop around, the current
> version of the analyzer
> will go around the loop three times before going further.
> (and we are quite fortunate that the unrolling limit for loops is three,
> otherwise it would keep going
> until the unrolling limit is reached).
>
> Multiple issues were discovered during the investigation.
>
> 1. Analyzer queue does not have a concept of priority, and performs a
> simple DFS by default.
> Thus if the successor of the if-branch under the loop in “bar" containing
> the desired destination is generated second,
> it will never be evaluated until the loop exploration limit is exhausted.
>
> 2. The previous issue slows down the exploration, but is not enough to get
> a pathological behavior of ultra-long paths.
> The second problem is a combination of:
> a) Block counter is not a part of a node's identity, and node A with a
> small block counter can be merged into a node B with a large block counter,
> and the resulting node will have a block counter associated with B.
>

Sorry for the questions, just wanted to clarify some things. You mean
ExplodedNodes? By merge, you mean the same thing as "caching-out"?


> b) The issue in (a) is triggered due to our heuristic to abandon the
> function’s exploration and switch to conservative evaluation
> if we are already *inside* the function and the block limit has been
> reached.
>
> Issue (1) combined with (2-b) causes the problematic behavior: the issue
> is discovered on the longest path first,
> and by the time the shortest path gets to “bar”, the block limit is
> already reached, and the switch to conservative evaluation is performed.
>
> Thus there are two mitigation strategies currently being evaluated:
>
> i) Remove the heuristic in (2-b)
> ii) Use a priority queue to hold nodes which should be explored; prefer
> nodes which give new source code coverage over others
> (or alternatively prefer nodes with least depth of loop stack)
>
> Me and Artem have evaluated the option (i) and the results were
> surprisingly good: some reports disappear, and slightly more reports
> reappear.
> The quality of the new reports seems to be slightly better, and I am still
> trying to figure out exact reasons.
> I suspect merges resulting from heuristic (2-b) cause us to lose some
> actually valid reports.
>

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 :)


>
> Option (ii) has not been evaluated fully yet, but current experiments show
> slightly more reports (5-10%), and a radical decline in report lengths
> (e.g. from 400+ to <100 for largest reports)
>
> Are there any thoughts on the matter?
>
> Personally I think we should do both (i) and (ii), even if they would
> shake up the results.
> - The original idea for heuristics (2-b) was to be able to produce a
> report even if we are out of budget, but since it actually results in less
> reports,
> I think the data does not validate the approach.
>
> - Option (ii) is AFAIK how most similar engines work, and should get us
> much larger coverage (and shorter paths) for the same node budget,
> even at the cost of log(N) overhead of the priority queue. Moreover, not
> having the priority queue will bite us later if we ever decide to further
> increase the analyzer budget or to increase the unroll limit.
>

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
but also have worse performance, we can also consider reducing the analysis
budget slightly.

Regards,
Gábor


>
> George
>
>
>
> _______________________________________________
> cfe-dev mailing list
> cfe-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20180130/e8779209/attachment.html>