面向程序理解的系統依賴圖構建算法

王克朝，王甜甜，蘇小紅，馬培軍，童志祥

(1.哈爾濱工業大學 計算機科學與技術學院，150001 哈爾濱;2.哈爾濱學院 軟件學院，150086 哈爾濱)

程序理解［1］是通過對程序的分析、抽象及推 理獲取知識的一個演繹過程，需要解決數據收集、知識組織及信息瀏覽3個方面的問題.解決這些問題的一個關鍵是程序的中間表示.

K.J.Ottenstein 等［2］提出了程序依賴圖的概念.S.Horwitz等［3］將程序依賴圖擴展為系統依賴圖，捕獲過程間的調用關系.系統依賴圖是程序基于圖形的中間表示，能清晰地表示出程序中的各種控制依賴和數據依賴關系及程序的語法與語義信息，因此在編譯器優化［4-5］、程序切片［6］、軟件審查［7］、軟件測試［8］、編程題自動評分［9-11］、克隆代碼檢測［12-13］以及軟件缺陷檢測［14-15］等領域得到了廣泛的應用.系統依賴圖的構建方法也得到了廣泛的研究，近年來提出了面向對象［16］、面向方面［17］以及函數式程序［18］的系統依賴圖的創建方法.

然而，程序理解過程中，常常需要按需的程序分析，如果程序規模較大，則很難一次理解、分析所有的系統依賴圖節點及邊;此外，由于編程語言的語法多樣性，同一個編程任務可由多種語法結構實現，這種現象稱為代碼多樣化，增加了程序理解的難度.因此，本文采取控制依賴和數據依賴分別求解，在控制依賴子圖的基礎上，按需進行數據流分析，降低了算法復雜度，使之適合于分析大規模代碼;將選擇語句和循環語句統一表示，將表達式表示為抽象語法樹，為實現程序標準化時進行語義等價的程序轉換和程序匹配提供了方便.

1 系統依賴圖的概念

定義1 程序依賴圖(Program Dependence Graph，PDG)單過程程序P的PDGG=(V，E)是一個有向圖.其中:V為節點集合，表示程序中的語句和謂詞;E?V×V為邊集合，表示節點間的數據依賴或控制依賴關系.

定義2 系統依賴圖(System Dependence Graph，SDG)多過程程序 P的SDGG={GPDGs，EInterpro}是一個有向圖.其中:GPDGs為PDG集合，每個過程(函數)表示為一個PDG;EInterpro為過程間調用邊與依賴邊的集合，過程間的調用邊將函數調用位置與被調函數的entry相連，過程間的數據依賴邊表示實參和形參間的數據流.

系統依賴圖包含控制依賴子圖和數據依賴子圖.

定義3 控制依賴子圖(Control Dependence Sub-graph，CDS)由節點和控制依賴邊構成，表示程序的控制流信息.

定義4 數據依賴子圖(Data Dependence Sub-graph，DDS)由節點和數據依賴邊構成，表示程序的數據流信息.

依賴圖中的邊主要有4種依賴關系:控制依賴、流依賴、聲明依賴和過程調用依賴.令v1，v2分別為依賴圖中的兩個節點，分別定義如下:

定義5(控制依賴) 如果v2的執行是由v1表示的謂詞在執行時確定的，那么v2控制依賴于v1.不從屬于任何控制謂詞的節點控制依賴于entry節點.

定義6(流依賴) 如果有一條從v1到v2的路徑，且存在一個在v2中定義并在v1中使用的變量，且該變量在從v1到v2的路徑上的其他任何地方沒有被重新定義，則稱v2流依賴于v1.

定義7(聲明依賴) 從聲明某變量的節點v1到后面的各個定義該變量的節點v2間的特殊的數據依賴.

定義8(過程調用依賴) 從函數調用節點v1到被調函數入口節點v2的邊.

2 面向程序理解的SDG自動生成模型

2.1 對傳統SDG的改進

1)傳統SDG數據流分析的復雜度高，不適合于大規模軟件分析，因此本文將SDG分解為CDS和DDS，基本操作基于CDS，只在需要數據流信息時，在CDS的基礎上計算數據流信息，這樣既可利用SDG能夠表示程序語法與語義信息及便于程序匹配的優點，又可降低數據流分析的復雜度，節省空間和時間，使之適合于分析大規模代碼.

