Protocol validation in complex systems
Author:
Open Access
- 1 August 1989
- journal article
- conference paper
- Published by Association for Computing Machinery (ACM) in ACM SIGCOMM Computer Communication Review
- Vol. 19 (4) , 303-312
Abstract
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. More than 10 years have elapsed since the first automated validation techniques were first applied to communications protocols [1,2]. In the meantime, considerable advances have been made in validation technology, but more significantly, the scale and nature of the validation problem have changed. The communications systems that we need to validate today are significantly more complex than those of ten years ago. Our methods must evolve in order to address the current challenge. This paper is concerned primarily with the nature of the validation process, and the results that we might reasonably expect to achieve when validating protocols in complex communications systems.Keywords
This publication has 11 references indexed in Scilit:
- Program verification: the very ideaCommunications of the ACM, 1988
- Format and protocol language (FAPL)Computer Networks and ISDN Systems, 1987
- Protocol verification using reachability analysis: the state space explosion problem and relief strategiesACM SIGCOMM Computer Communication Review, 1987
- A validation of the OSI session layer protocolComputer Networks and ISDN Systems, 1986
- Automated verification of connection management of NBS class 4 transport protocol1984
- Protocol Validation by Maximal Progress State ExplorationIEEE Transactions on Communications, 1984
- On Communicating Finite-State MachinesJournal of the ACM, 1983
- Executable Representation and Validation of SNA1982
- General Technique for Communications Protocol ValidationIBM Journal of Research and Development, 1978
- Automated Validation of a Communications Protocol: the CCITT X.21 RecommendationIBM Journal of Research and Development, 1978