基於語句覆蓋和缺陷檢測的多目標測試數據縮減方法

2023-05-31 08:24:36 1

基於語句覆蓋和缺陷檢測的多目標測試數據縮減方法
【專利摘要】本發明提出一種基於語句覆蓋和缺陷檢測的多目標測試數據縮減方法，目的是有效減少測試數據的冗餘度，提高軟體測試的效率。首先，將測試數據縮減問題轉化為多目標優化問題，優化的目標是使得測試數據集的語句覆蓋率和缺陷檢測率儘可能地多，並且測試數據的個數儘可能地少；然後明確各個目標函數，建立多目標優化模型；最後提出一種遺傳算法對該問題進行求解。該方法能夠找到有效的測試數據，使其同時滿足滿足語句覆蓋率、缺陷檢測率的最大化，測試數據個數最小化。
【專利說明】基於語句覆蓋和缺陷檢測的多目標測試數據縮減方法

【技術領域】
[0001] 本發明涉及計算機軟體測試領域，設計了一種基於語句覆蓋和缺陷檢測的多目標 測試數據縮減及進化求解方法。該方法區別於已有方法的特色在於，基於語句覆蓋和缺陷 檢測建立測試數據縮減問題的多目標優化模型，從而保證縮減後的測試數據具有較好的質 量；另外，給出一種遺傳算法來對上述模型進行求解。該方法不但可以有效減少測試數據的 數量，還可以保證縮減後的測試數據具有較好的檢錯能力，對提高軟體測試的效率和質量 具有重要意義。

【背景技術】
[0002] 軟體測試的目的是為了發現軟體中存在的缺陷甚至錯誤，從而提高軟體的質量。 而進行軟體測試的核心，是採用有針對性的理論和方法，生成有效的測試數據，以滿足既定 的測試充分性準則。但是，傳統方法生成的測試數據往往存在大量冗餘。測試數據之所以會 出現冗餘，是因為覆蓋某一測試目標的測試數據往往同時覆蓋其他測試目標。另外，在回歸 測試中，會根據新的測試要求不斷補充大量測試數據，從而導致測試用例的數量不斷攀升。
[0003] 測試數據冗餘是軟體測試領域面臨的一個重要難題。如果能夠找到更少的測試數 據滿足既定的測試要求，那麼，無疑將會提高軟體測試的效率，因為這可以減少執行測試數 據集所需的時間，從而降低測試成本。為此，人們提出多種測試數據進行縮減策略，從而達 到減少冗餘、提高軟體測試效率的目的。
[0004] 一般來說，測試數據縮減的思想是：按照某種覆蓋準則，找到原有測試數據集的子 集，使得該子集也能夠覆蓋所有測試目標，該子集稱為原有測試數據集的代表集。如果一個 測試數據集的任何真子集都不能滿足既定的測試準則，那麼，稱該測試數據集為最優集或 最小集。
[0005] Leung和White證明，尋找覆蓋所有測試目標的最小測試數據集屬於NP困難問題。 所以，人們往往尋找該問題的近似解。Harrold等提出一種啟發式算法縮減測試數據集，該 方法首先根據測試數據和測試目標的關聯矩陣對測試需求分類，再根據測試需求的等級， 按照一定順序選擇測試數據。Chen等提出另外一種啟發式方法，解決測試數據縮減問題，該 方法用到3種策略，分別是貪心策略、必要性策略和一對一策略，其中，貪心策略優先選擇 覆蓋更多測試目標的測試數據；必要性策略選擇必不可少的測試數據；而一對一策略選擇 只能由一個測試數據覆蓋的測試目標。Lin等改進了 Harrold的方法，區分具有相同優先級 的測試數據。
[0006] 解決測試數據冗餘問題的另一種方法，是在生成測試數據的同時，最小化測試數 據集。Ding等提出一種面向連續和並發程序的測試數據生成方法，該方法首先根據條件 語句，將程序的輸入域劃分為若干子區域；然後，在程序的每個輸出節點建立表達式，包括： 相應的輸入變量、到達的條件，以及一些"與、或"操作符號等；最後，根據表達式生成相應的 測試數據。實驗結果表明，該方法生成的測試數據避免了大量的冗餘。Li等提出一種利用 語句優先級選擇測試目標的語句覆蓋測試數據生成方法，該方法首先按照某種準則確定語 句的優先級；然後，根據語句的優先級選擇目標路徑，使得該路徑能夠覆蓋更多高優先級的 目標語句。
[0007] 一般情況下，人們把測試數據縮減看成單目標優化問題，優化的目標是測試數據 個數最少。但是，也有把測試數據縮減和其它目標相結合的方法，如：在Υ〇〇和Harman的 工作中，優化的目標包括：代碼覆蓋、以前的排錯記錄和執行該測試數據所需要的時間等。 Black等利用線性規劃縮減測試數據，該方法包含兩個模型，第一個優化的目標是測試數據 個數最少；第二個優化的目標有兩個，一個是測試數據個數最少；另一個是測試數據累計 覆蓋的測試目標最多。
[0008] 與測試數據縮減相近的另一工作是測試數據選擇，二者都是要找到原來的測試數 據集的代表集，不同的是代表集滿足的準則不同。測試數據縮減的準則是代表集能夠覆蓋 既定的測試目標；而測試數據選擇主要針對回歸測試，考察代表集能否覆蓋程序中修改的 部分。
[0009] 現有方法對測試數據進行縮減時，一般只要求縮減後的測試數據滿足特定覆蓋要 求。雖然也有利用多目標方法解決測試數據縮減問題的，但很少考慮縮減後測試數據的檢 錯能力。因此，已有測試數據縮減方法雖然可以降低測試數據的數量，但往往會消弱其缺陷 檢測能力。
[0010] 語句覆蓋是最基本的測試覆蓋準則，因此，本發明把語句覆蓋率作為衡量測試數 據質量的第一個目標。另外，軟體測試的核心是為了查找缺陷。測試數據發現的錯誤越多， 對應測試數據的質量也就越高。因此，本發明把缺陷檢測率作為衡量測試數據質量的第二 個目標。最後，為了降低測試成本，第三個目標是希望縮減後的測試數據數量越少越好。鑑 於此，本發明建立了測試縮減問題的多目標優化模型，並給出其進化求解方法。


