基於組合測試的錯誤定位方法

2023-05-03 15:35:41 1

基於組合測試的錯誤定位方法
【專利摘要】本發明提供一種基於組合測試的錯誤定位方法，該方法從輸出端的結果入手，分析輸出端的故障模式，結合apriori算法定位錯誤，提高了錯誤定位的定全率和定準率。作為軟體測試中定位故障的方法，本發明保證了錯誤定位結果的準確性。比對已有技術具有以下一些特點和創新之處：在基於組合測試的錯誤定位方法中，對輸出的故障模式進行掃描，找出出現最頻繁的項集，經過重複掃描，生成可疑的故障模式集，提高軟體錯誤定位的效率。
【專利說明】基於組合測試的錯誤定位方法

【技術領域】
[0001] 本發明涉及一種基於組合測試的錯誤定位方法，屬於軟體測試的錯誤定位領域。

【背景技術】
[0002] 軟體系統可能會受到它的參數間相互作用的影響。這些相互作用需要進行測試， 以保證軟體的質量。但對於有η個參數的待測系統，由於參數值的組合很多，我們不可能去 覆蓋所有可能的η元組參數值的組合。組合測試則是在測試成本和組合覆蓋度之間的一個 折衷方法。例如，2維組合測試要求覆蓋所有的2元組合，在η元組合中則不是。
[0003] 在錯誤檢測後，錯誤定位在軟體質量保證中起到了一個重要的作用，它也需要去 協助軟體調試。在交互錯誤定位階段，基於從組合測試用例的執行中獲取的信息，需要定位 導致故障的那些參數值得特定組合。然而，基於組合測試的交互錯誤定位技術很少被研究。 因此，需要進行研究來協助組合測試更廣泛的應用。
[0004] 目前，人們關於組合測試的研究主要集中在組合覆蓋測試用例的生成方面。Cohen 與Dalai等提出了一種基於兩兩組合覆蓋的測試數據啟發式生成方法，所產生的測試數據 可以根據測試要求實現對系統參數的兩兩組合覆蓋，或者多個參數的組合覆蓋。但這種方 法無法保證所產生的測試用例最優。Lei和Tai提出一種基於參數順序的漸進擴充的兩兩 組合覆蓋測試數據生成方法，在某些方面具有比較好的特性，同時，這種方法也有很大不足 之處。作為啟發式方法的一種重要補充，Kobayashi和Tsuchiya等提出了一種代數方法用 於生成兩兩組合覆蓋的測試數據，在某些情況下其效果要比啟發式方法好。
[0005] Zeller提出了 Delta Debugging方法，是一種能自動縮小程序的成功運行過程和 失敗運行過程之間區別的技術。在實現層面，它採用分治思想，把軟體配置（測試輸入、源 程序等）變動的集合進行劃分，然後分別進行測試，結果可以為通過、失敗和無解。然後遞 歸地把導致失敗配置的集合併入結果為通過配置的集合。通過逐漸減小兩個集合之間的差 異，最終確認成功配置和失敗配置差別的一個最小子集。
[0006] 徐寶文等人首先假定"若某個模式是錯誤模式，則任意包含該模式的其它模式也 將引發相同的錯誤"。在此前提條件下，他們通過分析執行失敗的測試用例，生成一批與之 類似的附加測試用例，並通過執行附加測試用例，逐步縮小故障模式集合Μ的範圍，直到錯 誤被精確地定位。


【發明內容】

