華中科技大學(xué)計算機科學(xué)與技術(shù)學(xué)院 雷 珂 何 威

1.引言

隨著軟件應(yīng)用規(guī)模的日益擴大和軟件應(yīng)用環(huán)境的日益復(fù)雜，因為軟件質(zhì)量導(dǎo)致的事故給人們造成的損失越來越多，后果也越來越嚴重，比如IBM360操作系統(tǒng)的失敗、阿麗亞娜號航天火箭的爆炸[1]等。為保證軟件的質(zhì)量，必須檢測軟件缺陷并對其加以控制。

檢測軟件缺陷，通常指檢查代碼缺陷，其方法有很多種，包括人工審查、動態(tài)測試和靜態(tài)分析。程序語義分析方法是靜態(tài)分析常用的一種分析技術(shù)。它通過分析程序的控制流和數(shù)據(jù)流以及函數(shù)調(diào)用關(guān)系等計算程序的多種語義表示，如調(diào)用圖和依賴圖，來輔助軟件審查。這種方法最大的優(yōu)點就是不必執(zhí)行目標程序，就可以通過掃描并分析程序的源代碼并查找代碼中的特定模式（可以理解為編程規(guī)則）集合，較早地發(fā)現(xiàn)程序代碼中的缺陷。

最新的靜態(tài)分析工具將數(shù)據(jù)挖掘技術(shù)（通常是頻繁子圖挖掘算法）與程序分析相結(jié)合。為了構(gòu)造一個針對某一種類型的軟件缺陷的高效的靜態(tài)分析工具，必須使用適當?shù)念l繁子圖挖掘算法。而該類靜態(tài)分析工具的效率、性能的關(guān)鍵也就是頻繁子圖挖掘算法。

FFSM[5]算法是基于模式增長方法的。它與目前主流的頻繁子圖挖掘算法AcGM[2]、FSG[3]和gSpan[4]等方法相比，時間復(fù)雜度最優(yōu)、挖掘效率最高。它使用CAM來唯一標識圖，使用FFSM-Join和FFSMExtension來擴展頻繁子圖，并通過相應(yīng)的剪枝策略來獲得候選子圖。在計算支持度時，只對embedding list進行掃描，提高了計算的速度和效率。但是FFSM算法存在一定的局限性，有如下五個主要問題：

不能處理多重圖（即兩個節(jié)點之間可能存在一條以上的邊）；

只能處理無向圖；

FFSM-Extension需要對邊和節(jié)點進行枚舉，效率低；

無法輸出有向頻繁子圖。

FFSM挖掘得到的頻繁子圖無法準確地表征規(guī)則，無法應(yīng)用到軟件缺陷檢測中，實用性差。

針對上述提出的經(jīng)典頻繁子圖挖掘算法存在的問題，本文在經(jīng)典的算法FFSM的基礎(chǔ)上，提出了一種新的頻繁子圖挖掘算法HFFSM（High-performance Fast Frequent Subgraph Mining）。本文的主要工作概述如下：

提出一種將有向標記圖等價轉(zhuǎn)換為無向標記圖的方法，即該方法可以在有向圖轉(zhuǎn)換為無向圖之后保留原圖邊的方向性。而且該方法簡單、通用、可移植。

基于經(jīng)典頻繁子圖挖掘算法FFSM，提出一個能處理有向多重圖并得到有向頻繁子圖的，比FFSM效率更優(yōu)的頻繁子圖挖掘算法HFFSM。

2.FFSM算法介紹

FFSM算法使用鄰接矩陣表示圖，按照從上到下，從左到右的順序掃描鄰接矩陣的下三角，包括對角線，將得到的串表達式稱為圖的代碼，將最大的代碼稱為圖的規(guī)范表示，并把相應(yīng)的鄰接矩陣稱為圖的CAM（Canonical Adjacency Matrix）。

FFSM算法的基本思想如下：

