Break loops when verifying recursive functions with context-sensitive function domains

[danmatichuk]

When running the verifier with context-sensitive function domains (i.e. using distinct domains for each call site for a function, rather than collapsing all function calls to have the same domain), there is a high risk of entering an infinite analysis loop when processing recursive functions. This occurs when the value domain is not strong enough to statically determine the termination condition for the recursion, resulting in an infinite number of possible call sites for the function (with each recursive call adding more context).

The easiest solution is to simply break loops when a function call is already present in the context, however this could also be generalized to allowing some fixed number of self-ancestors.

[travitch]

One of the usual ways to think about context sensitivity is to name each abstract state with a "key" and just let the fixed point engine churn away without any special handling of loops (unless you want to explicitly widen when you detect loops). The most common "key" is a "call string" constrained to a length k, where k is your degree of context sensitivity. A call string is just a sequence of all of the call sites on the call stack. This naturally limits the precision and avoids infinite recursion while supporting context sensitivity.

[danmatichuk]

I think that would be a fairly trivial change to the existing approach. I'm assuming that once you hit the context cap you just start dropping off the earliest entries? With a max context of k calls, a recursive loop would then get broken once after k iterations when the entire context is filled with the same recursive call.

[travitch]

I think that would be a fairly trivial change to the existing approach. I'm assuming that once you hit the context cap you just start dropping off the earliest entries? With a max context of k calls, a recursive loop would then get broken once after k iterations when the entire context is filled with the same recursive call.

Correct