Test generation for interaction detection in feature-rich communication systems

This paper proposes two techniques to generate test sequences to check the conformance of an implementation of a feature-rich communication system to its specification, as well as to detect the interactions between the features of the system. Concepts color span and feasible combination of features are introduced to measure the extent and possibility of the interactions between different features. Several algorithms are proposed to produce an approximate minimum-cost and minimum color span tour of the transition graph of a finite-state machine. Test generation using the proposed algorithms for the SIP-based Internet telephony end system and for the Link Management Protocol is reported.