徐 東，狄效國，孟宇龍，馮曉寧

（哈爾濱工程大學計算機科學與技術學院，哈爾濱150001）

1 概述

系統(tǒng)依賴圖（System Dependence Graph，SDG）和程序切片技術作為軟件語義分析的重要分析技術，被應用到軟件語義分析的各個階段。系統(tǒng)依賴圖是在Ottenstein等人提出的程序依賴圖（Program Dependence Graph，PDG）［1］的基礎上，進行擴展后得到的可以表示程序內(nèi)過程間依賴關系的圖形化的表示結構。由于它能夠清晰地表示程序之間各種數(shù)據(jù)依賴或控制依賴關系，易于軟件開發(fā)測試人員對軟件的理解，因此被廣泛應用到軟件的語義分析中。文獻［2］通過對軟件的系統(tǒng)依賴圖進行分析查找相似性程序的惡意代碼。傳統(tǒng)的系統(tǒng)依賴圖不能表示面向?qū)ο笳Z言的封裝、抽象、繼承和多態(tài)等特性，因此，對原有系統(tǒng)依賴圖進行面向?qū)ο髷U充形成了面向?qū)ο笙到y(tǒng)依賴圖［3］。近幾年，又提出了面向方面系統(tǒng)依賴圖和函數(shù)式程序的系統(tǒng)依賴圖［4］。本文對程序的控制依賴圖和控制流圖（Control Flow Graph，CFG）［5］構建算法進行了深入研究，提出一種基于依賴圖等價代換的系統(tǒng)依賴圖優(yōu)化算法，將程序的系統(tǒng)依賴圖用程序依賴圖進行替代。

2 基于控制依賴子圖生成控制依賴圖

根據(jù)文獻［6］的介紹可知，控制依賴圖（Control Dependence Graph，CDG）是一種可以確定2條語句關系的有效手段，通過控制依賴分析，可以方便地判斷一條語句的執(zhí)行是否會影響到另一條語句的執(zhí)行，這是程序進行并發(fā)執(zhí)行的基礎。通過對程序內(nèi)控制依賴關系分析研究可以將其定義為：

定義1 假設U1，U2為源程序的2條語句，若U1與U2存在一條邊即U1→U2，存在一條從U1到EXIT的路徑，并且該路徑中不包括U2即：

U2?｛U1，U2，…，EXIT｜U1→U2→…→EXIT｝則認為U2控制依賴于

控制依賴子圖（Control Dependence Subgraph，CDS）［7］生成算法基本思想是：建立一條從函數(shù)的分支節(jié)點指向該函數(shù)的邊。具體操作是采用雙向鏈表的雙親表示法，即在每個節(jié)點中開辟一個新的域用來存儲其雙親節(jié)點，則該節(jié)點就有一條到父節(jié)點的反向依賴邊。

整個源程序的控制依賴圖創(chuàng)建是通過在控制依賴子圖中添加一系列節(jié)點以及若干組邊實現(xiàn)的。首先，為程序中所有函數(shù)創(chuàng)建函數(shù)列表，使用原函數(shù)的節(jié)點作為控制依賴子圖的入口節(jié)點。若函數(shù)中存在參數(shù)，則需要為函數(shù)中的每個參數(shù)建立f＿para＿node節(jié)點即函數(shù)參數(shù)信息結點，該節(jié)點包括了參數(shù)的類型和參數(shù)名等基本信息。為該節(jié)點生成指向函數(shù)的反向控制依賴邊。其次為源程序建立函數(shù)調(diào)用關系列表，該表主要存儲源程序中函數(shù)之間存在各種調(diào)用關系F1→F2構建程序控制依賴圖時需要在程序中添加代表函數(shù)調(diào)用的依賴邊。主要思想是首先對函數(shù)列表進行檢查，如果函數(shù)調(diào)用列表中存在的調(diào)用關系并且該調(diào)用是用戶自定義的函數(shù)調(diào)用，則為其建立call＿node節(jié)點即控制依賴邊信息節(jié)點，并在F1和F2之間添加控制依賴邊和反向控制依賴邊。其具體算法如下：

