[發明專利]基于路徑覆蓋軟件測試的測試用例自動生成方法

有效

• 申請號: 201710766422.3
• 申請日: 2017-08-30
• 公開（公告）號: CN107590073B
• 公開（公告）日: 2021-03-30
• 發明（設計）人: 黃翰;劉方青;顏學明
• 申請（專利權）人: 華南理工大學
• 主分類號: G06F11/36
• 分類號: G06F11/36
• 代理公司: 廣州粵高專利商標代理有限公司 44102
• 代理人: 何淑珍

1.基于路徑覆蓋軟件測試的測試用例自動生成方法，其特征在于，包括以下步驟：

(a)對輸入的被測測試程序分析功能對應的輸入、輸出并且通過分析程序中存在的判斷、循環分支得到控制流圖CFG，并對需要覆蓋的路徑進行編碼；

(b)根據測試問題的實際輸入、輸出數據的類型和范圍確定問題編碼；

(c)通過對步驟(a)中得到了控制流圖CFG和步驟(b)中根據具體測試問題輸入確定的問題編碼，以及預設的計算分支距離的方法得到計算一個測試用例評估值的適應值函數；

(d)在測試用例的取值范圍內，使用均勻分布的方式隨機初始化種群；

(e)以步驟(d)中得到的種群，使用差分進化算法(DE)和收斂速度控制器(CSC)以及步驟(c)中得到的適應值函數更新迭代種群；

選取差分進化算法(DE)來迭代種群，差分進化算法迭代公式為：v_i＝y_i+F*(y_j-y_k)，其中v_i是得到的新測試用例，而y_i是差分進化前的舊測試用例，y_j和y_k是從種群所有解決方案中隨機選中的兩個測試用例；在上述計算完成之后，接下來進行差分進化算法(DE)的交叉操作，生成一個[0,1]之間的隨機數rand，如果rand的大小小于預設的交叉概率P_c，那么就保留新的解，如果rand的大小大于預設的交叉概率P_c，那么就舍棄剛剛求得的解，保留以前的解；在差分進化算法進行迭代更新的同時，通過收斂速度控制器(CSC)來控制DE算法的收斂速度，在判斷DE算法收斂速度太慢的時候進行相關維度的動態步長搜索操作，加快算法收斂速度，在判斷DE算法收斂速度太快的時候進行初始化種群部分維度操作，減緩算法收斂速度；其中動態步長搜索操作方法如下：在一個設定的維度的范圍內進行大步長搜索，找到其中適應值最好的位置，并以此位置進行更小范圍內的搜索，直到步長小于預設值，此時，在這個小于預設值的范圍內進行窮舉，找到適應值最高的點；并依據數據新建該維度動態步長搜索后得到的新種群個體；

收斂速度控制器(CSC)的減速算子如下，添加一個區域擊中次數統計數據結構，每次在程序運行之前，將程序輸入變量的范圍進行分區，具體為：測試用例X的第i個維度取值范圍是[1,100]，將其平均分成10個區域，并統計每一個區域的擊中次數，每次進行收斂速度控制器(CSC)的減速操作的時候，選擇測試用例的每個維度擊中次數最少的區域，并進行初始化；

(f)將步驟(d)、(e)中種群個體里，覆蓋被測試程序目前未被覆蓋路徑的測試用例記錄下來；

(g)檢測是否滿足差分進化算法的迭代終止條件：如果不滿足條件，則跳回步驟(e)繼續執行；如果滿足條件，則輸出記錄的覆蓋對應路徑的測試用例集合。

2.根據權利要求1所述基于路徑覆蓋軟件測試的測試用例自動生成方法，其特征在于：步驟(a)中，對輸入的被測程序采用單元測試的測試方法，對于各個功能單元分析對應功能單元的輸入、輸出以及判斷、循環分支，畫出功能單元的控制流圖CFG；并依據控制流圖CFG確定所有路徑的編碼，首先將測試程序匯總所有的判斷、循環分支進行編號，設為1～K，設定路徑為一個長度為N的字符串，如果路徑經過第k個分支判斷節點，那么該路徑的第k位的值為字符“1”或者字符“0”，字符“1”表示路徑走的是No方向，字符“0”表示路徑走的是Yes方向，如果未經過第k個分支判斷節點，則可使用字符“N”表示，通過這種方式對路徑進行編碼，所有的路徑都能用一個長度為N的字符串表示。

3.根據權利要求1所述基于路徑覆蓋軟件測試的測試用例自動生成方法，其特征在于：步驟(b)中，分析被測試程序的輸入、輸出數據類型和范圍，確定具體問題的編碼，具體包括：對于數值型的數據變量，需要確定數據具體是整數還是浮點數，并且設定其取值范圍；如果變量的類型是字符型，使用[0,255]范圍內的整數表示一個ASCII碼符號，而一個長度為m的字符串就可使用m個[0,255]范圍內的整數表示；如果變量是枚舉類型，其中枚舉選擇的數量是k，使用[1,k]范圍內的整數來表示一個輸入的測試用例；對于輸入、輸出是上述類型的組合的情況，只需要組合上述輸入、輸出的類型，就可得到一個測試用例。