一種聯合差異性隨機測試方法

2023-07-11 06:11:31

專利名稱：一種聯合差異性隨機測試方法
技術領域：
本發明屬於軟體測試領域尤其是自動化測試領域，涉及聯合差異性隨機測試技術CAT (Co-diversified rAndom Testing),用於高效率的生成測試用例集,從而實現對程序的有效測試，為一種聯合程序白盒和黑盒信息差異性的聯合差異性隨機測試方法。
背景技術：
隨機測試RT是一個簡單的自動化黑盒測試用例生成技術，容易實現，廣泛應用於原始碼和規格說明缺失的情景。RT產生測試用例由於完全隨機缺少目的性，只保證了測試的效率(Efficiency)而無法保證有效性(Effectiveness)。在眾多對RT的提高或改進的方法中，比較著名的是由T. Y. Chen等在2004年提出了的自適應隨機測試ART。同樣是黑盒測試技術，ART引入測試用例在輸入域上的歐幾裡得距離來衡量測試用例間的差異性，並通過這個差異性挑選隨機生成的測試用例來構造整個測試用例集，以增強隨機測試的有效性。符號執行是由自J.C.King在1976年提出的，其基本思想就是使用符號值而不是真實值來作為程序的輸入。符號執行中一個基本的概念就是路徑條件PC(PathCondition),路徑條件PC是一系列謂詞的析取(conjunction),輸入變量只有滿足一條路徑的PC條件，才能通過這條路徑。其中，構建PC非常具有挑戰性，即使一個分支語句只包含一個複雜的數據結構。而謂詞表達PI (Predicate Interpretation, PI)是一個PC的子表達式，一個分支的PI可以跳過其他分支語句簡單的獲得。

