Búsqueda avanzada

Abstract analysis of universal properties for tccp


The Timed Concurrent Constraint Language (tccp) is a time extension of the concurrent constraint paradigm of Saraswat. tccp was defined to model reactive systems, where infinite behaviors arise naturally. It is well-known that modeling and analyzing concurrent systems by hand can be an extremely hard task. Thus, the development of automatic formal methods is essential. The particular characteristics of ccp languages make such task even harder, since we have to deal with technical issues due to the infinite computations (natural to reactive systems), use of negative information (particular for ccp languages) and non-determinism.
One well established technique to develop semantic-based program analysis is abstract interpretation, which relies on the definition of a specific approximated abstract semantics that captures the information needed to perform the analysis. Typically, one defines an over-approximation of the concrete semantics that includes all possible traces of the system, possibly introducing inexistent ones. This allows one to develop (correct) analysis of universal properties. It does not allow to analyze existential properties, for instance to verify that there exists a suspension trace.
This paper (originally published in [1]) defines a framework of over-approximated abstract semantics parametric w.r.t. an abstract constraint system.
Since we need to preserve the notion of time—to be able to express properties of interest like safety or time-depending properties—the abstract semantics domains are not Noetherian (even if we use finite abstract constraint systems). Thus, in order to have an effective approach we use a widening to ensure finiteness of the analysis.
The abstract semantics is correct and can be represented as a finite graph where each node represents
a hypothetical computational step of the program containing approximated information for the variables.

Palabras Clave:





Este artículo tiene una licencia de uso CreativeCommons Reconocimiento (by)

Descarga el artículo haciendo click aquí.