基于次模函数最大化的测试用例集约简  

Test Suite Reduction via Submodular Function Maximization

作　　者：文进 张星宇 沙朝锋[1] 刘艳君 WEN Jin;ZHANG Xing-yu;SHA Chao-feng;LIU Yan-jun(School of Computer Science,Fudan University,Shanghai 200433,China)

机构地区：[1]复旦大学计算机科学技术学院,上海200433

出　　处：《计算机科学》2021年第12期75-84,共10页Computer Science

基　　金：国家重点研发计划(2018YFB0904503)。

摘　　要：随着软件回归测试规模的不断增大和成本的不断增加,测试用例集约简对于提高软件的回归测试效率显得愈发重要。在选取测试用例子集时,需考虑该子集的代表性和多样性,并采用一个有效的算法来求解。针对该测试用例集约简问题,文中提出了一种基于次模函数最大化的算法SubTSR。尽管引入的离散优化问题是NP-hard问题,但文中利用其目标函数的次模性,采用启发式贪心搜索,求得有近似度保证的次优解。在15个数据集上对SubTSR算法与其他测试用例集约简算法展开实验,针对平均错误检出率、错误检测损失率、首次错误检出位等指标,尝试改变LDA处理中的主题个数以及衡量测试用例相似度的距离,以验证SubTSR算法的有效性。实验结果表明,SubTSR算法在错误检出性能上较其他算法有着较大提升,且在多个数据集上的表现保持相对稳定。在主题个数变化引起文本表示变化时,采用曼哈顿距离的SubTSR算法的性能相较其他算法仍能保持相对稳定。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.

关 键 词：软件测试 测试用例集约简 错误检测 主题模型 次模函数 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]