基于维持种群多样性的测试数据生成算法的研究

Automated Test Data Generation Using Evolutionary Algorithm Based on Maintaining Population Diversity

测试数据自动化生成技术尝试寻找一个相对小的数据集来满足测试充分性标准,以降低软件测试的成本,提高测试效率.当测试项的数据集大小超过其上限时,算法会使用淘汰算法把差异性较小的测试数据从集合中淘汰掉,把差异性较大的测试数据留下来,以维持种群的多样性.针对此问题,提出一种基于维持种群多样性的演化算法来求解测试数据集,算法利用启发信息迭代地选择一个条件?判定语句作为子目标,通过演化算法生成数据以覆盖目标.在此算法框架内,利用一种新的计算评估值的方法计算数据与测试项的距离信息;以及利用归一的曼哈顿距离计算测试数据差异性,通过淘汰策略把差异性较小的测试数据淘汰掉.在实验中,对14个计算机科学基础算法的基准函数进行了测试,并与现有文献中的测试数据生成方法进行对比,验证了算法有效提高了条件?判定覆盖率,并且减少了测试数据的生成数量,提高了测试性能.

The automatic test data generation technology tries to find a relatively small set of test data to satisfy adequacy criterion, in order to reduce testing cost and increase testing efficiency. In this paper, an innovative test data generation algorithm based on maintaining population diversity is proposed, which satisfies condition/decision coverage criterion. This algorithm is based on an extended branch coverage table. Normalized Manhattan distance is employed to calculate the diversity between test data and eliminate the data with lower diversity, to maintain population diversity. Meanwhile, a new approach is introduced to evaluate the fitness values of test data. Then a greedy algorithm is used to reduce the number of test cases. Finally, this paper presents some experiments over a large benchmark composed of fourteen programs that include fundamental and practical aspects of computer science.