A Method for Symbolic Computation of Abstract Operations

Thakur, Aditya V. and Reps, Thomas W.
24th International Conference on Computer Aided Verification (CAV), 2012

This paper helps to bridge the gap between (i) the use of logic for specifying program semantics and performing program analysis, and (ii) abstract interpretation. Many operations needed by an abstract interpreter can be reduced to the problem of symbolic abstraction: the symbolic abstraction of a formula φ in logic L, denoted by alphaHat(φ), is the most-precise value in abstract domain A that over-approximates the meaning of φ. We present a parametric framework that, given L and A, implements alphaHat. The algorithm computes successively better over-approximations of alphaHat(φ). Because it approaches alphaHat(φ) from "above", if it is taking too much time, a safe answer can be returned at any stage.

Moreover, the framework is "dual-use": in addition to its applications in abstract interpretation, it provides a new way for an SMT (Satisfiability Modulo Theories) solver to perform unsatisfiability checking: given φ ∈ L, the condition alphaHat(φ) = ⊥ implies that φ is unsatisfiable.

PDF     Springer©    

@inproceedings{thakur_reps_CAV12,
  author = {Thakur, Aditya V. and Reps, Thomas W.},
  title = {A Method for Symbolic Computation of Abstract Operations},
  booktitle = {24th International Conference on Computer Aided Verification ({CAV})},
  year = {2012},
  pages = {174--192},
  publisher = {Springer},
  doi = {10.1007/978-3-642-31424-7_17}
}