【作者】 张岩；

【导师】 巩敦卫；

【作者基本信息】 中国矿业大学 ， 控制理论与控制工程， 2012， 博士

【摘要】 软件测试是保障软件质量的重要手段，其目的是在测试过程中尽可能多地发现软件存在的缺陷，因而其在整个软件开发过程中占有特别重要的位置。测试数据的好坏直接决定着测试的效果，因此软件测试中关键的问题是设计有效的测试数据。已有研究表明，路径覆盖是一种非常重要的软件测试充分性准则；遗传算法是自动生成路径覆盖测试数据的有效方法，但是已有研究成果在测试数据的生成效率和检错率上都有待提高。本文研究使用遗传算法自动生成路径覆盖测试数据的理论及方法。首先，针对现有方法对穿越难以覆盖节点的稀有数据缺乏保护措施问题，提出了在测试数据进化生成中动态捕捉稀有数据的方法。通过统计每代种群中目标路径各节点被穿越的个体数量，得到个体对生成穿越目标路径测试数据的贡献，以此作为权重调整个体的适应度，使稀有数据的适应度增加，在后续进化中得到保留，从而提高测试数据的生成效率。其次，提出了一种新的多路径覆盖测试数据生成方法。将被测程序表示成一棵二叉树，对目标路径采用赫夫曼编码方法表示成二进制串，依此设计了一种新的适应度函数，综合考虑个体穿越路径与每个目标路径的匹配程度，将提出的方法用于多个基准程序的测试，并与已有方法比较，结果表明所提方法计算量小，生成测试数据效率高。第三，针对已有方法生成的测试数据不能有效发现被测程序的缺陷，尤其是小概率缺陷的问题，提出了一种面向缺陷的路径覆盖测试数据进化生成方法。分别针对单路径和多路径情况，将路径覆盖和缺陷检测问题转化为约束多目标优化问题，以测试数据运行被测程序时发现的缺陷个数和缺陷的危险程度为目标，以穿越目标路径为约束，建立了该问题的数学模型，并提出了有针对性的求解方法。在实际软件测试中的应用表明，所提方法生成的测试数据不但穿越了目标路径，而且能有效检测到目标路径中的缺陷。最后，提出基于搜索空间缩减的路径覆盖测试数据进化生成理论。针对单路径覆盖测试数据生成问题，先确定目标路径与输入变量之间的关系，将可分目标路径分离出与部分分量相关的独立子路径；进化生成测试数据的过程中，固定被穿越子路径对应的输入分量，并缩小交叉和变异操作的范围，使种群在不断缩小的空间里寻找测试数据；然后针对多路径覆盖测试数据生成问题，提出了基于搜索空间缩减的多种群遗传算法，该方法将目标路径按照具有相同子路径进行分组，并确定每组公共子路径对应的分量，使用多个子种群分别进化生成各组目标路径的测试数据，进化过程中固定子种群内被穿越子路径对应的输入分量，并缩小交叉和变异操作的范围，使每个子种群在不断缩减的空间里寻找测试数据，有效提高了每个子种群内目标路径测试数据的生成效率，进而提高多路径覆盖测试数据进化生成效率。本论文所做的工作为路径覆盖测试数据的自动生成提供了新的思路，丰富了基于进化优化的软件测试理论，提高了测试数据的生成效率，保证了测试数据的质量，降低了软件测试成本，具有重要的理论意义和实际应用价值。更多还原

【Abstract】 Software testing is an important means that guarantees software quality, aims todetect as many faults in the program under test as possible, and plays an importantrole in software development. The qualities of test data directly decide the test result,so the key question of software testing is to design effective test data. Existingresearches show that path testing is an important test adequacy criterion, and geneticalgorithm is an efficient method to automatically generate test data for path testing.Whereas, both the efficiency and rate of detecting faults of existing methods ongenerating test data need to be improved. This dissertation focuses on the theories andmethods of automatically generating test data for path testing using geneticalgorithms.First, considering that previous methods cannot effectively protect scarce datawhich traverse those nodes difficult to be covered, a method for capturing scarce datain evolutionary generation of test data for paths coverage is presented. In this method,the contribution of an individual to generate test data which traverse target paths isobtained by recording the number of individuals which traverse each node of thetarget path, and is regarded as a weight to adjust the fitness of an individual. In thisway, the fitness of a scarce datum can be increased, the scarce datum can beconserved in subsequent evolution, and the efficiency of generating test data is thusimproved.Then, a novel approach to generate test data for multiple paths coverage ispresented. In this method, the program under test is expressed as a binary tree; thetarget paths are encoded into a binary string using Huffman coding; an individual’sfitness is the degree of the traversed path matching the target paths, and a geneticalgorithm is employed to generate multiple test data, The proposed approach isapplied to several benchmark programs, and compared with previous approaches. Theresults indicate that the computation of the proposed approach is cheap and theefficiency in generating test data is high.Third, since the existing path-oriented testing methods may not find the faults inthe program under test, especially for those faults which emerge with a smallprobability, a method for evolutionarily generating test data is proposed for fulfillingpath coverage while detecting faults. To this end, a mathematical model of generatingtest data for path coverage with fault detection is established, which takes the number of faults in the traversed path and the risk level of the faults as the objectives, andtakes the approach level as the constraint; furthermore, a multi-objective evolutionarymethod to generate test data is proposed. The proposed method is applied to somepractical software testing, and the experimental results confirm that the test datagenerated by the method can not only traverse the target paths, but also detect faultslying in them.Finally, an improved approach is devised for the evolutionary processes ofgenerating test data using genetic algorithm, and the theory for evolutionarilygenerating test data for path coverage based on automatic reduction of the searchspace is presented. For the problem of generating test datum for only one target path,the relation between the target path and the input variable is determined, and thedivisible target path is divided into some sub-paths related to several elements of theinput variable. The elements corresponding to the traversed sub-path are fixed, andthe ranges of crossover and mutation operations are reduced in the process of theevolution, leading to the original population search for test data in a reduced space sothat the efficiency of generating test data is improved. For the problem of generatingtest date for multiple target paths, target paths are divided into several groups basedon the same sub-path which is only related to a part of input variables, and theelements of the input variable corresponding to the sub-path are determined. Thesub-populations whose number is the same with that of groups are used to generatethe test data of traversing the target paths in each group, respectively. During theevolution, the elements corresponding to the traversed sub-path are fixed, and therange of crossover and mutation operations are reduced, leading to the sub-populationsearch for test data in a reduced space so that the efficiency of generating test data isimproved.Results of this study provide new ways to generate test data for path coverage,enrich the theories of software testing based on evolutionary optimization, improvethe efficiency and the quality of test data generation, and then the cost of softwaretesting is reduced. Therefore, they have important theoretical significance andpractical values.更多还原