[0007] 本發明的目的是提出一種基於組合測試的錯誤定位方法，該方法結合了 apriori 算法，該算法能不斷掃描故障模式集，找出出現頻率最高的一個幾個故障模式，最終達到軟 件測試中錯誤定位的定全率和準確率的目標。
[0008] 本發明的技術解決方案是：
[0009] 一種基於組合測試的錯誤定位方法，
[0010] S1、獲取可執行的待測系統以及測試用例集；
[0011] S2、運行測試用例，劃分通過和失敗的測試用例集，保留失敗測試用例集用來定位 故障；
[0012] S3、生成失敗附加測試用例集Tfail' ；
[0013] S4、合併所有失敗測試用例的集合為Tf ;
[0014] S5、利用apriori算法找到Tf中的頻繁項目集；
[0015] S6、故障定位結果的度量使用定全率和定準率兩個指標，計算可以故障模式集合 中的定全率和定準率，判斷是否達到100% :
[0016] 如果"是"，轉步驟S7 ;如果否，則跳轉步驟S3 ;
[0017] S7、頻繁項目集即為錯誤定位的結果，結束。
[0018] 進一步地，步驟S1具體為：
[0019] S11、獲取待測系統SUT ;
[0020] S12、待測系統SUT有η個參數f\，f2, . . .，fn，形成集合F = {f\，f2, . . .，fn}，形成該 因素的取值集合\ = {1，2, . . .，aj ;
[0021] S13、獲取測試用例集，記為T ;
[0022] S14、對Τ中的測試用例進行編號，按序編為test" test2, . . .，testy . . .，testn，其 中 test = {vd v2, · · ·，vj h e ν1; v2 e V2, · · ·，Vn e Vn)表示測試用例集 T 中的第 i 條測 試用例，n為測試用例的總條數。
[0023] 進一步地，步驟S2具體為：
[0024] S21、從測試用例集中選取測試用例testi ;
[0025] S22、運行當前選取的測試用例testi ;
[0026] S23、判斷測試用例的通過情況；
[0027] S231、判定測試用例test是否通過，如果"是"，則轉S232,否則轉S233 ;
[0028] S232、將測試用例test放入集合Tpass ;
[0029] S233、將測試用例test放入集合Tfail ;
[0030] S234、判定待測系統SUT是否執行結束，如果"是"，則轉S235,否則轉S21，直到T 中的測試用例均被待測系統SUT檢測；
[0031] S235、獲取集合Tfail，Tfail為所有失敗測試用例的集合。
[0032] 進一步地，步驟S3具體為：
[0033] S31、從Tfail中選取測試用例testi ;
[0034] S32、獲取附加測試用例集Τ' ；
[0035] S33、從Τ'中選取測試用例test/ ;
[0036] S34、運行當前選取的測試用例test/ ;
[0037] S35、判斷測試用例的通過情況；
[0038] S351、判定測試用例test/是否通過，如果"是"，則轉S352,否則轉S353 ;
[0039] S352、將測試用例test/放入集合Tpass' ；
[0040] S353、將測試用例test/放入集合Tfail' ；
[0041] S354、判定待測系統SUT是否執行結束，如果"是"，則轉S355,否則轉S33,直到 Tfail'中的測試用例均被待測系統SUT檢測；
[0042] S355、獲取集合Tfail'，Tfail'為所有失敗附加測試用例的集合。
[0043] 進一步地，步驟S31具體為：
[0044] S311、改變其中一項V/A (k=l)啲值，生成新的測試用例test/ ;
[0045] S312、將test/放入附加測試用例集Τ'中；
[0046] S313、判斷是否有k = η，如果"是"，則轉S31，k = k+Ι，否則轉S311 ;
[0047] S314、判斷Tfail中的測試用例test是否都被選取，如果"是"，則轉S32,否則轉 S31。
[0048] 進一步地，步驟S5具體為：
[0049] S51、算法開始；
[0050] S52、設定最小支持度為2 ;
[0051] S53、掃描集合Tf，對每個項Vi進行計數；
[0052] S54、生成1階候選項目集，k = 1 ;
[0053] S55、由保留的項Vi生成1階頻繁項目集，k = 1 ;
[0054] S56、掃描集合Tf，對(V 4)計數；
[0055] S57、生成2階候選項目集，k = 2 ;
[0056] S58、由保留的項(v;l，ν?:)生成2階頻繁項目集，k = 2 ;
[0057] S59、掃描 Tf，k = k+1，對(％，ν?:，…，' )計數；
[0058] S510、生成k階候選項目集；
[0059] S511、由保留的項(V,.,，\，…，\ )生成k階頻繁項目集；
[0060] S512、判斷k階頻繁項目集的每個項(ν;1，ν(· :，…，)計數是否大於最小支持度2,如 果"是"，則轉S513,否則轉S59 ;
[0061] S513、算法結束；
[0062] 進一步地，步驟S54具體為：
[0063] S541、從1階候選項目集中選取項Vi ;
[0064] S542、判斷Vi的計數是否大於最小支持度2,如果"是"，則轉S543,否則轉S544 ;
[0065] S543、保留該項 vi;
[0066] S544、刪除計數不大於2的項；
[0067] S545、判斷是否掃描1階候選項目集中所有項Vi，如果"是"，則轉S55，否則轉 S541。
[0068] 進一步地，步驟S57具體為：
[0069] S571、從2階候選項目集中選取項(?2);
[0070] S572、判斷(W的計數是否大於最小支持度2，如果"是"，則轉S573，否則轉 S574 ；
[0071] 3573、保留該項(^2);
[0072] S574、刪除計數不大於2的項；
[0073] S575、判斷是否掃描1階候選項目集中所有項(? )，如果"是"，則轉S58,否則轉 S571。
[0074] 進一步地，步驟S510具體為：
[0075] S5101、從k階候選項目集中選取項('，v,:，…，ν4 );
[0076] 35102、判斷〇,1，圪，?，1\)計數是否大於最小支持度2，如果"是"，則轉55103，否則 轉 S5104 ;
[0077] S5103、保留該項('，ν,:，…，v;i);
[0078] S5104、刪除計數不大於2的項；
[0079] S5105、判斷是否掃描1階候選項目集中所有項（ν;1，ν?2，…，ν4)，如果"是"，則轉 S511，否則轉 S5101。
[0080] 本發明的有益效果是：作為軟體測試中定位故障的方法，本發明保證了錯誤定位 結果的準確性。比對已有技術具有以下一些特點和創新之處：在基於組合測試的錯誤定位 方法中，對輸出的故障模式進行掃描，找出出現最頻繁的項集，經過重複掃描，生成可疑的 故障模式集，提高軟體錯誤定位的效率。

【專利附圖】

【附圖說明】
[0081] 圖1是實施例方法錯誤定位的流程圖。
[0082] 圖2是apriori算法流程圖。
[0083] 圖3是利用apriori算法找到故障模式中的頻繁項集流程圖。

【具體實施方式】
[0084] 下面結合附圖詳細說明本發明的優選實施例。
[0085] 在充分考慮保證生成結果最優的基礎上，提出了一種新的關於兩兩組合覆蓋的測 試數據生成算法。實施例方法主要是在現有理論的基礎上，分析輸出端的故障模式集，結合 apriori算法，找到可疑故障模式集合來定位錯誤，最終提高錯誤定位的定全率和準確率。 Apriori算法是一種挖掘關聯規則的頻繁項集算法，如圖2所示。
[0086] 實施例的該種基於組合測試的錯誤定位方法，從輸出端的結果入手，分析輸出端 的故障模式，結合apriori算法定位錯誤，提高了錯誤定位的定全率和定準率。在極小故障 模式模型中，認為軟體錯誤是由極小故障模式所引發的，這一模式必然被包含在一條運行 失敗的測試用例中。因此，組合測試故障的定位目標就在於尋找這樣的極小故障模式，或是 將這樣的極小故障模式確定在一個比較小的、可供人工篩選的範圍內。在進行組合測試的 故障定位時，可以考慮綜合使用DeltaDebuging和NearestNeighborHeuristic策略，即生 成並運行一些與失敗測試用例近似的附加測試用例，以尋找錯誤出現的規律，進而定位誘 發錯誤的極小故障模式。結合apriori算法，不斷掃描故障模式集，找出出現頻率最高的一 個或幾個故障模式，提高了錯誤定位的定準率和定全率。
[0087] 實施例基於組合測試，結合apriori算法，從開始選取測試用例到最終定位故障 的實現步驟為，如圖1所示：
[0088] 步驟1)獲取可執行的待測系統以及測試用例集；
[0089] 步驟1. 1)獲取待測系統SUT，其中引起故障的參數組合已知；
[0090] 步驟 1. 2)待測系統 SUT 有 η 個參數 f\，f2, . . .，fn，形成集合 F = {f\，f2, . . .，fn}， 其中因素 fi經過等價類劃分等前期處理後包含％個可選取值，形成該因素的取值集合\ = {1，2，· · ·，￡1土};
[0091] 步驟1. 3)獲取測試用例集，記為T，測試用例按照特定的規則利用測試工具自動 生成；
[0092] 步驟1.4)對T中的測試用例進行編號，按序編為 testj, test2, . . . , testj, . . . , testn, 其中 t e s t j = {v 1； v2, . . . , vn} (Vl e %，v2 e V2,...，vn e Vn)表示測試用例集T中的第i條測試用例，n為測試用例的總 條數，對測試用例進行編號為查找失敗測試用例提供便利。
[0093] 步驟2)運行測試用例，劃分通過和失敗的測試用例集，保留失敗測試用例集用來 定位故障；
[0094] 步驟2. 1)根據測試用例的編號按序從T中選取測試用例testi ;
[0095] 步驟2. 2)通過待測系統SUT運行當前選取的測試用例test ;
[0096] 步驟2. 3)判斷測試用例test的通過情況，根據結果劃分為通過和失敗兩個測試 用例集，Tpass表示通過測試用例集，T fail表示失敗測試用例集，保留Tfail來定位故障。
[0097] 步驟3)根據失敗測試用例生成失敗附加測試用例Tfail'，增加失敗的測試用例能 使錯誤定位更加準確；
[0098] 步驟3. 1)從Tfail*選取測試用例testp依次改變其中的一項，生成附加測試用例 集；
[0099] 步驟3. 2)獲取附加測試用例集Τ'，用待測系統SUT來運行Τ'中測試用例；
[0100] 步驟3. 3)從Τ'中選取測試用例test/ ;
[0101] 步驟3. 4)通過待測系統SUT運行當前選取的測試用例test/ ;
[0102] 步驟3. 5)判斷測試用例test/的通過情況，根據結果劃分為通過和失敗兩個測 試用例集，Tpass'表示通過測試用例集，T fail'表示失敗測試用例集，保留Tfail'來定位故障， Tfail'就是失敗附加測試用例集。
[0103] 步驟4)將所有失敗測試用例和附加失敗測試用例合併為集合Tf。
[0104] 步驟5)利用apriori算法找到Tf中的頻繁項集，如圖3所示，Apriori算法是一 種挖掘關聯規則的頻繁項集算法，通過該算法尋找失敗測試用例集中出現最頻繁的參數組 合，該參數組合則最有可能引起待測系統的故障；
[0105] 步驟5.1)算法開始；
[0106] 步驟5. 2) -般設定最小支持度為2 ;
[0107] 步驟5. 3)掃描集合Tf，對每條測試用例的每個項Vi進行計數；
[0108] 步驟5. 4)生成1階候選項目集，比較每個項Vi的計數與最小支持度2的大小，刪 除計數不大於2的項，即去除幹擾項，方便找到頻繁項；
[0109] 步驟5. 5)由保留的項Vi生成1階頻繁項目集，該集合中的每個項出現的次數均 大於2 ;
[0110] 步驟5. 6)掃描集合Tf，對(v;l，V,':)進行計數；
[0111] 步驟5. 7)生成2階候選項目集，比較每個項〇V\)的計數與最小支持度2的大 小，刪除計數不大於2的項；
[0112] 步驟5. 8)由保留的項('，化）生成2階頻繁項目集，該集合中的每個項出現的次數 均大於2 ;
[0113] 步驟5. 9)掃描Tf，k = k+Ι，對0^々，...，\)進行計數；
[0114] 步驟5. 10)生成k階候選項目集，比較每個項，…，v4)的計數與最小支持度2 的大小，刪除計數不大於2的項；
[0115] 步驟5. 11)由保留的項(^，一^4)生成讓階頻繁項目集，該集合中的每個項出 現的次數均大於2 ;
[0116] 步驟5. 12)判斷k階頻繁項目集的每個項0V4，…，ν?計數是否大於最小支持度 2,如果"是"，則轉步驟5. 9,否則轉步驟5. 13 ;
[0117] 步驟5. 13)當k階頻繁項目集中的每個項的計數均不大於最小支持度2的時候， 則停止apriori算法，得到的頻繁項集就是失敗測試用例集中T f的故障模式。算法結束。
[0118] 步驟6)故障定位結果的度量使用定全率（recall)和定準率（precision)等兩個 指標。計算可以故障模式集合中的定全率和定準率，是否接近1〇〇 %，如果"是"，則轉步驟 7,否，跳轉步驟3;
[0119] 定義：假設MinFaultScheSetO為待測系統中客觀存在且已被測試用例集T所命中 的極小故障模式構成的集合，FaultScheSetO為待測系統中客觀存在且已被測試用例集T 所命中的故障模式構成的集合，SuspScheSet為故障定位所得的嫌疑模式集合，貝U

