Abstract:

To alleviate the state-explosion problem of model checking, a novel distributed model checking method based on the propositional projection temporal logic (PPTL). First, the property to be verified in the PPTL formula is transformed into an automaton with the technique of Labeled Normal Form Graph, which in turn is partitioned into multiple subautomata according to the strongly connected components. Then, each subautomaton and the system model in the Hierarchical Syntax Chart are delivered to the members of the verification server cluster, and model checking of the system is implemented in parallel with the on-the-fly technique on multiple computers. Experimental results indicate that, compared with the standalone model checking approach, the proposed method can not only significantly reduce the time consumption but also verify more complex systems.

Key words: propositional projection temporal logic, model checking, formal verification, labeled normal form graph, distributed computing