劉 濤，李繼秀，王月波，蒲卿路，孫 云

(中國西南電子技術(shù)研究所，成都610036)

0 引 言

在軟件回歸測試中，傳統(tǒng)方式是將所有測試用例重新執(zhí)行一遍，當(dāng)軟件系統(tǒng)比較龐大或版本更新比較頻繁時，人力成本和測試效率都會受到很大的影響。而回歸測試中變更影響分析是重點難點，如何評估測試項更改之后的影響，量化測試項之間的關(guān)聯(lián)緊密程度，避免無關(guān)測試用例的執(zhí)行，是提升回歸測試效率的關(guān)鍵。軟件回歸測試中的影響域分析是回歸測試研究趨勢，具有研究和應(yīng)用價值。

三元閉包為社區(qū)網(wǎng)絡(luò)中兩個不認(rèn)識的人提供鏈路機制。許云峰等人[1]在此算法的基礎(chǔ)上實現(xiàn)了社區(qū)的劃分。孫昊天等人[2]在知識圖譜上應(yīng)用三元閉包知識，更精準(zhǔn)地表達(dá)了實體之間深層次的關(guān)系，更有利于社區(qū)網(wǎng)絡(luò)的研究發(fā)展。Liu等人[3]通過三元閉包理論查詢蛋白質(zhì)和模板蛋白質(zhì)之間的關(guān)系，以實現(xiàn)更精準(zhǔn)的蛋白質(zhì)折疊識別。高楊等人[4]在節(jié)點相似性上應(yīng)用三元閉包，并將權(quán)重應(yīng)用于節(jié)點相似性指標(biāo)中，用于提高鏈路預(yù)測的精度。楊梓舒[5]甚至認(rèn)為三元閉包是驅(qū)動社會網(wǎng)絡(luò)的結(jié)構(gòu)演化的因素之一。若把三元閉包理論用于梳理測試項關(guān)系，建立測試項社區(qū)網(wǎng)絡(luò)，尋找定位可能受到影響的測試項，實現(xiàn)測試用例約簡的同時，將可能有缺陷概率的測試項納入回歸測試，具備著非常大的實用價值。

自動生成回歸測試用例軟件系統(tǒng)使用基于三元閉包理論的回歸測試影響域分析方法，將軟件系統(tǒng)抽象為一個社交網(wǎng)絡(luò)，軟件系統(tǒng)提供的功能抽象為虛擬人，為虛擬人之間定義交流通道類型，通過圖論和三元閉包理論構(gòu)建非直接發(fā)生聯(lián)系的人的關(guān)系，給出回歸建議。首先建立有向有權(quán)圖模型，所有系統(tǒng)功能項用矩形表示，關(guān)系使用帶有方向的箭頭表示；再結(jié)合三元閉包理論，遞歸計算每一層三元閉包理論下的推薦值，計算出每個功能項的聚集系數(shù)，以及三元關(guān)系中可能存在關(guān)系的兩功能項之間的鄰里重疊度；最后是每個功能項推薦系數(shù)的算法實現(xiàn)，如果推薦系數(shù)大于0.5，則將該功能項納入回歸測試。本文算法實現(xiàn)了測試用例集約簡的同時，結(jié)合功能項社區(qū)網(wǎng)絡(luò)，針對性地將可能有缺陷的測試用例進(jìn)行回歸測試，提高了影響域分析的科學(xué)性和精準(zhǔn)性，并已在工程中進(jìn)行應(yīng)用。

1 軟件系統(tǒng)設(shè)計方案

軟件系統(tǒng)的組成框圖如圖1所示。系統(tǒng)輸入是獲得的測試輪次下所有功能項?；谌]包理論的軟件回歸測試影響域分析方法包括有向有權(quán)圖模型構(gòu)建模塊、功能項關(guān)聯(lián)概率計算模塊、功能項推薦系數(shù)計算模塊和回歸測試用例生成模塊四個模塊。系統(tǒng)輸出是推薦進(jìn)行回歸測試的所有測試用例。

