基于歷史數(shù)據(jù)和多目標(biāo)優(yōu)化的測(cè)試用例排序方法

李興佳，楊秋輝，洪 玫，潘春霞，劉瑞航

（四川大學(xué) 計(jì)算機(jī)學(xué)院，成都 610065）

0 引言

回歸測(cè)試是對(duì)修改后的軟件進(jìn)行重新測(cè)試，以確保未因修改代碼而引入新的缺陷。由于軟件不斷演化，回歸測(cè)試中的測(cè)試用例集會(huì)變得逐漸龐大與復(fù)雜，導(dǎo)致測(cè)試成本不斷增大。在持續(xù)集成開(kāi)發(fā)環(huán)境下，產(chǎn)品迭代速度不斷加快，增大了回歸測(cè)試成本，如在Google 中，開(kāi)發(fā)人員平均每秒鐘提交一次代碼，每天需要執(zhí)行超過(guò)1.5 億次測(cè)試［1］，測(cè)試成本較高。如何有效對(duì)測(cè)試用例集進(jìn)行優(yōu)化、減少測(cè)試用例執(zhí)行成本、提升回歸測(cè)試效益，吸引了眾多國(guó)內(nèi)外學(xué)者進(jìn)行研究。

回歸測(cè)試用例優(yōu)化技術(shù)可分為測(cè)試套件最小化技術(shù)、測(cè)試用例選擇技術(shù)和測(cè)試用例排序技術(shù)［2］。測(cè)試用例排序是按照某種規(guī)則安排測(cè)試用例的執(zhí)行次序，使具有高優(yōu)先級(jí)的測(cè)試用例更早執(zhí)行，以盡快檢測(cè)出缺陷，提升回歸測(cè)試效率。

本文在已有研究的基礎(chǔ)上，提出了一種基于歷史數(shù)據(jù)和多目標(biāo)優(yōu)化的測(cè)試用例排序方法。首先在歷史測(cè)試數(shù)據(jù)分析階段，將測(cè)試不同功能且具有不同代碼覆蓋范圍的測(cè)試用例進(jìn)行區(qū)分，同時(shí)挖掘測(cè)試用例間的關(guān)聯(lián)規(guī)則；然后在多目標(biāo)排序階段，在聚類結(jié)果的基礎(chǔ)上，使用多目標(biāo)優(yōu)化技術(shù)對(duì)測(cè)試用例集排序，以將相似的測(cè)試用例分隔開(kāi)；最后在動(dòng)態(tài)調(diào)整階段，根據(jù)測(cè)試用例間的執(zhí)行失敗關(guān)聯(lián)規(guī)則，動(dòng)態(tài)調(diào)整測(cè)試用例執(zhí)行順序。本文方法旨在提升測(cè)試的缺陷檢測(cè)速率，使具有多樣性和更有可能檢測(cè)到缺陷的測(cè)試用例優(yōu)先執(zhí)行，從而使測(cè)試人員更快發(fā)現(xiàn)缺陷，提升回歸測(cè)試效益。

1 相關(guān)工作

測(cè)試用例排序技術(shù)可分為使用靜態(tài)信息的排序技術(shù)、使用動(dòng)態(tài)信息的排序技術(shù)和使用混合信息的測(cè)試用例排序技術(shù)［3］。

