Set-Based Analysis
Program Analysis
The purpose of program analysis is to find out information
about a program's run-time behavior. One of the main applications of program
analysis is in compiler optimization.
The idea of approximating program behaviour is central to program analysis
because, for pragmatic and theoretical reasons, programs cannot be analyzed
exactly.
The Set-Based Approach
In set-based analysis (SBA), programs are approximated using a very simple
abstraction: programs variables are viewed as sets of values. In essence, this
corresponds to ignoring inter-variable dependencies, but making no approximation
of the underlying space of values. SBA provides an intuitive, abstract and
non-algorithmic view of what the analysis will achieve, in combination with an
accurate and uniform treatment of data-structures.
While SBA can be formulated as an abstract interpretation in a straightforward
way, the corresponding iterative fixpoint computation does not usually terminate
(the sets generated by a set-based approximation are typically infinite).
Instead, new algorithmic techniques are needed to reason directly about
(arbitrary) sets of values. This has motivated the developed the calculus of
set constraints.
Some SBA Papers
Some Related Papers
nch@cs.cmu.edu