圖1 自動生成回歸測試用例軟件系統(tǒng)組成框圖

自動生成回歸測試用例軟件系統(tǒng)流程圖如圖2所示。首先獲取軟件系統(tǒng)測試輪次下所有功能項，判斷功能項的通過狀態(tài)，如果是通過狀態(tài)，則推薦系數(shù)初始化為1，否則推薦系數(shù)初始化為0。推薦系數(shù)初始化完成后，需要給功能項之間的邊關(guān)系多個維度值并賦予權(quán)值，接著計算功能項聚集系數(shù)、鄰里重疊度、推薦系數(shù)，判斷功能項的推薦系數(shù)值是否大于0.5，如果大于0.5，則加入回歸測試隊列，作為回歸測試的輸入導(dǎo)入到測試需求分析中，流程結(jié)束，否則流程直接結(jié)束。

圖2 自動生成回歸測試用例軟件系統(tǒng)流程圖

2 算法描述

2.1 測試項之間的邊關(guān)系多個維度賦值并賦予權(quán)重

設(shè)進(jìn)行軟件回歸測試的輪次測試項數(shù)量為N,N(i)和N(j)分別表示第i個測試項和第j個測試項，定義(i,j)邊描述測試項和測試項之間直接的關(guān)系。本文邊的權(quán)值用Wij來描述，Wij的值介于0和1之間，值越大，說明兩者聯(lián)系更為緊密。文獻(xiàn)[6]將社交活躍度與用戶信任度等多維度用于社區(qū)網(wǎng)絡(luò)的推薦，受此啟發(fā)，本文關(guān)系定義了多個維度。測試項之間的控制依賴相關(guān)性，表示功能項間存在控制與被控制的關(guān)系，例如功能項A是生產(chǎn)者，功能項B是消費者，用dc來表示，介于0和1之間，分配權(quán)重用wc來表示，值為正整數(shù)；測試項之間的數(shù)據(jù)依賴相關(guān)性，表示功能項之間存在共享數(shù)據(jù)的使用，如全局變量等，用dd來表示，介于0和1之間，分配權(quán)重用wd來表示，值為正整數(shù)；測試項之間的數(shù)據(jù)交互相關(guān)性，功能項之間有數(shù)據(jù)交互，例如功能A需要使用功能B處理后的數(shù)據(jù)，用di來表示，介于0和1之間，分配權(quán)重用wi來表示，值為正整數(shù)；測試項之間的性能依賴相關(guān)性，表示功能項對系統(tǒng)的性能(如計算精度、響應(yīng)時間、CPU/內(nèi)存/存儲資源等)有影響，用dp來表示，介于0和1之間，分配權(quán)重用wp來表示；測試項之間的時序依賴相關(guān)性，表示功能項之間執(zhí)行順序不同對系統(tǒng)可能造成影響，例如多線程間的同步或互斥等，用dt來表示，介于0和1之間，分配權(quán)重用wt來表示；測試項之間的其他依賴相關(guān)性，表示在上述依賴關(guān)系之外的其他依賴，用do來表示，介于0和1之間，分配權(quán)重用wo來表示，值為正整數(shù)。相關(guān)性數(shù)值越大，表示兩個測試項之間該項的聯(lián)系越緊密；依賴權(quán)重越大，說明該項在兩者關(guān)系中越重要。

兩個測試項之間邊的權(quán)值計算公式如下：

(1)

式中：0≤Wij≤1，0≤dc≤1,0≤dd≤1,0≤di≤1,0≤dp≤1,0≤dt≤1,0≤do≤1。

2.2 基于三元閉包理論計算測試項相關(guān)概率

2.2.1 計算鄰里重疊度

鄰里重疊度用Oij來表示。用N(i)和N(j)分別表示第i個測試項和第j個測試項，通過定義(i,j)邊的“與N(i)、N(j)均為鄰居的節(jié)點數(shù)即|N(i)∩N(j)|”與“N(i)、N(j)邊中至少一個為鄰居的節(jié)點數(shù)即|N(i)∪N(j)|”的比值來表示Oij，公式如下：

