Correctly ordered postman tours and synchronizable test sequence generation for protocol conformance testing.

Abstract

In this thesis, we will consider the distributed architecture for communication protocol conformance testing, where there are two remote testers, called the lower tester and the upper tester. During the application of a predetermined test sequence in the distributed architecture, the upper and the lower testers are bound to synchronize with each other only through their interaction with the implementation. However, this requirement may lead to a synchronization problem when the upper and the lower tester processes are forced to consider the timing of an interaction in which they have not taken part. We present a heuristic for generating a minimum length synchronizable test sequence for protocol conformance testing. The approach is based on a variation of a well-known problem in graph theory known as the Chinese postman problem. In this variation, for each edge e = (i,j) in a digraph D, we specify a subset of edges leaving j as the eligible successors for e, and require that each edge in the postman tour be followed by an eligible successsor. We present a heuristic to solve this variation of the Chinese postman problem, and develop a specialized version of this heuristic for the problem of generating a minimum length synchronizable test sequence. We show empirically that our specialized heuristic has superior performance compared to other known heuristics for this problem.