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

  • A Finite Presentation Theorem for Approximating Logic Programs (popl-90) (ibm-tr)
  • A Decision Procedure for a Class of Set Constraints (lics-90) (ibm-tr)
  • Set-Based Analysis (unpublished)
  • Practical Aspects of Set-Based Analysis (jicslp-92)
  • Set-Based Analysis of ML Programs (lfp-94)
  • Set-Based Analysis and Arithmetic (cmu-tr)
  • Some Related Papers

  • An Engine for Logic Program Analysis (lics-92)
  • A Generic Algorithm for CLP Analysis (iclp-95)
  • Set Constraints in Program Analysis (Survey) (islp93-workshop)
  • Set Constraints and Set-Based Analysis (Survey) (ppcp-94)
  • Constraint-Based Program Analysis (Tutorial) (popl-95 slides)