整個過程是在控制依賴子圖的基礎上通過Step1向其中添加一系列的函數(shù)參數(shù)信息節(jié)點，并為之添加指向該函數(shù)的反向控制依賴邊，之后通過Step2向控制依賴子圖中添加控制依賴邊信息節(jié)點和其他依賴邊信息，進而生成控制依賴圖。

3 控制流圖和程序依賴圖

3．1 控制流圖的生成算法

控制流圖是對一個程序或者程序內(nèi)過程的抽象，是編譯器內(nèi)部維護的抽象的數(shù)據(jù)結構?？刂屏鲌D在軟件的語義分析中起著十分重要的作用，通過將程序的源代碼用圖的形式表示出來，可以方便地獲取程序中語句的前后繼關系和程序的執(zhí)行路徑?？刂屏鲌D相關定義如下：

定義2 假設存在（n1，n2）∈E，其中，E代表控制流圖中邊的集合，則稱n1是n2的直接前驅(qū)，n2為n1的直接后繼。nall－pre＝｛b∈N｜（b，n）∈E｝，nall－pre表示節(jié)點n所有的直接前驅(qū)的集合。nall－next＝｛b∈N｜（n，b）∈E｝，nall－next表示節(jié)點n的所有后繼。需要注意的是在控制流圖中，一個節(jié)點最多存在2個直接后繼［7］。

定義3 如果存在一個語句序列：

path＝（n1，n2，…，nk），?i，0＜i＜k，ni∈nall－pre則認為path為一條可執(zhí)行路徑［7］。

CFG是G＝（N，E）的有向圖，為了方便操作在控制流圖中添加Entry和Exit節(jié)點，其中，Entry代表控制流圖的入口節(jié)點，是CFG中每個節(jié)點的前驅(qū)，Entry本身沒有前驅(qū)節(jié)點；Exit代表控制流圖的出口節(jié)點，它是CFG中每個循環(huán)或者過程中結束語句節(jié)點的后繼。并且為了能夠方便得到控制依賴邊將在Entry與Exit之間也加入一條邊。

CFG節(jié)點中包含了該節(jié)點相應的控制依賴信息和數(shù)據(jù)依賴信息的存儲域，因此，可以將CFG看作是一種載體，它承載著程序依賴圖中存在的各種控制依賴關系和數(shù)據(jù)依賴關系?？刂屏鲌D不僅可以清晰地表示程序間各種依賴關系，它在安全漏洞分析中也起著重要的作用。例如，如果在控制流圖中，沒有能夠正確到達代表著內(nèi)存空間釋放的節(jié)點的路徑，則會造成內(nèi)存泄露等問題［7］。

綜合國內(nèi)外早期對依賴圖的研究就會發(fā)現(xiàn)，傳統(tǒng)的做法是首先對控制流圖進行分析，然后構建程序的控制依賴圖和數(shù)據(jù)依賴圖（Data Dependence Graph，DDG）［7］，在這里采用先建立系統(tǒng)的控制依賴圖，然后在此基礎建立程序的控制流圖的算法。

3．2 數(shù)據(jù)依賴圖

數(shù)據(jù)依賴圖是對程序中2個或者2個以上語句節(jié)點之間存在的數(shù)據(jù)定義和使用關系的圖形化表示形式。本文可以對其進行如下定義：

定義4 假設語句節(jié)點V2對語句節(jié)點V1存在數(shù)據(jù)依賴，則V1與V2滿足以下關系［8］：

即在某一存儲空間MS內(nèi)節(jié)點V1與節(jié)點V2之間存在一條執(zhí)行路徑，則V1數(shù)據(jù)依賴于V2。根據(jù)數(shù)據(jù)依賴依賴關系的不同將其分為以下3種類型：

（1）流依賴

（2）輸出依賴

（3）反依賴

其中，V（W）表示在節(jié)點V處對數(shù)據(jù)空間進行寫操作；V（R）在節(jié)點V處進行讀操作。

在建立程序控制流圖后，就可以根據(jù)對控制流圖的數(shù)據(jù)依賴圖分析構建程序的數(shù)據(jù)依賴圖［9］。變量i的定義集合為DEF（i）和引用集合為REF（i），若節(jié)點P和節(jié)點Q滿足：

（1）P∈DEF（i）；

（2）Q∈REF（i）；

