1  引言

随着信息化社会的飞速发展，图形处理芯片 GPU芯片的功能越来越丰富，性能要求越来越高，应用领域也越来越多源化。相应地，在 GPU 架构设计环节，功能级仿真 C-model 的规模和复杂度也不断增大。整个项目设计周期内，任何新版本的引入，无论是源于对已有错误的修正，还是为支持新功能而增加模块，都可能对原有 C-model 带来影响。如果无限制地任由研发团队的每个人随意检出检入，就会给项目带来风险，因此就需要对代码进行版本控制和有效管理。

与此同时，代码的频繁修改，理论上都需要更高频率的测试来验证，才能避免新错误的引入，确保芯片的正常功能。其过程十分重要，但是需要大量的人力、物力成本。因此，要确保项目高效正向推进，有必要在代码提交前对其进行有效的预检，为后续的回归测试和错误跟踪节省成本。

众所周知，测试用例决定了测试的成本及效果，针对版本控制系统端的测试用例，时效性显得尤为重要。因此，如何在时间有限的约束条件下，在代码预检端优选出能保障代码质量的测试用例集合，成为本文研究的重点。

2  CIMS 原理框架和集合覆盖问题

2.1 CIMS原理框架

作为我们自行研发的自动化测试框架的一部分，检入管理系统 CIMS（Check In Management System）相当于软件版本管理系统的前置过滤器。图 1 为其工作流程图。该系统利用 Perforce 提供的trigger 功能，将我们自定义的脚本嵌入。当研发人员修改代码并检入时，p4server 自动调用脚本对修改的代码进行编译和测试。只有通过所有编译和测试项的修改，才可过关进而被成功提交至 Perforce 存储库，并获得版本号。否则，修改将被退回，开发员可以通过 CIMS 系统提供的网页界面查询编译和测试状态，便于进一步自查和完善代码。虽然通过 CIMS这套机制，对代码质量设置了一定的门槛，但是也需要兼顾时间成本，为了让 CIMS 发挥更大的作用，测试集的优选算法值得重点研究。

目前，测试人员普遍采用回归测试来保证代码修改的正确性，并避免代码修改给被测程序其他模块带来的副作用。CIMS 系统中测试用例集的优选问题在以往的项目开发中，往往凭经验从已有的回归测试集合中，分模块挑选，以提高整个 pipeline 的功能覆盖，并无任何指标来评判其效用之优劣。本文从集合覆盖角度，对如何从已有回归测试集中筛选子集作为 CIMS 系统内的测试集展开研究。

2.2 集合覆盖问题

在集合论中，集合覆盖定义为：假设 A 是非空集合，如果 A 的若干非空子集的并集等于 A，则由这些子集构成的集合 C 称为 A 的覆盖。即非空集 A的一个覆盖 C 是 A 的非空子集的集合。

经典的集合覆盖问题 SCP（Set Covering Problem）描述如下：给定两个集合 R 和 S，元素的集合 R 和 R 的子集的集合 S，目标是找到 S 的一个子集 C，使得 C 中所有集合的并等于 R，且使 |C| 最小。这是 NP-hard 类的最优化组合问题。

早期回归测试工具大都基于黑盒测试。当时，还没有任何回归测试工具能在程序修改后自动在原始用例集中选择出一个用例子集进行回归测试，而是再测试全部已有用例进行回归测试。在这种情况下，Fischer 等人研究了如何在原始用例集中选择出一个最小的子集，用于回归测试，且不会降低测试效果和程序的可靠性，最早提出了测试用例最小化的思想[1]。对测试用例集最小化的定义如下：给定测试需求集 R{R1，R2，R3.....Rm}，测试用例集 T{T1，T2，T3....Tn}，该测试用例集 T 能够用来充分测试 R。问题：从 T 中找到一个最小子集 T'，该子集 T' 能够用来充分测试给定的测试需求集 R。

1993 年，Harrold 等人[2]首次提出了测试用例集约简的概念，也就是要在原始的测试用例中寻找一个子集，实现测试需求的充分覆盖。随后研究人员围绕测试用例集约减问题提出了贪心算法[3]、整数规划算法、遗传算法、HGS 等算法。这些方法各有优势和局限性，更多趋向于去除冗余的测试用例，没有考虑到要缩减用例的根本原因是资源有限，而且约减的目的并不单是测试用例的个数越少越好，也要考虑约减后测试用例集的错误检测能力是否保持在一定的水平上。为了充分利用资源，又兼顾资源的约束条件。

本文提出了一种改进的测试集优选算法，寻求能使代码覆盖率达到最大的用例集。

3  基于SCP原理的优化方案

3.1  集合覆盖贪心算法

最早提出用贪心算法来求解测试用例集合覆盖问题的是 V.Chvatal[4]。集合覆盖贪心算法是测试用例集约减问题的一个常用近似算法。贪心策略的思路是从问题的初始状态出发，通过若干次的贪心选择而得出最优解(或较优解)。其算法执行过程如下：逐次从 T 中选择一个测试用例，使之能尽可能多地满足 R 中的测试需求，然后从 R 中删除这些已被满足的测试需求，循环几次上述操作，直到所有测试需求都能被满足（即 R 为空集）。