Xiao 等［4］使用支持向量機(jī)預(yù)測(cè)測(cè)試用例檢測(cè)到缺陷的可能性，并對(duì)測(cè)試用例聚類，最后進(jìn)行簇內(nèi)排序和簇間排序。Najafi 等［5］對(duì)揭示更多缺陷和平均執(zhí)行時(shí)間更少的測(cè)試用例賦予更高的優(yōu)先級(jí)。Noor 等［6］使用多種距離度量方法計(jì)算測(cè)試用例相似性，并優(yōu)先執(zhí)行和歷史執(zhí)行失敗的測(cè)試用例相似的測(cè)試用例。Busjaeger 等［7］根據(jù)測(cè)試用例的代碼覆蓋率、內(nèi)容相似度、失敗歷史等信息，使用支持向量機(jī)對(duì)測(cè)試用例排序。De Oliveira Neto 等［8］根據(jù)測(cè)試用例在測(cè)試需求、測(cè)試依賴和測(cè)試步驟方面的相似性，去除相似性高的測(cè)試用例，減少了測(cè)試用例數(shù)量和測(cè)試執(zhí)行時(shí)間，同時(shí)保證了測(cè)試用例的多樣性。Carlson 等［9］使用層次聚類算法對(duì)測(cè)試用例進(jìn)行聚類，然后對(duì)每一類測(cè)試用例進(jìn)行排序，生成最終的排序序列。Thomas 等［10］利用語(yǔ)義主題模型生成測(cè)試用例的主題分布，然后計(jì)算測(cè)試用例間的相似性，在排序過(guò)程中，將與已排序用例集具有更低相似性的測(cè)試用例優(yōu)先排序。Pradhan等［11］提出了一種利用關(guān)聯(lián)規(guī)則和多目標(biāo)搜索的黑盒測(cè)試用例排序方法，首先挖掘測(cè)試用例的關(guān)聯(lián)規(guī)則，然后使用非支配排序遺傳算法（Non-dominated Sorting Genetic AlgorithmⅡ，NSGA-Ⅱ）對(duì)測(cè)試用例排序，在按照該順序執(zhí)行過(guò)程中，根據(jù)關(guān)聯(lián)規(guī)則，動(dòng)態(tài)調(diào)整執(zhí)行順序。

目前的測(cè)試用例排序技術(shù)在判斷測(cè)試用例相似性時(shí)，僅利用了單一的靜態(tài)信息或動(dòng)態(tài)信息；在利用多目標(biāo)排序技術(shù)時(shí)，沒(méi)有考慮測(cè)試用例冗余的問(wèn)題，不利于提升排序序列的揭錯(cuò)速率。針對(duì)現(xiàn)有方法存在的不足，本文提出了一種基于歷史數(shù)據(jù)和多目標(biāo)優(yōu)化的測(cè)試用例排序方法。

2 本文方法

為了提高檢測(cè)速率，盡早發(fā)現(xiàn)錯(cuò)誤，排序序列應(yīng)滿足以下要求：1）讓測(cè)試不同功能且具有不同代碼覆蓋范圍的測(cè)試用例盡早執(zhí)行；2）在一定時(shí)間內(nèi)盡可能執(zhí)行更多的測(cè)試用例；3）使可能檢測(cè)到缺陷的測(cè)試用例盡早執(zhí)行。為了滿足以上要求，所提方法的整體流程包括三個(gè)階段，分別為：歷史測(cè)試數(shù)據(jù)分析、多目標(biāo)排序和動(dòng)態(tài)調(diào)整執(zhí)行次序，整體流程如圖1 所示。

圖1 本文方法的整體流程Fig.1 Overall flow of the proposed method

2.1 基于文本主題和代碼覆蓋相似性對(duì)測(cè)試用例聚類

已有研究［9］證明，如果測(cè)試用例具有一些共同的屬性（如代碼覆蓋范圍），那么同一組中的測(cè)試用例可能具有類似的故障檢測(cè)能力。Carlson 等［9］通過(guò)實(shí)驗(yàn)對(duì)比了僅使用代碼覆蓋率、代碼復(fù)雜性、有關(guān)實(shí)際故障的歷史數(shù)據(jù)對(duì)測(cè)試用例進(jìn)行排序和將上述指標(biāo)分別與聚類算法結(jié)合后對(duì)測(cè)試用例排序兩種方式的平均故障檢測(cè)率（Average Percentage of Faults Detected，APFD），結(jié)果表明，結(jié)合聚類算法后APFD 值有明顯提升，其中代碼覆蓋率指標(biāo)效果更好。因此將聚類算法應(yīng)用于測(cè)試用例優(yōu)先級(jí)排序技術(shù)，可以提升排序效果。