【權利要求】
1. 一種基於組合測試的錯誤定位方法，其特徵在於： 51、 獲取可執行的待測系統以及測試用例集； 52、 運行測試用例，劃分通過和失敗的測試用例集，保留失敗測試用例集用來定位故 障； 53、 生成失敗附加測試用例集Tfail' ； 54、 合併所有失敗測試用例的集合為Tf ; 55、 利用apriori算法找到Tf中的頻繁項目集； 56、 故障定位結果的度量使用定全率和定準率兩個指標，計算可以故障模式集合中的 定全率和定準率，判斷是否達到100% : 如果"是"，轉步驟S7 ;如果否，則跳轉步驟S3 ; 57、 頻繁項目集即為錯誤定位的結果，結束。
2. 如權利要求1所述的基於組合測試的錯誤定位方法，其特徵在於，步驟S1具體為： 511、 獲取待測系統SUT ; 512、 待測系統SUT有η個參數f\，f2,. . .，fn，形成集合F = {f\，f2,. . .，fn}，形成該因素 的取值集合 Vi = {l，2，...，ai}; 513、 獲取測試用例集，記為T ; 514、 對Τ中的測試用例進行編號，按序編為test。test2, . . .，testy . . .，testn，其中 test = {vd v2, · · ·，vn} h e ν1; v2 e V2, · · ·，Vn e Vn)表示測試用例集 T 中的第 i 條測試 用例，n為測試用例的總條數。
3. 如權利要求2所述的基於組合測試的錯誤定位方法，其特徵在於，步驟S2具體為： 521、 從測試用例集中選取測試用例test ; 522、 運行當前選取的測試用例test ; 523、 判斷測試用例的通過情況； 5231、 判定測試用例test是否通過，如果"是"，轉S232,否則轉S233 ; 5232、 將測試用例test放入集合Tpass ; 5233、 將測試用例test放入集合Tfail ; 5234、 判定待測系統SUT是否執行結束，如果"是"，則轉S235,否則轉S21，直到T中的 測試用例均被待測系統SUT檢測； 5235、 獲取集合Tfail，Tfail為所有失敗測試用例的集合。
4. 如權利要求3所述的基於組合測試的錯誤定位方法，其特徵在於，步驟S3具體為： 531、 從Tfail中選取測試用例test ; 532、 獲取附加測試用例集Τ' ； 533、 從Τ'中選取測試用例test/ ; 534、 運行當前選取的測試用例test/ ; 535、 判斷測試用例的通過情況； 5351、 判定測試用例test/是否通過，如果"是"，則轉S352,否則轉S353 ; 5352、 將測試用例test/放入集合Tpass' ； 5353、 將測試用例test/放入集合Tfail' ； 5354、 判定待測系統SUT是否執行結束，如果"是"，則轉S355,否則轉S33,直到Tfail'中 的測試用例均被待測系統SUT檢測； S355、獲取集合Tfail'，Tfail'為所有失敗附加測試用例的集合。
5. 如權利要求4所述的基於組合測試的錯誤定位方法，其特徵在於，步驟S31具體為： 5311、 改變其中一項\ (1<=1)的值，生成新的測試用例test/ ; 5312、 將test/放入附加測試用例集Τ'中； 5313、 判斷是否有k = η，如果"是"，則轉S31，k = k+Ι，否則轉S311 ; 5314、 判斷Tfail中的測試用例test是否都被選取，如果"是"，則轉S32,否則轉S31。
6. 如權利要求1-5任一項所述的基於組合測試的錯誤定位方法，其特徵在於，步驟S5 具體為： 551、 算法開始； 552、 設定最小支持度為2 ; 553、 掃描集合Tf，對每個項Vi進行計數； 554、 生成1階候選項目集，k = 1 ; 555、 由保留的項Vi生成1階頻繁項目集，k = 1 ; 556、 掃描集合Tf，對〇VV,2)計數； 557、 生成2階候選項目集，k = 2 ; 558、 由保留的項(?)生成2階頻繁項目集，k = 2 ; 559、 掃描 Tf，k = k+1，對(?，…，& )計數； 5510、 生成k階候選項目集； 5511、 由保留的項(V,.,, ν?2，…,\ )生成k階頻繁項目集； 5512、 判斷k階頻繁項目集的每個項)計數是否大於最小支持度2,如果 "是"，則轉S513,否則轉S59 ; 5513、 算法結束。
7. 如權利要求6所述的基於組合測試的錯誤定位方法，其特徵在於，步驟S54具體為： 5541、 從1階候選項目集中選取項Vi ; 5542、 判斷Vi的計數是否大於最小支持度2,如果"是"，則轉S543,否則轉S544 ; 5543、 保留該項Vi ; 5544、 刪除計數不大於2的項； 5545、 判斷是否掃描1階候選項目集中所有項Vi，如果"是"，則轉S55,否則轉S541。
8. 如權利要求6所述的基於組合測試的錯誤定位方法，其特徵在於，步驟S57具體為： 5571、 從2階候選項目集中選取項('，' ); 5572、 判斷(νΑ,ν?:)的計數是否大於最小支持度2,如果"是"，則轉S573,否則轉S574 ; 3573、保留該項(',4); 5574、 刪除計數不大於2的項； 5575、 判斷是否掃描1階候選項目集中所有項(νΑ, ν,:)，如果"是"，則轉S58，否則轉 S571。
9.如權利要求6所述的基於組合測試的錯誤定位方法，其特徵在於，步驟S510具體 為： 55101、 從k階候選項目集中選取項('，v,:，…，\ ); 55102、 判斷(vA，圪，…，)計數是否大於最小支持度2，如果"是"，則轉S5103，否則轉 S5104 ； 55103、 保留該項; 55104、 刪除計數不大於2的項； 55105、 判斷是否掃描1階候選項目集中所有項('，…,)，如果"是"，則轉S511，否 則轉S5101。
【文檔編號】G06F11/36GK104050086SQ201410310475
【公開日】2014年9月17日 申請日期:2014年7月1日 優先權日:2014年7月1日
【發明者】張衛豐, 陸子南, 王雲, 王子元 申請人:南京郵電大學