基于數(shù)據(jù)挖掘的軟件測試技術(shù)研究

1、基于數(shù)據(jù)挖掘的軟件測試技術(shù)研究摘要 軟件的可靠性對社會(huì)，經(jīng)濟(jì)，國防等都有著巨大的意義，而要提高軟件的可靠性，必須對軟件進(jìn)行大量的測試。但是由于條件的限制，必須在資源耗費(fèi)和測試效果之間達(dá)到平衡。如何以最小的代價(jià)進(jìn)行盡量高效的測試，是一個(gè)值得研究的問題。因此，數(shù)據(jù)挖掘技術(shù)作為一種處理海量數(shù)據(jù)的有效方法被引入到軟件測試中，也產(chǎn)生了許多成果。 軟件測試中有兩個(gè)典型的“數(shù)據(jù)過量”問題：一個(gè)是測試用例的選擇：由于軟件輸入空間十分巨大，將所有這些輸入全部檢驗(yàn)是不現(xiàn)實(shí)的，因此必須用某種方法將輸入空間分成若干“等效的”類，在每個(gè)類中選擇少量元素作為測試用例， 從而減少測試用例的數(shù)量。另一個(gè)是與Bug報(bào)告的分析：

2、由于越來越多的軟件 采用了自動(dòng)報(bào)告Bug的方式以便可以準(zhǔn)確地獲得軟件Bug信息，這種方法對于Bug數(shù)據(jù)的收集是非常有效的，但軟件開發(fā)人員往往無法對過多的Bug數(shù)據(jù)進(jìn)行處理，造成了信息浪費(fèi)。因此必須找到一種自動(dòng)化的方法對這些數(shù)據(jù)進(jìn)行分析。 本文針對以上兩個(gè)問題，介紹和提出了使用數(shù)據(jù)挖掘技術(shù)的解決方案，即： 1縮減測試用例：在復(fù)雜軟件的測試中，其輸入空間幾乎是無限的，因此不可能將全部的測試用例都輸入到待測軟件中執(zhí)行。解決的方法就是通過某種方式選擇其中最有代表性的一部分對待測軟件進(jìn)行測試，稱作測試用例的縮減。數(shù)據(jù)挖掘技術(shù)可以作為縮減測試用例的一種有效方法。 2對Bug報(bào)告的分析：由于許多當(dāng)代的軟件可

3、以自動(dòng)監(jiān)測異常運(yùn)行狀態(tài)并將相關(guān)數(shù)據(jù)發(fā)送給軟件開發(fā)者，軟件開發(fā)者往往要面臨大量的Bug數(shù)據(jù)，如果對這些數(shù)據(jù)逐一分析是十分費(fèi)時(shí)費(fèi)力的，利用數(shù)據(jù)挖掘方法，自動(dòng)對這些數(shù)據(jù)進(jìn)行處理，縮小問題空間。數(shù)據(jù)挖掘 數(shù)據(jù)挖掘 是通過分析，從大量數(shù)據(jù)中尋找其規(guī)律的技術(shù)，主要有數(shù)據(jù)準(zhǔn)備、規(guī)律尋找和規(guī)律表示三個(gè)步驟： 1.數(shù)據(jù)準(zhǔn)備是從相關(guān)的數(shù)據(jù)源中選取所需的數(shù)據(jù)并整合成用于數(shù)據(jù)挖掘的數(shù)據(jù)集；2.規(guī)律尋找是用某種方法將數(shù)據(jù)集所含的規(guī)律找出來；3.規(guī)律表示是盡可能以用戶可理解的方式（如可視化）將找出的規(guī)律表示出來 數(shù)據(jù)挖掘的技術(shù)基礎(chǔ)是人工智能，僅利用了人工智能中一些己經(jīng)成熟的算法和技術(shù)，例如：人工神經(jīng)網(wǎng)絡(luò)(Artifici

4、al Neural Networks)遺傳算法(Genetic Algorithms)決策樹(Decision Trees)鄰近搜索方法(Nearest Neighbor Method)規(guī)則推理(Rule Induction)模糊邏輯(Fuzzy Logic)等等. 遺傳算法是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過程的計(jì)算模型，是一種通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法 由三個(gè)基本算子(或過程)組成：1.繁殖(選擇)，即從一個(gè)舊種群(父代)選出生命 力強(qiáng)的個(gè)體，產(chǎn)生新的種群(后 代)的過程。 2.交叉(重組)，即選擇兩個(gè)不同的個(gè)體(染色體) 的部分(基因)進(jìn)行交換，形成 新個(gè)體