(2)

Step1 獲取所有測試項。

Step2 找出所有入度和出度都大于零的測試項，即交點。

Step3 獲取第一層次的三元關(guān)系組。如果交點的入度是未通過測試項，假設(shè)未通過數(shù)量為m，遍歷交點所有出度，假設(shè)出度為n，則保存所有包含任一入度未通過測試項，交點測試項，任一交點出度為一個三元關(guān)系組，共有n×m個三元關(guān)系組。

Step4 獲取下一層次的三元關(guān)系組。對于上一層次的每一個三元關(guān)系組，判斷出度測試項的出度是否大于0，如果大于0，假設(shè)第x層次的出度數(shù)量為k(x)，以上一層次的三元關(guān)系組中交點作為三元關(guān)系組的入度點，上一層次的三元關(guān)系組中的出度作為交點，任一出度測試項的出度為三元關(guān)系組，即共有k(x)個三元關(guān)系組。

Step5 重復(fù)Step 4直到k(x)數(shù)量為0，即共有n×m×k(1)×k(2)×…×k(x)個三元關(guān)系組。

Step6 獲得了所有的三元關(guān)系組之后，計算三元關(guān)系組的入度測試項N(i)和出度測試項N(j)的交點數(shù)|N(i)∩N(j)|，還有并集數(shù)|N(i)∪N(j)|。

Step7 得出N(i)和N(j)的鄰里重疊度值。

2.2.2 計算測試項i的聚集系數(shù)Ci

節(jié)點A的聚集系數(shù)，即A的任意兩個朋友也是朋友的概率。

Step1 獲取所有測試項。

Step2 計算測試項的出度。

Step3 如果出度存在且大于1，存入鄰居數(shù)組，往下面步驟走；否則Ci為0，程序結(jié)束。

Step4 計算鄰居總對數(shù)：

鄰居總對數(shù)=(測試項出度/測試項出度 -1)/2。

(3)

Step5 計算鄰居間朋友對個數(shù)。

Step6 計算聚集系數(shù)Ci:

。

(4)

2.3 計算測試項推薦系數(shù)

Step1 如果測試項為不通過，推薦系數(shù)直接為1。

Step2 如果測試項為通過，推薦系數(shù)=所有直接相連的未通過測試項邊權(quán)重之和+所有相連的第一層三元閉包下的推薦值+所有相連的第二層三元閉包下的推薦值+…+所有相連的第一層三元閉包下的推薦值，若結(jié)果大于1，則該測試項的推薦系數(shù)等于1。

設(shè)測試項N(i)的推薦系數(shù)為Ri(0≤Ri≤1)，第n層相連三元閉包下的推薦值為Ri(n)，N(j)表示直接相連的未通過測試項，Wij表示連接測試項N(i)和測試項N(j)邊的權(quán)值，第一個求和表達(dá)的是和測試項N(i)直接相連的所有未通過測試項的邊權(quán)值之和，第二個求和表達(dá)的是和測試項N(i)相連的所有第一層三元閉包推薦值之和，第三個求和表達(dá)的是和測試項N(i)相連的所有第二層三元閉包推薦值，第n-1個求和表達(dá)的是和測試項N(i)相連的所有第n層三元閉包推薦值之和，公式如下：

(5)

若測試項N(i)處于第1層相連三元閉包中，第1層相連三元閉包下的推薦值為Ri(1)的計算方法如公式(6)所示。測試項N(i)為三元關(guān)系組中的出度點，N(q)為三元關(guān)系組中的交點，測試項N(p)為三元關(guān)系組中的入度點，且N(p)為未通過測試項。Opi表示測試項N(p)和測試項N(i)的鄰里重疊度，Cq表示測試項N(q)的聚集系數(shù)，Rp表示測試項N(p)的推薦系數(shù)，Rq表示測試項N(q)的推薦系數(shù)。

(6)

