基于負(fù)選擇算法的自動路徑測試*

張 華 陸 玉

(阜陽職業(yè)技術(shù)學(xué)院 安徽阜陽 236031)

軟件測試是軟件開發(fā)中不可避免的一個環(huán)節(jié)，是一個發(fā)現(xiàn)錯誤的過程[1]。軟件測試可以自動或手動進(jìn)行，是一個冗長而繁瑣的過程，其所耗時間和資源一般占軟件開發(fā)總成本的50%以上。軟件測試最關(guān)鍵的一步是生成案例程序的測試數(shù)據(jù)。手工測試是一個冗長乏味的耗時過程，為滿足測試的充分性標(biāo)準(zhǔn)，可以使用自動化的方式改進(jìn)。這個過程被稱為自動測試數(shù)據(jù)生成程序(automatic test data generation，ATDG)。

在結(jié)構(gòu)測試中，測試數(shù)據(jù)的生成意味著搜索測試數(shù)據(jù)以執(zhí)行所測試程序的內(nèi)部結(jié)構(gòu)，以滿足選定的測試標(biāo)準(zhǔn)。有3種主要類型的結(jié)構(gòu)覆蓋準(zhǔn)則：語句覆蓋(即每個語句在程序中被執(zhí)行至少一次)，分支覆蓋(即每一個邏輯分支在程序中執(zhí)行至少一次)，和路徑覆蓋(即每個不同路徑在程序中都至少可以被執(zhí)行一次)，文章將重點討論路徑覆蓋。

路徑測試是一種結(jié)構(gòu)測試方法，主要的困難之一是如何生成一個有效的測試數(shù)據(jù)，在短時間內(nèi)遍歷程序的所有路徑。為盡可能達(dá)到這一目的，路徑測試方法涉及選擇執(zhí)行和查找測試數(shù)據(jù)以覆蓋它的路徑子集。研究人員亦已經(jīng)提出了幾種路徑測試自動生成測試數(shù)據(jù)，比如使用隨機、動態(tài)等方法，但這些方法不足以產(chǎn)生足夠且合適的測試數(shù)據(jù)。

基于此，文章介紹了使用負(fù)選擇算法(negative selection algorithm，NSA)進(jìn)行路徑測試自動生成數(shù)據(jù)的一種方法，這在人工免疫系統(tǒng)中最重要的算法，可以在確保目標(biāo)路徑的完整覆蓋的前提下減少人工工作。

1研究動機和準(zhǔn)備工作

路徑覆蓋的主要任務(wù)是產(chǎn)生有效的測試數(shù)據(jù)，通過程序遍歷所有的邏輯路徑。為模擬軟件程序的執(zhí)行路徑，在測試之前需建立相關(guān)的控制流圖(control flow graph，CFG)[2]。在程序中n種決策會有2n種可能的路徑，即圈復(fù)雜度(cyclomatic complexity，CC)[3]，而程序中循環(huán)的存在會增加路徑的數(shù)目，即每個不同數(shù)量的循環(huán)的迭代是一個不同的路徑。手動測試因成本太高基本不可能實現(xiàn)，而即使是自動化測試生成工具也可能很難生成測試數(shù)據(jù)以獲得完整的路徑覆蓋率，尤其是當(dāng)程序包含嵌套循環(huán)時，故對于任何合理大小的程序，窮舉方式不可行。 同樣隨機方法可靠性也不高，動態(tài)測試數(shù)據(jù)生成技術(shù)效率低耗時長，往往容易陷入輸入數(shù)據(jù)域空間的局部最優(yōu)狀態(tài)。

為解決這些問題，很多科研者開始考慮使用基于啟發(fā)式框架的算法作為生成測試數(shù)據(jù)的更好的替代方案，如遺傳算法(GA)[4]、粒子群算法(PSO)[5]等。在上述方案中，遺傳算法是在該領(lǐng)域最常用的啟發(fā)式技術(shù)，可以提供穩(wěn)定的結(jié)果并且有利于全局擇優(yōu)。大量研究結(jié)果表明，遺傳算法比隨機檢驗更有效、更有效，且其試驗數(shù)據(jù)的質(zhì)量也高于隨機試驗。PSO算法被廣泛應(yīng)用于各種優(yōu)化問題中，具有收斂快、精度高等優(yōu)點。然而，它受到了早產(chǎn)的影響，從而降低了測試用例生成的效率。

在以上方案的基礎(chǔ)上仍需進(jìn)一步提高過程的效率和有效性，故在此評估NSA對隨機測試的有效性。文章希望NSA能自動生成一個更有效的測試數(shù)據(jù)來在更短的時間內(nèi)遍歷所有的程序路徑。

2算法原理

路徑測試是結(jié)構(gòu)化測試的主要策略，解決路徑測試的基本方法是在測試程序中找到可能覆蓋路徑的指定輸入數(shù)據(jù)。為確保路徑覆蓋的完善度，文章希望使用一種自動生成測試數(shù)據(jù)的算法，該算法是通過定義一組根據(jù)數(shù)據(jù)集生成的自采樣，然后生成檢測器作為 NSA的主要組件之一來實現(xiàn)的。在此過程中首先隨機生成檢測器的候選種群，然后在迭代過程中將其訓(xùn)練成熟。

實驗中需使用到漢明距離(hamming distance)[6]來定義檢測器之間的距離。該算法以最大距離選擇檢測器，覆蓋所有迭代域，直到滿足停止準(zhǔn)則算法結(jié)束。這里的停止條件是測試數(shù)據(jù)的最大數(shù)量。該算法的步驟如下：

