[發明專利]一種帶環路徑的編碼、執行及解碼方法

有效

• 申請號: 201210159676.6
• 申請日: 2012-05-22
• 公開（公告）號: CN102693133A
• 公開（公告）日: 2012-09-26
• 發明（設計）人: 李必信;王璐璐
• 申請（專利權）人: 東南大學
• 主分類號: G06F9/44
• 分類號: G06F9/44
• 代理公司: 南京天翼專利代理有限責任公司 32112
• 代理人: 王玉梅

技術領域

本發明涉及動態程序分析過程中執行信息的收集技術領域，特別是一種帶環路徑的編碼、執行及解碼方法。

背景技術

動態程序分析是基于程序執行的分析技術，所以收集程序的執行信息是動態分析方法不可缺少的一部分。為了高效的收集路徑的執行信息，現有技術普遍采用路徑編碼的方式，將每條路徑映射到一個或一組整數，以快速的判斷當前執行的路徑是否與已執行的某條路徑相同，方便的進行執行次數的累加。相應的，為了實現路徑的編碼，在程序執行之前，首先要對程序進行插裝，在分析程序的控制流圖（CFG，control?flow?graph）的基礎上，在程序的相關位置插入一個或多個探針變量的值操作語句及相關的邏輯控制、探針收集等語句。這樣當程序每一次執行完畢之后，所收集的路徑編碼計算結果就唯一確定該次執行的路徑。

對于無環控制流，現有技術采用的路徑編碼方式是：首先將無環控制流圖的每條邊分配一個整數權值，各條無環路徑的編碼即為該路徑中所有邊對應權值之和。為了實現該種路徑編碼，在程序中插裝的語句僅需在執行中將所執行的邊的權值進行累加，便可計算出最終的路徑編碼。此類方法在處理無環路徑上是精確的，且可以保證所有無環路徑的編碼是連續的整數（即路徑編碼是緊湊的），從而具有較高的存儲效率。

在處理循環的問題上，現有技術沿襲使用邊的權值累加的辦法進行編碼的方案，但每條邊在不同的循環執行情況可能具有不同的權值，采用帶有邏輯判斷的權值累加方案保證各條有環路徑具有唯一的編碼。但是在實際應用中，復雜的循環往往會導致邏輯判斷過于復雜，難以處理。

在實際的應用中，所處理的程序往往是帶有循環的，且循環的結構和執行情況多種多樣，因此，針對帶環路徑的實用編碼方案不可缺少。

發明內容

本發明的目的是提供一種帶環路徑的精確編碼方法，其能夠滿足：探針計算與路徑編碼方式能夠保證各條路徑的編碼具有唯一性，達到精確收集有環控制流執行信息的效果；處理過程間各種調用的能力使該方法能夠運用到在面向對象的場景之下。

為了實現上述目的，本發明采取的技術方案為：一種帶環路徑的編碼、執行及解碼方法，其包括以下步驟：

（1).?從程序源碼中獲取各個過程之間的調用關系、每個過程內部的控制結構以及在控制結構基礎上的無環子圖；

（2).?按照路徑的不同類型執行相應的插裝算法，即：

對于過程內的路徑，首先求出過程內部具有多個入邊的節點集合，對于集合中的每個節點，定義其具有n條入邊，將這n條入邊依次與從0開始的n-1個連續整數相對應；然后在該邊上插裝加法和乘法相結合的探針計算語句，執行終點處的探針變量的值對應于所執行路徑的編碼，以使得到的路徑編碼具有唯一性；

對于過程間的路徑，基于目標程序中各個過程之間的調用關系，以適當的策略將過程集簇；如果一個多態調用涉及的被調用方法分布在多個簇中，則對相應的調用語句進行拆解，以使每個調用邊的動態綁定情況局限于單個簇中；然后組合各個過程內的控制流圖得到全局控制流；對于全局控制流圖中的節點，按照過程內路徑的方式按序進行插裝，且對于有多個入邊的節點，依次在其所有入邊上插裝乘法和加法相結合的探針計算語句；

（3).?執行插裝后的程序，并收集相應的路徑編碼及其頻率；

（4).?由收集到的信息在控制流圖上進行回溯，將路徑編碼轉化為路徑，以獲取路徑的執行結果。

具體的，在步驟（1）中，由控制流分析器獲取控制流結構的相關信息，如過程間的調用關系、過程內的控制流圖以及在控制流圖上得出無環子圖，以應用于編碼算法。

無環子圖（RAS,Reduciable?Acyclic?Subgraph）是控制流圖中滿足如下的條件的子圖：(1)子圖是一個單入口單出口結構；(2)子圖中沒有回邊；(3)對于控制流圖中子圖之外的任意一個節點A，不存在從A指向子圖入口以外節點的邊，也不存在從子圖出口以外節點指向A的邊；(4)以子圖中節點為端點的所有非回邊都在子圖中，即如果控制流中存在一條從子圖的出口節點到其入口節點的回邊，那么該回邊可以不包括在子圖中。

在控制流結構中獲取無環子圖的意義在于，本發明的路徑編碼方法可以與已有的無環路徑編碼方法結合起來進行，能夠在一定程度上壓縮編碼，提升效率。