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

有效

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

本發明公開了一種基于黃金分割搜索及軟件執行軌跡的條件切片方法，根據給定的一階謂詞邏輯集，在符合條件的區間內，根據黃金分割搜索法選取變量值作為程序動態運行的輸入，通過程序多次運行的執行軌跡集合計算得到相應的語句覆蓋集，以此為基礎，結合程序的靜態切片，計算得到程序的條件切片。由于該方法不需要程序的全局分析，提高了效率，且空間復雜度較低，此外程序的執行軌跡獲取方便，不受程序類型的影響，使得該方法可應用于過程間、面向對象、并發程序。

技術領域

本發明屬于軟件維護中程序切片領域，涉及一種基于黃金分割搜索及軟件執行軌跡的條件切片方法。

背景技術

程序切片是將源程序中用戶所感興趣的變量或語句直接或間接相關的代碼抽取所得的新代碼的集合，由于將程序的規模大幅度縮減，便于程序理解，應用價值較高。該技術自Weiser在1979年提出至今，已經在軟件分析、理解、調試、測試、度量、軟件質量保證、逆向工程等許多方面有著廣泛的應用。因此出現了一系列程序切片的種類，條件切片便是基于靜態切片和動態切片之間的一種較為實用的程序切片。

目前主要的條件切片方法有：

1998年G.Canfora，A.Cimitile和D.Lucia提出的符號執行方法。該方法根據輸入條件的限制，通過符號執行的計算將程序進行簡化。該方法能夠較為精確的處理過程內的條件切片，但無法處理過程間、面向對象以及并發類程序。

2002年M.Daoudi和L.Ouarbya等人提出的將FermaT transformation system和符號執行相結合的方法。該方法進一步提高了程序簡化技術，但依然無法處理過程間、面向對象以及并發類程序。

2008年Wang Xiao-hua和GuYi-dong等人提出的依賴圖重構法。這一方法可以提高條件切片的所得切片的有效代碼段，但依舊無法處理過程間、面向對象以及并發類程序。

程序插樁是獲取程序動態運行信息的一種常用技術，最早是由J.C.Huang教授提出的，它是在保證被測程序原有邏輯完整性的基礎上在程序中插入一些探針(又稱為“探測儀”，本質上就是進行信息采集的代碼段，可以是賦值語句或采集覆蓋信息的函數調用)，通過探針的執行并拋出程序運行的特征數據，通過對這些數據的分析，可以獲得程序的控制流和數據流信息，進而得到邏輯覆蓋等動態信息，從而實現測試目的的方法。

條件切片的含義為，對于包含變量輸入的程序，限定變量輸入的一階謂詞集，使得變量的值有一定的限制，在限制范圍內進行程序的運行。以限定的程序范圍為基礎，在此之上實施靜態切片的計算，將程序運行范圍內的切片提取出來，便得到最終的條件切片。通過插裝來獲取程序動態運行的軌跡信息，并輔助切片算法的實施，是動態程序切片的常見做法。這里我們通過黃金分割搜索方法對變量值進行選取，作為程序的輸入，通過多次運行，獲得最終的語句覆蓋集，結合靜態切片，應用于條件切片的計算。

發明內容

技術問題：本發明提供一種能夠利用黃金分割搜索法對變量值進行選取，并通過軟件多次運行的執行軌跡信息計算程序的語句覆蓋集，具有較高精確性且應用范圍較廣的基于黃金分割搜索及軟件執行軌跡的條件切片方法。

技術方案：本發明的基于黃金分割搜索及軟件執行軌跡的條件切片方法，包括如下步驟：

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

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

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