發明內容
本發明所要解決的技術問題是現有的測試用例生成方法中黑盒測試方法具有很高的效率，但是不能保證測試用例的有效性；白盒測試方法雖然能生成有效的測試用例，但是由於複雜性問題無法保證測試用例生成的效率。因此需要一種兼顧高效率和高有效性的測試用例生成技術。本發明的技術方案為一種聯合差異性隨機測試方法，對待測試程序，隨機生成測試用例，在其中挑選測試用例，得到最終測試用例集，包括以下步驟I)隨機生成初始測試用例集Tu = {t0}；2)獲得待測程序的謂詞表達集合PI {Pl，P2,…，pn}首先使用開源工具Soot生成中間代碼的數據流圖，並使用反向數據流分析計算謂詞表達集合PI，即從數據流圖的出口沿數據流邊反向依次分析各個基本塊或每個語句，PI初始為空集，在分析過程中根據每個語句的傳遞函數fs增加或修改謂詞表達集合PI，對應處理如下a)如果語句s不是賦值語句也不是條件語句，則fs為單元函數，謂詞表達集合PI不變；b)如果語句s是一條條件語句，則將其中的謂詞語句加入到謂詞表達集合PI中fs (χ) = X U gens,其中gens表示這個條件語句中的謂詞集合，X表示原謂詞表達集合PI ；c)如果語句s是對變量V的賦值語句V = g(y1；y2,…)，那麼用V的表達式替換謂詞集合中的所有變量V fs(pi (V)) = pi (g(y1；y2,…))，其中賦值語句v = g(y1；y2,…)
將變量V賦予關於變量Yi (i = 1,2,......)的表達式，g是關於變量Yi (i = 1,2,......)的
任意一個函數，pi (V)表示關於V的謂詞表達式，pi (g(y1 I2,…))表示將V替換為g(yp12，…)後的謂詞表達式；3)若沒有達到預先定義的測試標準，則繼續步驟4)，否則結束，Tu就是最終的測試用例集，所述測試標準為測試人員根據測試要求預先設定的覆蓋程度，用百分比表示；4)隨機生成k個候選測試用例t1 t2, ···, tk,組成候選測試用例集Tr, Tr = It1,t2, ···, tk},對每一個候選測試用例& e Tr, i = 1,2,…k,計算bdi = min{B(ti, t」)}以及edi = miniEUytj)},其中t」e Tiubdi表示測試用例h到Tu中各個測試用例分支距離的最小值，edi表示測試用例\到Tu中各個測試用例的最小歐幾裡得距離；5)根據候選測試用例\到測試用例集Tu的分支距離和歐幾裡得距離，從候選測試用例集Tr中挑選一個測試用例用作為新的測試用例加入到測試用例集Tu中，具體為首先計算各個候選測試用例\與測試用例集Tu中測試用例的最小分支距離bdp優先選擇最小分支距離最大的測試用例，即若測試用例集Tu中不包含最小分支距離bdi最大的測試用例，則選用該用例，若測試用例集Tu中已包含，則選擇最小分支距離bdi第二大的測試用例，以此類推；若具有最小分支距離bdi最大值的測試用例有兩個以上，則判斷最小歐幾裡得距離θφ，優先選擇最小歐幾裡得距離edi最大的候選測試用例ti;若測試用例集Tu中已包含此測試用例，則選擇最小分支距離bdi第二大的測試用例，以此類推；將選擇的測試用例加入Tu中，回到步驟3)，依此不斷選擇新的測試用例，直到滿足測試標準。步驟5)中，測試用例\到Tu中各個測試用例分支距離的最小值bdi的計算如下將候選測試用例\帶入謂詞表達集合PI中的每一個謂詞表達式，若其結果為真，則為1，否則為0，每一個測試用例得到一個長度為謂詞表達集合PI的元素數目的01序列；對測試用例集Tu中的每一個測試用例做同樣計算，得到測試用例集Tu中各測試用例的01序列，兩個不同測試用例之間的分支距離B(ti; tj)為其01序列的漢明距離，由此計算bdi ；測試用例\到Tu中各個測試用例的最小歐幾裡得距離喊的計算如下設測試用例\ = (v1； V2,…，vq), V,對應待測程序的第q個函數參數，測試用例集Tu中的測試用例\ = (B1, a2，…，aq)，aq對應待測程序的第q個函數參數，則兩個測試用例的歐幾裡德距離為-.EitiJ) = ^(ν,-α,)2，由此計算edi。本發明通過PI識別隨機生成的測試用例之間在程序內部結構上的差異性，通過測試用例間的歐幾裡得距離來識別測試用例在輸入域上的差異性，然後聯合這二者的差異，從而高效率地生成有效的測試用例集。對於一個隨機生成的測試用例集Tr，對任意的ti e Tr，與每一個\ e Tu進行比較，計算每一個PI的值，以及由此得到的B(ti; tj);此外計算E(ti; tp，聯合B(ti; tj)和E(ti; tj)衡量測試用例\與已使用的測試用例間的差別，從而挑選更加有效的測試用例。 本發明為一種聯合差異性隨機測試技術CAT，與現有的隨機測試技術相比，在選擇測試用例時加入了程序的謂詞信息，從而在隨機生成的大量測試用例中挑選更加有效的測試用例，避免了盲目選擇。此外本發明的處理計算簡單，雖然加入了程序謂詞信息，但沒有加入所有的程序信息，避免了白盒測試中對程序的大量分析，如符號執行中路徑約束的計算，從而提高了生成測試用例的效率。綜上所述，本發明在避免大量計算的情況下，高效率的選擇高有效性的隨機測試用例，綜合了黑盒測試與白盒測試的優點，為現有的測試技術提供了新的思路。


圖I為本發明的流程示意圖。
具體實施例方式
如圖I，本發明的步驟如下I)隨機生成初始測試用例集Tu = {t0}；2)獲得程序的謂詞表達集合PI {Pl，P2,…，pn}首先使用開源工具Soot (http://www. sable, mcgill. ca/soot/)生成中間代碼的數據流圖，並使用後向數據流分析計算謂詞表達集合PI，即從數據流圖的出口沿數據流邊反向依次分析各個基本塊或每個語句。程序中，每條語句的傳遞函數描述了這個語句的作用，每條語句的傳遞函數仁，謂詞表達集合PI初始為空集，在分析過程中根據每個語句的傳遞函數fs增加或修改謂詞表達集合PI，對應處理如下a)如果語句s不是賦值語句也不是條件語句，則fs為單元函數，謂詞表達集合PI不變；b)如果語句s是一條條件語句，則將其中的謂詞語句加入到謂詞表達集合PI中fs (χ) = X U gens,其中gens表示這個條件語句中的謂詞集合，χ表示原謂詞表達集合PI ；c)如果語句s是對變量V的賦值語句V = g(y1；y2,…)，那麼用V的表達式替換謂詞集合中的所有變量V fs(pi (V)) = pi (g(y1；y2,…))，其中賦值語句v = g(y1；y2,…)
將變量V賦予關於變量Yi (i = 1,2,......)的表達式，g是關於變量Yi (i = 1,2,......)的
任意一個函數，pi (V)表示關於V的謂詞表達式，pi (g(y1 I2,…))表示將V替換為g(yp12，…)後的謂詞表達式；3)若沒有達到預先定義的測試標準，則繼續步驟4)，否則結束，Tu就是最終的測試用例集，所述測試標準為測試人員根據測試要求預先設定的覆蓋程度，用百分比表示，如50%路徑覆蓋或50%條件覆蓋等；4)隨機生成k個候選測試用例t1; t2, ···, tk,組成候選測試用例集Tr, Tr = It1,t2, ···, tk},對每一個候選測試用例& e Tr, i = 1,2,…k,計算bdi = min{B(ti, t」)}以及edi = min{E(ti, t」)},其中t」e Tu, bdi表示測試用例h到Tu中各個測試用例分支距離的最小值，edi表示測試用例t到Tu中各個測試用例的最小歐幾裡得距離；計算方法如下將每一個候選測試用例t帶入謂詞表達集合PI中的每一個謂詞表達式，若其結果為真，則為1，否則為0，每一個測試用例得到一個長度為謂詞表達集合PI元素數值的01序列；同理，Tu中的每一個測試用例也具有這樣的01序列；兩個不同測試用例之間的分支距離為其01序列的漢明距離，歐幾裡得距離的大小通過下面的公式計算設測試用例h = (V1, V2, ···, vq) , Vq對應待測程序的第q個函數參數，另一測試用例tj = (B1, a2，…，aq)，aq對應待測程序的第q個函數參數，則兩個測試用例的歐幾裡德距離為
權利要求
1.一種聯合差異性隨機測試方法，其特徵是對待測試程序，隨機生成測試用例，在其中挑選測試用例，得到最終測試用例集，包括以下步驟 1)隨機生成初始測試用例集Tu= {t0}； 2)獲得待測程序的謂詞表達集合PI:{P1，P2，...，pj 首先使用開源工具Soot生成中間代碼的數據流圖，並使用反向數據流分析計算謂詞表達集合PI，即從數據流圖的出口沿數據流邊反向依次分析各個基本塊或每個語句，PI初始為空集，在分析過程中根據每個語句的傳遞函數fs增加或修改謂詞表達集合PI，對應處理如下 a)如果語句s不是賦值語句也不是條件語句，則fs為單元函數，謂詞表達集合PI不變； b)如果語句s是一條條件語句，則將其中的謂詞語句加入到謂詞表達集合PI中fs(x)=X U gens,其中gens表示這個條件語句中的謂詞集合，x表示原謂詞表達集合PI ； c)如果語句s是對變量V的賦值語句V= g(y17y2,…)，那麼用v的表達式替換謂詞集合中的所有變量V :fs(pi (V)) = pi (g(y1 I2, ···))，其中賦值語句V = g(y1; y2,…)將變量V賦予關於變量Yi (i = 1,2,......)的表達式，g是關於變量yji = 1，2，......)的任意一個函數，pi (V)表示關於V的謂詞表達式，pi (g(y1 I2,…))表示將V替換為g(yp12，…)後的謂詞表達式； 3)若沒有達到預先定義的測試標準，則繼續步驟4)，否則結束，Tu就是最終的測試用例集，所述測試標準為測試人員根據測試要求預先設定的覆蓋程度，用百分比表示； 4)隨機生成k個候選測試用例Lt2,"^tk,組成候選測試用例集Tr,Tr = Itpt2,…,tk}，對每一個候選測試用例h e Tr, i = 1,2,…k,計算bdi =以及θφ =min{E(ti, tj)},其中t」e Tu, bdi表示測試用例h到Tu中各個測試用例分支距離的最小值，ed,表示測試用例\到Tu中各個測試用例的最小歐幾裡得距離； 5)根據候選測試用例ti到測試用例集Tu的分支距離和歐幾裡得距離，從候選測試用例集Tr中挑選一個測試用例用作為新的測試用例加入到測試用例集Tu中，具體為首先計算各個候選測試用例\與測試用例集Tu中測試用例的最小分支距離bdp優先選擇最小分支距離最大的測試用例，即若測試用例集Tu中不包含最小分支距離bdi最大的測試用例，則選用該用例，若測試用例集Tu中已包含，則選擇最小分支距離bdi第二大的測試用例，以此類推；若具有最小分支距離bdi最大值的測試用例有兩個以上，則判斷最小歐幾裡得距離edp優先選擇最小歐幾裡得距離edi最大的候選測試用例ti;若測試用例集Tu中已包含此測試用例，則選擇最小分支距離bdi第二大的測試用例，以此類推；將選擇的測試用例加入Tu中，回到步驟3)，依此不斷選擇新的測試用例，直到滿足測試標準。
2.根據權利要求I所述的一種聯合差異性隨機測試方法，其特徵是步驟5)中，測試用例\到Tu中各個測試用例分支距離的最小值bdi的計算如下 將候選測試用例\帶入謂詞表達集合PI中的每一個謂詞表達式，若其結果為真，則為、1，否則為0，每一個測試用例得到一個長度為謂詞表達集合PI的元素數目的01序列；對測試用例集Tu中的每一個測試用例做同樣計算，得到測試用例集Tu中各測試用例的01序列，兩個不同測試用例之間的分支距離B(ti; tj)為其01序列的漢明距離，由此計算bdi ； 測試用例\到Tu中各個測試用例的最小歐幾裡得距離edi的計算如下設測試用例ti= (v1； V2,…，V,)，V,對應待測程序的第q個函數參數，測試用例集Tu中的測試用例h= (a1；a2,…，a,)，a,對應待測程序的第q個函數參數， 則兩個測試用例的歐幾裡德距離為
全文摘要
一種聯合差異性隨機測試方法，通過PI識別隨機生成的測試用例之間在程序內部結構上的差異性，通過測試用例間的歐幾裡得距離來識別測試用例在輸入域上的差異性，然後聯合這二者的差異，高效率地生成有效的測試用例集，為一種結合黑盒測試技術和白盒測試技術的自動化隨機測試技術，本發明既改善了ART忽略程序結構所導致的測試用例冗餘問題，也緩解了符號執行中的PC路徑的複雜性問題，兼顧了軟體測試中測試用例生成的高效率和高有效性。
文檔編號G06F11/36GK102629229SQ20121005269
公開日2012年8月8日 申請日期2012年3月2日 優先權日2012年3月2日
發明者張智軼, 徐寶文, 時清凱, 陳振宇 申請人:南京大學