近年来，计算机软件越来越多地融入到人们生活的各个方面。软件的规模也越来越大，功能越来越复杂。由此带来的软件质量问题层出不穷。软件测试是一种有效提高软件质量的方法，它通过选取并运行部分程序输入，来检查程序是否存在问题。其中，组合测试作为一种黑盒测试方法，尤其适用于对参数化的系统进行测试。组合测试因其代价低、检错率高的特点，在许多实际测试场景中得到了成功应用。

组合测试领域中大量的研究集中在理想数学模型的范畴下讨论，而在实际的测试场景中，有许多理想数学模型之外的特殊测试需求需要考虑。因此如何提高组合测试的易用性，是将该方法推向实际应用的重要问题。一方面，我们在组合测试生成的过程中，应当考虑到这些特殊的测试需求；另一方面，我们应当为测试人员提供方便的途径来表达这些特殊的测试需求。

在测试阶段发现缺陷后的一个重要步骤是调试并修复错误，而其中大部分的时间都花在定位错误上。组合测试的错误定位问题是在发现失败测试用例后，定位哪些参数组合引发了错误。这些参数组合可以用于帮助开发人员找到失败发生的根本原因。

本文围绕组合测试开展了以下研究工作：

(1) 在组合测试生成上，本文提出了一种基于伪布尔优化的组合测试生成算法，将生成测试用例的组合优化问题转换为伪布尔优化问题进行求解。该方法能够有效地处理参数间约束；(2) 本文还介绍了组合测试生成工具Cascade 的设计，该工具能够支持许多实际应用场景中的测试需求；(3) 我们使用组合测试方法对音频播放器，展示了组合测试的实施流程，并发现了真实系统中的若干问题；(4) 在组合测试错误定位问题上，本文提出了一种基于适应性测试的有效算法，通过生成和运行一些附加测试用例，来定位引起一条失败测试用例失败的参数组合；(5) 此外，本文还提出了一种将组合测试生成应用于白盒边界值分析的方法。该方法有效地提高了白盒测试生成的边界覆盖，并采用组合测试生成方法有效地减少了测试用例数量。

In recent years, computer software has entered people’s life in many aspects. It is becoming larger in scale, and more complex in functionality. This brings a lot of issues related to software quality. Software testing is an effective way to increase software quality, which selects and executes some of the program inputs to detect whether it has problems. Combinatorial testing is a black-box testing technique, which is suitable for testing parameterized systems. Due to its low cost and high efficiency, it has been successfully applied to many real-life testing scenarios.

Most researches on combinatorial testing are based on an ideal mathematical model. However, in many real-life testing scenarios, there are special testing requirements beyond the ideal mathematical model. Therefore it is an important topic to improve the usability of combinatorial testing. On one hand, we need to consider these special testing requirements during test generation. On the other hand, we need to provide support for testers so they can easily specify these special testing requirements.

After we have discovered defects in the testing stage, an important step is to debug and fix the defects, and most of the time is usually spent on fault localization. Combinatorial-testing-based fault localization is to locate the parameter combinations triggering the failures after they are detected. These parameter combinations can be used to help developers to find the root cause for the failure.

This dissertation discusses the following topics:

(1) On the problem of combinatorial test generation, we propose a new algorithm based on pseudo-Boolean optimization. We translate the combinatorial optimization for generating test cases into pseudo-Boolean problems, and use constraint solvers to compute the results. Our method can effectively handle parameter constraints; (2) We introduce the design of a combinatorial test generation tool called Cascade. The tool can support many testing requirements in real-life scenarios; (3) We apply combinatorial testing on audio players to demonstrate how to apply combinatorial testing, and have found several defects in some real systems; (4) On the problem of combinatorial-testing-based fault localization, we introduce an effective algorithm based on adaptive testing, which generates and executes several additional test cases to locate the parameter combination that cause a test case to fail. (5) Besides, this dissertation proposes a method to apply combinatorial testing to boundary value analysis in white-box test generation. The method effectively increases the boundary coverage in white-box test generation, and reduces the number of test cases by applying combinatorial test generation.