Slicing communicating automata specifications pol

Authors: Sébastien Labbé JeanPierre Gallois

Publish Date: 2008/08/13

Volume: 20, Issue: 6, Pages: 563-595

PDF Link

Abstract

In the industry communicating automata specifications are mainly used in fields where the reliability requirements are high as this formalism allow the use of powerful validation tools Still on large scale industrial specifications formal methods suffer from the combinatorial explosion phenomenon In our contribution we suggest to try to bypass this phenomenon in applying slicing techniques preliminarily to the targeted complex analysis This analysis can thus be performed a posteriori on a reduced or sliced specification which is potentially less exposed to combinatorial explosion The slicing method is based on dependence relations defined on the specification under analysis and is mainly founded on the literature on compiler construction and program slicing A theoretical framework is described for static analyses of communicating automata specifications This includes formal definitions for the aforementioned dependence relations and for a slice of a specification with respect to a slicing criterion Efficient algorithms are also described in detail for calculating dependence relations and specification slices Each of these algorithms has been shown to be polynomial and sound and complete with respect to its respective definition These algorithms have also been implemented in a slicing tool named Carver that has shown to be operational in specification debugging and understanding The experimental results obtained in model reduction with this tool are promising notably in the area of formal validation and verification methods egmodel checking test case generation

Keywords: