楊祎巍，匡曉云，黃開天，洪超，鄭昌立，蔣小文*

（1.廣東省電力系統(tǒng)網(wǎng)絡(luò)安全企業(yè)重點(diǎn)實驗室（南方電網(wǎng)科學(xué)研究院有限責(zé)任公司），廣東廣州 510080；2.浙江大學(xué)信息與電子工程學(xué)院，浙江杭州 310027）

0 引言

回歸測試集是一組達(dá)到了目標(biāo)覆蓋率的用例集合，一般通過制訂用例計劃實現(xiàn)或由自動隨機(jī)產(chǎn)生的方式構(gòu)造，易導(dǎo)致一些點(diǎn)被多個用例重復(fù)覆蓋，造成用例冗余［1］。在回歸測試時，為縮短仿真時間，提高效率，希望找到極小的用例集合，在滿足覆蓋率的前提下，用盡量短的時間，完成回歸測試，在多次反復(fù)執(zhí)行中，節(jié)省了大量時間，從而大大縮短項目完成時間。通常，對所有用例進(jìn)行回歸測試，只適用于規(guī)模較小或項目時間較寬松的情況［2］。有時會根據(jù)對項目的理解，憑經(jīng)驗從用例集中挑選一些用例進(jìn)行計算，但效果并不理想，需具有與項目強(qiáng)相關(guān)的專業(yè)知識，通用性亦不好，當(dāng)用例選擇不同時，結(jié)果差別很大，且不能同時滿足覆蓋率和精簡化的要求。

目前，在相關(guān)測試用例集約簡技術(shù)中，從測試需求集或組合覆蓋著手的測試方法較多。其中，組合測試有正交試驗設(shè)計法和兩兩組合覆蓋法等［3］?；跍y試需求集的方法主要將約簡問題抽象為數(shù)學(xué)問題，用數(shù)學(xué)方法求解。用得較多的有貪心算法、啟發(fā)式算法、遺傳算法以及蟻群算法等生物進(jìn)化算法［4］。

在處理實際問題時，優(yōu)化算法是將問題用類似的生物或數(shù)學(xué)模型代替，然后代入合適的策略進(jìn)行求解。編碼與解碼互相對應(yīng)，在算法搜索空間和實際問題的解空間之間進(jìn)行轉(zhuǎn)換［5］。相較于其他進(jìn)化算法，Memetic 算法在求解中增加了局部處理步驟，其作用是對全局處理后的個體做局部處理，在一些位置做突變，盡早將一些不好的個體篩除，從而減少運(yùn)算次數(shù)，提升運(yùn)算效率。影響Memetic 算法的關(guān)鍵因素是各算子的選擇和局部策略的性能［6］。

1 用例集約簡模型

分析測試用例集的特點(diǎn)發(fā)現(xiàn)，其與集合覆蓋問題的數(shù)學(xué)描述相似，可將約簡測試用例集的求解問題轉(zhuǎn)換為集合覆蓋問題的優(yōu)化求解。集合覆蓋問題在日常生活中較常見，是一類帶有約束的離散優(yōu)化問題，其變量和解一般為整數(shù)向量，如調(diào)度問題、選址問題等，是一類非確定多項（non-deterministic polynomial，NP）難問題。通俗講，集合覆蓋問題可解釋為：有2 個集合E和S，S中元素能全部覆蓋E中元素，如果S中有n個子集，每個子集對應(yīng)一個耗費(fèi)代價，在S的子集中能找到完全覆蓋集合E的集合，且耗費(fèi)代價最小［7］。集合覆蓋示意如圖1 所示。測試用例集約簡問題，則是全部的功能覆蓋點(diǎn)集合E（為需要被覆蓋的集合），各用例組成的測試用例集為集合S，子集中每包含一個測試用例，其耗費(fèi)代價將相應(yīng)增加，在完全覆蓋所有被要求覆蓋的點(diǎn)的條件下，選擇耗費(fèi)代價最小的子集，即測試用例集數(shù)量最少的集合。

圖1 集合覆蓋問題示意Fig.1 The model of test case suite reduction

假設(shè)有i個行元素的整體，代表所有需要覆蓋的功能點(diǎn)，有j個列元素的整體，代表所有用例集合，用式（1）表示，其中，xj表示用例集中第j個用例是否被選擇組成子集，xj是一個二值元素（取0 或1），取1 時說明第j個用例被選中，加入約簡用例組合，取0 時說明第j個用例未被選中；tj表示每個用例所需的仿真時間，aij表示第j個用例是否覆蓋第i個功能點(diǎn)；cj表示每個用例的耗費(fèi)代價，在本文的約簡問題中，cj=1。

2 Memetic 算法

2.1 種群編碼及初始化

在測試用例約簡問題中，采用二進(jìn)制編碼，每比特有2 種取值，分別表示用例的選擇與否。通過此方式，有n個用例的用例集用一個n位的二進(jìn)制串表示，每位對應(yīng)一個用例，其值反映用例是否被選擇。

種群的數(shù)量是種群初始化的重要參數(shù)，對算法的運(yùn)算性能有一定影響。為使計算量不至于過大、多樣性不會太低，通常選擇種群數(shù)量為20～100［8］。本文選取的種群數(shù)量為50，即每代種群中有50 種不同的用例集組合。

由于在本文的約簡問題中有一些約束條件，不滿足約束條件的個體得到的是不可行解。當(dāng)不可行解較多時，從不可行解區(qū)域收斂至可行解區(qū)域會浪費(fèi)較多時間。本文采用貪心策略，如圖2 所示，在隨機(jī)產(chǎn)生的種群數(shù)量個體中，將所有用例按適應(yīng)度函數(shù)值從大到小排列。在種群初始化后，檢查初始化種群個體，若發(fā)現(xiàn)其為不可行解，則添加適應(yīng)度值大的用例使其變?yōu)榭尚薪狻?/p>

圖2 貪心修正策略Fig.2 The greedy correction strategy

2.2 適應(yīng)度函數(shù)

為使結(jié)果盡可能快速地向可行解區(qū)域收斂，將約束處理機(jī)制融入適應(yīng)度函數(shù)設(shè)計，并與后續(xù)的選擇策略相結(jié)合。當(dāng)個體滿足約束條件時，仿真時間較少的個體比仿真時間較多的個體優(yōu)先被選中，當(dāng)仿真時間相同時，用例集較小的個體優(yōu)先被選中。對可行解，計算每個個體的用例數(shù)與全部用例數(shù)的差與時間相關(guān)的數(shù)值和，并將其作為適應(yīng)度函數(shù)，對非可行解，用兩者的差值與時間參數(shù)值的和表示適應(yīng)度值，并令非可行解的適應(yīng)度函數(shù)值均小于0，令可行解的適應(yīng)度函數(shù)值均大于0。

其中，n為原始用例集的用例數(shù)，gij為當(dāng)前種群第i個個體X的第j位，總和即為用例集數(shù)，t(X)表示某個體代表的用例集運(yùn)行的仿真時間，T表示原始用例集運(yùn)行的仿真時間，cov（X）表示個體X的覆蓋率，cov（I）表示原始用例集的覆蓋率。

2.3 全局搜索策略

在設(shè)計全局搜索策略時，將遺傳算法和差分進(jìn)化算法相結(jié)合，整體架構(gòu)以差分進(jìn)化算法為基礎(chǔ)。在初始化種群后，采用差分進(jìn)化算法運(yùn)行步驟，先變異、交叉，然后選擇如圖3 所示的混合全局搜索策略。

圖3 混合全局搜索策略Fig.3 The hybrid global strategy

由于差分進(jìn)化的變異算子在實數(shù)域上，而本文討論的離散問題在實數(shù)域上搜索無效果，因此，首先，須采用遺傳算法中的變異算子處理二進(jìn)制數(shù)據(jù)串，然后，由差分進(jìn)化的交叉算子產(chǎn)生中間代種群，最后，在中間代種群與原始種群間做選擇。

2.3.1 變異算子

變異策略是全局策略中的重要操作，亦是保證種群多樣性的關(guān)鍵步驟，與染色體的編碼方式息息相關(guān)。本文采用的編碼變異方法具體表現(xiàn)為二進(jìn)制串每個基因位上的數(shù)值在0 和1 間翻轉(zhuǎn)。對傳統(tǒng)一元變異充分性不足問題，用2 個基因位結(jié)合使用的方法解決，如圖4 所示，對2 條染色體采用二元變異操作，效果明顯好于一元變異［2］。

圖4 二元變異Fig.4 The binary variation

在本文設(shè)計的變異策略中，同時使用同或和異或2 種運(yùn)算，2 個舊個體產(chǎn)生2 條新染色體，如此，每個基因位均為原來的0 和1，僅染色體組合不同，使得種群變化足夠豐富，同時保證了基因完整性。進(jìn)行變異運(yùn)算時，先將輸入的種群個體打亂，隨機(jī)排序，每次取相鄰的2 個個體做二元變異，n個個體種群就有n/2 個子集。

2.3.2 交叉算子

通常，交叉策略用得較多的為二項交叉和指數(shù)交叉2 種。受文獻(xiàn)［9］啟發(fā)，本文采用動態(tài)調(diào)整的方式，在種群更新中，每次迭代后更新交叉率。交叉率值（CR）由均值a和標(biāo)準(zhǔn)偏差決定，隨著種群的更新，均值a也相應(yīng)更新，以適應(yīng)不同進(jìn)化階段的特性。同時，隨適應(yīng)度變化做動態(tài)調(diào)整，當(dāng)適應(yīng)度較小時增大交叉率，較大時適當(dāng)減小交叉率，使其盡快收斂。

其中，c為0～1 的常數(shù)，fmax表示當(dāng)前種群最大的適應(yīng)度，f′表示完全用例集的適應(yīng)度。更新a之后，即可根據(jù)正態(tài)分布得到種群個體數(shù)量的CR 值，即scr列表，每個個體對應(yīng)一個值。mean（scr）為Lehmer平均值，計算式為

2.3.3 選擇策略

以差分進(jìn)化算法中常用的貪婪選擇方式為選擇策略，初始化后通過變異和交叉操作得到中間代種群，然后比較原始種群與中間代種群。在選擇策略中，比較原始種群與中間代種群對應(yīng)個體的適應(yīng)度值，適應(yīng)度大的個體加入新的種群，如式（5）所示。

其中，Vi+1(t)為新一代種群的第t個個體，Ui(t)和Vi(t)分別為中間代個體與當(dāng)前代個體。

2.4 局部搜索策略

在常見的幾種局部搜索策略中，禁忌搜索的局部尋優(yōu)能力最強(qiáng)［10］，為此，本文采用禁忌搜索策略。在完成全局策略的變異和交叉算子運(yùn)算后進(jìn)行局部搜索。禁忌搜索策略一般流程如圖5 所示。

圖5 禁忌搜索策略一般流程Fig.5 The general process of taboo search strategy

禁忌搜索中的關(guān)鍵因素有：禁忌長度、候選解、終止準(zhǔn)則、禁忌對象、鄰域結(jié)構(gòu)、特赦準(zhǔn)則等［11-12］。結(jié)合本文的測試用例集約簡問題，對禁忌搜索策略做一定改進(jìn)。在Memetic 算法中，局部搜索通常需多次運(yùn)算，每次迭代時間雖較單獨(dú)的全局搜索策略稍長，但因其迭代次數(shù)更少，所需總時間較少。本文中，因為最終的約簡集合為最優(yōu)個體所代表的用例集，所以應(yīng)保證最優(yōu)個體不陷入局部最優(yōu)解，同時為減少計算用時，在全局搜索后，選取在種群中適應(yīng)度排名前10%的個體，用局部搜索更新這些個體。其中禁忌長度設(shè)為5，鄰域操作為隨機(jī)翻轉(zhuǎn)某兩比特位，每次產(chǎn)生6 個鄰域解，循環(huán)10 次，結(jié)束。

