(湖南交通工程學(xué)院電氣與信息工程學(xué)院，湖南 衡陽 421001)

0 引 言

軟件開發(fā)團隊通常會創(chuàng)建大型測試套件來進行軟件測試，由于測試套件非常大，對每個源代碼執(zhí)行測試是不現(xiàn)實的。在這種情況下，開發(fā)人員需要對測試套件進行優(yōu)先級排序，以便更容易發(fā)現(xiàn)未被檢測到的錯誤測試用例。研究人員提出了許多自動化用例優(yōu)先級技術(shù) 。靜態(tài)測試用例優(yōu)先級排序技術(shù)與大多數(shù)現(xiàn)有技術(shù)不一樣，靜態(tài)技術(shù)具有較低的成本、輕量級，適用于許多實際情況。然而，現(xiàn)有的靜態(tài)測試用例優(yōu)先級排序技術(shù)基本不使用測試用例中的元數(shù)據(jù)，如測試用例的語言數(shù)據(jù)。因此提出一種新的靜態(tài)測試用例優(yōu)先級排序算法，使用測試用例的語言數(shù)據(jù)來幫助區(qū)分它們的功能。算法采用基于改進LDA主題模型的文本分析算法，利用語言數(shù)據(jù)創(chuàng)建主題，并對包含不同主題的測試用例進行優(yōu)先級排序。

1 系統(tǒng)模型

測試用例優(yōu)先級排序是指對被測試系統(tǒng)的測試用例集合中的測試用例進行排序，目標(biāo)是最大化測試用例故障檢出率等目標(biāo)。當(dāng)測試用例集合的執(zhí)行被中斷或停止時，則優(yōu)先級更高的測試用例就會被執(zhí)行。給定測試用例集合T，T的排序集合PT，評估函數(shù)f，測試用例優(yōu)先級排序的目的是對于所有的T′′∈PT，找到T′∈PT，使f(T′)≥f(T′′)。PT是關(guān)于T的所有可能優(yōu)先級集合，f是決定給定優(yōu)先級性能的評估函數(shù)。性能的定義可能會有所不同，這是因為開發(fā)人員在不同的時間會有不同的目標(biāo)。開發(fā)人員可能首先希望找到盡可能多的錯誤，然后實現(xiàn)最大的代碼覆蓋率。一般來說，實現(xiàn)最優(yōu)優(yōu)先級排序[1]的主要步驟如下：

1)將每個測試用例編碼為它所涵蓋的內(nèi)容。例如，編碼后的測試用例可能是測試用例覆蓋的程序語句。

2)使用距離最大化算法對測試用例進行優(yōu)先級排序，以最大化覆蓋率或多樣性為目的

1.最大化覆蓋率。對測試用例進行優(yōu)先級排序，從而最大化所覆蓋元素的數(shù)量，以測試盡可能多的測試用例，增加故障檢測的機會。

2.最大化多樣性。首先計算測試用例之間的相似度；然后通過最大化它們之間的不相似性來區(qū)分測試用例。相似度高的測試用例可能會檢測到相同的錯誤，因此只需要執(zhí)行一個測試用例。

黑盒靜態(tài)優(yōu)先級排序使基于測試用例的源代碼的優(yōu)先級排序。測試用例是基于其源代碼的某些方面進行編碼的，不需要執(zhí)行信息、規(guī)范模型，只需要測試用例的源代碼。此研究提出了一種新的黑盒靜態(tài)測試用例優(yōu)先級排序算法，利用了測試腳本中的元數(shù)據(jù)，即標(biāo)識符、注釋和字符串文字。然后將基于主題模型的文本分析算法應(yīng)用到測試用例語言數(shù)據(jù)中，將測試用例抽象為主題，并計算測試用例對之間的相似性。主題模型算法能夠從語言數(shù)據(jù)中發(fā)現(xiàn)的主題，該主題能夠很好地表征源代碼中的潛在功能。當(dāng)兩個測試用例包含相同的主題時，測試用例在功能上是相似的，并能檢測到相同的錯誤。所提出算法的處理流程如圖1所示。

圖1 基于改進LDA主題模型的測試用例優(yōu)先級排序算法流程

對測試用例集合進行預(yù)處理以提取其語言數(shù)據(jù)，包括了測試用例的標(biāo)識符、注釋和字符串文字。將主題模型應(yīng)用到預(yù)處理后的測試用例集合，為每個原始測試用例生成一個主題向量，主題向量描述了測試用例被分配到每個主題的概率。根據(jù)主題向量計算測試用例之間的距離。最后使用距離最大化算法將測試用例的平均距離最大化。

2 基于改進LDA主題模型的優(yōu)先級排序算法

提出一種改進的LDA(Enhanced Latent Dirichlet Allocation，ELDA)主題模型來表示文本數(shù)據(jù)和各種標(biāo)記。在應(yīng)用基于主題的測試用例優(yōu)先級排序算法之前，需要對測試用例的文本進行預(yù)處理。刪除測試用例中的特殊字符(如，&、！、+)、數(shù)字和編程語言的關(guān)鍵字，只留下標(biāo)識符名稱、注釋和字符串文字。接下來，根據(jù)駝峰式命名法和下劃線命名方案對標(biāo)識符名進行拆分，例如將標(biāo)識符“testCase”拆分為“test”和“Case”。然后把每個單詞表示成簡化形式。例如，將兩個單詞“tests”和“testing”表示為“test”。最后，去掉常見的停止詞以減少測試用例詞匯表的大小，從而在更干凈的數(shù)據(jù)集上進行操作。

