一種基於遺傳算法的數據流測試用例自動生成方法
2023-10-31 05:36:57 1
一種基於遺傳算法的數據流測試用例自動生成方法
【專利摘要】本發明公開了一種基於遺傳算法的數據流測試用例自動生成方法。目前基於遺傳算法的數據流測試用例自動生成技術中，遺傳算法的交叉、變異點隨機選取在個體基因中的任意位置，產生優良基因的同時也存在破壞已有優良基因的可能；子代種群的個體最大適應度值無論是否大於父代的個體最大適應度值，都向下繼續遺傳，延長了迭代過程。本發明在計算適應度函數時找到不滿足目標路徑的具體分支，利用該分支的結構信息約束遺傳算法交叉、變異操作的範圍，同時通過比較子代與父代種群中個體的最大適應度值，拋棄那些低於父代適應度值的子代，從而確保了優良基因的傳遞，降低了迭代次數，提高了計算效率。
【專利說明】一種基於遺傳算法的數據流測試用例自動生成方法
【技術領域】
[0001]本發明涉及一種測試用例自動生成方法，尤其涉及一種基於遺傳算法的數據流測試用例自動生成方法，屬於軟體結構測試技術。
【背景技術】
[0002]數據流測試是一種基於代碼的白盒測試技術，使用程序中的數據流關係來指導測試者選取測試用例。即可以選擇一定的測試用例，使程序按照某個變量的定義-使用路徑執行，通過檢查執行結果是否與預期的相符來發現程序的錯誤。相對控制流，基於數據流的軟體測試考察了每個數據的流向，對程序的執行更深入，更有利於對代碼的測試。
[0003]測試用例生成是軟體測試中的關鍵環節，其實現對於軟體測試過程的自動化具有重要意義。因此，隨著數據流測試技術的深入應用，研究面向數據流的測試用例自動生成方法十分必要。大量研究表明，遺傳算法採用概率化的搜索方式，具有全局搜索優化能力強，能自學習、自適應，在測試用例自動生成中取得了較好的效果。文獻《基於數據流分析的測試用例自動生成技術》、《基於數據流的測試數據自動生成技術研究》將遺傳算法與數據流技術相結合，依據數據流信息對測試用例進行評價，實現測試用例的自動生成。但是目前基於遺傳算法的數據流測試用例自動生成技術存在如下問題:遺傳算法在進行交叉、變異操作時，交叉、變異點可能選取在個體基因中的任意位置，交叉、變異操作產生優良基因的同時也存在破壞已有優良基因的可能；在迭代過程中，沒有對子代與父代種群中個體的最大適應度值進行比較，導致無論子代是否優於父代，都向下逐代遺傳。這些問題導致在生成測試用例時，迭代次數多，算法效率低。
【發明內容】
[0004]本發明解決的技術問題是:克服現有技術的不足，提供一種基於遺傳算法的數據流測試用例自動生成方法，本發明根據被測程序的結構信息約束遺傳算法交叉、變異操作的範圍，同時在迭代過程中拋棄種群最大適應度函數值不大於父代種群的子代，從而確保了優良基因的傳遞，降低了迭代次數，提高了算法效率。
[0005]本發明的技術方案是:一種基於遺傳算法的數據流測試用例自動生成方法，步驟如下:
[0006](I)針對被測程序P中的一個定義使用對(def, use),找出由入口節點Ii1開始並且經過定義節點def的使用節點use的支配路徑domdef Oi1, use)；
[0007](2)根據設定的遺傳算法參數和輸入變量的取值範圍、精度，隨機生成初始種群InitPop,並賦值給當前種群 CurrentPop,即 CurrentPop=InitPop,同時將 CurrentPop 賦值給父代種群 ParentPop,即 ParentPop=CurrentPop ；
[0008](3)將當前種群CurrentPop中的每個個體輸入被測程序P，檢查實際路徑Pa對支配路徑domdef Oi1, use)的覆蓋程度；
[0009](4)若當前種群CurrentPop中的所有個體執行完後，domdef Oi1, use)中仍有節點沒有被覆蓋，且當前遺傳代數沒有達到設定的最大遺傳代數，則執行(5)- (7)，否則執行(8);
[0010](5)計算當前種群CurrentPop中每個個體的適應度函數值,將其中最大值賦值給當前種群CurrentPop中個體的最大適應度值fmax_cur,當CurrentPop種群中個體的最大適應度值fmax_cur不大於父代種群中個體的最大適應度值fmax_old時,拋棄當前種群，將父代種群再賦值給CurrentPop,即CurrentPop=ParentPop,其中fmax_old初始值為O,然後執行(6);當CurrentPop種群中個體的最大適應度值fmax_cur大於父代種群中個體的最大適應度值fmax_old時,更新父代種群中個體的最大適應度值,即fmax_old=fmax_cur,然後執行(6)；
[0011](6)依據適應度函數值，根據程序結構信息對當前種群CurrentPop利用遺傳算法進行選擇、交叉和變異操作得到新的種群NewPop ；
[0012](7)將當前種群CurrentPop賦值給父代種群的副本ParentPop,即 ParentPop=CurrentPop,將新種群 NewPop 賦值給當前種群 CurrentPop,CurrentPop=NewPop,重複步驟(3)-(4)；
[0013](8)若在最大遺傳代數之內找到了覆蓋Cbmdef(I^use)中所有節點的測試用例，則輸出該符合要求的測試用例；否則返回步驟(2)重新設定遺傳算法參數，直到生成符合要求的測試用例。
[0014]所述步驟(1)中找出支配路徑domdef Oi1, use)的方法為:
[0015]domdef (Ii1, use) =dom (Ii1, def) U dom(def, use)
[0016]其中，domOv def)表示由入口節點Ii1到定義節點def所必須經過的節點組成的路徑，dom(def, use)表示由定義節點def到使用節點use所必須經過的節點組成的路徑。
[0017]所述步驟(5)中計算個體適應度函數值的公式為:
L
[0018]/= —
ηι
[0019]其中，m表示支配路徑Clomdef (叫，use)的長度，Ls為程序實際執行路徑Pa從入口點Ii1開始覆蓋支配路徑domdef Oi1, use)的連續路徑長度。
[0020]所述步驟(6)中根據程序結構信息對當前種群CurrentPop利用遺傳算法進行選擇、交叉和變異操作的方法為:
[0021](4.1)首先進行選擇操作:種群中每個個體進入下一代的概率等於其適應度值與整個種群中個體適應度值和的比值，採用優先級隨機概率選擇的方式選擇M個適應度好的個體，其中M > 2 ；
[0022](4.2)對選中的個體進行分組:按照適應度值對選中的個體進行分組，具有相同適應度值的個體被分在同一組裡，同組個體擁有相同的「第一個不滿足目標路徑的分支節點」 Clst，即以同組個體作為輸入測試被測程序時，程序執行路徑將在同一分支節點處偏離目標路徑，提取與該分支節點相關的輸入變量作為與該組個體相關的輸入變量，約束後續交叉變異的範圍；
[0023](4.3)對分組後的個體進行交叉操作:交叉操作在同組個體之間進行，對提取出的與該組個體相關的輸入變量所對應的數據位進行多點交叉，其他輸入變量直接賦值給子代；
[0024]根據組內個體數目，分兩種情況進行交叉操作:[0025]I)組內個體大於I時，對相鄰的兩個個體進行交叉；
[0026]2)組內只有一個個體時，通過複製個體的方式來完成交叉操作；
[0027](4.4)對交叉操作後的個體進行變異操作:對交叉操作生成的子代個體，隨機從每個需要修改的輸入變量所對應的數據位中選取一個或多個數據位進行修改，形成新的個體。
[0028]所述步驟(4.2)中提取與某分支節點相關的輸入變量的步驟為:
[0029](a)提取分支表達式中運算符號左右兩邊涉及到的所有變量，將其中的輸入變量
加入到R輸人變量集合中，即R輸人變量={R輸人變量I，R輸人變量2，…，R輸人變量J，將程序變量加入到R程序變量集合中，即R程序變量={R程序變量丨，R程序變量2，…，R程序變量J，n e [1，N], N為自然數；
[0030](b)對每個程序變量，從該分支表達式向前逐條語句回溯掃描，若掃描到該程序變量的賦值語句(該程序變量位於賦值號左邊)，則賦值號右邊的變量即為程序變量的相關變量;
[0031](C)如果這些相關變量都為輸入變量，則針對該程序變量的掃描停止，將其相關的輸入變量加入到R?入集合中，如果這些變量中還有程序變量，則繼續執行(b)和(c)，直到這些變量中沒有程序變量為止；
[0032](d)對集合中的所有變量執行(b)和(C)，從而找到與每一個程序變量相關的輸入變量，R?入》集合中所有的變量即為與該分支相關的所有輸入變量。
[0033]本發明與現有技術相比具有如下有益效果:
[0034](I)目前遺傳算法的交叉、變異點可能選取在個體基因中的任意位置，產生優良基因的同時也存在破壞已有優良基因的可能。本發明在計算適應度函數時找到不滿足目標路徑的具體分支，利用該分支的結構信息約束遺傳算法交叉、變異操作的範圍，從而確保了優良基因的傳遞，提高了算法效率；
[0035](2)目前基於遺傳算法的數據流測試用例自動生成技術沒有對迭代過程中子代與父代種群中個體的最大適應度值進行比較，即使子代適應度值低於父代，也仍然向下繼續遺傳，本發明比較子代與父代的最大適應度值，只有子代適應度值大於父代才繼續向下遺傳，否則拋棄子代，由父代再重新生成新的子代，從而降低了迭代次數，提高了效率。
【專利附圖】
【附圖說明】
[0036]圖1為本發明方法流程圖；
[0037]圖2為某程序流程圖。
【具體實施方式】
[0038]如圖1所示，本發明提供了一種基於遺傳算法的數據流測試用例自動生成方法，步驟如下:
[0039](I)針對被測程序P中的一個定義使用對(def, use),找出由入口節點Ii1開始並且經過定義節點def的使用節點use的支配路徑domdef Oi1, use)；
[0040]domdef (Ii1, use) =dom (Ii1, def) U dom(def, use)
[0041]其中，domOv def)表示由入口節點Ii1到定義節點def所必須經過的節點組成的路徑，dom(def, use)表示由定義節點def到使用節點use所必須經過的節點組成的路徑；[0042](2)根據設定的遺傳算法參數和輸入變量的取值範圍、精度，隨機生成初始種群InitPop,並賦值給當前種群 CurrentPop,即 CurrentPop=InitPop,同時將 CurrentPop 賦值給父代種群 ParentPop,即 ParentPop=CurrentPop ；
[0043](3)將當前種群CurrentPop中的每個個體輸入被測程序P，檢查實際路徑Pa對支配路徑domdef Oi1, use)的覆蓋程度；
[0044](4)若當前種群CurrentPop中的所有個體執行完後，domdef Oi1, use)中仍有節點沒有被覆蓋，且當前遺傳代數沒有達到設定的最大遺傳代數，則執行(5)- (7)，否則執行(8);
[0045](5)計算當前種群CurrentPop中每個個體的適應度函數值,將其中最大值賦值給當前種群CurrentPop中個體的最大適應度值fmax_cur,當CurrentPop種群中個體的最大適應度值fmax_cur不大於父代種群中個體的最大適應度值fmax_old時,拋棄當前種群，將父代種群再賦值給CurrentPop,即CurrentPop=ParentPop,其中fmax_old初始值為O,然後執行(6);當CurrentPop種群中個體的最大適應度值fmax_cur大於父代種群中個體的最大適應度值fmax_old時,更新父代種群中個體的最大適應度值,即fmax_old=fmax_cur,然後執行(6)；
[0046]計算個體適應度函數值的公式為:
[0047]
【權利要求】
1.一種基於遺傳算法的數據流測試用例自動生成方法，其特徵在於步驟如下: (1)針對被測程序P中的一個定義使用對(def,use),找出由入口節點II1開始並且經過定義節點def的使用節點use的支配路徑domdef Oi1, use)； (2)根據設定的遺傳算法參數和輸入變量的取值範圍、精度，隨機生成初始種群InitPop,並賦值給當前種群 CurrentPop,即 CurrentPop=InitPop,同時將 CurrentPop 賦值給父代種群 ParentPop,即 ParentPop=CurrentPop ； (3)將當前種群CurrentPop中的每個個體輸入被測程序P，檢查實際路徑Pa對支配路Sdomdef(IiDuse)的覆蓋程度； (4)若當前種群CurrentPop中的所有個體執行完後，domdefOi1, use)中仍有節點沒有被覆蓋，且當前遺傳代數沒有達到設定的最大遺傳代數，則執行(5)- (7)，否則執行(8)； (5)計算當前種群CurrentPop中每個個體的適應度函數值,將其中最大值賦值給當前種群CurrentPop中個體的最大適應度值fmax_cur,當CurrentPop種群中個體的最大適應度值fmax_cur不大於父代種群中個體的最大適應度值fmax_old時,拋棄當前種群，將父代種群再賦值給CurrentPop,即CurrentPop=ParentPop,其中fmax_old初始值為O,然後執行(6);當CurrentPop種群中個體的最大適應度值fmax_cur大於父代種群中個體的最大適應度值fmax_old時,更新父代種群中個體的最大適應度值,即fmax_old=fmax_cur,然後執行(6)； (6)依據適應度函數值，根據程序結構信息對當前種群CurrentPop利用遺傳算法進行選擇、交叉和變異操作得到新的種群NewPop ； (7)將當前種群CurrentPop 賦值給父代種群 ParentPop,即 ParentPop=CurrentPop,將新種群NewPop賦值給當前種群CurrentPop,即CurrentPop=NewPop,重複步驟(3)-(4)；` (8)若在最大遺傳代數之內找到`了覆蓋d0mdefOi1, use)中所有節點的測試用例，則輸出該符合要求的測試用例；否則返回步驟(2)重新設定遺傳算法參數，直到生成符合要求的測試用例。
2.根據權利要求1所述的一種基於遺傳算法的數據流測試用例自動生成方法，其特徵在於:所述步驟(1)中找出支配路徑Cbmdef(I^use)的方法為:
domdef (Ii1, use)=dom(n1, def) U dom(def, use) 其中，domOvdef)表示由入口節點Ii1到定義節點def所必須經過的節點組成的路徑，dom(def, use)表示由定義節點def到使用節點use所必須經過的節點組成的路徑。
3.根據權利要求1所述的一種基於遺傳算法的數據流測試用例自動生成方法，其特徵在於:所述步驟(5)中計算個體適應度函數值的公式為:
4.根據權利要求1所述的一種基於遺傳算法的數據流測試用例自動生成方法，其特徵在於:所述步驟(6)中根據程序結構信息對當前種群CurrentPop利用遺傳算法進行選擇、交叉和變異操作的方法為: (4.1)首先進行選擇操作:種群中每個個體進入下一代的概率等於其適應度值與整個種群中個體適應度值和的比值，採用優先級隨機概率選擇的方式選擇M個適應度好的個體，其中M≥2 ； (4.2)對選中的個體進行分組:按照適應度值對選中的個體進行分組，具有相同適應度值的個體被分在同一組裡，同組個體擁有相同的「第一個不滿足目標路徑的分支節點」 Clst,即以同組個體作為輸入測試被測程序時，程序執行路徑將在同一分支節點處偏離目標路徑，提取與該分支節點相關的輸入變量作為與該組個體相關的輸入變量，約束後續交叉變異的範圍； (4.3)對分組後的個體進行交叉操作:交叉操作在同組個體之間進行，對提取出的與該組個體相關的輸入變量所對應的數據位進行多點交叉，其他輸入變量直接賦值給子代；根據組內個體數目，分兩種情況進行交叉操作: O組內個體大於I時，對相鄰的兩個個體進行交叉； 2)組內只有一個個體時,通過複製個體的方式來完成交叉操作； (4.4)對交叉操作後的個體進行變異操作:對交叉操作生成的子代個體，隨機從每個需要修改的輸入變量所對應的數據位中選取一個或多個數據位進行修改，形成新的個體。
5.根據權利要求4所述的一種基於遺傳算法的數據流測試用例自動生成方法，其特徵在於:所述步驟(4.2)中提取與某分支節點相關的輸入變量的步驟為: (a)提取分支表達式中運算符號左右兩邊涉及到的所有變量，將其中的輸入變量加入到R輸人變量集合中，即R輸人變量={R輸人變量I，R輸人變量2，…，R輸人變量J，將程序變量加入到R程序變量集合中，即R程序變量={R程序變量丨，R程序變量2，…，R程序變量J，n e [1，N], N為自然數； (b)對每個程序變量，從該分支表達式向前逐條語句回溯掃描，若掃描到該程序變量的賦值語句(該程序變量位於賦值號左邊)，則賦值號右邊的變量即為程序變量的相關變量； (C)如果這些相關變量都為輸入變量，則針對該程序變量的掃描停止，將其相關的輸入變量加入到集合中，如果這些變量中還有程序變量，則繼續執行(b)和(C)，直到這些變量中沒有程序變量為止； (d)對集合中的所有變量執行(b)和(C)，從而找到與每一個程序變量相關的輸入變量，R?入集合中所有的變量即為與該分支相關的所有輸入變量。
【文檔編號】G06N3/12GK103593287SQ201310524293
【公開日】2014年2月19日 申請日期:2013年10月30日 優先權日:2013年10月30日
【發明者】楊桂枝, 鄭平, 張輝, 張偉, 詹海潭, 高金梁 申請人:北京信息控制研究所