Feature interaction detection determines whether interactions occur or not between the new and existing telecommunication services. Most of conventional detection methods on state transition model utilize an exhaustive search. The exhaustive search is fundamentally very powerful in the sense that all interactions are exactly detected. However, it may suffer from the state explosion problem due to the exponential growth of the number of states in the model when the number of users and the number of features increase. In order to cope with this problem, we propose a new detection method using a state reduction technique. By means of a symmetric relation, called permutation symmetry, we succeed in reducing the size of the model while preserving the necessary information for the interaction detection. Experimental evaluation shows that, for practical interaction detection with three users, the proposed method achieves about 80% reduction in space and time, and is more scalable than the conventional ones especially for the increase of the number of users in the service.

Despite the fact that the necessity of FDT (formal description techniques) had been emphasized, many approaches to verifying feature interactions were insufficient. This paper proposes formal definitions for feature interactions which can occur when telecommunication services specified independently are operated in parallel. Seven types of feature interactions are defined formally.