5、的過程。3.變異(突變)，即對某些個(gè)體的某些基因進(jìn)行 變異(0變19或l變0)，形成 新個(gè)體的過程。 數(shù)據(jù)挖掘的主要分析方法 1關(guān)聯(lián)分析(Associations) ，關(guān)聯(lián)分析的目的就是為了挖掘出隱藏在數(shù)據(jù)間的相互關(guān)系。 2序列模式分析(Sequential Patterns) 序列模式分析和關(guān)聯(lián)分析法相似，其目的也是為了挖掘出數(shù)據(jù)之間的聯(lián)系， 但序列模式分析的側(cè)重點(diǎn)在于分析數(shù)據(jù)間的前后或因果關(guān)系。 3分類分析(Classifiers) 假定記錄集會(huì)和一組標(biāo)記(TAG)，所謂標(biāo)記是指一組具有不同特征的類別。 分類分析時(shí)首先為每一個(gè)記錄賦予一個(gè)標(biāo)記，按標(biāo)記分類記錄。 4聚類分析(Clusteri

6、ng) 與分類分析法不同，聚類分析法的輸入集是一組未標(biāo)定的記錄，也就是說此時(shí)輸入的記錄還沒有被進(jìn)行任何分類。其目的是根據(jù)一定的規(guī)則，合理地劃分記錄集合。信息- -模糊網(wǎng) 簡介 信息-模糊網(wǎng)(Info-FuzzyNetwork，以下簡稱IFN)是由以色列Bcn-Gurion大學(xué)的Mark Last提出的一種基于信息論的分類方法，與傳統(tǒng)基于信息論的分類方法相比，在保證分類精度的同時(shí)可以得到比較簡約的分類規(guī)則。 信息-模糊網(wǎng)的結(jié)構(gòu)與決策樹不同，IFN具有網(wǎng)狀的，類似神經(jīng)網(wǎng)絡(luò)的分層結(jié)構(gòu)IFN由一個(gè)根節(jié)點(diǎn)，若干個(gè)中間層，和一個(gè)目標(biāo)層構(gòu)成。 IFN的每個(gè)中間層只對應(yīng)一個(gè)待分類的屬性， 第L中間層的一個(gè)節(jié)點(diǎn)

7、表示前L個(gè)輸入屬性值的并。如果某個(gè)屬性為連續(xù)變量， 需要將其離散化。目標(biāo)層的每個(gè)節(jié)點(diǎn)表示目標(biāo)屬性的一個(gè)值，如果目標(biāo)屬性是連續(xù)量，則目標(biāo)層表示若干不相交的區(qū)間。其中，直接與目標(biāo)層節(jié)點(diǎn)相連的中間層節(jié)點(diǎn)稱為終結(jié)點(diǎn)(final nodes)，終結(jié)點(diǎn)與目標(biāo)層節(jié)點(diǎn)間的連接表示一組輸入屬性可以被劃分一個(gè)特定類；例如有五個(gè)終結(jié)點(diǎn)：(1，1)，(1，2)， (3，1)，(3，2)。假如把圖看作是根據(jù)某個(gè)可執(zhí)行程序的輸入、輸出所建立的IFN， 則連接(1，1)-1的意義為：對于具有兩個(gè)輸入值都為1的測試用例，程序?qū)⑤敵鼋Y(jié)果1。信息- -模糊網(wǎng)的構(gòu)建算法 輸入為一個(gè)訓(xùn)練數(shù)據(jù)集，目標(biāo)屬性集合和節(jié)點(diǎn)分裂所需的最小熵壓縮

