provides liveness analysis and uses liveness for Sub.free_vars #1051
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
implements liveness analysis for subroutines and provides it
as [Sub.compute_liveness] which returns a fixed point solution to
the variable liveness property.
uses liveness to compute free variables when a subroutime is not
in the SSA form
Sub.to_graph now returns a fully connected graph with two
pseudo-nodes, [start], and [exit] (we keep doing every time we need to
do some graph computation, so let's make it official). This
pseudo-nodes are constants defined in the [Graphs.Tid] interface.
Context
We used to rely on the dominators tree to compute the set of free
variables when the SSA form is not available. It was an optimization,
as by that time we didn't have the fixpoint function and didn't want
to compute SSA just for getting free vars. It was also returning an
underapproximation, rather than overapproximation (i.e., was a must free
analysis), which was fine with some existing uses of the
[Sub.free_vars] function, but wasn't sufficient/correct for other
uses, e.g., in the promiscuous mode we were relying on it to turn a
subroutine into a closed form, to prevent failures in runtime with
undefined variable (we probably could just define all vars used in the
program, but this is a different story). Since [Sub.free_vars] were
returning an under-approximation we still experiences some runtime
failures, which were halting our machines that resulted in non-visited
code and missing vulnerabilities.