基于支配关系的数据流测试用例生成方法  

Test Case Generation Approach for Data Flow Based on Dominance Relations

作　　者：吉顺慧 张鹏程[1] JI Shun-hui;ZHANG Peng-cheng(College of Computer and Information,Hohai University,Nanjing 211100,China)

机构地区：[1]河海大学计算机与信息学院,南京211100

出　　处：《计算机科学》2020年第9期40-46,共7页Computer Science

基　　金：国家自然科学基金(61702159);江苏省自然科学基金(BK20170893)。

摘　　要：程序控制流的设计是为实现正确的数据流服务的,数据流测试是非常重要的。文中将面向all-uses数据流准则的测试用例生成问题建模为多目标优化问题,提出了一种基于遗传算法的测试用例生成方法。通过构建待测程序的控制流图进行数据流分析,计算出程序中所有的定义-使用对,得到测试目标,利用面向多测试目标的遗传算法生成满足all-uses准则的最优解。遗传算法中定义了一种改进的基于支配关系的适应度函数,在分析测试用例对定义-使用对的覆盖程度时考虑了存在重定义的可能性,且考虑了定义结点和使用结点在执行路径中的先后顺序。实验结果表明,所提方法可以有效地生成满足all-uses准则的测试用例,相比其他方法可以有效地提升测试目标的覆盖率,降低生成测试用例所需的迭代次数。The design of control flow in programs serves for realizing correct data flow.Performing the data flow testing is important.With formulating the problem of all-uses data flow criterion oriented test case generation as a many-objectives optimization problem,a genetic algorithm based test case generation approach is proposed.By constructing the control flow graph for to-be-tested program,data flow analysis is performed to compute all the definition-use pairs which are the testing requirements.Then many-objectives oriented genetic algorithm is performed to search the optimal solution for satisfying all-uses criterion.An improved fitness function is defined based on the dominance relations.The existence of killing definition,as well as the sequence of definition node and use node in the execution path,are taken into consideration to analyze the coverage of test case with respect to the definition-use pair.Experimental results show that the proposed approach can effectively generate test cases for satisfying all-uses criterion.And compared with other approaches,it can improve the coverage percentage and reduce the number of generations.

关 键 词：数据流测试 测试用例生成 遗传算法 适应度函数 支配结点 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]