[發(fā)明專利]一種基于程序失效聚類分析的錯誤定位方法

有效

• 申請?zhí)枺?/td>: 201611097861.1
• 申請日: 2016-12-03
• 公開（公告）號: CN106598850B
• 公開（公告）日: 2019-05-28
• 發(fā)明（設(shè)計）人: 張娜;王玉森;包曉安;趙澤丹
• 申請（專利權(quán)）人: 浙江理工大學(xué)
• 主分類號: G06F11/36
• 分類號: G06F11/36
• 代理公司: 杭州求是專利事務(wù)所有限公司 33200
• 代理人: 鄭海峰

1.一種基于程序失效聚類分析的錯誤定位方法，其特征在于包括以下步驟：

S1：收集每次失效執(zhí)行覆蓋的代碼信息，一次失效執(zhí)行所覆蓋的代碼行數(shù)的集合即為一個失效執(zhí)行切片，采用杰卡德距離公式計算失效執(zhí)行切片之間的距離；

S2：根據(jù)K-Means聚類算法對程序失效執(zhí)行切片進行聚類，得到失效執(zhí)行切片簇，同一失效簇內(nèi)的失效所覆蓋的代碼具有較高的相似度；

S3：根據(jù)跳轉(zhuǎn)指令的運行時程序狀態(tài)劃分方法繪出失效執(zhí)行切片的程序狀態(tài)序列圖，程序狀態(tài)序列圖反映一次失效執(zhí)行中函數(shù)嵌套調(diào)用的次數(shù)θ；

S4：根據(jù)程序狀態(tài)序列圖中函數(shù)嵌套調(diào)用次數(shù)θ分別建立以行/基本塊為單位的執(zhí)行路徑覆蓋向量和覆蓋矩陣，并分別求其頻繁集；頻繁集是指失效執(zhí)行中在所有覆蓋向量上對目標(biāo)基本塊/行保持覆蓋一致性的分量所對應(yīng)的基本塊/行的集合；

所述的步驟S4中根據(jù)程序狀態(tài)序列圖中函數(shù)嵌套調(diào)用次數(shù)θ對每條測試用例對應(yīng)的執(zhí)行分別建立以行/基本塊為單位的執(zhí)行路徑覆蓋向量和覆蓋矩陣，所述的基本塊為中間不存在控制跳轉(zhuǎn)的連續(xù)代碼語句，覆蓋向量的量化方法如下：

設(shè)執(zhí)行軌跡的覆蓋向量集合T＝<t₁,t₂,…,t_r>，所有覆蓋向量的集合構(gòu)成一個覆蓋向量矩陣，其中t_i表示第i次執(zhí)行覆蓋的信息構(gòu)成的覆蓋向量,T根據(jù)程序執(zhí)行結(jié)果的不同，將T分為成功執(zhí)行和失效執(zhí)行兩類，分別標(biāo)記為T_p和T_f；覆蓋向量t_i＝<e₁,e₂,…,e_s>

e_j表示第i次執(zhí)行覆蓋的第j個基本塊/行；

步驟S4中建立頻繁集的方法為：首先初始化tas(e)為單位向量，然后依次遍歷e分量不為0的覆蓋向量并將該覆蓋向量與tas(e)進行向量的與操作，求得e頻繁集，最后可得所有目標(biāo)基本塊/行的頻繁集集合TAS，tas(e)表示以e為目標(biāo)代碼的頻繁集；

S5：分別計算出各基本塊/行的可疑度并降序排列，根據(jù)基本塊/行可疑度的大小以及其對應(yīng)的頻繁集依次檢查各基本塊/行是否含有錯誤；

所述的步驟S5中根據(jù)基本塊/行可疑度的大小以及其對應(yīng)的頻繁集依次檢查各基本塊/行是否含有錯誤的步驟如下：

1)計算每個基本塊/行的可疑度，并根據(jù)可疑度的大小降序排列，根據(jù)程序狀態(tài)序列，查看程序函數(shù)調(diào)用次數(shù)是否小于θ，如果是轉(zhuǎn)步驟2)，否則轉(zhuǎn)步驟4)；

2)從排序后的列表中依次檢查基本塊是否含有錯誤，如果定位出錯誤轉(zhuǎn)步驟6)，否則轉(zhuǎn)步驟3)；

3)將沒有錯誤的基本塊作為目標(biāo)基本塊，依據(jù)覆蓋信息矩陣求解其頻繁集；將頻繁集中的基本塊依據(jù)其可疑度大小降序排列，依次檢查各基本塊是否含有錯誤，如果定位出錯誤轉(zhuǎn)步驟6)，否則轉(zhuǎn)步驟2)；

4)從排序后的列表中依次檢查各行是否含有錯誤，如果定位出錯誤轉(zhuǎn)步驟6)，否則轉(zhuǎn)步驟5)；

5)將沒有錯誤的行作為目標(biāo)行，依據(jù)覆蓋信息矩陣求解其頻繁集；將頻繁集中的各行依據(jù)其可疑度大小降序排列，依次檢查各行是否含有錯誤，如果定位出錯誤轉(zhuǎn)步驟6)，否則轉(zhuǎn)步驟4)；

6)統(tǒng)計已檢查的基本塊/行的數(shù)量。

2.根據(jù)權(quán)利要求1所述的一種基于程序失效聚類分析的錯誤定位方法，其特征在于：所述的步驟S1中失效執(zhí)行切片之間的距離的量化方法如下：

非空集合A,B表示兩個失效執(zhí)行切片；D(A,B)表示兩個失效執(zhí)行切片之間的相似度，|A|表示集合中元素的個數(shù)。

3.根據(jù)權(quán)利要求1或2所述的一種基于程序失效聚類分析的錯誤定位方法，其特征在于：所述的步驟S5中基本塊/行的可疑度的計算方法如下：

其中，n_uv(b)＝|{a|x_ab＝u∧r_a＝v}|,u,v∈{0,1}，x_ab＝u，u＝1時表示基本塊/行在a執(zhí)行中被覆蓋；u＝0時表示基本塊/行在a執(zhí)行中沒有覆蓋，r_a＝v，v＝1時表示a執(zhí)行是失效執(zhí)行；v＝0時表示a執(zhí)行不是失效執(zhí)行。