Sampling configurations from software product lines via probability-aware diversification and SAT solving

摘要

Sampling a small, valid and representative set of configurations from software product lines (SPLs) is important, yet challenging due to a huge number of possible configurations to be explored. Recently, the sampling strategy based on satisfiability (SAT) solving has enjoyed great popularity due to its high efficiency and good scalability. However, this sampling offers no guarantees on diversity, especially in terms of the number of selected features, an important property to characterize a configuration. In this paper, we propose a probability-aware diversification (PaD) strategy to cooperate with SAT solving in generating diverse configurations, with the effect that valid configurations are efficiently generated by SAT solving while also maintaining diversity brought by PaD. Experimental results on 51 public SPLs show that, when working cooperatively with PaD, the performance (regarding diversity) of off-the-shelf SAT solvers has substantial improvements, with large effect sizes observed on more than 71% of all the cases. Furthermore, we propose a general search-based framework where PaD and evolutionary algorithms can work together, and instantiate this framework in the context of search-based diverse sampling and search-based multi-objective SPL configuration (where there is a practical need of generating diverse configurations). It is demonstrated by the experimental results that PaD also brings abundant performance gains to these search-based approaches. Finally, we apply PaD to a practical problem, i.e., machine learning based performance predictions of SPLs, and show that using PaD tends to improve the accuracy of performance prediction models.