8、閾值sign，首先定義目標(biāo)層，每個(gè)節(jié)點(diǎn)表示一個(gè)類別；由一個(gè)表示空集的根節(jié)點(diǎn)開始，計(jì)算每個(gè)屬性分裂后引起的熵壓縮，對于取離散值得屬性可直接計(jì)算，對于連續(xù)值的屬性首先進(jìn)行離散化再計(jì)算；選擇引起熵壓縮最大的屬性進(jìn)行分裂，形成下一個(gè)中間層；重復(fù)以上步驟迭代地建立網(wǎng)絡(luò)，直到?jīng)]有候選屬性接點(diǎn)分裂起的熵壓縮大于sign時(shí)，網(wǎng)絡(luò)的建立過程結(jié)束。 計(jì)算某個(gè)結(jié)點(diǎn)分裂引起的熵壓縮使用如下的算法： 設(shè)S是s個(gè)數(shù)據(jù)樣本的集合，假定有m個(gè)互不相同的目標(biāo)屬性，定義m個(gè)不同類 。設(shè)Si是類Ci中的樣本數(shù)。對一個(gè)給定的樣本分類所需的期望信息(熵)可以由以下公式計(jì)算： Pi是任意樣本屬于Ci的估算概率).2 , 1(Cimi )

9、(log),.,(1221imiimppSSSIsspii設(shè)候選屬性A有v個(gè)不同值(al，a2 av)。可以用屬性A將S劃分為v個(gè)子集S1，S2，Sv)；其中，sj包含S中在A上值為aj的樣本。設(shè)sij是子集sj中類屬于Ci的樣本數(shù)。則將樣本按A劃分后，對一個(gè)給定樣本分類所需的期望信息(熵) 由下式給出： 其中，對于給定的子集Sj，pij是sj中的樣本屬于類Ci的概率，表示為vmjjjmjjjsssIssssAE1j2121),.,(.)(miijijmjjjppsss1221)(log-),.,( Ijijijssp 分裂屬性A所造成的熵壓縮為： 然后選擇引起熵壓縮最大的屬性進(jìn)行分裂 。.)

10、(),.,()(21AEsssIAGainm使用信息- -模糊網(wǎng)劃分等價(jià)類 使用IFN劃分測試用例等價(jià)類的系統(tǒng)結(jié)構(gòu)見圖 系統(tǒng)組成模塊及功能如下： 被測試模塊：這部分可以是一個(gè)程序，組件或完整的系統(tǒng)，并且它在以后的使用中將不斷的更新版本。要注意的是，它應(yīng)該是“數(shù)據(jù)驅(qū)動(dòng)” 的，即它的輸入和輸出都是一組了格式和類型的數(shù)據(jù)。 系統(tǒng)輸入輸出說明：對待測試模塊輸入和輸出數(shù)據(jù)的說明，可以包括變量數(shù)量，名稱，類型，取值范圍等。 測試用例產(chǎn)生器：根據(jù)系統(tǒng)輸入輸出說明提供的信息自動(dòng)地，隨機(jī)地產(chǎn)生測 試用例，產(chǎn)生的數(shù)量由用戶指定。產(chǎn)生的測試用例輸入數(shù)據(jù)交給測試驅(qū)動(dòng)程序和 IFN構(gòu)建算法。 測試驅(qū)動(dòng)程序：它將用例產(chǎn)

11、生器產(chǎn)生的測試用例送給被測試模塊執(zhí)行，并接收每個(gè)測試用例的輸出。然后交給IFN構(gòu)建算法。 IFN構(gòu)建算法：算法的訓(xùn)練數(shù)據(jù)集是接收自測試用例產(chǎn)生器的測試用例輸入數(shù)據(jù)和來自測試驅(qū)動(dòng)程序的測試用例輸出數(shù)據(jù)。算法根據(jù)某組輸入所對應(yīng)得輸出將隨機(jī)產(chǎn)生的大量測試用例劃分成若干等價(jià)類。 系統(tǒng)運(yùn)行時(shí)，首先由測試用例產(chǎn)生器根據(jù)輸入輸出說明中的描述產(chǎn)生一組輸入數(shù)據(jù)，這組輸入數(shù)據(jù)被交給測試驅(qū)動(dòng)程序；測試驅(qū)動(dòng)程序?qū)?shù)據(jù)輸入被測模塊并得到被測模塊的輸出；隨后，這組輸入和它相應(yīng)得輸出被作為一條訓(xùn)練數(shù)據(jù)交給IFN的構(gòu)建算法。構(gòu)建算法迭代的運(yùn)行，以輸出作為目標(biāo)層，將大量的輸入劃分成少量等價(jià)類。然后便可以從每個(gè)等價(jià)類中選擇少量的