3 實驗與分析

在完成上述算法設(shè)計后，進(jìn)行實驗分析。實驗平臺為基于通用驗證方法學(xué)（universal verification methodology，UVM）的仿真驗證平臺，如圖6 所示。設(shè)計模塊為一款軟硬件可配置的串行接口IP（RPC），串口協(xié)議特性如表1 所示，為可靈活配置的面積優(yōu)化的串行協(xié)議控制器，通過狀態(tài)機(jī)編程可使用不同的協(xié)議。該IP 支持配置為I2C、SPI 的主機(jī)或從機(jī)模式及標(biāo)準(zhǔn)UART 接口，此外，也可配置非標(biāo)準(zhǔn)接口。

表1 串口協(xié)議特性Table 1 The serial protocol features

圖6 實驗平臺架構(gòu)Fig.6 The experimental platform architecture

以I2C 為實驗對象，以選定的用例集所能覆蓋的功能點(diǎn)為全集，從回歸測試集中選取5 組不同規(guī)模的用例集，分別運(yùn)用標(biāo)準(zhǔn)遺傳算法和本文的Memetic 算法進(jìn)行約簡實驗。實驗比較了約簡后的用例集規(guī)模、約簡過程算法運(yùn)行時間、約簡后用例集的仿真時間。表2 為不同規(guī)模用例集約簡結(jié)果，其趨勢圖如圖7 所示，由圖7 可知，Memetic 算法較標(biāo)準(zhǔn)遺傳算法的約簡效果更好。表3 為在不同規(guī)模用例集下不同算法約簡的運(yùn)行時間，圖8 為其總體趨勢，由圖8 可知，Memetic 算法比標(biāo)準(zhǔn)遺傳算法的運(yùn)行時間更少，速度更快。表4 為不同規(guī)模用例集下不同算法約簡的仿真時間比較，圖9 為其直方圖。綜上可知，本文算法約簡效果更好，時間更節(jié)省，測試代價降低更顯著。

表2 不同規(guī)模用例集約簡結(jié)果Table 2 The results of test case suite reduction for different scales

表3 不同規(guī)模用例集下不同算法約簡的運(yùn)行時間Table 3 The runtime of different algorithm in test case suite reduction for different scales

圖7 用例集約簡結(jié)果Fig.7 The results of test case suite reduction

圖8 用例集約簡運(yùn)行時間Fig.8 The run time of test case suite reduction

表4 不同規(guī)模用例集下不同算法約簡的仿真時間Table 4 The simulation time of different algorithm in test case suit reduction for different scale

圖9 用例集仿真時間Fig.9 The simulation time of test case suite

4 結(jié)論

在調(diào)研用例集約簡技術(shù)的基礎(chǔ)上，首先，對約簡問題進(jìn)行了數(shù)學(xué)建模。然后，根據(jù)模型特點(diǎn)建立了Memetic 算法，對其中的全局策略和局部策略進(jìn)行了設(shè)計，研究了改進(jìn)算法中的各個算子，并將其應(yīng)用于約簡優(yōu)化問題。對于用例集約簡實驗，在實際項目基礎(chǔ)上，設(shè)計了相應(yīng)的UVM 仿真驗證平臺，形成了用例集，并對其進(jìn)行仿真分析，達(dá)到了覆蓋率要求，形成統(tǒng)一覆蓋率庫。最后，分別應(yīng)用標(biāo)準(zhǔn)遺傳算法和本文Memetic 算法對用例集進(jìn)行約簡實驗，結(jié)果表明，本文算法性能更優(yōu)、更節(jié)省時間、約簡效果更顯著，具有較好的實際應(yīng)用價值。