Test Suite Reduction via Submodular Function Maximization

Abstract

As regression testing size and cost increase,test suite reduction becomes more important to promote its efficiency.Du-ring the selection of test suite subset,we are supposed to consider the representativeness and diversity of subset,and apply an effective algorithm to solve it.Aimed at test suite reduction,a submodular function maximization based algorithm,SubTSR,is proposed in this paper.Although the introduced discrete optimization problem is an NP-hard problem,the heuristic greedy search is used in this paper to find the suboptimal solution with approximation guarantee by exploiting the submodularity of the objective function.To validate the effectiveness of the SubTSR algorithm,the SubTSR algorithm is experimented on fifteen datasets with changes of topic count in LDA and distance for similarity measurement,and compared with other test suite reduction algorithms about the average percentage of fault-detection,fault detection loss rate,first faulty test's index and other metrics.The experiment results show that the SubTSR algorithm has significant improvement in fault detection performance compared with other algorithms,and its performance remains relatively stable on different datasets.Under the text representation change due to topic count change,the SubTSR combined with Manhattan distance keeps relatively stable compared with other algorithms.

Keywords

• software testing|test suite reduction|fault detection|topic model|submodular function