2)傳統SDG以不同的形式表示各種選擇結構語句和循環語句，不利于代碼標準化操作，因此本文在SDG中新增加了選擇結構節點和循環結構節點類型.選擇結構節點包括selection節點和selector節點，統一了所有選擇結構語句if、if-else、switch和選擇運算符(?:)的表示形式，其中:selection節點為選擇結構;selector節點及其子節點為選擇分支.循環結構節點包括iteration節點和init-sub節點，統一了 for、while和 do-while的表示形式.其中iteration節點表示選擇結構，其子節點表示循環體中的語句，init-sub節點用于dowhile語句中.統一了選擇語句和循環語句表示，便于消除選擇結構和循環結構的語法表示的多樣化.

3)傳統的SDG將表達式表示為節點中的token串，這種表示方式不能充分表示表達式的語法結構，本文將表達式表示為抽象語法樹，連接到語句節點上.這樣，使得控制依賴樹不但可以表示控制流，還可以充分表示語法信息，便于執行指針分析和程序轉換.

2.2 自動生成模型

根據源程序SDG的特點，本文基于程序理解的基本原理將整個SDG自動生成過程劃分為:程序信息的提取、CDS的構造和DDS的構造.圖1給出了面向程序理解的SDG自動生成的模型.

圖1 面向程序理解的SDG自動生成模型

CDS是根據程序信息提取階段創建的token串、符號表和函數列表來構建的，在創建系統CDS的同時處理程序的某些語法錯誤.

DDS的構造本質上是建立流依賴邊和聲明依賴邊，可歸結到程序中到達-定值信息的求解.由于CDS包含控制流信息，可通過CDS獲得節點之間的控制依賴關系，從而獲得各個節點的到達-定值信息，因此可在創建完CDS后對其執行數據流分析，構建DDS.

3 CDS的構建

進一步分析程序信息提取階段創建的token串、符號表和函數列表來構建CDS，算法如圖2所示.其中:GS為語法棧，用來保存分析過程中需要記錄的語法信息;hQ為控制依賴節點隊列，用以記錄節點間的控制依賴關系.該算法識別程序的語法元素，并建立各個語句節點間的控制依賴關系，從而生成CDS.

圖2 系統CDS構建算法

4 按需DDS構建

數據依賴是節點表示的語句之間數據的定義和使用關系.數據依賴可分為不同的類型，如流依賴、聲明依賴等.

本文自底向上按需分析給定程序模塊的函數調用關系:對給定程序模塊的函數調用圖，首先計算其終端節點函數的數據依賴，然后自底向上分析該函數的主調函數的數據依賴，當終端節點存在多個主調函數時，只需分析終端節點一次，無需重復分析終端節點，也無需多個過程依賴圖拷貝.可以對給定程序模塊執行局部數據依賴分析，因此適用于分析大規模程序.

基于編譯器代碼優化領域中經典的迭代數據流分析算法，在CDS的基礎上計算數據依賴信息，建立DDS，其構建模型如圖3所示.

圖3 系統DDS構建模型

4.1 求到達－定值信息

要建立各種數據依賴邊應首先求節點間的到達-定值信息.到達-定值的相關概念如表1所示.

表1 數據流方程的定義

其中:

所有患者均順利完成手術。2組患者術前腰椎側凸Cobb角及腰椎前凸角差異無統計學意義（P ＞0.05，表1）；2組術后2周及1年腰椎側凸Cobb角及腰椎前凸角均較術前顯著改善，差異有統計學意義（P ＜ 0.05，表1）；A組術后1年腰椎側凸矯正率為79.2%，B組為81.4%，差異無統計學意義（P ＞ 0.05）。2組患者術前頂椎旋轉程度差異無統計學意義（P ＞ 0.05）；術后2周及1年頂椎去旋轉程度B組優于A組，差異有統計學意義（P ＜ 0.05，表2）。

1)變量x的定值是一個語句，它賦值或可能賦值給x.最普通的定值是對x的賦值或讀值到x中的語句.

2)如果有路徑從緊跟d的點到達p，并且在這條路徑上d沒有被注銷，則定值d到達p.

3)如果某個變量a的定值d到達點p，那么p引用a的最新定值可能在d點.如果沿著這條路徑的某兩點間是讀a或對a的賦值，那么注銷變量a的定值d.

為了計算到達程序中每個語句的定值的集合，首先計算局部的定值信息，然后通過控制依賴邊進行傳播.數據流信息可以由建立和解方程來收集，這些方程聯系程序不同點的信息.

當控制流通過一個語句時，語句末尾的信息是在這個語句中產生的信息或是進入語句開始點并且沒有被這個語句注銷的信息.由數據流方程可看出，算法的關鍵在于各個控制流節點的GEN和KILL集合的計算，而生成GEN和KILL集合則需要知道各個節點定值和使用了那些變量，用DEF與REF集合來表示.

