基于IPO算法的三三组合测试数据生成

作     者：艾华 

作者单位：航天科工集团第二研究院 

学位级别：硕士

导师姓名：宋晓秋

授予年度：2018年

学科分类：08[工学] 0835[工学-软件工程] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：软件缺陷 三三组合测试 数据生成 参数排序 

摘      要：最小测试用例集生成问题是NPC问题。可用不断寻找局部最优解得到的近似解来代替全局最优解，为得到一个较优的近似解，国内外进行了大量的研究。最初针对两两组合测试用例集的生成问题，提出了多种解决思路，有基于代数构造法的正交拉丁技术以及Williams算法，有基于贪心策略的IPO算法和AETG算法，也有基于解空间树结构的PSST算法……这些算法基本是针对成对测试的。接着研究人员又在部分算法的基础上进行了通用化改进，使得它们能解决n(2≤n≤6)组合的问题，甚至提出了能解决n取值为11组合问题的MIPOG算法。 原则上讲，软件应当进行充分的测试，即应当对全部参数的所有组合都进行测试，但测试用例集规模直接和覆盖强度n相关。在某研究实验中，发现约86％的软件缺陷可以通过两两组合测试来发现，而三三组合测试则能发现91％的软件缺陷，并且几乎100％的缺陷能通过六六组合测试来发现。目前对两两组合测试用例数据生成已有很多研究，也不乏通用的测试数据生成算法，但就三三组合测试问题提出的组合测试算法较少。 本文综合考虑各方面因素，在IPO算法的基础上，针对三三组合测试用例数据生成问题，以IPO算法的参数排序方式，每次扩展参数的数量，扩展时对参数取值的贪心策略为着眼点，研究和改进IPO算法，提出了IPOE3算法和IPOLS算法。 本文主要就以下三个方面进行研究与优化从而得出较优的算法，首先，IPO算法在参数排序上按照参数取值数量非递增的方式。这样能减少垂直扩展时增添新测试用例从而生成较少的测试用例，还能减少判断次数从而降低运算时间。其次，IPO算法每次扩展一个参数。根据覆盖强度每次扩展参数的数量应当进行调整，本文将通过实验研究在覆盖强度为3时扩展参数的数量和测试用例集的关系。最后，IPO算法在垂直扩展时没有利用贪心策略和删除已覆盖组合对，当覆盖组合对的测试用例存在多个时也没有提供选择的标准，本文增添了贪心策略选择出更合适的测试用例并删除已覆盖组合对。