基于數(shù)據(jù)挖掘技術的軟件缺陷檢測方法研究

華中科技大學計算機科學與技術學院 雷 珂 何 威

1.引言

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

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

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

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

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

只能處理無向圖；

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

無法輸出有向頻繁子圖。

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

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

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

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

2.FFSM算法介紹

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

FFSM算法的基本思想如下：

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

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

(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-頻繁子圖具有子圖同構關系的所有圖，稱為Embedding list。k+1-頻繁子圖的支持度可以通過掃描Embedding list獲得，提高了支持度的計算速度如圖1所示。

3.HFFSM算法

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

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

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

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

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

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

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

有一個可選方案是，直接忽略邊的方向性，這也是很多其他算法包括FFSM采取的處理方式。從2.2節(jié)對PDG的介紹可以看出，從節(jié)點a到b的數(shù)據(jù)或控制依賴與從節(jié)點b到a的數(shù)據(jù)或控制依賴在語義上是不等價的。直接忽略邊的方向性必然導致得到圖無法準確反映程序內部元素之間的語義關系，挖掘得到的規(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ī)則中這樣的邊是沒有意義的，可以忽略)，所以不用考慮邊的兩個頂點的標簽相等的情況，這就意味著，在本文的問題范圍內上述缺陷是不需要考慮的。

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

因為該方法在將有向圖轉換為無向圖時保留了圖中邊的方向性，所以解決了問題二。通過邊的標簽的大小寫可以判斷邊的方向，即大寫意味著邊的方向是通過標簽大的節(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ù)這個性質，利用前面提到的頻繁單節(jié)點矩陣集和頻繁邊集可以對FFSM-Extension進行優(yōu)化。

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

4.實驗

4.1 實驗環(huán)境

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

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

HFFSM算法采用Java技術實現(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 實驗內容

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

①輸出結果分析比較

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

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

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

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

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

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

圖7 圖6的文本輸出

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

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

5.總結

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

[1]鄭人杰.軟件用戶盼望獲得精品[J].測控技術,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.