4.1.1 計算REF與DEF集合

CDS中節點的 GEN、KILL、IN、OUT集合的計算都是基于各節點的REF與DEF信息的，所以從CDS的節點中收集REF與DEF信息對于到達-定值的計算是十分關鍵的.

CDS中每個節點都有一個REF和DEF集合.一個節點的REF集合包含了該節點進行計算時引用的所有變量，DEF集合包含了該節點計算的變量.如表2所示.

表2 基本表達式的REF集合定義

在建立好CDS后，便可以后根序遍歷CDS，根據節點的不同類型，采用表3中相應的表達式求其REF和DEF集合.

表3 各種不同類型的語句的REF和DEF集合定義

4.1.2 計算GEN和KILL集合

在獲得CDS中各個節點的REF和DEF集合信息后，GEN集合的生成將十分直接:在遍歷CDS時，如果當前節點是賦值語句節點或scanf語句節點，則根據它的DEF集合，由當前的節點號和DEF中的變量名組成GEN集合中一個元素，從而建立GEN集合.

KILL集合的生成需要對整個CDS中的節點進行多次遍歷.算法描述如圖4所示.

圖4 KILL集合求解算法

4.1.3 計算IN和OUT集合

為了傳播數據流信息，在計算到達-定值信息時需要使用IN和OUT集合.一個節點的IN集合由到達該節點的前一點的定值組成，OUT集合由到達該節點下一點的定值組成.由于一個語句節點的IN和OUT集合可能不同，本文為CDS中的每個語句節點都計算這兩個集合.

采用迭代法求各個節點的IN和OUT集合.在每次迭代時對CDS中每個節點N，使用KILL和GEN集合計算IN與OUT集合.IN［N］等于節點N在CDS中前驅節點的OUT集合，OUT［N］是用IN［N］、GEN［N］、KILL［N］生成的.算法描述如圖5所示.

圖5 到達－定值信息的求解算法

到此為止，CDS中每個節點的到達-定值信息就計算完畢了.

4.2 建立數據依賴邊

在獲得了各個節點的IN和OUT集合后，后根序遍歷CDS，利用各節點的IN集合和REF集合即可獲得節點間的數據依賴關系.具體的規則是如果當前節點的REF集合中某個變量名和IN集合中某個二元組中的變量名相同，則認為當前節點和IN集合同一個二元組中給出的節點之間存在流依賴關系，并將生成的流依賴關系放入表中存儲.建立流依賴邊和聲明依賴邊的算法如圖6所示.

圖6 程序系統DDS建立算法

5 系統依賴圖的生成實例

如圖7，8中所示的兩個示例程序，均實現相同的功能，但循環結構和選擇結構采用了不同的語法表示形式，Horwitz方法采用不同的形式表示這兩個程序，而本文創建的SDG可將這兩個語義等價程序表示成相同的形式，如圖9所示，從而可以統一分析、理解這兩個程序，降低了程序理解的復雜度.在此基礎上，可以進一步執行程序標準化轉換，消除代碼多樣化.

圖7 示例程序1

圖9 系統依賴圖實例

此外，與Horwitz方法相比，本文方法直接基于控制依賴子圖分析數據流信息，并且可實現按需的數據流分析，降低了數據流分析的復雜度，節省空間和時間，使之適合于分析大規模代碼.

圖8 與示例程序1語義等價的示例程序2

6 SDG在程序理解中的應用

本文提出的系統依賴圖生成算法已在“基于程序理解的C語言編程題自動評分系統”中得到了應用，整個評分過程劃分為3個階段:將程序代碼轉換成SDG;根據控制流和數據流對SDG進行標準化轉換;最后匹配標準化后的學生程序與模板程序控制依賴子圖，并根據匹配結果給出評分.由此可看到，編程題自動評分系統的基礎和關鍵是SDG.

本文算法還被應用于“語義相似的程序識別”中，識別大規模程序中語義相似的程序代碼［19］.其基本思想是:分別將待檢測的兩段源代碼解析為兩棵系統依賴圖的控制依賴樹，并分別執行基本代碼標準化;利用度量值方法提取兩棵基本代碼標準化后的控制依賴樹的候選相似代碼控制依賴樹;對提取的候選相似代碼，進行數據流分析，執行高級代碼標準化操作;計算語義相似度，獲得相似度結果，從而識別語義相似的程序代碼.