(1)FFSM算法利用CAM來唯一標識圖。

(2)簡化輸入數(shù)據(jù)庫中的圖為無向簡單圖并利用CAM的性質(zhì)來解決子圖同構(gòu)問題。

(3)FFSM算法利用FFSM-Join和FFSMExtension操作來生成候選子圖。FFSMJoin根據(jù)k-頻繁子圖所屬類型的不同，采用不同的方式進行合并，生成k+1-頻繁子圖。FFSM-Extension每次在頻繁子圖上添加一條邊和新的節(jié)點來獲得新的頻繁子圖。

圖1 FFSM算法的核心思想

圖2 添加虛擬節(jié)點處理多重圖

圖3 邊方向性處理方案無法處理的例子

(4)剪枝：去除既非次優(yōu)CAM也非頻繁的子圖。

圖4 FFSM-Extension偽代碼：

圖5 FFSM-Extension偽代碼

輸入圖集中，與k-頻繁子圖具有子圖同構(gòu)關(guān)系的所有圖，稱為Embedding list。k+1-頻繁子圖的支持度可以通過掃描Embedding list獲得，提高了支持度的計算速度如圖1所示。

3.HFFSM算法

針對第一部分提到的FFSM的種種缺陷，本文針對第一部分中提出的HFFSM頻繁子圖挖掘算法的缺點，對原FFSM算法做出以下幾點改進：

(1)問題一解決方案：多重圖等價轉(zhuǎn)換為簡單圖

HFFSM算法無法處理多重圖，但是兩個頂點之間可能同時存在數(shù)據(jù)依賴和控制依賴或控制依賴邊和共享數(shù)據(jù)依賴邊，所以必須將多重圖轉(zhuǎn)換為簡單圖。

楊炯等人[6]提出虛擬節(jié)點的概念，對多邊情況進行處理，轉(zhuǎn)化為單邊。他們?yōu)榱颂幚硪粚?jié)點間的多條邊，使用一條長度為2通過一個新的虛擬節(jié)點連接到原終點的路徑來代替每一條多出來的邊。

如圖2所示，當節(jié)點1和節(jié)點2之間存在多條邊時，每一條多出來的邊通過添加一個虛擬節(jié)點將其轉(zhuǎn)換為長度為2的路徑。

(2)問題二和問題四解決方案：有向圖等價轉(zhuǎn)換為無向圖

由于HFFSM算法只能處理無向圖，而靜態(tài)分析得到的PDG圖卻是有向標識圖，所以必須將其轉(zhuǎn)換為無向標識圖。

有一個可選方案是，直接忽略邊的方向性，這也是很多其他算法包括FFSM采取的處理方式。從2.2節(jié)對PDG的介紹可以看出，從節(jié)點a到b的數(shù)據(jù)或控制依賴與從節(jié)點b到a的數(shù)據(jù)或控制依賴在語義上是不等價的。直接忽略邊的方向性必然導(dǎo)致得到圖無法準確反映程序內(nèi)部元素之間的語義關(guān)系，挖掘得到的規(guī)則也極有可能是虛假規(guī)則。

本文提出一個新方案來解決該問題。首先給出一個定義，以便于對邊的方向進行處理。

定義1：大邊和小邊

給定邊e＜a, b＞，la和lb分別是頂點a和b的標簽。如果la＞lb，則邊e為大邊；否則，邊e為小邊。

新方案包含如下三條規(guī)則：

大邊的標簽用大寫字母表示，小邊的標簽用小寫字母表示；

忽略共享數(shù)據(jù)依賴邊的方向，標簽統(tǒng)一用小寫字母表示；

添加虛擬節(jié)點之后邊的方向由原來邊的方向確定。

按照上述三條規(guī)則對原圖進行處理，就可以通過標簽的大小寫區(qū)分從節(jié)點a到b和從節(jié)點b到a的邊，同時大寫意味著邊的方向是通過標簽大的節(jié)點指向小的節(jié)點，小寫意味著邊的方向是通過標簽小的節(jié)點指向大的節(jié)點。

