基于Spark的并行化组合测试用例集生成方法  

Generating Combinatorial Test Suite with Spark Based Parallel Approach

作　　者：戚荣志[1] 王志坚[1] 黄宜华[2] 李水艳[3] QI Rong-Zhi;WANG Zhi-Jian;HUANG Yi-Hua;LI Shui-Yan(College of Computer and Information,Hohai University,Nanjing 211106;National Key Laboratory for Novel Software Technology,Nanjing University,Nanjing 210046;College of Science,Hohai University,Nanjing 211106)

机构地区：[1]河海大学计算机与信息学院,南京211106 [2]南京大学计算机软件新技术国家重点实验室,南京210046 [3]河海大学理学院,南京211106

出　　处：《计算机学报》2018年第6期1284-1299,共16页Chinese Journal of Computers

基　　金：国家重点研发计划(2016YFC0400910);国家科技支撑计划(2013BAB06B04);中央高校基本科研业务费项目(2015B22214;2013B07514)资助~~

摘　　要：软件系统的正常运行受很多因素影响,各种因素及其相互作用可能引发软件故障,需要设计测试用例检测这些故障.如果因素数量较多且取值情况较复杂,则所需测试用例的数量将非常庞大.如何设计规模较小的用例集是测试用例生成研究的一个关键问题.组合测试能够从待测软件的大规模组合空间中,生成小规模的用例集,实现对各因素取值组合的充分覆盖.已有研究表明,组合测试的最小测试用例集生成问题是一个NP完全问题.目前已有一些研究尝试使用启发式搜索算法生成尽可能小的用例集.启发式搜索算法将组合测试用例集生成问题转化为搜索问题,并使用元启发式算法生成用例集.启发式搜索算法通常能够生成较小规模的用例集,但需要较长的计算时间.为了解决这个问题,文中提出了一种基于Spark的岛模型并行化遗传算法,利用Hadoop分布式文件系统实现了Spark运行节点间交换信息的方法,进而实现个体在子种群间的迁移.该算法首先从初始种群创建Spark的弹性分布式数据集;然后,将该数据集划分为多个子种群分布到集群的多个节点中;接着,各个子种群在各自的节点上计算适应度函数值和独立进化,并每隔一定的进化代数选择一些个体在各个子种群间迁移,提高了种群的多样性以及搜索最优解的有效性和性能;最后,算法返回满足覆盖准则的最优测试用例集.这种基于Spark的并行化遗传算法是大规模并行化在组合测试用例集生成方面的一个有效尝试.在实验部分,首先对文中提出的并行化算法进行系统的参数调整,给出适合组合测试用例集生成的推荐参数配置;接着将文中所提算法与串行遗传算法和独立运行遗传算法进行比较.实验结果表明,文中所提算法在生成用例集规模和消耗时间上均显著优于这两个算法.在运行所选实例时,该算法比串行算法加速约4至30倍,�The normal operation of computer system is influenced by many factors.Failures may be triggered by various factors and interactions of these factors in software.In order to detect these interaction failures,the researchers try to design suitable test cases.If the quantity of factors is larger and the values of these factors are more complex,the number of test cases may become very huge.How to design a small number of test cases,which can achieve full coverage of combinations of factor values of the software,is a key issue of the research of test case generation.Combinatorial testing can generate small test suite from large scale combinatorial space of the software under test.The generated test suite can cover combinations of factor values of the software fully.It has been proven that generating minimum test suite is an NP-complete problem,so,heuristic search algorithms have been used for generating smaller test suite by many researchers in recent years.Heuristic search algorithms formulate combinatorial test generation problem as a search problem,and apply metaheuristic algorithms to generate combinatorial test suite.Heuristic search algorithms can often produce smaller test suite than other approaches,but require a longer computation.To solve this problem,in this paper,we propose a Spark based parallel genetic algorithm based on the island model.This algorithm uses Hadoop distributed file system to implement the method of exchanging information among the running nodes of Spark,and implement the migration of individuals among various subpopulations.The Spark resilient distributed dataset is first generated from initial population.Then the resilient distributed dataset is split into several subpopulations.These subpopulations are then distributed into the nodes of the Spark cluster.Each subpopulation calculates the fitness function on its own node,and evolves separately.During the process of evolution,some individuals will be selected according to the migration strategy every other generation.Then these selected i

关 键 词：组合测试 测试用例集生成 并行化遗传算法 岛模型 SPARK 

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