基於程序執行軌跡的動態切片系統的製作方法

2023-08-06 04:28:11 1

專利名稱：基於程序執行軌跡的動態切片系統的製作方法
技術領域：
本發明涉及一種在軟體開發過程中進行程序切片的方法，尤其是不僅可以有效處理複雜大型程序，而且可以提高切片精度的基於程序執行軌跡的動態切片系統。
背景技術：
隨著軟體規模的日益增大，傳統的調試技術不能夠有效的處理複雜大型程序。大型應用系統通常有數百行的代碼，程序開發人員往往不能夠快速的理解程序中的代碼，這給程序的調試和維護工作帶來了很大的困難。而程序切片是一種程序分析技術，用來將大程序分解成小片段，刪除一些與興趣點不相關的語句，幫助開發人員從中提取感興趣的部分。其概念和原理由M. Weiser於1979年首次建立。使用程序切片技術，將簡化程序分析和理解的難度，加速程序的測試和調試工作，縮短程序的開發和維護時間。 程序P中的切片準則可以表示成一個二元組〈P，V〉，其中P是程序中的一條語句，V是在η處定義或引用的變量集合。關於該切片準則的切片將包含哪些影響和控制P處變量V的值得語句。程序切片的計算可以看作一個圖的可達性問題，是在系統依賴上找出可達節點。系統依賴圖由一個或多個程序依賴圖組成。每個過程依賴圖表示一個過程內的控制依賴和數據依賴關係。在系統依賴圖中，每個過程的依賴圖被連接起來，這些邊表示過程間的數據依賴和控制依賴。程序切片可以分為靜態程序切片和動態程序切片。針對給定的切片準則，兩者主要的差異在於進行切片時所需要的信息不同，靜態程序切片僅需要程序的靜態信息，即源程序；而動態程序切片需要根據程序的輸入，記錄程序的整個執行軌跡。靜態程序切片考慮的是程序所有的執行情況，而動態切片僅考慮程序針對某一輸入的特定執行情況。因此，動態切片包含的語句更少，結果更精確些。然而，動態程序切片需要的程序執行軌跡在獲取和儲存方面都受到時間和空間的限制。優化過的動態切片算法需要數分鐘到幾十分鐘，其前期的準備時間更長，所以動態切片的算法優化是一個很重要的問題。