但是該方法存在一個缺陷——當邊兩個頂點的標簽相等時，使用該方法無法保證得到的無向圖與有向圖在語義上等價。如圖3所示，用上述方法處理完之后，左圖和右圖等價，但是它們在語義上并非等價。

但是，兩個頂點之間的邊是屬于數(shù)據(jù)依賴或控制依賴或共享數(shù)據(jù)依賴，同一類型的語句(頂點)間不會存在邊(即使存在，在規(guī)則中這樣的邊是沒有意義的，可以忽略)，所以不用考慮邊的兩個頂點的標簽相等的情況，這就意味著，在本文的問題范圍內(nèi)上述缺陷是不需要考慮的。

總之，通過上述三條規(guī)則，可以在本文的問題范圍內(nèi)(在挖掘編程規(guī)則時)將有向PDG圖等價轉(zhuǎn)換為無向標記圖。

因為該方法在將有向圖轉(zhuǎn)換為無向圖時保留了圖中邊的方向性，所以解決了問題二。通過邊的標簽的大小寫可以判斷邊的方向，即大寫意味著邊的方向是通過標簽大的節(jié)點指向小的節(jié)點，小寫意味著邊的方向是通過標簽小的節(jié)點指向大的節(jié)點。因此可以將挖掘得到的無向頻繁子圖還原為有向頻繁子圖，解決了問題四。另外，本方案是針對于標記圖，所以可以很方便的移植到同類算法中去，如gSpan。

(3)問題三解決方案：FFSM-Extension的改進

FFSM-Extension操作是向CAM添加一條從一個新節(jié)點到CAM最后行表示的節(jié)點的邊。其有兩個限定條件：

CAM必須是outer矩陣(矩陣最后一行除對角線元素之外有且僅有一個非0元素)。

添加的邊必須是CAM最后一行表示的節(jié)點到一個未在CAM中的節(jié)點的邊。

FFSM-Extension偽代碼，如圖4所示。

一個圖是頻繁的，那么圖中的每個節(jié)點和邊必然也是頻繁的。根據(jù)這個性質(zhì)，利用前面提到的頻繁單節(jié)點矩陣集和頻繁邊集可以對FFSM-Extension進行優(yōu)化。

從頻繁單節(jié)點集中去除已經(jīng)在M中的節(jié)點，然后遍歷頻繁單節(jié)點集。對于其中的每一個節(jié)點，檢測其和M的最后一行表示的節(jié)點間是否存在邊，若存在其且未包含在M中而包含在頻繁邊集中，則添入該節(jié)點和邊生成新的矩陣。利用該方法可以避免產(chǎn)生一些非頻繁的矩陣。要檢驗每個矩陣是否為次優(yōu)CAM、是否頻繁，這些都會帶來資源的消耗，所以盡量減少非頻繁矩陣的產(chǎn)生可以帶來效率的提高。FFSMExtension偽代碼，如圖5所示。

4.實驗

4.1 實驗環(huán)境

圖6 頻度為5時FFSM輸出的一個頻繁子圖

圖8 HFFSM VS FFSM在不同頻度閾值下運行耗時

HFFSM算法采用Java技術(shù)實現(xiàn)。

實驗運行的硬件環(huán)境：

CPU是Intel(R)Core(TM)2 Duo CPU T6400(2.00GHz)，

一級緩存128KB，二級緩存2MB，

RAM是DDR2 800MHz 2.00GB。

實驗運行的軟件環(huán)境：

操作系統(tǒng)是Windows 7旗艦版32位，

編譯軟件是Eclipse SDK v3.7.1和jdk1.7.0、jre7。

4.2 實驗內(nèi)容

本部分主要比較HFFSM算法和改進過FFSM-Extension后的FFSM算法的性能。

①輸出結(jié)果分析比較

