软件产品线（Software Product Line,SPL）旨在通过重用通用功能来开发相关的软件产品,SPL中的产品通过其功能特征来区分,其功能特征定义了软件系统的功能和行为。SPL通常通过特征模型来表示,特征模型根据特征及其之间的关系来捕获SPL所有可能产品的信息。软件产品线中,可以将SPL测试用例定义为要测试的产品线的产品,SPL中的大量功能组合可能导致成千上万甚至数百万种不同的产品,这样就不可能对SPL产品进行详尽的测试。为了减少测试工作,已经提出了使用组合交互测试（Combinatorial Interaction Testing,CIT）进行测试工作。但是由于计算特征组合会引起组合爆炸,所以应用CIT的成本很高,一般只可能运行集合中的部分测试用例。在这种情况下,在组合测试中控制测试用例集的执行顺序可能变得至关重要,因为经过排序的测试用例集合可以更快地识别故障,因此可以更早的实现故障诊断和纠正。据统计,大约90%的错误可以由三个及以下个数的参数组合交互发现,由此Bryce等人提出了基于固定组合覆盖力度的抽象测试用例集优先排序算法（Fixed-strength Interaction Coverage Based Prioritization,FICBP）,通过使用贪心搜索方法对组合实现快速覆盖,对于固定的组合覆盖力度,每次总是选择当前覆盖了最多未被覆盖的组合的测试用例添加到已排序测试用例集中去,随着力度的增加,错误检测率也随之提升。本文针对该方法主要思想,分析研究了该算法的不足之处加以改进,对实现如何完成交互组合的覆盖进行了深入的研究并将其应用在软件产品线上以进行验证。1、针对经典的FCIBP算法在贪心搜索排序过程中,忽视了组合覆盖频率变化带来的影响,导致了每轮中存在较大概率会进行随机选择操作;并且当所有组合均被覆盖后,剩余测试用例均进行随机排序,本文提出了一种基于覆盖频率的组合测试用例优先排序算法（Prioritizing Interaction Test Suites Based on Lexicographical Frequency,FICBPL）。该算法使用贪心搜索策略,以每个组合的覆盖频率为指导进行测试用例排序,采用字典排序算法在每轮优先挑选覆盖了最多覆盖频率最小的组合的测试用例,同时采用频率区间划分策略,减少其排序时间;并根据搜索深度进一步提出了相应的扩展算法以解决多个用例同时满足的情况。本文提出的基于覆盖频率的排序方法,其错误检测率明显高于现有的固定力度排序算法,同时取得了较低的时间开销。其扩展模型在稳定时间开销的同时,进一步提高了错误检测率。2、针对贪心搜索面对高维组合爆炸时间开销急剧增大,并且无法寻求到组合覆盖最优解的问题,提出了基于遗传算法的组合测试用例优先排序算法（Prioritizing Interaction Test Suites Based on Genetic Algorithms,FICBPG）。该算法使用元启发式搜索策略,将候选解编码为测试用例执行序列,将对组合的覆盖速率作为适应度函数,通过对染色体进行选择、交叉、变异,进行迭代演化得到最终测试用例排序结果,从而在个体遗传时找到排序序列最优解。该算法与现有的固定维度排序算法相比,具有较优的在错误检测率。同时在真实场景中,随着程序规模的不断增大,其时间开销具有较好的延展性。3、针对当前手工测试固有的弊端,为了避免重复劳动与人工造成的误差,本文设计并实现了组合测试优先级排序原型系统,实现将测试用例生成、优先级排序与评估同时集成于系统中,在验证算法有效性的基础上还实现了高效自动化测试。