應用結果表明:本文構建的SDG能夠充分表示程序的語法和語義，既可應用于分析小規模程序代碼，也可應用于分析大規模程序代碼，對可執行按需數據流分析，具有較低的復雜度和較高的準確性，并為程序標準化與語義分析提供了方便.

7 結論

1)提出了一種面向程序理解的SDG構建算法，包含程序信息的提取、CDS的構建和DDS的構建3個階段.

2)改進了傳統的SDG，直接基于CDS分析數據流信息，統一表示選擇語句和循環語句，將表達式表示為抽象語法樹.

3)提出的SDG構建算法已被應用于基于程序理解的編程題自動評分系統和大規模程序的語義相似程序代碼識別中，結果表明該SDG能夠充分表示程序的語法和語義，且按需進行數據流分析的方法降低了程序理解和分析的復雜度.

［1］ EXTON C.Constructivism and program comprehension strategies［C］//Proceedings of the 10th International WorkshoponProgram Comprehension(IWPC'02).Washington，DC:IEEE Computer Society，2002:282-283.

［2］ OTTENSTEIN K J，LOTTENSTEIN M.The program dependence graph in a software development environment［C］//Proceedings of the First ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments.New York:ACM，1984:177-184.

［3］HORWITZ S，REPS T，BINKLEY D.Interprocedural slicing using dependence graphs［J］.ACM Transactions on Programming Languages and Systems，1990，12(1):26-60.

［4］ MATSUMOTO T，SAITO P，FUJITA P.Equivalence checking of C programs by locally performing symbolic simulation on dependence graphs［C］//Proceedings of the 7th International Symposium on Quality Electronic Design(ISQED'06). Washington， DC:IEEE Computer Society，2006:370-375.

［5］逄龍，王甜甜，蘇小紅，等.支持多程序語言的靜態信息提取方法［J］.哈爾濱工業大學學報，2011，43(3):62-66.

［6］SRIDHARAN M，FINK P J，BODIK R.Thin slicing［C］//Proceedingsofthe2007 ACM SIGPLAN Conference on Programming Language Design and Implementation.New York:ACM，2007:112-122.

［7］ANDERSON P，ZARINS M.The codesurfer software understanding platform［C］//Proceedings of the 13th International Workshop on Program Comprehension.Washington，DC:IEEE Computer Society，2005:147-148.

［8］MILLER J，REFORMAT M，ZHANG H.Automatic test data generation using genetic algorithm and program dependence graphs［J］.Information and Software Technology，2006，48(7):586-605.

［9］ WANG Tiantian，SU Xiaohong，MA Peijun，et al.Ability-training-oriented automated assessment in introductory programming course［J］.Computers ＆Education，2011，56(1):220-226.

［10］WANG Tiantian，SU Xiaohong，WANG Yuying，et al.Semantic similarity-based grading of student programs［J］.Information and Software Technology，2007，49(2):99-107.

［11］馬培軍，王甜甜，蘇小紅.基于程序理解的編程題自動評分方法［J］.計算機研究與發展，2009，46(7):1136-1142.

［12］楊軼，蘇璞睿，應凌云，等.基于行為依賴特征的惡意代碼相似性比較方法［J］.軟件學報，2011，22(10):2438-2453.

［13］WANG Tiantian，SU Xiaohong，MA Peijun.Program normalization for removing code variations［C］//International Conference on Computer Science and Software Engineering. Washington， DC:IEEE Computer Society，2008:306-309.

［14］SNELTING G，ROBSCHINK T，KRINKE J.Efficient path conditions in dependence graphs for software safety analysis［J］.ACM Transactions on Software Engineering and Methodology，2006，15(4):410-457.

［15］王甜甜，蘇小紅，馬培軍.程序標準化轉換中的指針分析算法研究 ［J］.電子學報，2009.37(5):1104-1108.

［16］DU Lin，XIAO Guorong，LI Daming.A novel approach to construct object-oriented system dependence graph and algorithm design［J］.Journal of Software，2012，7(1):133-170.

［17］ZHAO Jianjun，RINARD M.System Dependence Graph Construction for Aspect-Oriented Programs［R］.MIT-LCSTR-891，MIT:Laboratory for Computer Science，2003.

［18］SILVA J TAMARIT S，TOMáS C.System dependence graphs in sequential erlang［C］//Proceedings of the 15th International Conference on Fundamental Approaches to Software Engineering.Washington，DC:IEEE Computer Society，2012:486-500.

［19］王甜甜，馬培軍，蘇小紅，等.一種基于程序源代碼語義分析的代碼相似度檢測方法:中國，200910073094.4［P］.2009.