若測試項N(i)處于第2層相連三元閉包中，第2層相連三元閉包下的推薦值為Ri(2)的計算方法如公式(7)所示。測試項N(k)為三元關(guān)系組中的出度點，N(q)為三元關(guān)系組中的交點，測試項N(p)為三元關(guān)系組中的入度點，且N(p)為未通過測試項，測試項N(i)為測試項N(k)的出度點。Oqi表示測試項N(q)和測試項N(i)的鄰里重疊度，Ck表示測試項N(k)的聚集系數(shù)，Rq表示測試項N(q)的推薦系數(shù)，Rk表示測試項N(k)的推薦系數(shù)。

(7)

若測試項N(i)處于第n層相連三元閉包中，第n層相連三元閉包下的推薦值為Ri(n)的計算方法如公式(8)所示。測試項N(k)為三元關(guān)系組中的出度點，N(q)為三元關(guān)系組中的交點，測試項N(p)為三元關(guān)系組中的入度點，且N(p)為未通過測試項，測試項N(a)為測試項N(k)的出度點，測試項N(b)為測試項N(a)的出度點…一直到無出度點的測試項N(i)處為止。設(shè)測試項的N(i)前兩項分別為測試項N(s)和測試項N(t)。

(8)

式中：Osi表示測試項N(s)和測試項N(i)的鄰里重疊度，Ct表示測試項N(t)的聚集系數(shù)，Rs表示測試項N(s)的推薦系數(shù)，Rt表示測試項N(t)的推薦系數(shù)。

3 工程應(yīng)用實踐

在網(wǎng)絡(luò)頻率規(guī)劃管理軟件項目回歸測試上應(yīng)用該算法，共有42個功能項，其中無需進(jìn)行測試的功能項23個，已通過功能項6個，有缺陷功能項共有13個，如表1所示，其中無需進(jìn)行測試的功能項不再計入統(tǒng)計范圍。

表1 項目首輪測試結(jié)果

將項目網(wǎng)絡(luò)頻率規(guī)劃管理軟件所有功能項抽象為虛擬人，通過賦予邊關(guān)系權(quán)值方式為虛擬人之間定義交流通道類型，N(i)和N(j)分別表示第i個測試項和第j個測試項，如表2所示。

表2 虛擬人之間定義交流通道類型

未運行測試項推薦系數(shù)為0，未通過測試項推薦系數(shù)為1，本算法影響域分析之后，本項目已通過測試項的推薦系數(shù)如表3所示。

表3 各功能項推薦系數(shù)

根據(jù)表3結(jié)果可知，經(jīng)過影響域分析算法計算，首輪測試中無缺陷的“頻率規(guī)劃”和“規(guī)劃文件生成”兩個功能項需要進(jìn)入回歸測試。在回歸測試中，“頻率規(guī)劃”功能項出現(xiàn)了3個缺陷，“規(guī)劃文件”功能項回歸出現(xiàn)了2個缺陷。下面具體展開“頻率規(guī)劃”功能項缺陷。

(1)由于“VHF電臺子網(wǎng)規(guī)劃”中測試用例“在界面編輯定頻頻率，包括定頻范圍內(nèi)的異常邊界值、異常值以及頻率間隔異?！敝校嬖谌毕荨胺秶磁袛唷?，修復(fù)此測試用例的缺陷后，影響了“頻率規(guī)劃”功能項的測試用例“通過界面設(shè)置VHF電臺子網(wǎng)頻率規(guī)劃”，產(chǎn)生了新缺陷“范圍并未同步，輸入異常數(shù)據(jù)，軟件沒有停止處理，沒有提示異?！?。

(2)在“頻率管理”測試用例“選擇禁用頻率類型為救生頻率，輸入值為異常值及異常邊界值”中，存在缺陷“救生范圍未判斷”。修復(fù)此測試用例的缺陷后，影響了頻率規(guī)劃功能項的測試用例“通過界面設(shè)置救生頻率”，產(chǎn)生了新缺陷“范圍并未同步，輸入異常數(shù)據(jù)，軟件沒有停止處理，沒有提示異?！?。

