[發明專利]一種基于分類樹的測試數據自動生成方法及系統

在審

• 申請號: 202011641866.2
• 申請日: 2020-12-31
• 公開（公告）號: CN112699039A
• 公開（公告）日: 2021-04-23
• 發明（設計）人: 楊京禮;林連雷;魏長安;盛云龍
• 申請（專利權）人: 哈爾濱工業大學
• 主分類號: G06F11/36
• 分類號: G06F11/36;G06F16/22
• 代理公司: 哈爾濱華夏松花江知識產權代理有限公司 23213
• 代理人: 岳昕

1.一種基于分類樹的測試數據自動生成方法，其特征在于，包括以下步驟：

利用帶有分類樹的測試數據表對待測試的數據進行表示；基于測試數據的約束描述和覆蓋準則，采用遺傳算法生成聯合覆蓋數組，包括以下步驟：

(1)參數初始化

參數初始化包括兩個部分：

1.1、對遺傳算法本身的參數進行初始化；

1.2、生成測試數據過程的初始化：

采用“Map”數據結構存儲組合約束，“Map”的鍵“Key”表示參數的組合，值“Value”是一個存儲了參數約束取值組合對應索引的數組；存儲約束時，非約束的索引不能出現；

目標取值組合使用“Map”數據結構進行存儲，目標取值組合“Map”中的每一個參數組合“Key”對應的“Value”數組中的每一個索引都需要進行約束一致性驗證，通過約束一致性驗則是目標取值組合；

利用整數集表示任意t個參數的全部取值組合，已知每個取值對應參數的取值個數集任意一個取值組合對應的索引index的求解過程為：

(1.1)令

(1.2)令j從2取到t，循環執行

(1.3)index即為取值組合對應的索引；

其中，g_j為每個取值對應參數的取值個數；

取值序列表采用“Map”結構，“Map”的鍵“Key”表示參數的取值序列，值“Value”是一個存儲了參數取值序列對應索引的一個數組；存儲取值序列時，如果其中的取值序列不滿足取值次序約束一致性，則其對應的索引不能出現在“Value”中；

每一條測試數據的組合適應值為覆蓋未被覆蓋的取值組合的個數，序列適應值為當前測試數據與之前的t_s-1條測試數據一起覆蓋的未被覆蓋的取值序列的個數；一條測試數據的適應值是組合適應值和序列適應值兩者之和；

(2)生成候選解集

為M個新的染色體中每一個基因x_ij進行初始化，初始值從第j個參數的取值區間[0,g_j-1]中隨機選擇；

(3)選擇

從M個染色體中選出適應值大的M/2個染色體作為自然選擇的結果；

(4)交叉

將選擇出的M/2個染色體平均分為兩組；每組對應位置的染色體之間進行交叉，對于任一對需要交叉的染色體對，其中每個對應位置的基因按照交叉概率P_c進行交叉；

(5)變異

對于交叉之后的染色體，其中第j基因從[0,g_j-1]中隨機變異一個新的值，并按照變異概率P_m進行選擇；

(6)判斷是否滿足最大覆蓋

如果在進化過程中的適應值為則提前跳出進化過程；

(7)搜索策略

在染色體完成進化過程之后，如果其中的最優的染色體的適應值為0，使用搜索策略進行后續的尋優過程；如果最優個體不滿足最大覆蓋，則判斷是否達到最大迭代次數，如果沒有達到返回步驟(3)，如果達到最大迭代次數也使用搜索策略進行后續的尋優過程；

搜索策略將生成一條測試數據并放入聯合覆蓋數組中，該條測試數據中每個參數對應的取值，與該取值前面或后面的測試數據中對應參數的取值構成的取值路徑中，能夠覆蓋未被覆蓋的取值序列；根據每個參數的取值情況的不同，搜索策略將具體分為如下兩個過程：

在第一個過程中，搜索策略對聯合覆蓋數組中的最后一條測試數據到倒數第t_s-1條測試數據進行檢查，檢查從倒數第r，1≤r≤t_s-1，條測試數據到倒數第一條測試數據中，是否存在未被覆蓋的取值序列的一段，如果存在，則將這一段所在未被覆蓋的取值序列的下一個值放到新生成的測試數據中對應的位置；如果經過第一個過程，新的測試數據中有的參數已經選取了取值，則對沒有選取取值的參數隨機賦一個滿足約束一致性的值；如果在新的測試數據中全部參數都沒有選取取值，則進行第二個過程；

在第二個過程中，將聯合覆蓋數組中最后一條測試數據中的每個參數的取值作為一個樹的根節點，該節點的子節點為該值可以轉移到的取值；在樹不斷壯大的過程中，直到某一層子節點是未被覆蓋的取值序列的起始值時停止該過程；在根節點到最后一層子節點的路徑上的第二個節點，將作為新生成的測試數據中對應參數的取值；一旦某個參數已經選取了取值，則結束該過程并對沒有選取取值的參數隨機賦一個滿足約束一致性的值；

(8)判斷是否滿足覆蓋要求

當不存在次序約束時，聯合覆蓋數組兩條測試數據之間將沒有任何約束，在搜索時間下覆蓋全部的參數取值組合和取值序列，結束生成測試數據。