基于改進(jìn)LDA算法的測(cè)試用例優(yōu)先級(jí)排序研究

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

0 引 言

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

1 系統(tǒng)模型

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

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

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

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

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

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

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

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

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

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

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

算法1 改進(jìn)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 //對(duì)于每一個(gè)文檔8: λ～Dir(μ);9: Calculate(Td); //用td生成Td10: εd～Dir(Td×π);11: Calculate(?d); //用εd生成?d12: For wdi in wd do //對(duì)于每一個(gè)單詞13: zdi～Multi(?d);14: wdi～Multi(pzdi);15: End for16:End for

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

(1)

(2)

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

(3)

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

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

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

(4)

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

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

(5)

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

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

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

(6)

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

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

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

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

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

(7)

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

表2 三種算法的對(duì)比實(shí)驗(yàn)結(jié)果

4 結(jié) 語(yǔ)

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