[發明專利]基于矩陣重復度的最小組合測試用例生成方法

無效

• 申請號: 201310556759.3
• 申請日: 2013-11-11
• 公開（公告）號: CN103631714A
• 公開（公告）日: 2014-03-12
• 發明（設計）人: 陳錦富;蘇晨飛;趙小磊;陳加梅;楊鶴標
• 申請（專利權）人: 江蘇大學
• 主分類號: G06F11/36
• 分類號: G06F11/36
• 代理公司: 南京知識律師事務所 32207
• 代理人: 盧亞麗

技術領域

本發明屬于軟件測試中的組合測試用例生成技術領域，涉及一種基于矩陣重復度的最小組合測試用例生成方法。?

背景技術

通常軟件系統是一個復雜的邏輯系統，其正常運行受到多因素的影響，這些因素包含系統配置、內部事件、外部輸入及運行環境等，可以抽象表示為軟件系統的輸入因素。這些因素的相互作用通常會導致軟件的失效，在實際軟件測試中，可以通過測試這些系統參數的所有組合來對軟件系統進行充分的測試。對于一個具有n個輸入參數（因素），每個因素的取值個數為v₁,v₂,…,v_n的軟件系統，根據輸入參數組合完全測試這個軟件系統需要??????????????????????????????????????????????????個測試用例，對于一般的測試系統而言，這個組合是一個非常龐大的數字。為了盡可能少地使用測試用例來有效地更早檢測出軟件錯誤，人們提出了基于組合覆蓋的軟件測試方法，簡稱組合測試（Combination?Testing）。在工業界，IBM、微軟和Bell實驗室等國際知名企業都開發了相應的組合測試工具，這些組合測試工具在測試用例生成算法方面，普遍采用速度較快的貪心算法。貪心算法的思想是從空矩陣開始，逐行或者逐列擴展矩陣，直到所有的t組合都被覆蓋。按照擴展方式的不同，可以分成一維擴展和二維擴展兩類。一維擴展的算法框架最初由商業測試用例生成工具AETG實現，AETG的貪心策略是非確定的，所以多次運行AETG得到的測試用例結果可能不同，故難以保證生成的組合測試用例集最小化，且結果不穩定。微軟開發的工具PICT采用的方法類似AETG的方法，但是PICT的貪心策略是確定性的，多次運行PICT的結果相同，但同樣無法保證其生成的組合測試用例集最小化。在二維擴展的方式中，Lei等人提出了IPO(in-parameter-order)算法，這種算法主要針對成對測試，最初只能產生成對覆蓋數組，后來Lei等人將這種算法擴展，得到了一種能產生任意t組合測試用例的算法IPOG。IPOG算法雖然是貪心算法，但它采用了指數級復雜度的方法來選擇最少行進行垂直擴展，故在處理大規模實例時仍然需要花費大量時間。?

為了進一步減少組合測試用例數量，節約軟件測試成本。我們把軟件輸入空間轉化成矩陣形式，然后通過判斷矩陣中測試用例行間的重復度來生成最小覆蓋解矩陣，最終生成最小的組合測試用例集。?

發明內容

上面所述的PICT、IPOG等貪心算法雖然效率較高，但是生成的測試用例數量比較多。?本發明針對目前方法生成的測試用例數量較多的缺點，提出了一種基于矩陣重復度的最小組合測試用例生成方法，在保證組合覆蓋的覆蓋率不減少的情況下，使得生成的測試用例條數更少，從而提高軟件測試的效率，降低軟件測試的成本。并且將本方法的實驗結果與現有的組合測試工具ACTS和PICT的結果進行比較，驗證了提出方法的有效性和生成的測試用例個數少的優勢。?

本發明的構思如下：?

步驟1，根據因素個數和每個因素取值個數生成輸入矩陣A；?

步驟2，采用比較重復度的方法生成初步的解矩陣B；?

步驟3，驗證生成的解矩陣B是否能覆蓋所有的因素組合，將沒有覆蓋的因素組合記錄到矩陣C中；?

步驟4，采用貪心算法的思想覆蓋矩陣C，得到最終的解矩陣B。?

上述步驟1的具體步驟如下：?

步驟1.1，根據因素個數確定輸入矩陣A的列數和每個因素的最大值；?

步驟1.2，將每個因素置為初始值，將這一行加入到輸入矩陣A中；?

步驟1.3，因素的最低位加1，如果大于該位最大值，向前進位；?

步驟1.4，如果最高位小于或者等于最高位的最大值，將剛剛生成的一行加入到輸出矩陣A中，然后轉到步驟1.3，如果最高位大于最高位的最大值，輸出得到的輸入矩陣A，算法結束。?

上述步驟1.1-步驟1.4中，每個因數的初始值和取值范圍作如下約定，第1個因數的初始值為100，如果第一個因素的取值個數為3，則第1個因數的取值范圍是100～102的整數，最大值為102，第二個因數的初始值為200，第三個初始值為300，以此類推。?

上述步驟2的具體步驟如下：?

步驟2.1，初始化解矩陣B，將步驟1中得到的輸入矩陣A的第一行加入到解矩陣B中；?

步驟2.2，將輸入矩陣A的第一行設為當前處理行；?