（3）在節(jié)點P和節(jié)點Q中存在一條路徑，該路徑?jīng)]有出現(xiàn)對變量i的重新定義，則稱節(jié)點Q數(shù)據(jù)依賴于P。

3．3 程序依賴圖

程序依賴圖是由程序的控制依賴圖、控制流圖和數(shù)據(jù)依賴圖組成，其中，控制依賴圖表示程序中各語句以及各代碼塊之間的控制依賴關系，控制流圖描述了程序間的控制流，數(shù)據(jù)依賴圖負責描述程序間數(shù)據(jù)依賴關系［10］。程序依賴圖中存在的主要依賴關系有：

（1）控制依賴

如果在程序中語句節(jié)點V1控制決定語句節(jié)點V2的執(zhí)行，則稱V2控制依賴于節(jié)點V1，記為：

程序的每一部分不是從屬于任何控制謂詞，而是依賴于入口節(jié)點的控制。控制依賴關系反應的是程序中的各種嵌套結構。

（2）數(shù)據(jù)依賴

V2使用了在V1中定義的變量i，存在一條V1～V2的路徑，在該路徑中i變量沒有被重新定義，就稱V2數(shù)據(jù)依賴于節(jié)點V1。其依賴關系表示為：

但是僅僅是程序依賴還不足以完成對軟件的分析，因為程序依賴圖是通常只能表示只有一個過程的程序，需要分析的程序通常都是由若干過程組成的，所以提出一種能夠分析由多個過程相互作用構成的程序的中間表示形式——系統(tǒng)依賴圖。

4 基于依賴圖等價代換的SSDG生成

基于程序依賴圖只能計算程序的過程內(nèi)切片，為了適應目前程序復雜多變性的特點，引入了程序的系統(tǒng)依賴圖，通過將程序依賴圖擴展成為SDG，可以很好地解決程序間過程調(diào)用的問題。因為SDG能夠表示程序間的調(diào)用關系，所以它也能夠表示過程間的參數(shù)傳遞。根據(jù)系統(tǒng)依賴圖的特點可以給出以下論斷：如果2個程序具有相同的系統(tǒng)依賴圖，則認為這2個程序是語義相同的。但2個語義等價的程序卻不一定具有相同的系統(tǒng)依賴圖。SDG結合了程序間的數(shù)據(jù)依賴和控制依賴，并將其轉(zhuǎn)換成為了一種單一結構的依賴關系，它很好地彌補了程序依賴圖，只能表示過程間依賴關系的不足，為軟件語義分析過程間的程序切片奠定了基礎［11］。

4．1 系統(tǒng)依賴圖的構造及存在的問題

系統(tǒng)依賴圖是對程序依賴圖的擴充［12］，程序中存在的過程間的相互調(diào)用關系都能夠在系統(tǒng)依賴圖中得到展示。需要在程序依賴圖的基礎上做以下工作：

（1）為每個程序中被調(diào)用的過程，增加一個entry節(jié)點。

（2）為程序中調(diào)用語句的每個實參增加Actualin和Actual－out節(jié)點，該語句節(jié)點與其實參的關系為控制依賴。

（3）為被調(diào)用過程內(nèi)的每個形參添加Formal－in節(jié)點，如果該形參在調(diào)用中發(fā)生狀態(tài)轉(zhuǎn)變，則為其添加Formal－out節(jié)點。新添加的節(jié)點與節(jié)點entry存在控制依賴。

（4）為entry節(jié)點與調(diào)用語句節(jié)點添加一條調(diào)用邊。

（5）為存在依賴關系的實參和形參添加依賴邊，添加Actual－in與Actual－out之間依賴邊。

程序的系統(tǒng)依賴圖相對于程序依賴圖來說，具有更加復雜的構造過程，即使是一個簡單的程序，其產(chǎn)生的系統(tǒng)依賴圖規(guī)模也相當龐大，這給基于系統(tǒng)依賴圖計算程序切片的算法帶來嚴重影響，稍微一點疏忽就可能會造成計算的程序切片結果不精確。針對這種情況，本文提出一種優(yōu)化程序的系統(tǒng)依賴圖的算法。首先對程序進行等價變換，然后再進行構造系統(tǒng)依賴圖。該算法的使用對降低系統(tǒng)依賴圖的時間復雜度，具有不可忽視的作用，有效地提高了計算程序切片的效率和準確率。