基于文本主題相似性的方法從測(cè)試用例靜態(tài)文本的角度出發(fā)，考慮了測(cè)試用例在功能上的相似性，提升了排序效果［10］。但是仍舊存在以下問(wèn)題：對(duì)于如基于文本主題相似性的局限性示例中的被測(cè)方法和測(cè)試用例，測(cè)試用例1 和測(cè)試用例2 只有參數(shù)不同，從文本相似性角度分析，這兩個(gè)測(cè)試用例屬于同一類；但是這兩個(gè)測(cè)試用例測(cè)試的代碼塊完全不同，不應(yīng)歸為同類測(cè)試用例。因此本文同時(shí)考慮了基于代碼覆蓋的相似性，從測(cè)試用例動(dòng)態(tài)執(zhí)行信息的角度出發(fā)，考慮測(cè)試用例語(yǔ)句級(jí)別代碼覆蓋范圍的相同程度。為更全面地評(píng)價(jià)測(cè)試用例的相似性，在分別計(jì)算出基于文本主題和基于代碼覆蓋的相似性后，將這兩種相似性進(jìn)行加權(quán)結(jié)合。

基于文本主題相似性的局限性示例如下。

基于文本主題的測(cè)試用例相似性計(jì)算方法如下：將預(yù)處理后的測(cè)試用例文本信息集Tpre=｛tp1，tp2，…，tpn｝（tpi代表測(cè)試用例ti的文本信息，n為測(cè)試用例總數(shù)）使用隱含狄利克雷分布（Latent Dirichlet Allocation，LDA）模型進(jìn)行主題建模，得到D=｛d1，d2，…，dn｝，其中di表示測(cè)試用例ti的主題分布；topicj表示主題j。然后將主題分布di視為向量并計(jì)算向量之間的距離以度量測(cè)試用例的相似性，距離值越小，測(cè)試用例越相似。最終得到的相似矩陣是一個(gè)對(duì)稱矩陣，其中disij即為測(cè)試用例ti與tj之間的距離值?；谖谋局黝}的測(cè)試用例相似性計(jì)算流程如圖2 所示。

圖2 基于文本主題的測(cè)試用例相似性計(jì)算流程Fig.2 Test case similarity computing process based on text topic

已有研究［12-13］證明，語(yǔ)句級(jí)別覆蓋在測(cè)試用例排序技術(shù)中表現(xiàn)最好；因此，本文采用語(yǔ)句級(jí)別的覆蓋來(lái)計(jì)算測(cè)試用例代碼覆蓋的相似性。首先，統(tǒng)計(jì)測(cè)試用例執(zhí)行后的語(yǔ)句覆蓋情況TC=｛tc1，tc2，…，tcn｝，其中tci表示測(cè)試用例ti覆蓋的語(yǔ)句集合；然后，使用杰卡德距離［14］度量?jī)蓚€(gè)測(cè)試用例間的相似性，兩個(gè)測(cè)試用例語(yǔ)句覆蓋范圍重合越大，杰卡德距離越小，也就代表兩個(gè)測(cè)試用例越相似。最終得到一個(gè)與圖2 中結(jié)構(gòu)相同的相似矩陣。

將這兩種動(dòng)靜態(tài)相似性結(jié)合的表達(dá)式如式（1）所示：

其中：Similarityfinal是加權(quán)計(jì)算后的相似矩陣；Similaritytopic是基于文本主題的相似矩陣；Similaritycoverage是基于代碼覆蓋的相似矩陣；α是權(quán)重系數(shù)。

最后，根據(jù)加權(quán)結(jié)合后的測(cè)試用例之間的相似性距離矩陣，使用層次聚類算法將測(cè)試用例集中的測(cè)試用例劃分為不同的類。聚類結(jié)果為C=｛c1，c2，…，cz｝，其中ci代表第i個(gè)類簇。

2.2 測(cè)試用例的關(guān)聯(lián)規(guī)則挖掘