輸入：正在測試的程序

輸出：測試數(shù)據(jù)集

步驟1：輸入測試源代碼下的程序；

步驟2：從程序源代碼中構(gòu)建CFG；

步驟3：計算CC的取值，見式(1)：

CC=P+1

(1)

其中P是謂詞節(jié)點的數(shù)量，其中節(jié)點在CFG中有多個相鄰節(jié)點。此值決定必須覆蓋的獨立路徑的數(shù)量。

步驟4：隨機生成初始的待選檢測器(這些檢測器代表測試路徑數(shù)據(jù)集，即為CC的取值)；

步驟5：重復(fù)；

步驟6：生成新的測試用例；

步驟7：計算檢測器之間的漢明距離D，見式(2)：

(2)

A和B是任意兩個檢測器。

步驟8：選擇具有最大適應(yīng)值的新一代檢測器；

步驟9：繼續(xù)執(zhí)行，直到滿足了停止條件或超過了最大代數(shù)。

3實驗結(jié)果分析

文章選擇了基準(zhǔn)測試程序中的三角形分類器作為案例，使用 NSA算法與隨機算法分別進(jìn)行路徑測試，并比較結(jié)果。

這個程序的機制是通過輸入一組三邊數(shù)據(jù)，使用分類器來確定它是不是一個三角形，或者進(jìn)一步確認(rèn)其三角形的類型。這個程序之所以被普遍使用，是因為即使使用了大量的整數(shù)，也只有少數(shù)組合滿足代碼中的特定分支。例如，使用范圍從1-10的三邊數(shù)值中只有12個組合可能是不等邊三角形。另外，隨機搜索最困難的路徑是等邊三角形路徑，因為它必須找到三個相等的整數(shù)值。這使得三角程序成為軟件測試和測試數(shù)據(jù)生成研究的極好的試驗平臺。

圖1給出了程序的源代碼和CFG的相應(yīng)構(gòu)造。CC值為4，這是謂詞節(jié)點加上1的數(shù)量(謂詞節(jié)點是CFG中有多個相鄰節(jié)點的節(jié)點)。CC的值標(biāo)識出程序獨立路徑的個數(shù)。

圖1 三角分類器執(zhí)行源代碼及其相關(guān)控制流圖

為簡單起見將輸入域作為1-10考慮3個整參數(shù)來對三角形進(jìn)行分類(x，y，z)，用于覆蓋程序路徑的測試數(shù)據(jù)見表1。

實驗中使用了1 000個測試數(shù)據(jù)來對比隨機算法和NSA。結(jié)果表明，由于NAS可以將測試數(shù)據(jù)提前生成所需的路徑，故其生成的測試數(shù)據(jù)質(zhì)量優(yōu)于隨機算法。實驗中選擇十代數(shù)據(jù)，表2顯示了當(dāng)按圖1所示進(jìn)行兩種算法測試時的各代測試數(shù)據(jù)路徑數(shù)以及測試執(zhí)行時間情況。

表1 生成的測試數(shù)據(jù)樣本

表2 隨機算法測試時各代測試數(shù)據(jù)路徑數(shù)及執(zhí)行時間

表3顯示了圖1中的測試數(shù)據(jù)路徑數(shù)以及使用NSA算法的測試時間執(zhí)行情況。

表3 NSA方式一代至十代測試數(shù)據(jù)路徑數(shù)及執(zhí)行時間

從表1和表2可發(fā)現(xiàn)，從分類三角形問題的1 000個測試數(shù)據(jù)中，已經(jīng)生成了2個測試數(shù)據(jù)用于用該算法從第一代遍歷等邊路徑。值得注意的是，隨機測試時沒有機會生成相同路徑的測試數(shù)據(jù)，只在第六代中有一次機會遍歷測試數(shù)據(jù)，如圖4所示。

圖4 使用NSA和隨機算法覆蓋路徑的平均值比對

由圖4可以看出，NSA在生成測試數(shù)據(jù)中比隨機算法更能成功地覆蓋所有路徑，尤其是最困難的等邊路徑，比如NSA過程中遍歷了3次而隨機算法只有0.1次。與此同時，NSA比隨機算法減少了67%的耗時，如表3所示。

為完善實驗評估結(jié)果，文章加入了遺傳算法的測試數(shù)據(jù)進(jìn)行比對。圖5顯示了當(dāng)同時遍歷等邊數(shù)據(jù)路徑時，隨機算法、NSA和遺傳算法的執(zhí)行數(shù)據(jù)結(jié)果?？梢?，使用NSA算法時等邊數(shù)據(jù)的路徑覆蓋程度更加完善。

圖5 3種算法在等邊數(shù)值路徑遍歷中的比對

5結(jié)論

文章以三角形分類基準(zhǔn)程序為例，使用負(fù)選擇算法(NSA)進(jìn)行了數(shù)據(jù)自動生成的路徑覆蓋率測試，結(jié)果表明該算法能夠以較少的時間將搜索移動到所需的搜索范圍，比隨機生成算法更有效、更經(jīng)濟。為了完善評價結(jié)果，將此算法與遺傳算法進(jìn)行了比較，結(jié)果表明該方法確實能夠提高測試數(shù)據(jù)的質(zhì)量。在以后的研究中，該算法將在實驗中使用更多的基準(zhǔn)程序和不同的數(shù)據(jù)類型，以進(jìn)一步評估算法的性能。