[發明專利]一種基于多目標優化的測試用例優先級排序方法

有效

• 申請號: 202010428825.9
• 申請日: 2020-05-20
• 公開（公告）號: CN111666209B
• 公開（公告）日: 2023-03-31
• 發明（設計）人: 夏春艷;張巖;霍婷婷;郭冰;石晨陽
• 申請（專利權）人: 牡丹江師范學院
• 主分類號: G06F11/36
• 分類號: G06F11/36
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于多目標優化的測試用例優先級排序方法，其特征在于，針對待測程序和測試用例集，采用十進制的編碼方式對測試用例進行編碼，依據測試用例的相似度和相異度構建選擇函數，從而評價初始種群中的測試用例集，擇優生成種群數據；在此基礎上，基于Pareto最優的非支配排序遺傳算法，以測試用例集的錯誤檢測率、語句覆蓋率和有效執行時間為優化目標，針對測試用例的優先級別進行排序，最終輸出測試用例的最優排序集TS'；該方法包括如下步驟：

1)測試用例集的評價，給定測試用例集TS＝{TC₁,TC₂,…,TC_n}，第一，采用十進制的編碼方式對測試用例進行編碼，以測試用例TC_k在TS中的序號k作為其相應的十進制編碼；對TS中的所有測試用例進行全排列，從而得到含有n！個測試用例集的初始種群initinal_population_set；第二，從initinal_population_set中隨機選擇m個測試用例集，構成規模為m的種群數據population_data_set；從initinal_population_set中隨機選擇一個測試用例集TS_i，計算TS_i和TS_j(TS_j∈population_data_set,j＝1,2,…,m)的相似度Similarity(TS_i,TS_j)和相異度Diversity(TS_i,TS_j)；

a.Similarity(TS_i,TS_j)采用的是計算TS_i和TS_j相同編碼的長度與編碼總長度n的比值，表示TS_i和TS_j的相似程度，計算公式如下：

其中，

b.Diversity(TS_i,TS_j)采用的是計算TS_i和TS_j不同編碼的個數與編碼總長度n的比值，表示TS_i和TS_j的相異程度，計算公式如下：

其中，

第三，依據Similarity(TS_i,TS_j)和Diversity(TS_i,TS_j)的計算公式，構建TS_i的選擇函數Choice_Function(TS_i)，進而對TS_i進行評價；如果Choice_Function(TS_i)＞ε，則將TS_i存入population_data_set；當population_data_set的規模達到2m時，輸出population_data_set；其中，Choice_Function(TS_i)的計算公式如下：

Choice_Function(TS_i)＝α·F₁(TS_i)+β·F₂(TS_i)

其中，

α和β代表函數的權重值；F₁是依據測試用例的相似性定義的函數，能夠強化搜索目的；F₂是依據測試用例的相異度定義的函數，能夠平衡搜索過程的多樣性；

2)測試用例集的多目標優化，給定待測程序PG和種群數據population_data_set，第一，運行PG，計算TS_i(TS_i∈population_data_set)的故障檢測率、語句覆蓋率和有效執行時間,進而計算TS_i的Pareto最優解集；故障檢測率、語句覆蓋率和有效執行時間的計算方法如下：

a.故障檢測率(APFD)，主要用于計算測試用例執行過程中檢測到缺陷的平均累計比例，其計算公式如下：

其中，n是TS_i中測試用例數量，n₁是被測軟件缺陷總數量，TFD_i表示首次檢測到第i個缺陷的測試用例在該執行序列中所處的次序；

b.語句覆蓋率(APSC)，主要用于計算在測試用例執行時，所用到的可執行語句數與全部可執行語句數的比例，其計算公式如下：

其中，n是TS_i中測試用例數量，n₂是被測軟件語句總數量，TSC_i表示首次覆蓋第i行代碼的測試用例在該執行序列中所處的次序；

c.有效執行時間(EET)，主要用于計算測試用例的故障檢測率和語句覆蓋率達到最大時的執行總時間，計算公式如下：

其中，ET_i表示執行第i個測試用例所消耗的時間；

第二，計算處于相同層次中的TS_i(TS_i∈population_data_set)的擁擠度，選擇較優的m'個測試用例集生成新父種群parent_population；如果達到最大迭代次數，則輸出最優測試用例排序集TS'；否則，進行遺傳算法的選擇交叉變異操作，從而生成子代種群children_population；其中，選擇、交叉和變異方法如下：

a.選擇操作使用的是錦標賽選擇方法，即隨機選擇一定數量的測試用例集，從中選擇最好的一個作為父代種群；

b.交叉操作使用的是部分映射交叉方法，即隨機選擇基因段，將其交換，并對其余基因作沖突檢測，按照映射進行匹配；

c.變異操作使用的是序號變異方法，即隨機選擇兩點，將兩點的值進行交換；

第三，父代和子代個體合并，生成種群數據population_data_set；重復上述過程，直到達到最大迭代次數，輸出最優測試用例排序集TS'。