【作者】 陈翔；

【导师】 陈道蓄； 顾庆；

【作者基本信息】 南京大学 ， 计算机软件与理论， 2011， 博士

【摘要】 软件测试是保障被测软件质量的重要手段。但软件测试研究面临诸多挑战,例如被测软件制品的分析建模技术、测试充分性准则的设定、有效的测试用例生成技术、回归测试技术和变异测试等。组合测试作为一种重要的测试用例生成技术已经得到国内外学者的广泛关注。当完成对被测软件制品建模分析后,测试人员可以获得由因素和因素取值构成的实例,组合测试通过关注少数因素间取值组合的覆盖可以构造出小规模组合测试用例集,但最优组合测试用例集的构造已被证明为是一个NP难问题。本文系统回顾和总结了组合测试技术和应用的已有研究成果,针对组合测试中典型的成对组合测试和一些组合测试扩展问题进行了深入研究,提出了多种基于元启发式搜索技术的有效测试用例集构造算法。同时针对回归测试中的测试用例集约简问题,提出了一种基于测试需求间成对组合覆盖的约简算法。具体贡献可以概括为以下三个方面。(1)针对传统成对组合测试问题,本文提出一种基于粒子群优化的成对组合测试用例集构造算法。在生成单个测试用例时,尝试利用粒子群优化生成组合覆盖能力强的测试用例,并对搜索空间、适应值函数和启发式的合理设定进行了深入探讨。同时以上述单个测试用例生成算法为基础,提出两种不同的测试用例集构造算法,一种基于one-test-at-a-time策略,另一种基于类IPO策略。随后采用一个压缩算法对组合测试用例集做进一步的压缩。最后通过实证研究分析了算法框架内的不同设定对最终构造出的测试用例集规模的影响,并与已有的经典算法和工具进行比较来验证该算法的有效性。(2)针对组合测试扩展问题,本文将蚁群优化技术在传统成对组合测试问题上的应用进行扩展,使之可以有效构造基于优先级的组合测试用例集和可变强度组合测试用例集。具体来说,针对基于优先级的组合测试问题,本文采用one-test-at-a-time策略构造测试用例集,在构造单个测试用例时,提出四种不同的蚁群优化策略(AS、ASelite、ACS和MMAS)并针对该问题对其中的启发式设定进行了深入探讨,最后通过实例研究将这四种策略与经典的贪心策略WDA (Weighted Density Algorithm)进行了比较,同时也对这四种不同策略的具体执行效果进行了比较并验证了所提方法的有效性。针对可变强度组合测试问题,本文同样采用one-test-at-a-time策略来构造测试用例集,在构造单个测试用例时,采用ACS策略并针对该问题对其中的启发式设定进行了深入的探讨,随后采用一个压缩算法对组合测试用例集做进一步的压缩。最后通过实例研究与已有的经典方法和工具进行比较来验证该方法的有效性。(3)针对测试用例集约简问题,传统测试用例集约简算法仅考虑对单个测试需求的覆盖,这类方法一般会大幅度削弱约简后的测试用例集缺陷检测能力。本文通过考虑对测试需求间成对组合的覆盖,提出了一种轻量级的测试用例集约简方法PWIR。在实证研究中,采用Siemens套件中的实际C语言程序作为实验对象。最终结果显示该方法可以仅通过添加少量测试用例就可以有效提高约简后的测试用例集缺陷检测能力。更多还原

【Abstract】 Software testing is a key method to guarantee the quality of software under test. But software testing faces many challenges, such as the modeling techniques of software artifacts, the design of test adequacy criterion, the effective test case gen-eration techniques, regression testing, and mutation testing. Combinatorial testing (also known as interaction testing) is an important test case generation technique and is widely researched by many researchers. After modeling the software under test, testers can get an instance composed of factors and values. Combinatorial test-ing can generate test suites with small size by covering interactions of a few factors. Some empirical studies also show that it can effectively reduce the test suite size but still keep high fault detection ability in some testing scenarios. However, the construction of the optimal combinatorial test suite is demonstrated to be NP-hard.In this dissertation, we systematically review the related work of combinato-rial testing technique and its applications. For traditional pairwise testing and its variants, we propose several effective test suite construction algorithms based on meta-heuristic search techniques. For test suite reduction in regression testing, we propose a test suite reduction approach based on pairwise interaction of test require-ments. The contributions of this dissertation can be summarized as follows:(1) For traditional pairwise testing issue, we propose a framework of particle swarm optimization based pairwise testing. To generate a single test case, we apply particle swarm optimization aiming to cover more interactions. Meanwhile we dis-cuss the reasonable settings of search space, fitness function, and heuristics. Based on the above algorithm, we propose two different test suite construction algorithms. One is based on one-test-at-a-time strategy, the other is based on IPO-like strategy. In our empirical study, we analyze the impact factors in our framework and make a comparison with other well-known approaches to show the effectiveness of our framework.(2) For the variant issues of combinatorial testing, we extend the application of ant colony optimization in traditional combinatorial testing to support the con-struction of prioritized combinatorial test suites and variable strength combinatorial test suites. In particular, to build prioritized combinatorial test suites, we use one-test-at-a-time strategy. To generate a single test case, we propose four concrete ant colony optimization strategies (AS, ASelite, ACS, and MM AS) and discuss the set-tings of heuristics. In the part of case studies, we compare our approach to a classical greedy approach WDA (Weighted Density Algorithm) and also make a comparison among these four different approaches. To build variable strength combinatorial test suites, we also use one-test-at-a-time strategy. To generate a single test case, we apply ant colony system (ACS) strategy aiming to cover more interactions and discuss the settings of heuristics. After the test suite is constructed, we can use a test suite minimization algorithm to further reduce this test suite size. In the final case studies, we compare this approach to some classical approaches and tools to show the effectiveness of our approach.(3) For the test suite reduction issue in regression testing, most of traditional test suite reduction approaches only consider the coverage of individual test require-ment, but these approaches may significantly lose fault detection ability of original test suites. We propose a lightweight test suite reduction approach PWIR. In this approach, we consider the coverage of pairwise interaction of test requirements. In our empirical study, we use the Siemens suite as our subjects and find that this approach can effectively increase the fault detection ability of reduced test suite by adding only a few test cases.更多还原