Minimum-cost synchronizable test sequence generation via the duplexU digraph
Authors:
- H. UralHUH. Ural
- 31 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 128-135 vol.1
Abstract
A test sequence generation method is proposed for testing the conformance of a protocol implementation to its specification in a remote testing system, taking both external synchronization and input/output operation costs into consideration. The method consists of a set of transformation rules that constructs a duplexU digraph from a given finite state machine (FSM) representation of a protocol specification and a heuristic algorithm that finds a rural postman tour in the duplexU digraph to generate a synchronizable test sequence utilizing multiple UIO sequences. If the protocol satisfies a specific property, the heuristic algorithm yields a minimum-cost test sequence. The X.25 DTE and ISO Class 0 Transport protocols are proved to possess this specific property. otherwise, the heuristic algorithm yields a test sequence whose cost is within a bound from the cost of the minimum-cost test sequence. The bound for the test sequence generated from the Q.931 Network-side protocol is shown to be the cost sum of an input/output operation and an external synchronization operation.Keywords
This publication has 8 references indexed in Scilit:
- The synchronization problem in protocol testing and its complexityInformation Processing Letters, 1991
- An optimization technique for protocol conformance test generation based on UIO sequences and rural Chinese postman toursIEEE Transactions on Communications, 1991
- An optimization technique for protocol conformance testing using multiple UIO sequencesInformation Processing Letters, 1990
- Formal methods for generating protocol conformance test sequencesProceedings of the IEEE, 1990
- Formal methods for protocol testing: a detailed studyIEEE Transactions on Software Engineering, 1989
- A protocol test generation procedureComputer Networks and ISDN Systems, 1988
- OSI conformance testingComputer Networks and ISDN Systems, 1987
- Synchronization and Specification Issues in Protocol TestingIEEE Transactions on Communications, 1984