该算法的时间复杂度是 O (m,n,min(m，n))。算法如下。

input A：包含 m 个元素的集合

C(A)：A 的 n 个子集的集合

output C：从 C(A) 中选择的元素的集合

declare U：A 中所有未覆盖元素的集合

X：从 C(A) 中选中的元素

Begin

/初始化/

U=A；

C=Φ；

While(U≠Φ )

/选择一个能满足未覆盖元素的最大数目的子集/

select{X}    C(A) such that |{X}∩ U| is maximum；

U=U\{X}；

C=C ∪ {X}；

End-while

End

贪心算法所做出的选择虽然只是在某种意义上的局部最优解，但许多问题自身的特性决定了该问题运用贪心策略可以得到最优解或较优解。CIMS 系统中测试集的集合覆盖问题可以用贪心算法求解。即通过一系列当前状态下某种意义的最好选择(贪心选择)来得到一个问题的解。最小化问题的贪心选择性质表现为：问题的整体最优解是通过一系列局部最优的选择，即贪心选择来达到的。

3.2 测试用例约减模型

针对 CIMS 系统中测试集的集合覆盖问题[4,5]，本文定义了资源约束条件下的测试用例约减模型为：假设给定一个回归测试用例集 R={r1，r2.....rn}，其中每个测试用例对应的运行时间为 T={t1,t2....tn}，每个测试用例对应的函数覆盖率为 C={c1,c2....cn}，假定约束时间为 Tsum，我们要找出一个测试用例集的子集 P={ p1，p2.....pm }，其中 m<n。该测试用例子集 P 满足时间约束的要求，并且被选中的测试用例所对应的函数覆盖率最大化，即：

（3）

3.3 算法实现

根据测试用例约减模型，假设已有回归测试用例集为 R={r1，r2.....rn}，其对应的函数覆盖率为 Ctotal，其中，每个测试用例 rn 对应了不同的函数覆盖率 cn 和不同的测试时间 tn，取函数覆盖率和测试时间的比值 cn/tn 作为该测试用例 rn 的优先级系数，需要选出最佳测试子集 P，使得该集合所对应的函数覆盖率尽可能接近 Ctotal、该集合中所有测试用例运行时间之和不大于约束值 Tsum。算法流程如图 2 所示，具体实现步骤如下。

（1）设定时间约束条件为 Tsum。

（2）将测试用例按其函数覆盖率 Cn 从大到小排序，将排位第一的测试用例选入 P。

（3）在余下的测试用例中，筛选与已选中的测试用例对应的被覆盖函数交集最小的测试用例，若其值相同，则选取优先级系数最大的测试用例。

（4）以此类推,依次选取，累加被选中的测试用例的运行时间，直到运行时间之和 ∑mi=1 ti 超过约束时间 Tsum 为止。

4  实验验证

本文研究的重点是基于函数覆盖率的测试用例筛选，所以覆盖率信息收集的是函数覆盖率相关信息，包括覆盖到的函数块数量，总共的函数块数量，以及两者之间的比值即函数覆盖率。另外，计算出每个测试用例覆盖到的函数块数量与其运行时间的比值，作为优先级系数。在算法中我们会优先考虑选择运行时间尽可能短、而覆盖率尽可能高的测试用例，从而来保证时间约束条件下，覆盖更多的函数块，得到的覆盖率百分比尽可能地接近完全测试的覆盖率百分比。

根据 3.2 中提出的用例约减模型，本文选取已有回归测试用例 13 067 个进行实验，图 3 是利用工具 Bullseye 获取单个测试用例的覆盖率信息。

并且，编写程序自动化采集下列相关信息。

（1）测试用例名称。

（2）测试用例的函数覆盖率信息。

（3）测试用例运行的时间。

（4）测试用例优先级系数等，部分数据如表 1 所示。

本文选取的 C-model 代码拥有 13 216 个函数功能块，实验时所取的完全测试所得到的函数覆盖率为 84%。实验结果显示：相同运行时间下，改进前 CIMS 测试集对应的函数覆盖率为 49%，而采用本文算法后获得的测试集所对应的函数覆盖率可达 76%（参见图 4）。

实验证明，采用本文的改进算法后，在原有测试运行时间不变的情况下，算法筛选出的测试集所对应的函数覆盖率提高了 27%。说明在时间有限的约束下，采用本文的算法能合理挑选符合条件的测试用例集，使得到的测试用例子集的函数覆盖率更接近完全测试所对应的覆盖率。

5  结语

本文针对 CIMS 系统中测试集的筛选问题，结合集合覆盖原理展开研究，定义了一个资源约束条件下的测试用例约减模型，并实现了一种改进的算法，使得 CIMS 测试集在规定时间内覆盖更多函数块，提升了代码质量预检的性能，对保证项目质量有着积极的实际意义。

随着项目的推进，测试集的筛选也需要定期动态调整。如何进一步完善算法，使其能优选出可以覆盖代码修改部分的测试用例，更好地满足测试需求，是下一步值得研究的方向。