4．2 依賴圖等價代換算法

該算法的基本思想是采用程序依賴圖代替程序的系統(tǒng)依賴圖描述經(jīng)過變換后的過程間調(diào)用關系。

只有滿足了以下2個條件，程序P的程序依賴圖才能夠正確表示它的系統(tǒng)依賴圖：

（1）同步性

對于特定輸入，SDG發(fā)生中斷時，PDG也發(fā)生中斷。

（2）等值性

任何時候，PDG中和SDG中與興趣點相關的變量的值相等vp＝vs。其中，vs∈VS，vp∈VP，VS為SDG中與興趣點N相關的變量集合；VP為PDG中與興趣點N相關的變量集合。

用PDG等價代換SDG主要分為2個階段（等價轉(zhuǎn)換都是在子程序的副本中進行的，不會影響源代碼）：

（1）程序的變換

由于源程序代碼之間存在大量的依賴性，影響了程序切片的精度。為了更好地對算法進行描述，首先進行如下定義：

1）簡單變量：不依賴其他任何變量的變量。

2）復雜變量：依賴于其他復雜變量、常量或者簡單變量。

對以上2種變量進行簡單定義以后，介紹程序的變換規(guī)則：

1）對于包含多個的賦值語句的表達式，如m＝＋＋n，將其變?yōu)閚＝n＋1；m＝n。

2）將源程序中的常量符號用具體的值進行替換。

3）使用常量或者簡單變量等價代換復雜變量。

（2）用過程內(nèi)的調(diào)用關系替換過程間的調(diào)用關系

建立程序P的子過程參數(shù)關系映射表RMT，建立程序P調(diào)用關系表，通過該表記錄父過程調(diào)用子過程時形參與實參的對應映射關系。具體的轉(zhuǎn)換規(guī)則如下：

1）改變程序的形參表示形式，在符號表示上使其與實參保持一致。將映射關系保存到RMT表中，計算切片時統(tǒng)一使用實參表示。

2）如果存在actual＝C，則會有formal＝C，在RMT表中添加該映射關系。計算切片時使用C替代formal。

3）如果函數(shù)的返回值return不在實參與形參的并集中，則令return為實參，保存到映射關系表RMT中。

5 實驗結果與分析

根據(jù)控制依賴子圖和控制依賴圖的生成算法，建立程序的控制依賴圖。算法的基本流程：首先建立程序的函數(shù)列表和函數(shù)調(diào)用列表，為函數(shù)中的參數(shù)建立指向函數(shù)F的反響控制依賴邊，為用戶自定義的函數(shù)調(diào)用添加由被調(diào)用函數(shù)到調(diào)用函數(shù)的反響依賴邊。然后模擬3．1節(jié)提到控制流圖生成算法建立程序的控制流圖，在控制流圖的基礎上進行數(shù)據(jù)依賴分析建立數(shù)據(jù)依賴圖。圖1為一個采用傳統(tǒng)算法構造的關于程序mathCal的系統(tǒng)依賴圖。

圖1 傳統(tǒng)系統(tǒng)依賴圖

雖然mathCal程序代碼規(guī)模較小，但是其產(chǎn)生的系統(tǒng)依賴圖結構卻十分復雜。很小的疏忽就會使構建的系統(tǒng)依賴圖結果不準確，從而影響程序切片的計算，嚴重影響了軟件語義分析的結果。根據(jù)4．2節(jié)提到的依賴圖等價代換算法對程序mathCal進行變換后生成新的程序mathCal＿mod，代碼如下：

在這之后建立mathCal＿mod的系統(tǒng)依賴圖，如圖2所示。

圖2 簡化的系統(tǒng)依賴圖

對比圖2與圖3可以看出，通過系統(tǒng)依賴圖優(yōu)化算法得出系統(tǒng)依賴圖的節(jié)點數(shù)以及邊數(shù)明顯小于傳統(tǒng)算法得出的系統(tǒng)依賴圖中的節(jié)點個數(shù)和依賴邊邊數(shù)。

