[發明專利]一種基于黃金分割搜索及軟件執行軌跡的條件切片方法

有效

• 申請號: 201710530045.3
• 申請日: 2017-06-30
• 公開（公告）號: CN107391124B
• 公開（公告）日: 2020-06-16
• 發明（設計）人: 李必信;張歡;王璐璐
• 申請（專利權）人: 東南大學
• 主分類號: G06F8/75
• 分類號: G06F8/75
• 代理公司: 南京蘇高專利商標事務所(普通合伙) 32204
• 代理人: 柏尚春

1.一種基于黃金分割搜索及軟件執行軌跡的條件切片方法，其特征在于，該方法包括如下步驟：

步驟1)對源代碼進行插裝，得到運行時能夠產生執行軌跡的帶探針的程序；

步驟2)通過黃金分割搜索法選取符合一階謂詞邏輯集的變量值，具體方法為：在滿足一階邏輯限定的取值范圍內，選取待分割的區間，通過黃金分割搜索法取點的方式得到變量的值，作為程序運行的輸入；

步驟3)獲取執行軌跡，配置執行所述步驟1)得到的帶探針的程序，運行的過程中產生實時運行軌跡，運行完成后得到此次程序運行的執行軌跡；

步驟4)利用下式計算語句覆蓋集，然后選取當前變量值與左鄰接變量值作為右區間端點和左區間端點值，得到新的變量區間：

statements_i+1＝statements_i∪t_i+1

其中，i表示執行軌跡的編號，statements_i+1為前i+1次程序運行所得的語句覆蓋集，statements_i為前i次程序運行所得的語句覆蓋集，t_i+1為第i+1次程序運行的軌跡；

如果所述語句覆蓋集發生更新，則將新的變量區間加入待分割區間集合中，然后返回步驟2)；若覆蓋集未發生更新，則按照如下方式設定所述新的變量區間黃金分割的次數α：

如果新的變量區間所在的父級區間之前設定過α值，則令α＝α-1，如果α不變為0，則直接返回步驟2)；如果α變為0，則舍棄該新的變量區間，此時如果待分割區間以及待執行變量均為空，則語句覆蓋集計算完成，進入步驟5)，否則返回步驟2)；

如果新的變量區間所在的父級區間之前沒有設定過α值，則計算與左鄰接變量執行軌跡的語句覆蓋集差異，然后以所述語句覆蓋集差異，根據下式設定新的變量區間的α值：

其中j和i+1表示選取變量的編號，α_j,i+1表示執行路徑j與i+1的分割次數值，用以進一步驗證該區間是否還會對語句覆蓋集產生影響，diff_j,i+1表示兩者執行軌跡的不同集所對應的語句覆蓋數，s_j∪s_i+1表示兩者執行軌跡的語句覆蓋總數，β是設定的指數，根據對路徑覆蓋的精度需求進行調整；

步驟5)計算條件切片，具體流程為：

a)通過解析源代碼的抽象語法樹獲取代碼中相應的節點信息，提取各個節點間的依賴關系，構建完整的程序依賴圖；

b)以所述程序依賴圖為基礎，結合源代碼執行靜態切片算法，獲取靜態切片staticSlice；

c)結合靜態切片staticSlice和語句覆蓋集statements，利用下式計算程序的條件切片：

conditionedSlice＝staticSlice∩statements。

2.根據權利要求1所述的基于黃金分割搜索及軟件執行軌跡的條件切片方法，其特征在于，所述步驟2)中的黃金分割搜索法是在區間內選取左右兩個黃金比例的值為變量值。