ELDA算法是基于LDA文檔主題生成模型進行改進，通過學(xué)習(xí)狄利克雷分布先驗(Dirichlet priori)和標(biāo)簽之間的權(quán)重，ELDA能夠處理半結(jié)構(gòu)化和非結(jié)構(gòu)化文檔。語料庫D={(w1,t1),...,(wM,tM)}中有M個文檔，其中二元組(wi,ti)表示文檔i，wi是文檔i的詞袋集合，ti是文檔i的標(biāo)簽集合。目的是為語料庫建立一個概率模型，該模型利用標(biāo)簽信息為相似的文檔賦予極大似然。假設(shè)有概率矩陣P={pij}K×V，主題分布矩陣TD={tdij}L×K，狄利克雷分布超參數(shù)μ，狄利克雷分布參數(shù)π，以及伯努利先驗參數(shù)η。L是指標(biāo)簽的數(shù)量，K是指主題的數(shù)量。用?d表示文檔d的主題分布，用ξd表示文檔d中標(biāo)簽的權(quán)重向量。提出的改進LDA(ELDA)算法如下所示。

算法1 改進LDA(ELDA)1: For k in K do //初始化概率矩陣2: pk～Dir(β);3: End for4: For t in T do //初始化主題分布矩陣5: tdt～Dir(α);6: End for7: For d in D do //對于每一個文檔8: λ～Dir(μ);9: Calculate(Td); //用td生成Td10: εd～Dir(Td×π);11: Calculate(?d); //用εd生成?d12: For wdi in wd do //對于每一個單詞13: zdi～Multi(?d);14: wdi～Multi(pzdi);15: End for16:End for

算法1中，Dir()是狄利克雷分布生成函數(shù)，Multi()是多項式分布生成函數(shù)。λ是標(biāo)簽的主題分布。接下來，定義Θd如下，

(1)

(2)

p(εd,z|wd,Td,TD,P,η,π,μ)=

(3)

對公式(3)進行變形，能夠得到文檔d的邊緣分布。為了提高計算邊緣分布的效率，采用了基于平均場理論的變分期望最大化算法，Jensen不等式，得到邊緣最大似然的計算公式如下

L=E[logp(T|η)]+E[logp(εd|Td×π)]+

E[logq(εd)]-E[logq(λ)]-E[logq(z)]

(4)

其中，q是如下所示的全分解分布

q(εd,λd,z|ξ,ρ,γ)=

(5)

使用曼哈頓距離作為距離的度量，而對于距離最大化算法，使用一個改進版的貪心算法(Elbaum et al. 2002)。首先利用公式(6)計算每兩個測試用例之間的距離。

PairDis(tci,PS,Dis(tci.tcj))=

min{Dis(tci.tcj)|tcj∈PS,j≠i}

(6)

然后，對于距離較大的測試用例，將其中一個測試用例加入已排序集合PS。接下來，對于每一個測試用例，以迭代的方式將距離大的測試用例加入集合PS，直到所有測試用例都被確定了優(yōu)先級。

3 實驗及結(jié)果分析

為了驗證ELDA算法的有效性，將本文提出的基于主題的算法與基于圖形技術(shù)[2]、基于字符串的算法進行對比。從軟件基礎(chǔ)設(shè)施庫(SIR)[3]中獲得實驗所需的三個測試數(shù)據(jù)集，每個數(shù)據(jù)集包括了故障注入的源代碼、測試用例和故障矩陣，數(shù)據(jù)集的詳細參數(shù)如表1所示。

表1 測試數(shù)據(jù)集參數(shù)

利用表1的數(shù)據(jù)集來考察三種算法在平均故障檢測率的性能差異，實驗結(jié)果如表2所示。平均故障檢測率是指優(yōu)先級測試套件所檢測到的故障百分比的平均值，計算方式如公式(7)所示。

(7)

其中，n是測試用例的數(shù)量，m是故障的數(shù)量，fi是在檢測到故障i之前必須執(zhí)行的測試數(shù)量。當(dāng)測試用例優(yōu)先級技術(shù)的有效性增加時(即使用更少的測試用例以檢測出更多的故障)，平均故障檢測率AverF就會接近100。由表2可知，該算法ELDA具有最高的平均故障檢測率。

表2 三種算法的對比實驗結(jié)果

4 結(jié) 語

針對靜態(tài)黑盒測試用例優(yōu)先級排序問題，提出了一種新的基于改進LDA算法的黑盒靜態(tài)用例優(yōu)先級排序算法，使用改進后的LDA主題模型算法將每個測試用例抽象為更高層次的主題。未來使用不同的距離度量以及采用基于進化算法的距離最大化算法來進一步優(yōu)化基于主題的算法，并且將擴展案例研究以進一步驗證算法的性能。