【發明內容】

[0011] 本發明給出一種基於語句覆蓋和缺陷檢測的多目標測試數據縮減方法。首先，把 測試數據縮減問題轉化為多目標優化問題，優化的目標分別語句覆蓋率、缺陷檢測率和縮 減率。在此基礎之上，設計了一種遺傳算法對上述多目標優化模型進行求解。最後的實驗 結果表明，本發明提出的方法不但可以大幅度縮減測試數據的數量，同時可以保證其語句 覆蓋率和檢錯能力不會降低。
[0012] 本發明所要解決的技術問題：基於語句覆蓋和缺陷檢測建立測試數據縮減問題的 多目標優化模型，從而保證縮減後的測試數據具有較好的質量；提出一種求解上述優化問 題的遺傳算法，從而保證該優化問題求解的效率。
[0013] 本發明的技術解決方案：一種基於語句覆蓋和缺陷檢測的測試數據縮減方法，其 特徵包含以下步驟：
[0014] 步驟1.把測試數據縮減問題轉化為多目標優化問題
[0015] 首先，明確我們所要解決的問題。假設被測程序為G，其輸入空間為D，要求覆蓋 的目標語句集為S = {sp s2,…，sm}，其中，m為目標語句的個數。已有測試數據集為Ω = {Xl，x2，…，xn}，其中Xi eD。假設Ω能夠覆蓋目標語句集S的所有目標語句。現在要解決 的問題可描述為：找到測試數據集Ω的一個子集Ω*，使其儘可能滿足以下幾個目標要求： 能夠覆蓋的目標語句的個數儘可能的多，即語句覆蓋率最大化；檢測到的缺陷個數儘可能 的多，即缺陷檢測率最大化；且包含的測試數據個數儘可能的少，也就是說測試數據集最小 化。
[0016] 因此，我們需要得到滿足上述目標的一個子集Ω*。為了有效解決該問題，需要建 立語句覆蓋率函數、缺陷檢測率函數以及縮減率函數，從而本發明將測試數據縮減問題建 模為一個多目標優化問題。
[0017] 步驟2.明確測試數據縮減問題各個目標函數，建立多目標優化模型
[0018] 我們在對測試數據集進行約簡時，同時考慮三個因素，即保證測試數據得到約簡， 並且測試數據集的語句覆蓋率和缺陷檢測能力不會降低。因此，所建立的優化模型包含三 個目標函數，分別是語句覆蓋率、缺陷檢測率和測試數據縮減率。
[0019] (1)語句覆蓋率
[0020] 語句覆蓋準則要求測試數據集能夠覆蓋所有的目標語句。若Ω *覆蓋了目標語句 集S中的t條語句，那麼，Ω *對S的語句覆蓋率可定義為：
[0021]

