基于改進LDA算法的測試用例優先級排序研究

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

0 引 言

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

1 系統模型

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

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

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

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

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

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

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

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

2 基于改進LDA主題模型的優先級排序算法

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

ELDA算法是基于LDA文檔主題生成模型進行改進，通過學習狄利克雷分布先驗(Dirichlet priori)和標簽之間的權重，ELDA能夠處理半結構化和非結構化文檔。語料庫D={(w1,t1),...,(wM,tM)}中有M個文檔，其中二元組(wi,ti)表示文檔i，wi是文檔i的詞袋集合，ti是文檔i的標簽集合。目的是為語料庫建立一個概率模型，該模型利用標簽信息為相似的文檔賦予極大似然。假設有概率矩陣P={pij}K×V，主題分布矩陣TD={tdij}L×K，狄利克雷分布超參數μ，狄利克雷分布參數π，以及伯努利先驗參數η。L是指標簽的數量，K是指主題的數量。用?d表示文檔d的主題分布，用ξd表示文檔d中標簽的權重向量。提出的改進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()是狄利克雷分布生成函數，Multi()是多項式分布生成函數。λ是標簽的主題分布。接下來，定義Θ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，直到所有測試用例都被確定了優先級。

3 實驗及結果分析

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

表1 測試數據集參數

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

(7)

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

表2 三種算法的對比實驗結果

4 結 語

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