圖6是頻度閾值為5時，F(xiàn)FSM算法輸出的一個頻繁子圖，圖7是其文本輸出。

與HFFSM輸出的結(jié)果不同，因為FFSM算法只能處理和輸出無向圖，從圖3和圖4很難判斷其對應(yīng)的源程序代碼，以及其代表的規(guī)則的含義，也就是說，F(xiàn)FSM挖掘得到的結(jié)果無法表征編程規(guī)則，在實際應(yīng)用中基本無法使用。

而HFFSM算法輸出的是有向圖，通過邊的方面可以知道程序的執(zhí)行規(guī)則，從而可以還原圖為超圖中的源代碼，便于理解規(guī)則的含義。

綜上所述，F(xiàn)FSM算法只能輸出無向頻繁子圖，HFFSM算法可以輸出有向頻繁子圖。FFSM算法無法準確表征編程規(guī)則，HFFSM算法不僅可以準確表征編程規(guī)則，還可以將規(guī)則還原為相應(yīng)的源代碼，比FFSM算法具有更高的實用性。

②不同頻度閾值下的運行耗時

圖8是HFFSM和FFSM在不同頻度閾值下運行耗時的圖。

圖7 圖6的文本輸出

由圖8可知，HFFSM和改進FFSM-Extension后的FFSM在運行時間，即算法運行的時間效率上基本沒有差別，所以本文對FFSM的改進并未造成算法效率的降低。

由于對于FFSM的改進是將新的操作插入到原算法的實現(xiàn)中，例如對方向性的改進就是在解析輸入PDG圖文件時判斷大小邊對標簽進行處理。所以，保證了改進算法時效率基本等效。

5.總結(jié)

采用靜態(tài)分析技術(shù)可以較早地發(fā)現(xiàn)程序代碼中的缺陷，以便于得到高質(zhì)量的軟件。但是，沒有一種軟件缺陷檢測技術(shù)能夠檢測所有的軟件缺陷，靜態(tài)分析技術(shù)只能查找某些特定模式或規(guī)則。為了處理有向多重圖、得到有向頻繁子圖并提高算法效率和實用性，尤其是減少算法應(yīng)用時的虛假警報，本文在經(jīng)典的算法FFSM的基礎(chǔ)上，提出了一種新的頻繁子圖挖掘算法HFFSM。通過實驗表明，本文算法比FFSM在時間效率上略有提高，但是避免了輸出的一些錯誤的頻繁子圖，提高了算法的準確率。同時，算法輸出的頻繁子圖是有向圖，能夠更加精確地表征規(guī)則，提高了算法的實用性。由于頻繁子圖挖掘算法和圖結(jié)構(gòu)都很復(fù)雜，處理時難度較大，本文算法仍有許多不足亟待解決。

[1]鄭人杰.軟件用戶盼望獲得精品[J].測控技術(shù),2000,19(2):1-5.

[2]A.Inokuchi,T.Washin,K.Nishimura,H.Motoda.A Fast Algorithm for Mining Frequent Connected Subgraphs.Research Report RT-0448,IBM Tokyo Research Lab,2002.

[3]M.Kuramoehi,G.Karypis.Frequent Subgraph Discovery.Proceedings of IEEE the 2001 International Conference on Data Mining(ICDM’01),November 2001:313-320.

[4]X.Yan,J.Han.gSpan:Graph-based Substructure patterns Mining.Proceedings of IEEE the 2002 International Conference on Data Mining(ICDM’02),2002:721-724.

[5]J.Huan,W.Wang,J.Prins.Efficient Mining of Frequent Subgraphs in the Presence of Isomorphism.Proceedings of IEEE the 2002 International Conference on Data Mining(ICDM’03),2003:549-552.

[6]Ray-Yaung Chang, Andy Podgurski,Jiong Yang.Discovering Neglected Conditions in Software by Mining Dependence Graphs,2008,34(5):579-596.