12、數(shù)據(jù)作為測試用例。使用序列模式挖掘技術(shù)分析BugBug報(bào)告 什么是BUG報(bào)告在軟件測試和使用過程中，當(dāng)測試人員或用戶發(fā)現(xiàn)一個(gè)缺陷時(shí)，需要把它告 訴給開發(fā)人員，Bug報(bào)告就是將Bug的詳細(xì)信息傳遞給開發(fā)人員的方式。有效的 Bug描述，會(huì)更加容易幫助開發(fā)解決問題。因此，在Bug報(bào)告中需要盡量給出足夠多的指引，以便開發(fā)人員能夠根據(jù)報(bào)告中的描述重現(xiàn)錯(cuò)誤。BUGBUG報(bào)告的內(nèi)容 一般來說，高質(zhì)量的Bug報(bào)告，應(yīng)該包括以下內(nèi)容： 1、Bug標(biāo)題：簡明扼要地對Bug進(jìn)行一個(gè)概述。 2、Bug的屬性。 Bug的屬性應(yīng)該包括： (1)產(chǎn)品名稱：測試產(chǎn)品的名稱。 (2)產(chǎn)品子系統(tǒng)：測試產(chǎn)品的子系統(tǒng)，如果產(chǎn)品比較小

13、，該項(xiàng)可以忽略。 (3)產(chǎn)品模塊：測試產(chǎn)品發(fā)現(xiàn)問題的模塊的名稱。 (4)測試版本：當(dāng)前的測試版本。(5)測試平臺(tái)：Bug的產(chǎn)生很可能跟平臺(tái)有關(guān)。 (6)測試階段：模塊測試、內(nèi)部集成測試、外部集成測試。 (7)問題級別：緊急、嚴(yán)重、一般、建議，級別高的問題應(yīng)優(yōu)先處理。 (8)問題來源：測試、工程故障、升級、其他 (9)問題類型：功能問題、版本問題、遺留問題、新需求、低級錯(cuò)誤、改進(jìn)建 議、移植修改、割接問題、配置錯(cuò)誤、編譯問題、性能問題、設(shè)計(jì)問題、兼容問 題、新功能增強(qiáng)、偶發(fā)性出錯(cuò)自動(dòng)BugBug報(bào)告 自動(dòng)記錄并發(fā)送Bug信息的技術(shù)是軟件開發(fā)技術(shù)的一項(xiàng)重要進(jìn)步，使軟件的開發(fā)人員能 夠獲得足夠的數(shù)據(jù)

14、來確認(rèn)和定位Bug，提高軟件質(zhì)量。但是，這種技術(shù)給開發(fā)人員帶來了一個(gè)新的問題：接收到的自動(dòng)Bug報(bào)告往往數(shù)量巨大，根本無法逐個(gè)進(jìn)行分析，那又如何從用戶實(shí)際使用時(shí)的事件序列中定位缺陷位置呢?為解決這個(gè)問題提出：從若干個(gè)這些事件序列中的發(fā)現(xiàn)出現(xiàn)的較為頻繁的共同的子序列，則這個(gè)子序列就可能是導(dǎo)致錯(cuò)誤發(fā)生的事件序列。軟件的開發(fā)人員可以使用這個(gè)子序列重現(xiàn)錯(cuò)誤，繼而定位錯(cuò)誤，從而避免了對大量的錯(cuò)誤報(bào)告逐一分析，大大提高了效率。 下面給出一個(gè)形式化的描述： 設(shè) 是軟件可能發(fā)生的事件集合，O中的每個(gè)元素代表一個(gè)事件；設(shè) 是若干事件序列組成的集合，S中的每個(gè)元素是一個(gè)可以導(dǎo)致軟件產(chǎn)生錯(cuò)誤的事件序列： 如果S中有

