[發(fā)明專利]基于程序行為切片的測試案例約減方法

有效

• 申請?zhí)枺?/td>: 201310479195.8
• 申請日: 2013-10-14
• 公開（公告）號: CN103559122A
• 公開（公告）日: 2014-02-05
• 發(fā)明（設(shè)計）人: 管曉宏;鄭慶華;劉烴;王海軍;俞樂晨;黃小龍
• 申請（專利權(quán)）人: 西安交通大學(xué)
• 主分類號: G06F11/36
• 分類號: G06F11/36
• 代理公司: 西安通大專利代理有限責(zé)任公司 61200
• 代理人: 蔡和平

1.基于程序行為切片的測試案例約減方法，其特征在于，包括如下步驟：

S1)根據(jù)輸入的待測程序，利用靜態(tài)程序分析方法，分析待測程序的控制流和信息流，提取待測程序的控制依賴和數(shù)據(jù)依賴；

S2)根據(jù)待測程序的控制依賴和數(shù)據(jù)依賴，計算待測程序的潛在依賴；

S3)根據(jù)待測程序的控制依賴、數(shù)據(jù)依賴和潛在依賴，在程序控制流圖上構(gòu)建程序的組合依賴；

S4)利用符號執(zhí)行方法隨機(jī)生成一條初始路徑，并將對應(yīng)初始路徑的測試案例存入有效測試案例集；

S5)計算新生成的路徑覆蓋的程序行為切片，第一次執(zhí)行時為初始路徑：對路徑執(zhí)行的每一個分支節(jié)點(diǎn)，計算它在路徑上的程序行為切片；路徑上某個節(jié)點(diǎn)n_i的程序行為切片包含所有滿足如下性質(zhì)的節(jié)點(diǎn)：節(jié)點(diǎn)在路徑上通過控制依賴，數(shù)據(jù)依賴，潛在依賴，組合依賴或者它們的傳遞和節(jié)點(diǎn)n_i存在影響關(guān)系；

S6)計算新生成的路徑未覆蓋的程序行為切片，第一次執(zhí)行時為初始路徑：根據(jù)依賴關(guān)系計算路徑上所有需要取反的分支，并計算這些分支取反后在路徑上的程序行為切片；

S7)對未覆蓋程序行為切片庫進(jìn)行更新：刪除被新生成路徑覆蓋的程序行為切片，并添加新生成路徑未被覆蓋的程序行為切片；

S8)如果未覆蓋程序行為切片庫為空，即不存在未被覆蓋的程序行為切片，轉(zhuǎn)步驟S10);否則，轉(zhuǎn)步驟S9）；

S9)根據(jù)廣度優(yōu)先算法搜索從未覆蓋程序行為切片庫中選取一條程序行為切片，引導(dǎo)符號執(zhí)行生成測試路徑，若路徑有效，將其對應(yīng)的測試案例存入有效測試案例集，并轉(zhuǎn)步驟S5）；若無法生成有效路徑，從未覆蓋程序行為切片庫中刪除該程序行為切片，轉(zhuǎn)步驟S8）；

S10)輸出：有效測試案例集，該測試案例集覆蓋待測程序的所有程序行為切片。

2.根據(jù)權(quán)利要求1所述的測試案例約減方法，其特征在于，步驟S2)中潛在依賴的定義：條件語句s₁和語句s₂同時滿足如下兩個條件，稱條件語句s₁和語句s₂存在潛在依賴：1)當(dāng)條件語句s₁取分支br時，存在一條語句s’₁滿足如下條件：語句s₁和語句s’₁通過br存在直接或間接控制依賴并且語句s’₁和語句s₂存在數(shù)據(jù)依賴；2)當(dāng)條件語句s₁取br的反向分支br’時，不存在語句s’₁滿足如下條件：語句s₁和語句s’₁通過分支br’存在直接或間接控制依賴并且語句s’₁和語句s₂存在數(shù)據(jù)依賴控制依賴和數(shù)據(jù)依賴描述了語句s₁的執(zhí)行對另外一條語句s₂的影響，然而潛在依賴刻畫了語句s₁控制另外一條語句s’₁不執(zhí)行時對語句s₂的影響。

3.根據(jù)權(quán)利要求1所述的測試案例約減方法，其特征在于，步驟3)中組合依賴的定義：語句s₁和語句s₂同時滿足如下三個條件，稱語句s₁和語句s₂存在組合依賴：1)存在一條路徑從語句s₁，經(jīng)過語句s₂能夠到達(dá)語句s₃；2)在該路徑上，語句s₁和語句s₃存在數(shù)據(jù)依賴，潛在依賴或者組合依賴；3)在該路徑上，語句s₂和語句s₃存在動態(tài)控制，數(shù)據(jù)，潛在或者組合依賴。