组合测试是一种黑盒抽样技术,它采用组合的思想精简测试用例集规模,并且能够解决组合爆炸问题。经验数据表明,二维覆盖组合测试能覆盖软件中50%-97%的缺陷,具有非常高的实用价值。此外,在实际软件中,参数取值之间的约束也是普遍存在,并且对解决组合测试用例生成问题具有非常大的现实意义。在此背景下,本文主要针对二值型约束条件,提出了一个基于二值型约束和解空间树的pairwise测试用例生成算法(PSST_C)。在此基础之上,本文提出了一个并行测试算法,意在缩短测试过程所花费的时间。首先,本文针对约束条件中的二值型约束和二值型约束对测试用例集规模的影响等问题进行详细的研究;其次,将待测软件模型映射到一颗完整的解空间树上,并通过待测软件中存在的二值型约束对解空间树进行剪枝操作;然后通过回溯法对剪枝后的解空间树进行充分遍历,生成符合两两覆盖标准的最小规模的测试用例集;再次,采用贪心算法做为补充,进一步覆盖软件中所有有效的二维组合;最后,在PSST_C用例生成算法基础之上,本文采用并行的思想,通过将测试用例生成过程与测试用例执行检错过程并行化的方法实现了并行测试算法。本文通过对两个经典Benchmark模型和多个不同规模的待测软件仿真模型对本文提出的PSST_C算法和并行测试算法进行仿真,仿真结果表明:1)对于本文提出的用例生成算法PSST_C,约束条件能够明显的精简测试用例集规模;2)在相同约束条件下,本算法能够产生更小规模的、更有效的测试用例集;3)在相同条件下,本文提出的并行测试算法能够有效的缩短测试过程的时间。