The recent extensive availability of "big data" platforms calls for a widespread adoption by the formal verification community. Cloud computing platforms represent a great opportunity to run massively parallel jobs, yet classical formal verification tools techniques must undergo a deep technological transformation in order to exploit the new available architectures. This has raised an increasing interest in deploying verification techniques on parallel distributed frameworks. In this paper we introduce a framework to ease the adoption of a distributed approach to verification of Computation Tree Logic (CTL) formulas on very large state spaces. The approach exploits integrates a recently developed, parametric state-space builder. The whole framework adopts M AP R EDUCE as core computational model, and can be tailored to different modelling formalisms. The outcomes of several tests performed on (Petri-nets based) benchmark specifications are presented, thus showing the convenience of the proposed approach.
The main idea of distributed algorithms for both LTL and CTL model checking is in fact similar: the state graph is partitioned among the network nodes, each network node owns a subset of the state space. The differences are in the way the state space is partitioned (through a ): this is a crucial issue. In order to increase performance of the parallel model checking, it is key to achieve a good load balancing among machines, meaning that each partition should contain nearly the same number of states. The performance of these algorithms depends also on the number of cross-border transitions of the partitioned state space ( transitions having the source state in a component and the target state in another component). This number should be as small as possible, since it has an effect on the number of messages sent over the network during the analysis @cite_24 . In the context of LTL model checking, probabilistic techniques to partition the state space have been used, for example, in @cite_29 @cite_19 , and a technique that exploits some structural properties derived from the verified formula has been proposed in @cite_5 .
@cite_24 @cite_19 @cite_29 @cite_5
2081955678 2125040344 2021285256 2167672803
As model checking becomes increasingly used in industry, there is a big need for efficient new methods to deal with the large real-size designs. The author presents a novel method for improving the performance of model checking using parallelisation techniques. The model checking is performed on a distributed-memory environment consisting of a network of machines. The important two keys to focus on are the memory balance and communication reduction. A new algorithm for partitioning the large state space modelling industrial designs with hundreds of millions of states and transitions is proposed. The state space is supposed to be represented by a weighted Kripke structure (this is an extension of the Kripke structure where weights are associated with the states and with the transitions). This algorithm partitions the weighted Kripke structure by performing a combination of abstraction-partition-refinement on this structure. The CTL model checking algorithm is distributed on processes located on different network machines. Each one owns a partition and executes the algorithm on it. The algorithm for CTL model checking is designed to reduce the communication overhead between the processes. The experimental results on large real designs show that this method improves the quality of partitions, the communication overhead and then the overall performance of the model checking. In this paper, we propose a distributed algorithm for CTL model-checking and a counterexample search whenever the CTL formula is not satisfied. The distributed approach is used in order to cope with the state space explosion problem. A cluster of workstations performs collaborative verification over a partitioned state space. Thus, every process involved in the distributed verification performs the labelling procedure on its own partial state space, and uses the parse tree of the CTL formula to evaluate sub-formulas and delay the synchronisations so as to minimise idle time. A counterexample search consists in a distributed construction of the tree-like corresponding to the failure executions. Some experiments have been carried out to evaluate the efficiency of this approach. In this paper we discuss the problem of performing distributed CTL model checking by splitting the given state space into several "partial state spaces." The partial state space is modelled as a Kripke structure with border states. Each computer involved in the distributed computation owns a partial state space and performs a model-checking algorithm on this incomplete structure. To be able to proceed, the border states are augmented by assumptions about truth values of formulas and the computers exchange assumptions about relevant states to compute more precise information. We study the problem of model checking software product line (SPL) behaviours against temporal properties. This is more difficult than for single systems because an SPL with n features yields up to 2n individual systems to verify. As each individual verification suffers from state explosion, it is crucial to propose efficient formalisms and heuristics. We recently proposed featured transition systems (FTS), a compact representation for SPL behaviour, and defined algorithms for model checking FTS against linear temporal properties. Although they showed to outperform individual system verifications, they still face a state explosion problem as they enumerate and visit system states one by one. In this paper, we tackle this latter problem by using symbolic representations of the state space. This lead us to consider computation tree logic (CTL) which is supported by the industry-strength symbolic model checker NuSMV. We first lay the foundations for symbolic SPL model checking by defining a feature-oriented version of CTL and its dedicated algorithms. We then describe an implementation that adapts the NuSMV language and tool infrastructure. Finally, we propose theoretical and empirical evaluations of our results. The benchmarks show that for certain properties, our algorithm is over a hundred times faster than model checking each system with the standard algorithm.