Generalizing featured finite state machines constructed by model merging

A family-based behavioral model represents the behavior of a software product line (SPL) as a whole. A well-known type of these models is the Featured Finite State Machine (FFSM), which is an FSM whose states and transitions are annotated with feature expressions. FFSM Diff is a model merging algorithm that integrates the FSMs of SPL products and constructs an FFSM. In many cases, due to the large number of SPL products, it is practically impossible to analyze all products. Therefore, the FFSM is constructed using a subset of products, called a sample. The FFSM constructed by model merging of products in a sample only includes the behavior of the sample products. The goal is to construct an FFSM which represents the approximate behavior of the out-of-sample products as well. In this paper, a method is presented to generalize the FFSMs constructed using FFSM Diff. When generalizing a transition, the literals of features whose presence does not affect that transition are removed from feature expressions. We also incorporate the effect of feature interactions in the provided method. When generalizing the transitions, it is possible to introduce nondeterminism in the models derived from the generalized FFSM. To reduce this nondeterminism, we introduce a BFS-based similarity metric which is used during model merging. We also equip the basic generalization method with a lookahead mechanism to reduce the nondeterminism in the generalized model. We use the presented generalization methods on three different subject system, and evaluate the accuracy in terms of Precision, Recall, and F1. The results show that in all three subject systems, with sufficient sample size, the provided generalization methods can result in F1 values equal to or higher than 95 percent for out-of-sample products.