樸素貝葉斯應用于自動化測試用例生成

李欣 張聰 羅憲

（重慶交通大學，重慶 400074）

樸素貝葉斯應用于自動化測試用例生成

李欣 張聰 羅憲

（重慶交通大學，重慶 400074）

提出使用樸素貝葉斯作為核心算法來產生自動化測試用例的方法，將分類的思想引入到自動化測試用例的生成中。通過實驗驗證此生成測試用例方法的可行性。

樸素貝葉斯；自動化測試；測試用例生成

在軟件測試過程中，測試用例的設計和生成是軟件測試的重點和難點。根據統計，軟件測試用例設計的開銷約占整個軟件測試開銷的40%。傳統的軟件測試方法——手工測試存在測試用例集合龐大、成本高等缺點。為了解決這些問題，測試趨勢整體朝著自動化發展，而軟件測試用例的自動化生成是軟件測試自動化的關鍵技術。本文將分類的思想引入到自動化測試用例的生成中,利用樸素貝葉斯［1］的策略來對隨機生成的測試用例進行分類得到最后的有效測試用例。

1 測試用例的自動生成技術

測試用例自動生成［2］是軟件測試自動化的關鍵技術之一，目的在于減少測試人員手工生成測試用例的工作量，降低測試成本，提高測試效率。目前，軟件測試用例自動生成技術一般可以分為面向功能的測試用例自動生成技術和面向路徑的測試用例自動生成技術兩大類。本文提出的自動化測試用例生成算法將應用于面向路徑的測試用例技術。

2 樸素貝葉斯算法

貝葉斯推理提供了用于推理的一種概率手段。它基于待考查的量遵循某概率分布，且可根據這些概率以及觀察到的數據進行推理，以作出最優的分類。而貝葉斯學習方法中實用性很高的一種為樸素貝葉斯學習器，常被稱為樸素貝葉斯分類器。

將樸素貝葉斯分類器［3］應用到任務中，每個實例x是由屬性值的合取描述，而目標函數f(x)從某有限集合V中取值。學習器被提供一系列關于目標函數的訓練樣例以及新實例，然后對新實例分類。

貝葉斯方法的新實例分類目標是在給定描述實例的屬性值＜a1，a2，…，an＞下，得到最可能的目標值 vMAP。

可使用貝葉斯公式將表達式改寫為：

由式（1）、（2）可知，估計每個 P(vj)很容易，只要計算每個目標值vj出現在訓練數據中的頻率就可以。但除非有一個非常大的訓練集合，否則用這種方法估計不同的 P(a1，a2，…，an|vj)項不太可行。然而，樸素貝葉斯分類器基于一個簡單的假設：在給定目標值時屬性之間相互條件獨立。因而可以將上式轉換為：

其中，vNB表示樸素貝葉斯分類器輸出的目標值。

3 基于樸素貝葉斯的路徑測試用例生成設計

在應用樸素貝葉斯分類器時的兩個主要問題是，首先要決定怎樣將任意一組測試用例表示為屬性值的形式，其次要決定如何估計樸素貝葉斯分類器所需的概率。這里表示任意測試用例的形式特別簡單，給定一個測試用例，可以把每個參數定義為一個屬性。而對測試用例的分類可以分為cover和uncover這兩大類。

本文使用判斷三角形類別的程序［4］作為被測程序，進行路徑測試數據生成的算法設計。此程序將3個整數作為輸入，判斷這3個整數能否構成一個三角形。若能，則輸出等腰三角形、等邊三角形和普通三角形；若不能，則輸出非三角形。由于該程序包含清晰的邏輯，而且即使將一個較大范圍的整數作為輸入，也只有少量的輸入組合能滿足代碼的某些特定分支，因而有利于對于自動生成算法的分析。由python編寫的被測程序如下：程序流程如圖1所示：

圖1 被測程序的流程圖

程序共有4條路徑：路徑1得到等邊三角形，路徑2得到等腰三角形，路徑3得到普通三角形，路徑4得到非三角形。路徑1和路徑2是2條最長的路徑，均要執行3個嵌套的IF語句分支，且若用隨機法產生測試用例，路徑2和路徑1的執行概率比其他2條更低。因此，為更好地突出樸素貝葉斯算法的效果，本文選擇其中的路徑1作為示例測試路徑，其他路徑的測試工作就不再重述。

實驗中，人為創建數目為80的數據樣本作為已分類的測試用例集合。并隨機創建基于圖1的新的待分類的數目為100的預測測試用例集合，并對其中一個進行分類作為例子。若從預測數據集合中讀出如下數據（4，4，2），其中 4、4 和 2 分別對應于參數a、b 和 c。

樸素貝葉斯分類算法［5］的步驟如下：

首先分別計算訓練數據中符合路徑覆蓋和不符合路徑覆蓋的類型所占的比例。由于80個訓練集合中符合的數據數目為50，不符合的數目為30。因此有：

其次，對于要被預測的測試用例，分別計算每個屬性在訓練集合中的條件概率：

然后，使用這些概率估計以及對剩余屬性的相似估計，可按照式（3）計算vNB如下：

基于從訓練數據中學習到的概率估計，樸素貝葉斯分類器將此實例賦以目標值uncover。進一步地，通過將上述量化歸一，可計算出給定觀察值下的目標值為uncover的條件概率。對于此例，概率為：

4 結 語

測試用例的自動生成是實現軟件測試自動化的基本前提，因此，如何自動生成測試用例就成為解決自動化測試問題的關鍵。本文以實現自動化測試為目標，引入了樸素貝葉斯對產生的隨機測試用例分類這一思想，通過實驗論證這種方法是可行的。

[1]Tom M Mitchell.機器學習[M].曾華軍,張銀奎，譯.北京：機械工業出版社，2003.

[2]陳雨.基于遺傳算法的測試用例生成[D].上海：東華大學,2009.

[3]Stuart J.Russell,Peter Norving,et al.人工智能——一種現代的方法：第二版[M].北京：清華大學出版社，2006.

[4]梅爾斯.軟件測試的藝術：第二版本[M].王峰,陳杰譯.北京：機械工業出版社，2006.

[5]西格蘭.集體智慧編程[M].南京：東南大學出版社，2009.

Naive Bayesian Applied in Automatic Test Cases Generation

LI Xin ZHANG Cong LUO Xian
(Chongqing Jiaotong University,Chongqing 400074)

Automatic testing cases are generated by Bayesian methods as the core algorithm.And the thoughts of classification is introduced in test case generate.The results shows the method presented in this paper is an feasible method to generate test cases.

Bayesian;automatic testing;test case generate

TP311

A

1673-1980（2012）02-0150-03

2011-11-29

重慶科技攻關項目(CSTC,2010AC2077)

李欣(1984-)，男，湖北襄樊人，重慶交通大學在讀碩士研究生，研究方向為軟件工程。