Open Collections

Coverage analysis for conformance testing of communication protocols

University of British Columbia

Generation of effective test suite and the evaluation of any given test suite are two of the most essential issues in conformance testing. We combine these two aspects and propose quantitative coverage measures that are subsequently used as the basis for generating test suites with any test coverage requirement. Two criteria for coverage measure are studied: a) fault coverage which measures the effectiveness by examining the fault detecting ability of a test suite under a certain fault model, and b) behavior coverage which measures the effectiveness by computing the amount of protocol behavior space that are exercised by a test suite. In the realm of fault coverage, we propose a coverage measure that targets on finite state specifications, typically in the form of I /O Finite State Machines (FSMs). A formal definition and algorithms that compute the measure are given. The computation of the measure is hard in general (no better than NP-complete); however, with search optimization techniques, the performance of our algorithm has been shown to be high and practical for some large protocols. The measure is then utilized to generate additional test cases to a "weak" test suite, thereby producing test suites with better coverage. The enhancement of a test suite can be done incrementally to satisfy a particular coverage requirement. The application of the measure in fault localization is also explored. The above coverage measure is further extended to the case of testing embedded modules of a composite system modeled as a set of communicating FSMs. The problem differs from the isolated module case in that the module under test has limited observability and controllability due to the presence of the test context. We propose an approach that reduces the problem to the case of isolated modules while maintaining observational equivalence at the composite system level. We prove that the calculation of the coverage measure is no better than NP-complete. However, application of the measure to a real life protocol, the protocol that supports the Universal Personal Computing on the Internet, shows that at a higher level of abstraction, the approach remains effective. As a last contribution of the thesis, we studied the coverage measure for behavior coverage based on Labeled Transition System (LTS). We use the basic metric based method [100] as our theoretical foundation. We generalize the basic method to handle protocols extended with data storage in the model of extended LTS. This results in a metric characterization that incorporates the testing distance contribution from data variations. We proved that this generalized metric space possesses the total boundedness and completeness properties, which allows for a test generation and selection process that can approximate the entire protocol space with arbitrary precision.

Thesis/Dissertation

application/pdf

2009-07-02

For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.

http://hdl.handle.net/2429/9921

Computer Science

University of British Columbia

UBCV

DSpace