【權利要求】
1. 基於語句覆蓋和缺陷檢測的多目標測試數據縮減方法，其特徵在於如下步驟： 步驟1.1:把測試數據縮減問題轉化為多目標優化問題，優化目標是能夠覆蓋的目標 語句的個數儘可能的多；檢測到的缺陷個數儘可能的多；包含的測試數據個數儘可能的 少，也就是說測試數據集最小化。 步驟1. 2 :明確測試數據縮減問題的各個目標函數，建立多目標優化模型。 步驟1. 3 :利用遺傳算法對基於語句覆蓋和缺陷檢測的多目標測試數據縮減問題進化 求解。
2. 權利要求1中步驟1. 1所述的把測試數據縮減問題轉化為多目標優化問題，其特徵 在於本發明優化的目標是使得測試數據集的語句覆蓋率和檢錯率不會降低，以及使得測試 數據的個數儘可能的少。
3. 權利要求1中步驟1. 2所述的明確測試數據縮減問題各個目標函數，建立多目標數 學模型，其特徵在於將目標函數建立為多目標優化模型。
4. 權利要求1中步驟1. 3所述利用遺傳算法進化求解，其特徵在於以下步驟： 步驟4. 1 :個體編碼方法 設是待求問題（4)的一個候選解，下面將給出的編碼方法。對於原有測試數 據集Q = {x,，Xa…，xj，令
則可得到一個長為n的（0-1)串a a2，…，an。可以看出，（0-1)串Yi, y2，…， 和子集是一一對應的關係。因此，我們可以使用長度為n的（0-1)串Yl，Y2，…，Y n來表不個體Q*。這樣表不，為遺傳操作的順利實施奠定了基礎。 步驟4. 2 :種群初始化 隨機生成m個長為n的（0-1)字符串，分別記為，…，。每個字符串是一個個 體，m個個體組成一個初始種群。 步驟4. 3 :個體評價方法 由於（4)式建立的是一個多目標優化問題，需要給出個體的評價方法。由式（1)、（2) 和⑶可知，目標函數&(〇*)，&⑴*)和f3(Q*)的取值都在0和1之間，因此，不需要對 目標函數進行歸一化處理。 另外，由於和&(0*)是最大化問題，f3(Q*)是最小化問題，現在統一轉化 為最小化問題。令 Q *) = 14 ( Q *)，f2 ' （ Q *) = l-f2 ( Q *)。則 Q *)和 ⑴*)的值都在〇和1之間，且對心⑴*)和^⑴*)是最大化問題，等價於對f/⑴*) 和(Q*)的最小化問題。 最後，將f/ (Q*)，f2' (Q*)和f3(Q*)進行加權組合，得到個體Q*的適應值函數 如下： fit(Q*) = c〇1f1(Q>ll<) + c〇3f3(^*) (6) 其中，〇2, 〇3為權重係數。個體的適應值越小，就越接近我們期望的解。 步驟4. 4 :進化策略 由於每個個體都是一個（〇，1)字符串，可以採用傳統的進化算子對個體實施遺傳操 作。本文算法中，個體交叉算子為單點交叉，變異算子為單點變異，選擇算子採用輪盤賭選 擇。 步驟4. 5 :算法步驟 基於前面提出的個體編碼及適應值計算策略，使用遺傳算法來求解式（4)的步驟如 下： (1) 遺傳算法的參數設置及個體編碼 確定算法的控制參數，包括種群規模、算法終止代數、選擇概率、交叉概率，以及變異概 率等。種群的個體為已有測試數據集的子集，並按照第4. 1小節給出的方法進行編碼。 (2) 種群初始化 隨機生成包含若干個體的初始種群A，進化代數t = 1。 (3) 個體適應值計算 對第i代種群％，按照（6)式計算每個個體的適應值。個體適應值越小，說明該個體越 接近最優解，被遺傳到下一代的概率也就越大。 (4) 判斷算法終止條件是否滿足 算法終止的條件是，連續進化若干代後沒有出現更優個體，或者種群進化代數超過設 定的最大值。若終止條件被滿足，轉步驟6 ;否則，轉步驟5。 (5) 進行遺傳操作 對個體實施選擇、交叉和變異算子；令i = i+1，轉步驟3。 (6) 停止進化，輸出結果。
【文檔編號】G06F11/36GK104281522SQ201410543046
【公開日】2015年1月14日 申請日期:2014年10月14日 優先權日:2014年10月14日
【發明者】鞏敦衛, 姚香娟, 李彬, 胡雷, 陳永偉 申請人:中國礦業大學