参数配对及n-way组合覆盖算法研究

Research on Algorithm of Parameter Pairwise and n-way Combinatorial Coverage

组合测试是软件测试数据生成研究的一个重要领域,其中参数配对组合测试的应用最为广泛.对常用的参数配对组合覆盖方法进行了综述分析.目前主流的配对覆盖算法AETG和IPO所存在的主要问题是在确定水平取值时,具有盲目性和随机性,从而难以控制测试用例的规模.为此提出了改进的AETG算法和IPO算法,改进算法通过对参数进行预处理以及综合考虑各因素的水平组合等手段,对测试用例的规模进行控制,采用更加完备的方法尽早确定水平取值.为验证新算法的有效性,进行了仿真实验和实际测试,结果表明,改进算法所生成的测试用例数量要少于原算法,测试用例约减效果更为明显;测试用例数与配对数之间、测试用例数与因素水平数之间存在着某些规律性的联系,分析得出了一系列相关的结论.在配对覆盖的基础上,提出了遗传算法与AETG算法相结合的n-way组合覆盖算法,证明了其时间复杂性较已有算法得到了改善.

Combinatorial testing is an important part of software test data generation research domain. The parameter pairwise testing is the most widely-used technique. Various parameter pairwise coverage methods for test data generation are surveyed in the paper. The main problem of the existing and dominating pairwise coverage algorithm AETG and IPO is their blindness and randomieity when deciding level value, therefore the size of test cases is difficult to control. Based upon this, improved AETG and IPO algorithms are proposed. In the proposed methods, the size of test cases is effectively controlled by the pretreatment of parameters and the consideration of the level combination of all factors. The level value is decided as early as possible by more tonsure- mate way. To validate the effectiveness of new testing are carried out. The experiment results algorithms, emulation experiments and practical show that the number of test cases generated by improved algorithms is smaller than the one by original algorithms, and the reduction effect is more evident disciplinarian relation exists between test case amount and pairwise amount, also between test case amount and factor level amount. A series of conclusions are drawn by analyzing the results. On the basis of pairwise coverage, n-way combinatorial coverage algorithm which combined with genetic and AETG algorithm is proposed. The fact that time complexity of new algorithm is lower than existing method is also proved.