在此基礎上，本文對多個不同程序進行了一系列的實驗以作對比，其中，優(yōu)化前使用的是一般的系統(tǒng)依賴圖生成算法［13］，優(yōu)化后使用的是本文提出的系統(tǒng)依賴圖生成算法，實驗過程中分別選取不同規(guī)模的軟件程序進行實驗，優(yōu)化前與優(yōu)化后程序的節(jié)點個數(shù)的實驗結果如圖3所示。

圖3 優(yōu)化前后的節(jié)點個數(shù)

程序優(yōu)化前后依賴邊的邊數(shù)變化的實驗結果如圖4所示。

圖4 優(yōu)化前后依賴邊邊數(shù)

可以看出，使用系統(tǒng)依賴圖優(yōu)化算法得出的系統(tǒng)依賴圖的節(jié)點數(shù)和邊數(shù)明顯少于未使用系統(tǒng)依賴圖優(yōu)化算法時的數(shù)量，并且優(yōu)化的比例相當可觀，這可以很大程度上降低系統(tǒng)依賴圖的規(guī)模，并對以后的程序切片的速率也有一定的提升。依賴圖規(guī)模的降低使得依賴圖更加簡潔，從而可以提高程序切片的準確度。

6 結束語

本文介紹程序的各種圖形化表示形式，包括控制流圖、數(shù)據(jù)流圖、控制依賴圖、數(shù)據(jù)依賴圖、程序依賴圖以及系統(tǒng)依賴圖。在打破傳統(tǒng)的系統(tǒng)依賴圖構建流程的基礎上，提出一種先建立控制依賴圖，然后建立程序控制流圖的算法，并給出基于依賴圖等價代換的系統(tǒng)依賴圖優(yōu)化算法。實驗結果表明其有效性。在接下來的工作中，會將該算法進一步用在SSDG可達性動態(tài)切片生成中［14］，進而達到避免數(shù)據(jù)流程算法中因反復迭代造成復雜度高的缺陷，從而提高軟件系統(tǒng)的可信性和可靠性。

［1］Ottenstein K J，Lottenstein M．The Program Dependence Graph in a Software Development Environment［C］／／Proceedings of the 1st ACM SIGSOFT／SIGPLAM Software Engineering Symposium on Practical Software Development Environments．New York，USA：ACM Press，1984：177－184．

［2］楊 軼，蘇璞睿，應凌云，等．基于行為依賴特征的惡意代碼相似性比較方法［J］．軟件學報，2011，22（10）：2438－2453．

［3］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．

［4］Tamarit S J S，Tom S C．System Dependence Graphs in Sequential Erlang［C］／／Proceedings of the 15th Inter－national Conference on Fundamental Approaches to Software Engineering．Washington D．C．，USA：IEEE Computer Society，2012：486－500．

［5］石 峰．C＋＋語言的程序依賴圖的構造和應用研究［D］．西安：西安電子科技大學，2004．

［6］Baah G K，Podgurski A， Harrold M J． The Probabilistic Program Dependence Graph and Its Application to Fault Diagnosis［J］．IEEE Transactions on Software Engineering，2010，36（4）：528－545．

［7］王雅文．基于缺陷模式的軟件測試技術研究［D］．北京：北京郵電大學，2009．

［8］Antoniol G．XML－oriented GCC AST Analysis and Transformations［C］／／Proceedings of the 3rd IEEE International Workshop on Source Code Analysis and Manipulation．Washington D．C．，USA：IEEE Press，2005：869－901．

［9］Yuan Dong，Yang Yun，Liu Xiao，et al．A Data Dependency Based Strategy for Intermediate Data Storage in Scientific Cloud Workflow Systems［J］．Concurrency and Computation：Practice and Experience，2012，24（9）：956－976．

［10］王雪蓮．程序切片技術研究及其在軟件測試數(shù)據(jù)生成中的應用［D］．北京：北京化工大學，2005．

［11］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．

［12］Horwitz S，Liblit B，Polishchuk M．Better Debugging via Output Tracing and Callstack－sensitive Slicing［J］．IEEE Transactions on Software Engineering，2010，36（1）：7－19．

［13］李 鑫．GCC抽象語法樹的解析及控制依賴子圖的建立方法研究［D］．哈爾濱：哈爾濱工業(yè)大學，2008．

［14］馬 亮．面向?qū)ο蟪绦騽討B(tài)切片系統(tǒng)的研究與實現(xiàn)［D］．南京：南京航空航天大學，2007．