測(cè)試用例之間可能存在這樣的關(guān)系：在歷史執(zhí)行中，當(dāng)一個(gè)測(cè)試用例執(zhí)行失敗時(shí)，其余一個(gè)或多個(gè)測(cè)試用例往往同時(shí)也失敗；那么可以認(rèn)為這個(gè)測(cè)試用例和與它經(jīng)常同時(shí)失敗的測(cè)試用例之間存在關(guān)聯(lián)規(guī)則，表示為ti→（ti1，ti2，…，tik），意思為當(dāng)ti執(zhí)行失敗時(shí)，ti1，ti2，…，tik往往也失敗，并且認(rèn)為每個(gè)失敗的測(cè)試用例都是由一個(gè)單獨(dú)的錯(cuò)誤引起的［11］。研究［5，11，15-16］表明利用這些隱含的關(guān)系，可以提升回歸測(cè)試的有效性。

本文使用Apriori 算法［17］挖掘歷史執(zhí)行信息中存在的關(guān)聯(lián)規(guī)則，將每次執(zhí)行結(jié)果中所有失敗的測(cè)試用例看作一個(gè)事務(wù)，將事務(wù)中每一個(gè)失敗過(guò)的測(cè)試用例看作一個(gè)項(xiàng)。該算法過(guò)程主要分為兩步：1）通過(guò)迭代檢索出測(cè)試用例執(zhí)行信息數(shù)據(jù)庫(kù)中支持度不小于設(shè)定閾值的項(xiàng)集，這些項(xiàng)集被稱作頻繁項(xiàng)集；2）從頻繁項(xiàng)集中獲取置信度不小于設(shè)定閾值的關(guān)聯(lián)規(guī)則。支持度公式如式（2）所示：

其中：number(AB)表示同時(shí)出現(xiàn)測(cè)試用例A和B的事務(wù)的總數(shù)；number(AllRecord)表示總事務(wù)數(shù)；support(A→B)表示關(guān)聯(lián)規(guī)則(A→B)的支持度，即A和B同時(shí)發(fā)生的概率。

置信度公式如式（3）所示：

其中：number(AB)表示同時(shí)出現(xiàn)測(cè)試用例A和B的事務(wù)的總數(shù)；number(A) 表示出現(xiàn)測(cè)試用例A的事務(wù)總數(shù)；confidence(A→B)表示關(guān)聯(lián)規(guī)則(A→B)的置信度，即在A發(fā)生的情況下B發(fā)生的條件概率。

在挖掘到的關(guān)聯(lián)規(guī)則中可能存在這樣的情況：某些存在關(guān)聯(lián)規(guī)則的測(cè)試用例揭示的是相同的缺陷，這種情況并不能有效提升揭錯(cuò)效率，因此需要進(jìn)行篩選。篩選過(guò)程的核心思想是：若兩個(gè)測(cè)試用例揭示相同的缺陷次數(shù)超過(guò)共同失敗次數(shù)的一半，那么在A揭示這個(gè)缺陷后，就沒(méi)有必要立即執(zhí)行關(guān)聯(lián)的測(cè)試用例B了；因?yàn)锽在很大概率下也會(huì)揭示相同的缺陷，因此應(yīng)將其視為無(wú)效。在挖掘關(guān)聯(lián)規(guī)則后，對(duì)這種類型的關(guān)聯(lián)規(guī)則進(jìn)行篩選，本文僅保留有效的關(guān)聯(lián)規(guī)則，用于調(diào)整測(cè)試用例執(zhí)行次序。最終得到關(guān)聯(lián)規(guī)則集合如R=｛t1→（t2，t3），t21→（t12），…，ti→（ti1，ti2，…，tik）｝。

2.3 多目標(biāo)排序和動(dòng)態(tài)調(diào)整執(zhí)行次序

Epitropakis 等［18］通過(guò)對(duì)比使用多目標(biāo)優(yōu)化算法和其他方法的排序效果，證明了使用多目標(biāo)優(yōu)化算法解決測(cè)試用例排序問(wèn)題的有效性。多目標(biāo)優(yōu)化問(wèn)題是求出使各個(gè)目標(biāo)盡可能最優(yōu)的解，這種解通常是一組Pareto 最優(yōu)解。多目標(biāo)優(yōu)化［19］問(wèn)題的表達(dá)式如式（4）所示：

