Interaction languages such as MSC are often associated with formal semantics by means of translations into distinct behavioral formalisms such as automatas or Petri nets. In contrast to translational approaches we propose an operational approach. Its principle is to identify which elementary communication actions can be immediately executed, and then to compute, for every such action, a new interaction representing the possible continuations to its execution. We also define an algorithm for checking the validity of execution traces (i.e. whether or not they belong to an interaction’s semantics). Algorithms for semantic computation and trace validity are analyzed by means of experiments.
Interaction models describe the exchange of messages between the different components of distributed systems. This paper presents an approach for checking the validity of multi-traces against interaction models. A multi-trace is a collection of traces (sequences of emissions and receptions), each representing a local view of the same global execution of the distributed system. We formally prove our approach, study its complexity, and implement it in a prototype tool.
Interactions are graphical models representing communication flows between actors. Well-known interaction languages include UML Sequence Diagrams or Message Sequence Charts. Even though interactions allow for concise and intuitive specifications, their use remains limited in formal verification, partly because the subsets of formalized languages often lack expressiveness. As many verification methods, such as model-checking or runtime verification, are routinely available for finite automata, we propose a new approach to generate finite automata from an expressive interaction language with operators such as the concurrent region. Our approach leverages an operational semantics to compute derivatives of an interaction and assimilate them to states of a finite automata. In addition, we use term rewriting to merge states on-the-fly so as to obtain small automata without relying on costly a-posteriori minimization techniques.
Interaction languages such as MSC are often associated with formal semantics by means of translations into distinct behavioral formalisms such as automatas or Petri nets. In contrast to translational approaches we propose an operational approach. Its principle is to identify which elementary communication actions can be immediately executed, and then to compute, for every such action, a new interaction representing the possible continuations to its execution. We also define an algorithm for checking the validity of execution traces (i.e. whether or not they belong to an interaction's semantics). Algorithms for semantic computation and trace validity are analyzed by means of experiments.