Abstraction is intensively used in the verification of large, complex or infinite-state systems. With abstractions getting more complex it is often difficult to see whether they are valid. However, for using abstraction in model checking it has to be ensured that properties are preserved. In this paper, we use a translation validation approach to verify property preservation of system abstractions. We formulate a correctness criterion based on simulation between concrete and abstract system for a property to be verified. For each distinct run of the abstraction procedure the correctness is verified in the theorem prover Isabelle/HOL. This technique is applied in the verification of embedded adaptive systems. This paper is an extended version a previously published work.
This technical report contains the preliminary versions of the regular papers presented at the first workshop on Verification of Adaptive Systems (VerAS) that has been held in Kaiserslautern, Germany, on September 14th, 2007 as part of the 20th International Conference on Theorem Proving in Higher Order Logics. The final versions will be published with Elsevier's Electronic Notes on Theoretical Computer Science (ENTCS). VerAS is the first workshop that aims at considering adaptation as a cross-cutting system aspect that needs to be explicitly addressed in system design and verification. The program committee called for original submissions on formal modeling, specification, verification, and implementation of adaptive systems. There were six submissions from different countries of Europe. Each submission has been reviewed by three programme committee members. Finally, the programme committee decided to accept three of the six submissions. Besides the presentations of the regular papers, the workshop's programme included a tutorial on the `Compositional Verification of Self-Optimizing Mechatronic Systems' held by Holger Giese (University of Paderborn, Germany) as well as three presentations of DASMOD projects on the verification of adaptive systems.
Ownership Domains generalize ownership types. They support programming patterns like iterators that are not possible with ordinary ownership types. However, they are still too restrictive for cases in which an object X wants to access the public domains of an arbitrary number of other objects, which often happens in observer scenarios. To overcome this restriction, we developed so-called loose domains which abstract over several precise domains. That is, similar to the relation between supertypes and subtypes we have a relation between loose and precise domains. In addition, we simplified ownership domains by reducing the number of domains per object to two and hard-wiring the access permissions between domains. We formalized the resulting type system for an OO core language and proved type soundness and a fundamental accessibility property.
A translation contract is a binary predicate corrTransl(S,T) for source programs S and target programs T. It precisely specifies when T is considered to be a correct translation of S. A certifying compiler generates --in addittion to the target T-- a proof for corrTransl(S,T). Certifying compilers are important for the development of safety critical systems to establish the behavioral equivalence of high-level programs with their compiled assembler code. In this paper, we report on a certifying compiler, its proof techniques, and the underlying formal framework developed within the proof assistent Isabelle/HOL. The compiler uses a tiny C-like language as input, has an optimization phase, and generates MIPS code. The underlying translation contract is based on a trace semantics. We investigate design alternatives and discuss our experiences.