15、一個(gè)子集 ，滿足 c(c是人為選定的正整數(shù))，并且 中任意一個(gè)元素序列 ，都有子序列P,則P就可能是導(dǎo)致錯(cuò)誤發(fā)生的事件序列。 需要注意的是，這里“序列”的意義與集合不同，序列中元素的出現(xiàn)是有次序的。,.o,o,o321O,.,321SSSS ONjNissssSsssSsssSij),(.,.,.,.,33,3231323,2221213,12111SSS)0(SSiSi序列模式挖掘技術(shù) 序列模式挖掘由 Agrawal和Srikant最早提出：給定一個(gè)由不同序列組成的集合，其中每個(gè)序列由不同的元素按順序有序排列、每個(gè)元素由不同項(xiàng)目組成，同時(shí)給定一個(gè)用戶指 定的最小支持度閾值，序列模式挖掘的任務(wù)

16、就是找出所有頻繁子序列，即出現(xiàn)頻率不低于最小支持度閾值的子序列。 定義：序列： 序列(sequence)是項(xiàng)集的有序表， 。其中S是 項(xiàng)集(也是S的元素)。序列包含的項(xiàng)集的個(gè)數(shù)稱為序列的長度，長度為k的序列記為k-序列。 子序列： ，使得 ，則稱序列A為序列B的子序列。支持度:序列A在序列數(shù)據(jù)庫S中的支持度為序列數(shù)據(jù)庫S中包含序列A的序列個(gè)數(shù)， 記為Support(A)。 模式給定支持度閾值c:如果序列A在序列數(shù)據(jù)庫中的支持?jǐn)?shù)不低于c，則稱序列A為序列模式，長度為k的序列模式記為k-模式。 可見，前一節(jié)提出的問題，可以部分的轉(zhuǎn)化為從序列數(shù)據(jù)庫中發(fā)現(xiàn)序列模式的問題。,.,321SSSS mjjj

17、BBBBAAAAnnn.1,.,.,212121如果存在整數(shù)jnnjjBABABA,.,2211IPMIPM算法 基本概念 1. 所有事件序列的集合。集合中的每個(gè)序列S是軟件發(fā)生錯(cuò)誤之前用戶事件序列(可以取最近若干個(gè)事件)。 2.候選模式：等待算法判斷是否是模式的一個(gè)子序列。 3.下標(biāo)運(yùn)算符i：一個(gè)序列的第i項(xiàng)。 4.插入錯(cuò)誤：當(dāng)序列SS包含序列P時(shí)，對區(qū)間 (0，length(p)中的每一個(gè)正整數(shù)i,取J=i+1,記滿足條件 時(shí)的正整數(shù)li與ki之差為Ci，則Max(C)稱為插入錯(cuò)誤。 5.判定標(biāo)準(zhǔn)c：用戶定義的三元組(minLen，minSupp，maxError)，表示模式P成為頻繁模式

18、需要滿足的最小長度，最小支持度，最大允許插入錯(cuò)誤。,.,321SSSS PiiikSjPlS 6.模式描述表：用來描述一個(gè)模式，記為localist(P)，表中的每個(gè)項(xiàng)是描 述模式P的三元組(seqnum，startloc，endloc)表示包含該模式的序列在S 中的編號，該模式在包含它的序列中起始和終止的位置。顯然，每 個(gè) 模 式 的 描 述 表 長 度 等 于 它 的 支 持 度 ，localist(P)Jength=Support(P)。 7.模式的前綴：記做prefw(P)，表示模式P的前l(fā)ength(P)一1項(xiàng)組成的序 列。 8.模式的后綴：記做suffix(P)，表示模式P移除第一個(gè)項(xiàng)后的序列。算法執(zhí)行過程 IPM算法的基本過程與各種經(jīng)典序列挖掘算法相同，首先找到較短的頻繁序列，然后將其擴(kuò)展以得到長序列。算法接受一個(gè)輸入序列集合S和判定標(biāo)準(zhǔn)c， 找出S中符合c的所有頻繁模式。主要由兩個(gè)階段構(gòu)成，首先：算法搜索輸入串， 窮舉所有的長度為2，插入錯(cuò)誤小于c . m a x E r