其中：x=(x1，x2，…，xh) ∈Ω是h維決策變量，Ω是決策空間，表示每一維決策向量的上下界；e是子目標(biāo)數(shù)；f1(x)至fe(x)是各個(gè)子目標(biāo)優(yōu)化函數(shù)。

本文采用帶精英策略的非支配排序遺傳算法NSGA-Ⅱ［20］在每個(gè)類簇內(nèi)進(jìn)行多目標(biāo)排序。該算法具有運(yùn)行速度快、解集收斂性好的優(yōu)點(diǎn)，目前在多目標(biāo)測(cè)試用例優(yōu)先級(jí)排序領(lǐng)域中應(yīng)用較為廣泛。首先在每個(gè)類簇內(nèi)進(jìn)行多目標(biāo)排序，得到，TS_ci表示類簇ci的排序序列；然后依次從每個(gè)排序序列中抽取測(cè)試用例，生成最終的排序序列TS。

本文中使用的優(yōu)化子目標(biāo)分別為代碼覆蓋率最大化、歷史執(zhí)行失敗率最大化以及執(zhí)行時(shí)間最小化，在迭代過(guò)程中，越滿足這三個(gè)目標(biāo)的個(gè)體，越容易被保留下來(lái)。

代碼覆蓋率最大化的函數(shù)表達(dá)式如式（5）所示：

其中：SCti表示測(cè)試用例ti的語(yǔ)句覆蓋數(shù)量；h代表排序測(cè)試用例集的數(shù)量；i代表測(cè)試用例在排序序列中位置；ssc為測(cè)試用例集中所有測(cè)試用例語(yǔ)句覆蓋數(shù)量的和。

歷史執(zhí)行失敗率最大化的函數(shù)表達(dá)式如式（6）所示：

其中：FRti表示測(cè)試用例ti的歷史執(zhí)行失敗率；sfr為測(cè)試用例集中所有測(cè)試用例FR值的和；其余參數(shù)含義同式（5）中參數(shù)一致。

執(zhí)行時(shí)間最小化的函數(shù)表達(dá)式如式（7）所示，

其中：TIMEti表示測(cè)試用例ti的執(zhí)行時(shí)間；st表示執(zhí)行時(shí)間總和；其余參數(shù)含義同式（5）中參數(shù)一致。

生成最終排序序列的過(guò)程為：循環(huán)遍歷每個(gè)類簇內(nèi)的排序序列TS_ci，對(duì)于第j輪遍歷，若TS_ci的長(zhǎng)度大于等于j，則抽取第j個(gè)測(cè)試用例添加到TS的末尾；否則，跳過(guò)TS_ci，直至遍歷完所有的測(cè)試用例，得到最終的排序序列TS={t1，t2，…，tn}。最終的排序序列靠前部分既保留了多樣性，又保留了每一類中最有可能發(fā)現(xiàn)缺陷的測(cè)試用例，增大了快速發(fā)現(xiàn)不同缺陷的機(jī)會(huì)。

為了提升執(zhí)行序列的缺陷檢測(cè)速度，當(dāng)測(cè)試用例執(zhí)行時(shí)，根據(jù)測(cè)試用例間的執(zhí)行失敗關(guān)聯(lián)規(guī)則動(dòng)態(tài)調(diào)整測(cè)試用例執(zhí)行次序，讓更可能檢測(cè)到缺陷的測(cè)試用例優(yōu)先執(zhí)行。

使用關(guān)聯(lián)規(guī)則動(dòng)態(tài)調(diào)整測(cè)試用例排序次序的主要流程為：在按排序序列TS執(zhí)行過(guò)程中，若當(dāng)前測(cè)試用例ti執(zhí)行失敗且有關(guān)聯(lián)規(guī)則ti→（ti1，ti2，…，tik），則立即執(zhí)行ti1，ti2，…，tik中尚未執(zhí)行的測(cè)試用例，然后再依次執(zhí)行TS序列中剩余測(cè)試用例，直至達(dá)到終止條件或測(cè)試用例全部執(zhí)行完畢。以哈希表的形式存儲(chǔ)測(cè)試用例和關(guān)聯(lián)規(guī)則，其中每個(gè)測(cè)試用例僅被執(zhí)行1 次，時(shí)間復(fù)雜度為O（n），n為測(cè)試用例總數(shù)；獲取k個(gè)相關(guān)聯(lián)的測(cè)試用例的時(shí)間復(fù)雜度為O（k），總時(shí)間復(fù)雜度為O（nk）；需要存儲(chǔ)的變量有排序序列、關(guān)聯(lián)規(guī)則和根據(jù)關(guān)聯(lián)規(guī)則調(diào)整的測(cè)試用例，因此空間復(fù)雜度是O（n）。動(dòng)態(tài)調(diào)整過(guò)程如算法1 所示。

