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

（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 測試集在規定時間內覆蓋更多函數塊，提升了代碼質量預檢的性能，對保證項目質量有著積極的實際意義。

隨著項目的推進，測試集的篩選也需要定期動態調整。如何進一步完善算法，使其能優選出可以覆蓋代碼修改部分的測試用例，更好地滿足測試需求，是下一步值得研究的方向。