Protocol validation and verification techniques have been applied successfully for a number of years to a wide range of protocols. The increasing complexity of our communications systems requires us to examine existing techniques and make a realistic assessment of which techniques will be applicable to the complex systems of the future. We believe that validation techniques based on an exhaustive reachability analysis will not be effective. Sampling techniques, such as executing a random walk through the reachable state space, are effective in complex systems, since most protocol errors occur in many different states of the system.

For several years the authors have been part of an effort developing automated techniques for examining the syntax of protocols for the absence of various errors. Recently, we have turned our attention to trying to prove various functional properties of protocols used in ring-topology systems. Ring systems have a number of properties that distinguish them from the more general computer networks towards which our earlier validation work was directed. We report here on the resulting changes in the protocol models and validation techniques, together with extensions used to prove that the protocol being examined has the various desirable functional properties demanded of it.

The definition of IBM's Systems Network Architecture (SNA) has evolved into a specification of a node in the form of a metaimplementation using formal, state-oriented descriptive techniques. This evolution is traced here, and the different formal techniques are described. The culmination of this process has been the development of a PL/I-based programming language, Format and Protocol Language (FAPL), as a descriptive tool. Using FAPL, the architects now define SNA by a programmed meta-implementation of a node. In this form, it is precise, readily accessible to the implementing product designers and programmers, and structurally close to the implementations. The essential features of the meta-implementation and of FAPL are described, along with the implications and advantages of describing the architecture in an executable form. One major benefit, already being realized, is the capability to test the logical consistency and completeness of the executable description itself. The current status of the validation of the executable description and sample results obtained are described.

The production of error-free protocols or complex process interactions is essential to reliable communications. This paper presents techniques for both the detection of errors in protocols and for prevention of errors in their design. The methods have been used successfully to detect and correct errors in existing protocols. A technique based on a reachability analysis is described which detects errors m a design. This "perturbation technique" has been implemented and has successfully detected inconsistencies or errors in existing protocol designs including both X.21 and X.25. The types of errors handled are state deadlocks, unspecified receptions, nonexecutable interactions, and state smbiguities. These errors are discussed and their effects considered. An interactive design technique is then described that prevents design errors. The technique is based on a set of production rules which guarantee that complete reception capability is provided in the interacting processes. These rules have been implemented in the form of a tracking algorithm that prevents a designer from creating unspecified receptions and nonexecutable interactions and monitors for the presence of state deadlocks and ambiguities.

An interaction between two communicating processes can be defined in terms of a protocol or set of rules governing the exchange of messages between them. For any given protocol, it is a significant problem to determine whether or not errors can occur when the processes interact. In this paper, we describe an implementation of a recent theory of Zafiropulo, which defines protocols in terms of the interaction between two directed graphs, and uses set theory and predicate logic to determine all error conditions that can arise. The overall structure of the theory is used, but the determination of the error conditions is based on a graphical representation of the interaction, and particular emphasis is placed on the state of the channel between the two processes. The technique is currently limited to the validation of two-process protocols in which the processes return to an initial state after a finite number Of interaction steps. The implementation demonstrates that a completely automated procedure can be defined which finds a significant class of errors in communications protocols.