3 實(shí)驗(yàn)與結(jié)果分析

3.1 實(shí)驗(yàn)對(duì)象

SIR（Software-artifact Infrastructure Repository）庫(kù)［21］是 一個(gè)廣泛應(yīng)用于回歸測(cè)試用例集優(yōu)化研究的開(kāi)源數(shù)據(jù)庫(kù)。本文從SIR 庫(kù)和GitHub 共獲取5 個(gè)Java 開(kāi)源項(xiàng)目作為實(shí)驗(yàn)對(duì)象。表1 介紹了實(shí)驗(yàn)的項(xiàng)目信息，其中：“新版本缺陷數(shù)”代表每個(gè)項(xiàng)目最新版本所包含的缺陷數(shù)；“歷史缺陷數(shù)”代表項(xiàng)目在歷史版本中所揭示缺陷的總數(shù)；“歷史版本數(shù)”也為“歷史執(zhí)行記錄數(shù)”，是將測(cè)試用例在每個(gè)歷史版本上的執(zhí)行結(jié)果作為一次執(zhí)行記錄。獲取自SIR 庫(kù)的ant、derby 和jboss 項(xiàng)目歷史版本數(shù)相對(duì)較少，因此將缺陷數(shù)較多的版本劃分為多個(gè)版本，以增加歷史版本數(shù)。

表1 實(shí)驗(yàn)項(xiàng)目信息Tab.1 Information of experimental projects

3.2 評(píng)估指標(biāo)

評(píng)價(jià)指標(biāo)選擇平均故障檢測(cè)率（APFD）和基于成本的平均故障檢測(cè)率（APFD cost-cognizant，APFDc）。APFD 是指測(cè)試套件在執(zhí)行過(guò)程中檢測(cè)到缺陷的百分比，該評(píng)價(jià)指標(biāo)被廣泛地應(yīng)用于評(píng)估測(cè)試用例排序技術(shù)，計(jì)算方法如式（8）所示：

其中：TFi表示首次揭示第i個(gè)缺陷的測(cè)試用例在排序序列中的位置；m為缺陷的總個(gè)數(shù)；n代表測(cè)試用例數(shù)量。檢測(cè)到不同缺陷的測(cè)試用例越排在前面，APFD 值越大，說(shuō)明排序序列的揭錯(cuò)速度越快，對(duì)應(yīng)的排序方法效果也越好。

APFDc 增加了對(duì)測(cè)試用例成本和缺陷嚴(yán)重程度的度量。文獻(xiàn)［18，22］對(duì)傳統(tǒng)的APFDc 進(jìn)行簡(jiǎn)化，僅考慮測(cè)試用例執(zhí)行時(shí)間，將缺陷嚴(yán)重程度都視為1。本文采用簡(jiǎn)化后的APFDc 指標(biāo)，其計(jì)算公式如式（9）所示：

其中：m、n、TFi表達(dá)的含義與式（8）中一致；TIMEj代表執(zhí)行第j個(gè)測(cè)試用例所花費(fèi)時(shí)間。與APFD 值一樣，APFDc 值越大，對(duì)應(yīng)排序方法效果越好。

3.3 實(shí)驗(yàn)設(shè)計(jì)

