1987 · 106 citations · 19 references
ComputingComputer ScienceAlgorithmsFormal MethodsSecurity ProtocolsModel CheckingNetwork ProtocolsProtocol AnalysisProtocol VerificationVerificationAutomated Protocol VerificationCommunication ProtocolsFinite State Machine VerificationFinite-state VerificationProtocol TestingReachabilityReachability AnalysisState Space Explosion
Reachability analysis has proved to be one of the most effective methods in verifying correctness of communication protocols based on the state transition model. Consequently, many protocol verification tools have been built based on the method of reachability analysis. Nevertheless, it is also well known that state space explosion is the most severe limitation to the applicability of this method. Although researchers in the field have proposed various strategies to relieve this intricate problem when building the tools, a survey and evaluation of these strategies has not been done in the literature. In searching for an appropriate approach to tackling such a problem for a grammar-based validation tool, we have collected and evaluated these relief strategies, and have decided to develop our own from yet another but more systematic approach. The results of our research are now reported in this paper. Essentially, the paper is to serve two purposes: first, to give a survey and evaluation of existing relief strategies; second, to propose a new strategy, called PROVAT (PROtocol VAlidation Testing), which is inspired by the heuristic search techniques in Artificial Intelligence. Preliminary results of incorporating the PROVAT strategy into our validation tool are reviewed in the paper. These results show the empirical evidence of the effectiveness of the PROVAT strategy.
19
On Communicating Finite-State Machines
Daniël Brand, P. Zafiropulo · Journal of the ACM · 1983 · 1.1K citations · Full text
Towards Analyzing and Synthesizing Protocols
P. Zafiropulo, Colin H. West, H. Rudin et al. · IRE Transactions on Communications Systems · 1980 · 239 citations