發明內容
為了克服現有的動態切片算法其效率和精度較低的問題，本發明提供一種基於程序執行軌跡的動態切片系統，該動態切片系統依據堆棧跟蹤進行切片的方法，首先利用調試器的信息記錄程序執行軌跡，找出該次執行中涉及的語句；在記錄程序執行軌跡的同時計算程序的控制依賴關係得到程序切片，在程序切片的過程中不需要對程序進行回溯，大大提聞了算法的效率，根據控制依賴關係和變量的定義引用 目息提聞了切片的精度。本發明解決其技術問題所採用的技術方案是
本系統使用eclipse進行開發，可以對Java程序進行動態程序切片。依據程序動態執行軌跡進行程序切片需要依據以下六步進行
(O系統獲得程序的執行路徑信息，即Path Analysis，獲取當前執行語句的信息。在得到當前執行語句的信息，對這些信息進行數據依賴分析，即DefVars or UseVarsAnalysis，得到當前執行語句的定義變量集和使用變量集。模塊核心功能是獲得待分析語句一次完整執行的執行序號ExecutionNum和語句行號LineNum。執行序號比較好分析，它是從I開始，並每次加I的執行序列，即I2 3 4…η,其中η表不最後執行的序號。每個執行序號對應一個語句行號,表不程序第ExecutionNum執行語句LineNum,因為分析過程內程序,不需要考慮不同的類、不同的方法。語句行號需要從虛擬機獲取。在處理ThreadStartEvent時，即程序即將開始執行，設置StepRequest，虛擬機開始單步執行程序。單步執行的效果是在每條語句執行前，單步執行事件StepEvent發生，執行語句的線程被掛起，調試器獲得當前的執行位置信息Location，通過其模塊可以獲得當前執行的行號信息。信息獲取完成後，恢復掛起的線程。(2)對Java的.class文件進行靜態分析,實現了對Java源文件中每條語句中定義變量集DefVars和使用變量集UseDefs的獲取功能。(2a)首先，初始化Soot，完成Soot的初始設置工作。Soot是一種用於Java優化的框架，它為不同的分析目的提供了四種不同的中間表示，這裡需要做的是對Soot中的Jimple這一中間表示進行分析。Jimple是一種基於類型的3地址格式語句的中間表示,是一種介於Java原始碼和Java字節碼的中間表示。該模塊是對中間表示Jimple進行分析，獲得源文件的信息，因此在初始化工作中，需要進行一些設置，如Jimple中間表不的行號為原始碼中行號，Jimple中間表不的變量名為原始碼中變量名。只有通過這些設置，模塊才可以獲得完整、準確的原始碼信息，對原始碼完成 DefVars or UseVars Analysis 工作。(2b)完成Soot初始化工作後，接著需要做的便是獲取需要分析的類和方法。因為DynamicSlicer4j系統分析目標是Java過程內程序，因此,只需獲取類中的main方法 即可。Soot會對待分析的類和方法分別建立自己的Soot類和Soot方法，即SootClass和SootMethod,並為Soot方法建立方法體SootBody,這樣就可利用Soot各個類提供的方法進行分析，大大提高分析的效率。(2c)通過SootBody,模塊可以獲得該方法中任一語句，Jimple中間表示的Soot實例，用Unit表示。Unit保存了該語句的所有信息，模塊只需從中獲取需要的信息就可以了，即該語句的行號或該語句中的定義集合和使用集合，這樣，模塊即可實現DefVars orUseVars Analysis 功倉泛。(2d) Unit中的信息並非即得即用的,Unit保存的是Jimple中間表示的每一條語句，而原始碼中往往一條語句會有多條Jimple代碼，因此，如何將多條Jimple代碼獲得的信息集中到各自相應的Java原始碼，是一個需要處理的問題。還有，模塊通過調用Unit中的方法，可以輕易獲取Unit中的定義集合和使用集合，模塊需要的定義變量集合Def Vars和使用變量集合Use Vars就包含其中，如果把它們從中剝離出來，也是一個需要處理的問題。而且在處理獲得定義變量集合Def Vars和使用變量集合Use Vars時，還需要將在Jimple中間表示中產生的不屬於Java原始碼的臨時變量去除掉。通過步驟(2a)、(2b)、(2c)及(2d)的處理，才能獲得完整的、準確的定義變量集合Def Vars和使用變量集合Use Vars,由此完成執行DefVars or UseVars Analysis功能。(3)對程序執行軌跡中每個序列的每條語句的附加變量集進行分析，該附加變量集包括 DefVars 和 UseVars。該模塊對 Path Analysis 和 DefVars or UseVars Analysis兩個模塊的結果進行解析，分別獲取必須的信息，並將這些信息按結構有規律、有順序的組合在一起，形成可供中間分析的結果。(3a)路徑變量分析Variable Types Analysis模塊實現對程序執行軌跡中每個序列的每條語句的附加變量集進行DefVars和UseVars處理工作。該模塊對Path Analysis和DefVars or UseVars Analysis兩個模塊的結果進行解析,分別獲取必須的信息,並將這些信息按結構有規律、有順序的組合在一起，形成可供中間分析的結果。(3b) Variable Types Analysis 模塊將 Path Analysis 和 DefVars or UseVarsAnalysis兩個模塊的結果文件讀入到內存中，分別保存在DocDA和DocSA中，同時在內存中生成自己的結構DocVTA ;模塊解析DocDA和DocSA，將解析的結果存 入到DocVTA中。模塊解析在思想上是並發的，Doc之間互相不幹預。遍歷DocDA和DocSA中的元素，在內存中保存各個元素的信息，DocVTA使用這些信息。但在實際執行過程中，考慮到空間問題和效率問題，模塊是順序執行的。模塊首先計算程序執行序列，獲得本次執行序號ExecutionNum，將ExecutionNum記錄到DocVTA中。通過ExecutionNum在DocDA中獲得當前執行的類名ClassName,包括包名以及當前執行語句所在Java源文件的行號LineNum,將獲得的ClassName與LineNum記錄到DocVTA中。通過ClassName和LineNum信息,模塊在DocSA中查找到相應兀素的信息，包括定義變量集合DefVariables，使用變量集合UseVariables，變量類型VariableType，變量名稱VariableName ;這些信息將被DocVTA使用，構建自己的結構。通過這樣的流程,一次執行的Variable Types Analysis完成,而通過遍歷整個執行序列，模塊對程序一次執行的Variable Types Analysis完成。(4)控制依賴分析Control Dependence Analysis模塊是基於Soot開發的一個模塊，它對java的.class文件進行靜態分析，實現了對源程序中每條語句直接控制依賴結點的獲取功能。(4a)模塊首先獲取待分析的類，生成待分析類的Soot實例SootClass,再從中獲取待分析的方法，即類中的main方法，生成待分析方法的Soot實例SootMethod，並為SootMethod建立方法體SootBody,通過Soot提供的BriefUnitGraph類為方法建立控制流圖CFG。至此，模塊使用Soot對程序進行處理結束。(4b)在完成CFG流圖的建立後，接下來需要做的就是尋找控制流圖中各個結點的控制依賴關係。為了從控制流圖CFG獲取各結點的控制依賴關係，首先要建立控制流圖的後必經樹Post Domiante Tree，再利用相應算法對後必經樹進行處理，以此獲得後必經樹PDT中部分結點的控制依賴於關係Control Depends,最後通過對控制依賴於關係的處理，獲得控制流圖中各個結點的控制依賴關係Control Dependence。(5)對程序執行軌跡中每個序列的每條語句進行附加控制依賴工作。該模塊對Variable Type Analysis 和 Control Dependence Analysis 兩個模塊的結果進行解析,分別獲取必須的信息，並將這些信息按結構有規律、有順序的組合在一起，形成可供切片的最終中間結果。(5a)首先計算程序執行序列，獲得本次執行序號ExecutionNum，將ExecutionNum記錄到DocInterA中。通過ExecutionNum在DocVTA中獲得當前執行的類名ClassName,包括包名以及當前執行語句所在Java源文件的行號LineNum,將獲得的ClassName與LineNum 記錄到 DocInterA 中。(5b)通過ClassName和LineNum信息,模塊在DocVTA和DocCDA中分別查找到相應元素的信息。在DocVTA中查找定義變量集合DefVariables，使用變量集合UseVariables，變量類型VariableType，變量名稱VariableName，在DocCDA中查找控制依賴信息，這些信息將被DocInterA使用，構建自己的結構。通過這樣的流程,一次執行的Intermediate Analysis完成。而通過遍歷整個執行序列，模塊對程序一次執行的Intermediate Analysis完成。該模塊去除了前面兩個模塊分析結果的冗餘信息，是更高層模塊精確分析的基礎。不僅如此,Intermediate Analysis是中間信息處理的最後一步,它集合了對程序進行切片處理所需的/[目息。
(6)系統完成對Java過程內程序進行動態切片的功能。該模塊對IntermediateAnalysis的結果進行解析，獲取切片必要的信息。(6a)首先,獲取Intermediate Analysis Results的一次執行的信息,這些信息保存在一個ExecutionNum元素中，從信息中模塊可以獲得行號信息LineNum，此時模塊就可以對序號為ExecutionNum行號為LineNum的語句結點做NodeSlice。NodeSlice獲得的切片由三部分組成，分別是語句本身切片，結點直接控制依賴Control Dependence結點的切片，結點所有使用變量Use Variables的切片。(6b)語句本身很簡單，就是將語句行號加入到NodeSlice中。結點直接控制依賴Control Dependence結點的切片指結點的最近的直接控制依賴結點的切片。結點所有使用變量Use Variables的切片中在該結點出現的所有使用變量，它們各自切片的併集。得到三種切片後，對它們做併集處理，得到的結果即是序號為ExecutionNum行號為LineNum語句結點的NodeSlice。對於行號為LineNum的語句，若它的使用變量在其中並沒有被重定義，也就是語句執行前後它本身並沒有發生實質性變化。因此，語句中的使用變量的切片在語句執行前後並未發生變化。對於行號為LineNum的語句，若它的定義變量在其中被重定義，在語句執行前後它本身發生了實質性變化。因此，語句中的定義變量的切片在語句執行前後發生了變化。由於它的變化是由該語句引起的，因此，語句執行後，它的切片與語句的切片NodeSlice相同。(6c)NodeSlice完成後，需要修改或添加結點中所有定義變量的切片，它們的切片與NodeSlice相同，而使用變量的切片沒有發生改變。本發明的有益效果是，該動態切片系統依據堆棧跟蹤進行切片的方法，首先利用調試器的信息記錄程序執行軌跡，找出該次執行中涉及的語句；在記錄程序執行軌跡的同時計算程序的控制依賴關係得到程序切片，在程序切片的過程中不需要對程序進行回溯，大大提聞了算法的效率，根據控制依賴關係和變量的定義引用 目息提聞了切片的精度。


下面結合附圖和實施例對本發明作進一步說明。
圖I是本發明的Path Analysis模塊流程圖。圖2是本發明的DefVars or UseVars Analysis模塊流程圖。圖3是本發明的Variable Types Analysis模塊核心解析流程圖。圖4是本發明的Control Dependence Analysis模塊總體流程圖。
圖5是本發明的Intermediate Analysis模塊核心解析流程圖。
圖6是本發明的Slicer模塊算法流程圖。
具體實施例方式為了便於利用程序執行軌跡對程序進行切片，我們首先對切片過程的依賴關係進行定義
定義I控制依賴如果程序中語句u和w滿足以下三個條件，那麼就稱w直接控制依賴於U ;
1)從u到w之間存在一條路徑P；
2)從P上除U，w之外的每個節點V，節點w都是它的後向必經節點；
3)節點w不是節點u的後向必經節點。定義2控制依賴圖G (N，E)，N表示程序中語句對應的節點集合，E表示邊集，其中每條邊表示w控制依賴於U。定義3 數據依賴如果程序中，語句u對變量V進行了定義，w引用了變量V的值，並且U到W之間存在一條路徑，該路徑上沒有對V進行重新定義，那麼就稱W關於變量V直接數據依賴於W。定義4數據依賴圖G (N，E)，N表示程序中語句對應的節點集合，E表示邊集，其中每條邊表示W直接數據依賴於U。在圖中，該基於程序執行軌跡的動態切片系統的計算和設計包括如下步驟
(O系統獲得程序的執行路徑信息，即Path Analysis，獲取當前執行語句的信息。在得到當前執行語句的信息，對這些信息進行數據依賴分析，即DefVars or UseVarsAnalysis，得到當前執行語句的定義變量集和使用變量集。模塊核心功能是獲得待分析語句一次完整執行的執行序號ExecutionNum和語句行號LineNum。執行序號比較好分析，它是從I開始，並每次加I的執行序列，即I
23 4…η,其中η表不最後執行的序號。每個執行序號對應一個語句行號,表不程序第ExecutionNum執行語句LineNum,因為分析過程內程序,不需要考慮不同的類、不同的方法。語句行號需要從虛擬機獲取。在處理ThreadStartEvent時，即程序即將開始執行，設置StepRequest，虛擬機開始單步執行程序。單步執行的效果是在每條語句執行前，單步執行事件StepEvent發生，執行語句的線程被掛起，調試器獲得當前的執行位置信息Location，通過其模塊可以獲得當前執行的行號信息。信息獲取完成後，恢復掛起的線程。(2)對Java的.class文件進行靜態分析,實現了對Java源文件中每條語句中定義變量集DefVars和使用變量集UseDefs的獲取功能。(2a)首先，初始化Soot，完成Soot的初始設置工作。Soot是一種用於Java優化的框架，它為不同的分析目的提供了四種不同的中間表示，這裡需要做的是對Soot中的Jimple這一中間表示進行分析。Jimple是一種基於類型的3地址格式語句的中間表示,是一種介於Java原始碼和Java字節碼的中間表示。該模塊是對中間表示Jimple進行分析，獲得源文件的信息，因此在初始化工作中，需要進行一些設置，如Jimple中間表不的行號為原始碼中行號，Jimple中間表不的變量名為原始碼中變量名。只有通過這些設置，模塊才可以獲得完整、準確的原始碼信息，對原始碼完成 DefVars or UseVars Analysis 工作。(2b)完成Soot初始化工作後，接著需要做的便是獲取需要分析的類和方法。因為DynamicSlicer4j系統分析目標是Java過程內程序，因此,只需獲取類中的main方法即可。Soot會對待分析的類和方法分別建立自己的Soot類和Soot方法，即SootClass和SootMethod,並為Soot方法建立方法體SootBody,這樣就可利用Soot各個類提供的方法進行分析，大大提高分析的效率。(2c)通過SootBody,模塊可以獲得該方法中任一語句，Jimple中間表示的Soot實例，用Unit表示。Unit保存了該語句的所有信息，模塊只需從中獲取需要的信息就可以 了，即該語句的行號或該語句中的定義集合和使用集合，這樣，模塊即可實現DefVars orUseVars Analysis 功倉泛。(2d) Unit中的信息並非即得即用的,Unit保存的是Jimple中間表示的每一條語句，而原始碼中往往一條語句會有多條Jimple代碼，因此，如何將多條Jimple代碼獲得的信息集中到各自相應的Java原始碼，是一個需要處理的問題。還有，模塊通過調用Unit中的方法，可以輕易獲取Unit中的定義集合和使用集合，模塊需要的定義變量集合Def Vars和使用變量集合Use Vars就包含其中，如果把它們從中剝離出來，也是一個需要處理的問題。而且在處理獲得定義變量集合Def Vars和使用變量集合Use Vars時，還需要將在Jimple中間表示中產生的不屬於Java原始碼的臨時變量去除掉。通過步驟(2a)、(2b)、(2c)及(2d)的處理，才能獲得完整的、準確的定義變量集合Def Vars和使用變量集合Use Vars,由此完成執行DefVars or UseVars Analysis功能。(3)對程序執行軌跡中每個序列的每條語句的附加變量集進行分析，該附加變量集包括 DefVars 和 UseVars。該模塊對 Path Analysis 和 DefVars or UseVars Analysis兩個模塊的結果進行解析，分別獲取必須的信息，並將這些信息按結構有規律、有順序的組合在一起，形成可供中間分析的結果。(3a)路徑變量分析Variable Types Analysis模塊實現對程序執行軌跡中每個序列的每條語句的附加變量集進行DefVars和UseVars處理工作。該模塊對Path Analysis和DefVars or UseVars Analysis兩個模塊的結果進行解析,分別獲取必須的信息,並將這些信息按結構有規律、有順序的組合在一起，形成可供中間分析的結果。(3b) Variable Types Analysis 模塊將 Path Analysis 和 DefVars or UseVarsAnalysis兩個模塊的結果文件讀入到內存中，分別保存在DocDA和DocSA中，同時在內存中生成自己的結構DocVTA ;模塊解析DocDA和DocSA，將解析的結果存入到DocVTA中。模塊解析在思想上是並發的，Doc之間互相不幹預。遍歷DocDA和DocSA中的元素，在內存中保存各個元素的信息，DocVTA使用這些信息。但在實際執行過程中,考慮到空間問題和效率問題，模塊是順序執行的。模塊首先計算程序執行序列，獲得本次執行序號ExecutionNum，將ExecutionNum記錄到DocVTA中。通過ExecutionNum在DocDA中獲得當前執行的類名ClassName,包括包名以及當前執行語句所在Java源文件的行號LineNum,將獲得的ClassName與LineNum記錄到DocVTA中。通過ClassName和LineNum信息,模塊在DocSA中查找到相應兀素的信息，包括定義變量集合DefVariables，使用變量集合UseVariables，變量類型VariableType，變量名稱VariableName ;這些信息將被DocVTA使用，構建自己的結構。通過這樣的流程,一次執行的Variable Types Analysis完成,而通過遍歷整個執行序列，模塊對程序一次執行的Variable Types Analysis完成。(4)控制依賴分析Control Dependence Analysis模塊是基於Soot開發的一個模塊，它對java的.class文件進行靜態分析，實現了對源程序中每條語句直接控制依賴結點的獲取功能。(4a)模塊首先獲取待分析的類，生成待分析類的Soot實例SootClass,再從中獲取待分析的方法，即類中的main方法，生成待分析方法的Soot實例SootMethod，並為 SootMethod建立方法體SootBody,通過Soot提供的BriefUnitGraph類為方法建立控制流圖CFG。至此，模塊使用Soot對程序進行處理結束。(4b)在完成CFG流圖的建立後，接下來需要做的就是尋找控制流圖中各個結點的控制依賴關係。為了從控制流圖CFG獲取各結點的控制依賴關係，首先要建立控制流圖的後必經樹Post Domiante Tree，再利用相應算法對後必經樹進行處理，以此獲得後必經樹PDT中部分結點的控制依賴於關係Control Depends,最後通過對控制依賴於關係的處理，獲得控制流圖中各個結點的控制依賴關係Control Dependence。(5)對程序執行軌跡中每個序列的每條語句進行附加控制依賴工作。該模塊對Variable Type Analysis 和 Control Dependence Analysis 兩個模塊的結果進行解析,分別獲取必須的信息，並將這些信息按結構有規律、有順序的組合在一起，形成可供切片的最終中間結果。(5a)首先計算程序執行序列，獲得本次執行序號ExecutionNum，將ExecutionNum記錄到DocInterA中。通過ExecutionNum在DocVTA中獲得當前執行的類名ClassName,包括包名以及當前執行語句所在Java源文件的行號LineNum,將獲得的ClassName與LineNum 記錄到 DocInterA 中。(5b)通過ClassName和LineNum信息,模塊在DocVTA和DocCDA中分別查找到相應元素的信息。在DocVTA中查找定義變量集合DefVariables，使用變量集合UseVariables，變量類型VariableType，變量名稱VariableName，在DocCDA中查找控制依賴信息，這些信息將被DocInterA使用，構建自己的結構。通過這樣的流程,一次執行的Intermediate Analysis完成。而通過遍歷整個執行序列，模塊對程序一次執行的Intermediate Analysis完成。該模塊去除了前面兩個模塊分析結果的冗餘信息，是更高層模塊精確分析的基礎。不僅如此,Intermediate Analysis是中間信息處理的最後一步,它集合了對程序進行切片處理所需的/[目息。系統完成對Java過程內程序進行動態切片的功能。該模塊對IntermediateAnalysis的結果進行解析，獲取切片必要的信息。(6a)首先,獲取Intermediate Analysis Results的一次執行的信息,這些信息保存在一個ExecutionNum元素中，從信息中模塊可以獲得行號信息LineNum，此時模塊就可以對序號為ExecutionNum行號為LineNum的語句結點做NodeSlice。NodeSlice獲得的切片由三部分組成，分別是語句本身切片，結點直接控制依賴Control Dependence結點的切片，結點所有使用變量Use Variables的切片。(6b)語句本身很簡單，就是將語句行號加入到NodeSlice中。結點直接控制依賴Control Dependence結點的切片指結點的最近的直接控制依賴結點的切片。結點所有使用變量Use Variables的切片中在該結點出現的所有使用變量，它們各自切片的併集。得到三種切片後，對它們做併集處理，得到的結果即是序號為ExecutionNum行號為LineNum語句結點的NodeSlice。對於行號為LineNum的語句，若它的使用變量在其中並沒有被重定義，也就是語句執行前後它本身並沒有發生實質性變化。因此，語句中的使用變量的切片在語句執行前後並未發生變化。對於行號為LineNum的語句，若它的定義變量在其中被重定義，在語句執行前後 它本身發生了實質性變化。因此，語句中的定義變量的切片在語句執行前後發生了變化。由於它的變化是由該語句引起的，因此，語句執行後，它的切片與語句的切片NodeSlice相同。(6c)NodeSlice完成後，需要修改或添加結點中所有定義變量的切片，它們的切片與NodeSlice相同，而使用變量的切片沒有發生改變。
權利要求
1.基於程序執行軌跡的動態切片系統，其特徵是包括如下步驟 (O系統獲得程序的執行路徑信息，即Path Analysis，獲取當前執行語句的信息；在得到當前執行語句的信息，對這些信息進行數據依賴分析，即DefVars or UseVarsAnalysis，得到當前執行語句的定義變量集和使用變量集； (2)對Java的.class文件進行靜態分析,實現了對Java源文件中每條語句中定義變量集DefVars和使用變量集UseDefs的獲取功能； (3)對程序執行軌跡中每個序列的每條語句的附加變量集進行分析，該附加變量集包括 DefVars 和 UseVars ;該模塊對 Path Analysis 和 DefVars or UseVars Analysis 兩個模塊的結果進行解析，分別獲取必須的信息，並將這些信息按結構有規律、有順序的組合在一起，形成可供中間分析的結果； (4)控制依賴分析ControlDependence Analysis模塊是基於Soot開發的一個模塊，它對java的.class文件進行靜態分析，實現了對源程序中每條語句直接控制依賴結點的獲取功能； (5)對程序執行軌跡中每個序列的每條語句進行附加控制依賴工作；該模塊對Variable Type Analysis 和 Control Dependence Analysis 兩個模塊的結果進行解析,分別獲取必須的信息，並將這些信息按結構有規律、有順序的組合在一起，形成可供切片的最終中間結果； (6)系統完成對Java過程內程序進行動態切片的功能；該模塊對IntermediateAnalysis的結果進行解析，獲取切片必要的信息。
2.根據權利要求I所述的基於程序執行軌跡的動態切片系統，其特徵是所述步驟(2)中的對Java的.class文件進行靜態分析包括如下步驟 (2a)首先，初始化Soot，完成Soot的初始設置工作； (2b)完成Soot初始化工作後，接著需要做的便是獲取需要分析的類和方法； (2c)通過SootBody,模塊可以獲得該方法中任一語句,Jimp Ie中間表示的Soot實例，用Unit表示； (2d)在處理獲得定義變量集合Def Vars和使用變量集合Use Vars時，還需要將在Jimple中間表示中產生的不屬於Java原始碼的臨時變量去除掉。
3.根據權利要求I所述的基於程序執行軌跡的動態切片系統，其特徵是所述步驟(3)中的對程序執行軌跡中每個序列的每條語句的附加變量集進行分析包括如下步驟 (3a)路徑變量分析Variable Types Analysis模塊實現對程序執行軌跡中每個序列的每條語句的附加變量集進行DefVars和UseVars處理工作； (3b) Variable Types Analysis 模塊將 Path Analysis 和 DefVars or UseVarsAnalysis兩個模塊的結果文件讀入到內存中，分別保存在DocDA和DocSA中，同時在內存中生成自己的結構DocVTA。
4.根據權利要求I所述的基於程序執行軌跡的動態切片系統，其特徵是所述步驟(4)中的控制依賴分析包括如下步驟 (4a)模塊首先獲取待分析的類，生成待分析類的Soot實例SootClass，再從中獲取待分析的方法，即類中的main方法，生成待分析方法的Soot實例SootMethod，並為SootMethod建立方法體SootBody,通過Soot提供的BriefUnitGraph類為方法建立控制流圖 CFG ； (4b)在完成CFG流圖的建立後，接下來需要做的就是尋找控制流圖中各個結點的控制依賴關係。
5.根據權利要求I所述的基於程序執行軌跡的動態切片系統，其特徵是所述步驟(5)中的對程序執行軌跡中每個序列的每條語句進行附加控制依賴工作包括如下步驟 (5a)首先計算程序執行序列，獲得本次執行序號ExecutionNum,將ExecutionNum記錄到 DocInterA 中； (5b)通過ClassName和LineNum信息，模塊在DocVTA和DocCDA中分別查找到相應兀素的信息。
6.根據權利要求I所述的基於程序執行軌跡的動態切片系統，其特徵是所述步驟(6)中的對Intermediate Analysis的結果進行解析包括如下步驟 (6a)首先,獲取Intermediate Analysis Results的一次執行的信息,這些信息保存在一個ExecutionNum元素中，從信息中模塊可以獲得行號信息LineNum，此時模塊就可以對序號為ExecutionNum行號為LineNum的語句結點做NodeSlice ； (6b)將語句行號加入到NodeSlice中； (6c) NodeSlice完成後，需要修改或添加結點中所有定義變量的切片。
全文摘要
本發明涉及一種基於程序執行軌跡的動態切片系統，包括系統獲得程序的執行路徑信息、對Java的.class文件進行靜態分析、對程序執行軌跡中每個序列的每條語句的附加變量集進行分析、對源程序中每條語句直接控制依賴結點的獲取、對程序執行軌跡中每個序列的每條語句進行附加控制依賴工作及完成對Java過程內程序進行動態切片的功能。在程序切片的過程中不需要對程序進行回溯，大大提高了算法的效率，根據控制依賴關係和變量的定義引用信息提高了切片的精度。
文檔編號G06F11/36GK102789420SQ201210256470
公開日2012年11月21日 申請日期2012年7月24日 優先權日2012年7月24日
發明者姜淑娟, 張豔梅, 李威, 李海洋, 王興亞 申請人:中國礦業大學