首先使用層次聚類算法對(duì)測(cè)試用例集聚類，經(jīng)實(shí)驗(yàn)驗(yàn)證，α值為0.7 時(shí)效果最好；使用Aprior 算法挖掘關(guān)聯(lián)規(guī)則，設(shè)置最小置信度minconf為0.8；由于不同項(xiàng)目具有的歷史執(zhí)行記錄數(shù)不同，對(duì)應(yīng)的項(xiàng)集頻繁程度不同，設(shè)置最小支持度minsup的取值范圍為0.1～0.5。然后使用NSGA-Ⅱ在每個(gè)類簇內(nèi)對(duì)測(cè)試用例排序，再生成最終的排序序列。最后動(dòng)態(tài)調(diào)整測(cè)試用例執(zhí)行次序，直至所有測(cè)試用例執(zhí)行完畢或達(dá)到終止條件。統(tǒng)計(jì)執(zhí)行結(jié)果的APFD 值和APFDc 值。

為驗(yàn)證本文方法的有效性，在5 個(gè)Java 項(xiàng)目上將本文方法與下述幾種方法的排序結(jié)果進(jìn)行對(duì)比。

1）隨機(jī)排序方法。將測(cè)試用例集以隨機(jī)順序執(zhí)行，并統(tǒng)計(jì)執(zhí)行結(jié)果的APFD 值和APFDc 值；由于該方法存在隨機(jī)性因素，因此記錄30 次執(zhí)行結(jié)果進(jìn)行比較。

2）文獻(xiàn)［9］方法。執(zhí)行Carlson 等［9］提出的基于聚類的排序方法，并統(tǒng)計(jì)執(zhí)行結(jié)果的APFD 值和APFDc 值；由于該方法不存在隨機(jī)性因素，該方法僅需執(zhí)行一次。

3）文獻(xiàn)［10］方法。執(zhí)行Thomas 等［10］提出的基于主題模型的排序方法，并統(tǒng)計(jì)執(zhí)行結(jié)果的APFD 和APFDc 值；由于使用LDA 模型推導(dǎo)測(cè)試用例主題分布時(shí)，使用了隨機(jī)數(shù)種子，因此記錄該方法30 次執(zhí)行結(jié)果進(jìn)行比較。

4）文獻(xiàn)［11］方法。執(zhí)行Pradhan 等［11］提出的基于關(guān)聯(lián)規(guī)則和多目標(biāo)優(yōu)化的排序方法，并統(tǒng)計(jì)執(zhí)行結(jié)果的APFD 和APFDc 值；由于多目標(biāo)遺傳算法具有隨機(jī)性，因此記錄該方法的30 次執(zhí)行結(jié)果進(jìn)行比較。

3.4 實(shí)驗(yàn)結(jié)果與分析

本文方法綜合利用了測(cè)試用例的靜態(tài)信息和動(dòng)態(tài)信息?；跍y(cè)試用例靜態(tài)信息的處理主要包括計(jì)算測(cè)試用例文本主題和代碼覆蓋相似性、層次聚類與多目標(biāo)排序，在測(cè)試用例本身未改變前，上述過(guò)程的結(jié)果可以重復(fù)使用?；趧?dòng)態(tài)信息的處理主要包括關(guān)聯(lián)規(guī)則挖掘與動(dòng)態(tài)調(diào)整執(zhí)行次序兩個(gè)過(guò)程，其中動(dòng)態(tài)調(diào)整執(zhí)行次序到的時(shí)間復(fù)雜度為O（nk）。

3.4.1 APFD結(jié)果

表2 展示了在5 個(gè)項(xiàng)目上分別使用5 種排序方法所得到的平均APFD 值和APFDc 值。

表2 不同項(xiàng)目使用不同排序方法的平均APFD值和APFDc值對(duì)比Tab.2 Comparison of average APFD values and APFDc values of different projects using different prioritization methods

