Towards Abstraction for DynAlloy Specifications

NAZARENO AGUIRRE; MARCELO F. FRIAS; PABLO PONZIO; BRIAN J. CARDIFF; JUAN P. GALEOTTI; GERMÁN REGIS

LECTURE NOTES IN COMPUTER SCIENCE

Springer Berlin Heidelberg

Año: 2008 p. 207 - 225

0302-9743

DynAlloy is an extension of the Alloy language to better de- scribe state change via actions and programs, in the style of dynamic logic. In this paper, we report on our experience in trying to provide ab- straction based mechanisms for improving DynAlloy specifications with respect to SAT based analysis. The technique we employ is based on predicate abstraction, but due to the context in which we make use of it, is subject to the following more specific improvements: (i) since DynAl- loy?s analysis consists of checking partial correctness assertions against programs, we are only interested in the initial and final states of a com- putation, and therefore we can safely abstract away some intermediate states in the computation (generally, this kind of abstraction cannot be safely applied in model checking), (ii) since DynAlloy?s analysis is in- herently bounded, we can safely rely on the sole use of a SAT solver for producing the abstractions, and (iii) since DynAlloy?s basic operational unit is the atomic action, which can be used in different parts within a program, we can reuse the abstraction of an action in different parts of a program, which can accelerate the convergence in checking valid properties. We present the technique via a case study based on a translation of a JML annotated Java program into DynAlloy, accompanied by some preliminary experimental results showing some of the benefits of the technique.