(3)“網(wǎng)絡(luò)拓?fù)湟?guī)劃”中某測試用例的步驟之一“規(guī)劃UHF電臺子網(wǎng)”存在“重進(jìn)之后，拓?fù)鋱D連線與之前規(guī)劃不一致”的缺陷，修復(fù)之后，導(dǎo)致UHF電臺子界面無法顯示出網(wǎng)絡(luò)拓?fù)鋱D中規(guī)劃的UHF子網(wǎng)，從而導(dǎo)致“頻率規(guī)劃”中無法通過界面設(shè)置UHF電臺子網(wǎng)頻率規(guī)劃。

由項目實踐結(jié)果可知，該算法在以下兩種情況中表現(xiàn)優(yōu)異：一是將所有測試項進(jìn)行回歸測試的案例——共19個測試項，案例情況下，需要回歸19個測試項，101個測試用例，使用本算法只需回歸15個測試項，74個測試用例，實現(xiàn)了測試用例集約簡，測試效率得到了較大提升；二是只對有缺陷的測試項進(jìn)行回歸測試的案例——共19個測試項，案例情況下，需要回歸13個有缺陷的測試項，66個測試用例，使用本算法在回歸所有有缺陷測試用例的情況下，計算由于程序變更或其他依賴關(guān)系所可能導(dǎo)致其他測試用例出現(xiàn)缺陷的概率，得出額外有2個測試項，8個測試用例可能出現(xiàn)缺陷，測試充分性和覆蓋率得到了較大提升。

4 實驗結(jié)果與分析

本節(jié)將列舉本文算法在網(wǎng)絡(luò)頻率規(guī)劃管理軟件、任務(wù)數(shù)據(jù)接入處理軟件、偵察過程回放軟件、導(dǎo)調(diào)控制檢測軟件和海事五代星實裝訓(xùn)練軟件這五個軟件回歸測試中的表現(xiàn)。如表4所示，“測試用例數(shù)”等于輪次測試下“已通過測試用例數(shù)”和“有缺陷的測試用例數(shù)”之和，不包含輪次下未執(zhí)行測試用例數(shù)。

表4 算法在五個軟件回歸測試的表現(xiàn)

由表4的實驗結(jié)果可知，該算法在五個項目應(yīng)用中將五個軟件系統(tǒng)抽象為五個社交網(wǎng)絡(luò)，軟件系統(tǒng)提供的功能抽象為虛擬人，為虛擬人之間定義交流通道類型，通過圖論和三元閉包理論構(gòu)建非直接發(fā)生聯(lián)系的人的關(guān)系，給出回歸建議。與將所有測試項進(jìn)行回歸測試的案例相比，實際回歸測試用例數(shù)遠(yuǎn)少于所有測試用例數(shù)，實現(xiàn)了測試用例集的約簡；與只對有缺陷的測試項進(jìn)行回歸測試的案例相比，實際回歸測試用例數(shù)大于輪次測試下有缺陷的測試用例數(shù)，預(yù)測了由于測試項更改引發(fā)其他測試項出現(xiàn)新缺陷的概率，從而決定是否將其他測試項進(jìn)行回歸測試。工程應(yīng)用實踐結(jié)果表明，本文算法在回歸測試中有可能發(fā)現(xiàn)新缺陷，可以在一定程度上提升回歸測試的充分性和覆蓋率。

5 結(jié)束語

本文應(yīng)用三元閉包理論梳理測試項關(guān)系，結(jié)合圖論建立測試項社區(qū)網(wǎng)絡(luò)，尋找定位可能受到影響的測試項，實現(xiàn)測試用例約簡的同時，將可能有缺陷概率的測試項納入回歸測試，可能發(fā)現(xiàn)新缺陷，節(jié)約了人力成本，減少了資源的消耗，具有較大的實用價值。但本文在測試項與測試項之間的權(quán)值取值上沒有具體到代碼層面，這也是后續(xù)改進(jìn)的方向。