從表2 中可以看出，在大部分項(xiàng)目中，本文方法得到的APFD 值更高。尤其是在ant 項(xiàng)目中，本文方法相較于隨機(jī)方法提升了24.13%，提升明顯；相較于文獻(xiàn)［9］、文獻(xiàn)［10］和文獻(xiàn)［11］方法，分別提升了15.53%、3.78%和10.35%。在derby 項(xiàng)目中，本文方法相較于除隨機(jī)方法外的其他方法優(yōu)勢(shì)不明顯，是因?yàn)樵擁?xiàng)目中部分測(cè)試用例能單獨(dú)檢測(cè)出較多的缺陷，這類測(cè)試用例被排在靠前位置時(shí)，總能導(dǎo)致排序結(jié)果的APFD 值較高。在jboss 項(xiàng)目中，相較于文獻(xiàn)［10］和文獻(xiàn)［11］方法提升不明顯的原因也是如此。在commons-lang項(xiàng)目中，本文方法相較于文獻(xiàn)［11］方法表現(xiàn)差一些，通過(guò)分析項(xiàng)目發(fā)現(xiàn)：該項(xiàng)目的測(cè)試用例間的相似性較差，而本文使用了相似性進(jìn)行聚類，文獻(xiàn)［11］方法未考慮相似性，因此本文方法排序效果更差。相較于對(duì)比方法，本文方法在所有項(xiàng)目上的APFD 平均值更高，分別提高了12.59%、5.98%、3.01%和2.95%。

3.4.2 APFDc值結(jié)果

從表2 中可以看出，在大部分項(xiàng)目中，本文方法得到的APFDc 值更高。與隨機(jī)方法相比，本文方法得到的APFDc 值在各個(gè)項(xiàng)目中都提升明顯，在commons-lang 項(xiàng)目中的提升率最高，達(dá)到27.29%。在derby 項(xiàng)目中，本文方法相較于文獻(xiàn)［10］方法表現(xiàn)得差一些，通過(guò)分析發(fā)現(xiàn)：該項(xiàng)目的測(cè)試用例集中存在執(zhí)行時(shí)間較長(zhǎng)（約為98 s），但在歷史執(zhí)行結(jié)果中多次發(fā)現(xiàn)缺陷的測(cè)試用例；這兩個(gè)性質(zhì)在多目標(biāo)排序階段互相制約，導(dǎo)致本文方法在該項(xiàng)目上的效果比文獻(xiàn)［10］方法的差。相較于文獻(xiàn)［9］、文獻(xiàn)［10］和文獻(xiàn)［11］的方法，本文方法的APFDc 值在joda-time、commons-lang 和derby 項(xiàng)目上的最高提升率分別為14.28%、11.51%和12.76%。相較于對(duì)比方法，本文方法在所有項(xiàng)目上的APFDc 平均值更高，分別提高了17.17%、5.04%、5.08%和8.21%。綜合上述情況，驗(yàn)證了本文方法的有效性。

4 結(jié)語(yǔ)

針對(duì)如何提升回歸測(cè)試效益問(wèn)題，提出了一種綜合利用歷史數(shù)據(jù)和執(zhí)行中信息的測(cè)試用例排序方法。首先利用測(cè)試用例文本信息和歷史執(zhí)行信息，對(duì)測(cè)試用例進(jìn)行聚類和關(guān)聯(lián)規(guī)則挖掘；然后利用多目標(biāo)優(yōu)化算法對(duì)測(cè)試用例排序和調(diào)整；最后在執(zhí)行過(guò)程中，根據(jù)測(cè)試用例的執(zhí)行信息對(duì)序列進(jìn)行進(jìn)一步優(yōu)化。通過(guò)與其他4 個(gè)方法對(duì)比可知，本文方法的APFD 和APFDc 值具有一定的提升。

另一方面，本文所提方法還存在一些不足，未來(lái)可深入進(jìn)行研究，在多目標(biāo)排序階段，合理增加優(yōu)化子目標(biāo)，如在實(shí)際的工業(yè)項(xiàng)目中，還會(huì)考慮需求覆蓋等目標(biāo)，以進(jìn)一步研究加入這些目標(biāo)后的排序效果；本文實(shí)驗(yàn)所用數(shù)據(jù)集的歷史記錄不夠龐大，對(duì)關(guān)聯(lián)規(guī)則的挖掘具有一定的影響，未來(lái)可考慮在具有龐大歷史執(zhí)行記錄的實(shí)際工業(yè)項(xiàng)目中驗(yàn)證本文的方法。