基于軟件網絡錯誤傳播分析的軟件質量量度

2012-08-01 05:39:18潘偉豐李兵

中南大學學報(自然科學版) 2012年11期

潘偉豐，李兵

(1.浙江工商大學計算機與信息工程學院，浙江杭州，310018；2.武漢大學軟件工程國家重點實驗室，湖北武漢，430072；3.武漢大學計算機學院，湖北武漢，430072)

復雜網絡可以用來描述從技術到生物直至社會各類開放復雜系統的骨架，而且是研究它們拓撲結構和動力學性質的有力工具，已成為極其重要且富有挑戰性的科學前沿。近年來，統計物理和復雜系統科學領域的研究人員嘗試將軟件結構用網絡的形式來描述，即將軟件元素(方法、類、包等)視為節點，元素之間關系(調用、繼承、關聯等)作為邊的軟件網絡，并結合復雜網絡的最新研究成果，對大量開源軟件系統進行了深入研究。如在軟件網絡拓撲結構特性研究方面，Potanin等[1-3]在不同層次(方法、類和包等)對大量開源軟件的依賴網絡進行了分析，發現這些網絡都具有“小世界”和“無標度”特性；韓明暢等[4-5]對Java和Linux等軟件系統進行分析，也發現了類似的結果。在軟件網絡演化機理研究方面，Krapivsky等[6]提出了一種基于復制和分岔規則的軟件演化模型；He等[7]從設計模式的角度提出了基于模式冷凍部分的軟件演化生長模型；Pan等[8]根據軟件網絡中節點和邊之間的交互與動態變化，提出了一種基于軟件網絡的軟件演化模型。在軟件復雜性度量和評估方面，Vasa等[9]提出了一套度量指標來檢測軟件開發過程中軟件結構的穩定性變化；Ma等[10]提出了一個層次型的度量體系，從不同層次、不同角度度量大規模軟件系統的各種結構特性。在軟件網絡指導工程實踐方面，Pan等[11]提出了一種基于復雜網絡社區發現的軟件重構技術。但是，目前從軟件系統復雜網絡的角度來研究軟件結構，揭示軟件內部結構和外部質量間關系的文獻較少。MacCormack等[12]提出了傳播代價(Propagation cost)的概念，并用于研究文件間的耦合網絡，從易變性角度衡量軟件的質量。劉婧等[13]定義了平均傳播代價(Average Propagation Ratio)，探討了面向對象軟件網絡的結構與平均傳播代價的內在關系，并用平均傳播代價對類級軟件網絡的質量進行量化。這些方法都是先求得單個節點的影響范圍，然后求所有節點影響范圍之和，最后將這個和進行單位化，作為系統質量的度量指標。實際上，這些方法考慮的僅僅是單個節點對整個軟件網絡結構的平均影響范圍，即單個節點改變(如修改、出錯等)會影響到的其他節點的數量，以此來評估軟件的質量。然而，現實中往往是多個節點同時改變，如多個節點同時被修改、出錯等，此時，研究這些改變對軟件網絡結構的影響對衡量軟件的質量至關重要。鑒于此，本文作者提出一種用于研究軟件質量的新方法，該方法將面向對象軟件系統在方法層次抽象成網絡模型——方法調用網絡，通過隨機和受控的方式向網絡中植入錯誤，研究錯誤在網絡中的傳播行為，并定義新的度量來刻畫錯誤傳播對軟件結構造成的影響，以此來量度軟件的質量。

1 基本概念及分析方法

圖1所示為本文分析方法的基本框架。以OO(Object-Oriented，OO)軟件為研究對象，對其源代碼進行語法/詞法分析，得到方法及方法間的調用關系；提取方法調用網絡；基于方法調用網絡進行錯誤植入研究；通過錯誤植入研究量度軟件質量。

1.1 OO軟件源代碼

本文選擇開源的OO軟件(主要指以c++和Java開發的系統)作為研究對象，主要出于以下考慮：(1)現有的相關研究工作，主要以OO軟件系統為研究對象，采用相同的編程范型，便于結果的比較和分析；(2)OO編程范型從20世紀90年代開始就廣為流傳，網上具有大量的開源軟件系統，便于獲取大量實驗源數據；(3)采用OO編程技術開發的軟件系統，內部結構比較清晰，軟件元素(方法、類、包等)及它們之間的關系比較容易提取。

1.2 軟件網絡模型

目前，使用復雜網絡模型研究軟件系統主要集中于3個層次，即方法層次、類層次和包層次。本文主要研究方法層次的軟件網絡的質量。

定義1 方法調用網絡MCN(Method-calling network)。面向對象軟件系統的方法調用網絡MCN可以用1個有向圖表示，即N=(M,C)。其中：N為網絡MCN；M為節點的集合，代表軟件中所有方法的集合；C為有向邊的集合，表示方法間的調用關系，由調用者指向被調用者。如圖2所示，方法b( )調用方法a( )，則MCN中有1條從b( )指向a( )的有向邊。

圖1 方法基本框架Fig.1 Framework of proposed method

圖2給出了1段Java寫的源代碼及其對應的MCN。

圖2 代碼段及對應的MCNFig.2 Code segment and its MCN

目前還沒有一種開源的工具能夠直接從軟件源代碼提取方法調用網絡。本文所有軟件的MCN都是由我們自主研發的軟件網絡分析工具SNAT[14](Software network analysis tool)自動提取的。SNAT可以實現從OO軟件源代碼生成各個層次(方法、類、包)的軟件網絡，然后，對軟件網絡進行一系列的度量、分析、可視化等，但該工具目前還不是開源的。

1.3 錯誤傳播特征及錯誤植入算法

錯誤傳播是分析可靠性系統不確定性的基本問題，可以發現系統中最易受到毀壞的部分及各部分之間的相互影響[15]。目前已有很多關于錯誤傳播方面的研究，如Voas等[16]提出了軟件中的錯誤傳播分析，主要用于計算某一源代碼位置傳播數據錯誤的概率；Hiller等[17]提出了一個分析軟件中數據錯誤傳播的框架；Johansson等[18]對操作系統內部的錯誤傳播進行了分析，等。但是，本文的錯誤傳播分析方法與以往的不同，是基于軟件拓撲結構的。

軟件錯誤種類各異，對系統的破壞性也不盡相同。有些軟件錯誤能夠導致系統的崩潰(如內存非法訪問)，而大部分的錯誤一般只是造成系統的輸出不能滿足用戶的要求。本文從軟件拓撲結構(方法調用網絡)的角度，通過錯誤植入來對軟件的質量進行研究，并不能詳盡地表達這些錯誤種類間的差別。為了簡化問題的研究，忽略了不同錯誤對軟件破壞程度的差異，并假設：(1)所有的錯誤僅僅會對軟件的運行正確性造成影響；(2)錯誤僅僅會在方法調用網絡中傳播。也就是說，錯誤只會出現在方法中，這些錯誤僅僅造成軟件不能完成既定的功能，不會給系統帶來嚴重的影響(如崩潰)，某個方法(節點)若存在錯誤，錯誤僅僅會傳播到與之有直接或間接關系的其他方法(節點)。

為了嚴格描述錯誤在MCN中的傳播過程，首先給出錯誤傳播關系及其他相關概念的形式化定義。

定義2 錯誤傳播關系(Error propagation relation)EPR(i,j)。設EPR是MCN節點集上的二元關系，i和j表示2個不同的節點。對于任一有序的節點對(i,j)，當且僅當j有1條有向路徑通向節點i時，稱節點i和節點j存在錯誤傳播關系EPR(i,j)，表示若節點i為錯誤節點，那么節點i的錯誤會傳播到節點j，使節點j也成為錯誤節點。

性質1 錯誤傳播關系具有自相關性，即(i,i)∈EPR恒成立。

性質2 錯誤傳播關系具有傳遞性。如果(i,j)∈

定義3 錯誤傳播域(Error-propagation field)EPF(i)。設EPF是MCN節點集上的一元關系，i和j示節點i的錯誤傳播域。顯然，1個節點的錯誤傳播域是該節點存在錯誤情況下，可能影響的最大范圍的一種描述。它由所有與節點i具有錯誤傳播關系的節點特別說明，|*|都表示集合*中元素的個數。

定義4 錯誤反向傳播域(Error back-propagation field)EBPF(i)。設EBPF是MCN節點集上的一元關系，達的所有節點的集合。

定義5 錯誤介數(Error betweenness)EB(i)。節點i的錯誤介數定義為其錯誤反向傳播域EBPF(i)中節點的個數，記為EB(i)=|EBPF(i)|。

顯然，EBPF(i)描述的是節點i可能受其影響的節點的集合，而EB(i)正是對這種影響能力的度量，即EB(i)越大的節點越容易受其他節點的影響而產生錯誤。

錯誤介數與文獻[10]中提出的波及度在形式上類似，但兩者含義不同。文獻主要用波及度對OO軟件的結構復雜性進行分析，而本文中的錯誤介數是對節點出錯可能性的一種衡量。

通過深度優先遍歷算法，可以在O(|M|+ |C|)時間內得到節點i的EPF(i)，EBPF(i)和EB(i)等值。

為了清楚地說明上面的定義和性質，以1個簡單有向網絡為例(圖3)。這個網絡由6個節點和5條有向邊組成。若節點D存在錯誤，因為B存在到節點D的有向路徑B→D，F存在到節點D的有向路徑所以，D，B，F和E都與D存在錯誤傳播關系，即：EPR(D,D)，EPR(D,B)，EPR(D,F)和EPR(D,E)∈EPR，EPF(D)={D,B,F,E}，|EPF(D)|=4。因為從B出發可達的節點集是{B,D,A}，所以DBPF(B)={B,D,A}，EB(B)=3。

圖3 簡單的有向網絡Fig.3 Simple direct network

軟件中的錯誤通常有2種引入方式：(1)程序員在軟件開發中不小心引入的錯誤，這些錯誤的引入往往是隨機的，其錯誤的引入位置、時間等都是不確定的；(2)人為地惡意破壞程序中的代碼。為了研究軟件的質量，模擬軟件錯誤的2種引入方式，進行了軟件MCN上的錯誤植入實驗，即：在MCN上選擇節點植入錯誤，根據錯誤傳播關系計算其錯誤傳播域，分析錯誤植入對軟件MCN造成的影響，并以此對軟件的質量進行評價。但是，這里考慮的是一種極端的情況，即不斷地選擇節點植入錯誤，一直到MCN中所有節點都成為錯誤節點為止。根據錯誤植入位置選擇方式的不同，分錯誤隨機植入和錯誤受控植入2種情況來進行研究。

為了衡量錯誤植入對MCN的影響，首先定義MCN的結構健壯度(Structure robustness)SR。

定義6 結構健壯度SR定義為錯誤植入后，未受影響的節點數占網絡總節點數|M|的比例，即：

其中：ierrorSet表示MCN中已被選擇植入錯誤的節點集合。以圖3為例，若節點B被首先選擇植入錯誤，那么ierrorSet={B}，SR=1-3/6=0.5；若A也被選擇植入錯誤，那么，ierrorSet={A，B}，SR=1-5/6=1/6，以此類推。

從SR的定義可以看出：在相同的錯誤植入數(即相同的|ierrorSet|)下，SR越大，表明ierrorSet中節點的錯誤只會傳播到較少一部分的節點中去，錯誤通過軟件結構進行傳播的能力比較弱，軟件結構的容錯能力比較強。反之，SR越小，表明ierrorSet中節點的錯誤對軟件造成的影響比較大，錯誤極易通過MCN傳播到其他的部分，并對軟件造成極大破壞。因此，可以通過SR來對軟件結構的質量進行評價。在相同的錯誤植入數下，一個結構設計良好的軟件應使錯誤傳播控制在盡可能小的范圍內(SR盡可能的大)，以降低錯誤通過軟件結構傳播對軟件造成的影響。

算法1 錯誤隨機植入。錯誤隨機植入，即隨機的選擇節點植入錯誤，根據錯誤傳播關系，分析錯誤在軟件MCN中的傳播行為，及其對軟件(SR)造成的影響。算法步驟如下：

步驟1 提取軟件方法調用網絡MCN(其實是MCN最大連通子圖，見實證部分的說明)作為算法的輸入；

步驟2 初始化算法運行的參數，包括：軟件MCN的節點數nNodes:=|M|；已經植入的錯誤數iErrors:=0；MCN中總共的錯誤節點數nErrors:=0；被選擇植入錯誤的節點集合ierrorSet:=NULL；錯誤節點集合errorSet:=NULL；

步驟3 若nErrors=nNodes，令fc1:=iError，并保存fc1，轉步驟6執行；否則，轉步驟4執行；

步驟4 隨機的選擇節點i(i∈(M-ierrorSet))植入錯誤，并將其放入集合ierrorSet，即ierrorSet:=ierrorSet∪{i}，計算結構健壯度SR，errorSet:=errorSet∪EPF(i)；iError:=iError+1，nError:=|errorSet|，保存iError和對應的SR；

步驟5 若nErrors＜nNodes，返回步驟3繼續執行；否則，執行步驟6；

步驟6 保存數據，結束算法執行。

算法2 錯誤受控植入。錯誤受控植入，即按使SR下降最快的節點順序植入錯誤。算法如下：

步驟1 提取軟件方法調用網絡MCN(其實是MCN最大連通子圖，見實證部分的說明)作為算法的輸入；

步驟3 計算MCN中所有節點i的|EPF(i)|，i∈M。選擇具有最大|EPF|的節點im，植入錯誤，并將其放入集合ierrorSet，即ierrorSet:=ierrorSet∪{im}，并將EPF(im)中的所有節點放入errorSet集，即errorSet:=EPF(im)∪errorSet，并使iError:=iError +1，nError:=|errorSet|，保存iError和對應SR；

步驟4 若nErrors=nNodes，令fc2=iError，并保存fc2，轉步驟7執行；否則，轉步驟5執行；

步驟6 選擇具有最大|EPF|的節點jm，植入錯誤，并將EPF(jm)中的所有節點放入errorSet集，并使iError:=iError +1，nError:=|errorSet|，保存iError和對應SR，轉步驟4繼續執行；

步驟7 保存數據，結束算法執行。

比較算法1和算法2可以發現：算法1和算法執行的次數可能不同，但2種算法最終都將使MCN中所有節點都成為錯誤節點。算法1中，受植入錯誤節點影響的節點也有可能被選擇植入錯誤；算法2中，一旦某一節點被選擇植入錯誤，則受該節點影響而出錯的其他節點將不可能被選擇植入錯誤。

雖然結構健壯度SR可用來描述錯誤動態植入過程中軟件結構的變化，但是，仍缺乏相應的度量來對軟件整體的結構質量進行衡量。基于錯誤植入實驗中保存的SR值，提出了一個新的度量指標——軟件質量系數(Software quality coefficient)SQC，用于從整體上對軟件的質量進行評估。

從SQC的定義可以看出：它綜合考慮了軟件錯誤隨機植入和受控植入對軟件造成的影響，能夠比較全面的從錯誤傳播的角度對軟件的質量進行度量。用SQC評價軟件質量，SQC值越大說明軟件結構的質量越好，錯誤通過軟件結構進行傳播的能力比較弱，軟件結構具有好的容錯能力；SQC越小，說明軟件結構對軟件錯誤比較敏感，軟件錯誤比較容易通過軟件的拓撲結構“放大”，從而對軟件造成極大破壞。因此，結構設計良好的軟件應使SQC盡可能大，以降低錯誤引入對軟件造成的影響。

2 實例驗證

2.1 數據來源

對將近20個開源的面向對象系統進行實例研究，都發現了類似的結果。這里以其中4個有代表性的系統為例進行說明。這些系統包括Tomcat 6.0.18(用java編寫的免費的Web服務器，支持Servlet和JSP規范，源代碼可在http://to mcat.apache.org/下載)、Azureus(用java編寫的BitTorrent的客戶端應用程序，用于下載發布的網上資源，源代碼可在http://azureus.sourceforge.net/下載)、Jxtaim0.1i(用java編寫的基于java加密擴展JCE和JXTA的即時通訊系統，源代碼可在http://jxtaim.sourceforge.net/下載)和jfreechart1.0.12(用java編寫的開放的圖表繪制類庫，是為application，applets，servlets以及JSP等使用所設計的。源代碼可在http://www.jfree.org/jfreechart/下載)。軟件規模(即方法的個數)從1萬多到3萬多不等。結果如表1所示。

從軟件源代碼提取的MCN，并非是全連通的，往往有幾個子圖構成。由于一個子圖上的錯誤不會傳播到另外一個子圖，所以本文只關注各軟件MCN的最大弱連通子圖MWCC[19](Maximal Weekly Connected Components)，以此來對軟件的結構質量進行研究。實驗中，算法1和算法2的輸入為MCN的最大弱連通子圖MWCC。圖4所示為各軟件MCN最大弱連通子圖的網絡圖。

表1 實驗系統的規模Table1 Statistics of subjects

圖4 軟件MCN的網絡圖Fig.4 Networks for MCNs of software

本文的實驗策略如下：首先，用MCN模型來描述這4個軟件系統，提取各個系統的MCN；然后，采用錯誤植入方法研究錯誤隨機植入和錯誤受控植入對MCN結構健壯度SR的影響，并分析決定SR的一些關鍵因素；最后，計算軟件質量系數SQC，從整體上評價軟件的質量，同時引入隨機有向網絡模型分析不同因素對軟件質量系數SQC的影響。

2.2 實驗結果與分析

圖5(a)～(d)所示為4個軟件MCN的結構健壯度SR與植入錯誤節點比例P(即|ierrorSet|/總的節點數)的關系曲線圖。為了降低隨機因素對實驗結果的影響，每個錯誤隨機植入實驗都獨立運行了10 000次，計算每次運行中的SR，然后取平均值。

從圖5(a)～(d)可以發現：(1)在錯誤隨機植入和錯誤受控植入時，隨著P從0增加到1，4個系統MCN的SR都從1迅速下降，這說明軟件系統是非常脆弱的，軟件錯誤極易通過軟件的拓撲結構進行傳播，造成軟件大部分功能的失效；(2)錯誤受控植入時，SR的下降速度都比在錯誤隨機植入時要快。這說明軟件MCN對隨機錯誤具有一定的容錯能力，但是，對錯誤受控植入側很脆弱，少量節點的出錯就會使整個系統的性能降低一半；(3)在錯誤隨機植入和錯誤受控植入的過程中，一旦P超過某一臨界值(錯誤隨機植入時的Pc1，錯誤受控植入時的Pc2)，SR都減為0，出現了一種類似于“反向滲流轉變”的現象[20]。這說明，一旦P超過某一臨界值，錯誤就傳播到了MCN的所有節點中。并且錯誤受控植入時的臨界值Pc2一般比錯誤隨機植入時的Pc1要低得多。這是因為在錯誤受控植入是按SR下降最快的節點順序植入錯誤的。

由于MCN的SR值是通過|EPF|來計算的，因此，可以推測上述這些特征可能與節點的|EPF|有關。為此，研究了上述4個系統的|EPF|及其與其他參數的相互關系。

圖5(e)～(h)所示為4個系統相應的累積|EPF|分布。可見：這些系統的累積|EPF|分布大致服從冪率分布，而且具有“長尾”特征。這說明，網絡中大多數的節點只有很小的|EPF|，而少數節點卻擁有很大的|EPF|。所以，在錯誤隨機植入時，擁有較小|EPF|的節點更有可能先被選擇植入錯誤，而錯誤受控植入是按SR下降最快的順序選擇節點植入錯誤的，因此，錯誤選擇性植入時，SR的下降速度比在錯誤隨機植入時更快。

同時，研究了節點|EPF|和EB的相互關系，其散

點圖如圖6所示。圖中每個節點代表1個方法(|EPF|，EB)對。可以發現：雖然這些系統來自不同的領域，但|EPF|和EB的相關性都展現了相似的趨勢，即：|EPF|大的節點一般擁有較小的EB，而EB大的節點一般|EPF|較小。這說明那些EB大的節點(處于較高層次的方法)若植入錯誤，對系統其他部分的影響比較小，而|EPF|大的節點(處于較低層次)對系統的影響比較大，若它們被植入錯誤，將導致其他很多部分也出錯。在錯誤隨機實驗過程中發現，導致錯誤隨機植入時SR快速下降的不是那些具有較大|EPF|的節點(如圖6中矩形框內的點)，因為這些節點數量較少，而是圖6中直線以上的節點，這些節點為數眾多，而且EB比較大，極易受其錯誤反向傳播域中節點的影響而成為錯誤節點。而那些同時具有較大|EPF|和EB的節點(如圖中橢圓框內的節點)是最易出錯且危害也比較大的節點。因為這些節點擁有較大的EB，極易受到其錯誤反向傳播域中節點的影響而成為錯誤節點，一旦這些節點出錯，它又將影響其EPF中的節點，導致錯誤快速的在MCN上傳播，使SR迅速下降。

圖5 SR vs.P和Pcum(|EPF|)vs.|EPF|圖Fig.5 SR vs.P and Pcum(|EPF|)vs.|EPF|

圖6 各系統|EPF|和EB的散點圖Fig.6 Scatter point graph of |EPF| and EB

各個節點|EPF|與其入度和出度的pearson線性相關性分析結果如表2所示，其中，Kin和Kout分別表示節點的入度和出度。從表2可以發現：節點的|EPF|和其入度之間具有顯著度為0.01的正相關性。這說明入度大(重用率高)的節點，它們的|EPF|(影響范圍)往往很大，一旦這些入度大的節點出錯，將給系統帶來比較大的危害。這一點與文獻[10]中的研究結果相符。所以，重用雖然提高了軟件開發的效率，但是，也可能給軟件質量帶來威脅，一旦重用率高的方法出錯，將造成其他很多方法也出錯。因此，對重用率高的方法，應該加大測試的力度，確保其正確性。同時還發現|EPF|與其出度具有顯著度為0.01負相關性，這說明處于較低層次的方法(|EPF|大的節點)不傾向于調用其他的方法。

表2 |EPF|和出/入度的相關性分析Table2 Correlation analysis of |EPF| and in/out-degree

為了從總體上評價錯誤植入對軟件造成的影響，從而評價軟件結構的質量，計算了各個系統的SQC，結果如表3所示。通過對比表1和表3可以發現：SQC大的系統，其規模不一定小(如Azureus的SQC在4個系統中排第2，但其規模在4個系統中是最大的)，反之亦然。這表明并不是規模越大的系統就越難以保障其質量，越簡單的系統其質量就越容易控制，軟件的質量與軟件的規模間并沒有必然的因果關系。

表3 MCN的SQC值Table3 SQC of MCN

由于網絡的結構可以通過各種參數來進行描述，如結構熵、平均度等[10]。為了進一步研究SQC和這些網絡統計參數之間的關系，引入文獻[21]中的隨機有向網絡模型，用該模型生成具有相同規模(即節點數)、不同邊數的有向網絡，并研究了網絡結構熵、平均度、平均|EFP|(各節點|EFP|之和取平均值)、平均EB(各節點EB值之和取平均值)與SQC之間的相互關系。生成的網絡節點數為1 000，邊數從3 000到10 000不等。每種邊數的網絡都生成100個實例，計算得到的網絡的結構熵、平均度、平均|EFP|、平均EB和SQC，然后取平均值，以降低隨機因素的影響。圖7所示為具有相同節點數，不同邊數的網絡的結構熵、平均度、平均|EFP|、平均EB和SQC。其中：H表示網絡的結構熵；avg(Degree)表示平均度；avg(|EPF|)表示平均|EFP|；avg(EB)表示平均EB。表4所示為部分參數間的pearson線性相關性分析。

圖7 Tomcat 6.0.18有向網絡Fig.7 Direct networks of Tomcat 6.0.18

表4 參數間線性相關性分析Table4 Correlation analysis of parameters

從圖7和表4可以發現：(1)在網絡規模一定的情況下，隨著網絡中邊數的增加，結構熵H、平均度avg(Degree)，avg(|EPF|)和avg(EB)也隨之增大，但是，SQC逐漸減小。這說明在網絡規模一定的情況下，邊數的增加使網絡越來越“無序”，網絡的連通性增強，avg|EPF|和avg(EB)增大，軟件質量系數SQC下降，即軟件的結構比較便于錯誤在其上傳播。因此，在軟件開發中，要將方法間的交互關系數控制在一定的范圍內；(2)網絡結構熵H和平均|EPF|之間存在著顯著度為**的強正相關性，與SQC間存在顯著度為**的負相關性。這說明在網絡規模一定的情況下，網絡越“無序”，其平均錯誤傳播域就越高，軟件質量就越低，極易被破壞。因此，軟件開發應該使軟件保持一定的“有序”性，這有利于提高軟件的質量。這與文獻[10]中的研究結果相符；(3)avg|EPF|與軟件質量系數SQC存在顯著度為**的負相關性。這說明網絡的平均錯誤傳播域越大，軟件質量就越低。

3 結論

(1)將復雜軟件系統抽象成方法調用網絡，研究了錯誤在該網絡上的傳播行為，提出了量度軟件質量的新度量——軟件質量系數(SQC)。

(2)SQC能有效度量軟件質量，并與其他結構參數具有密切的聯系：①節點|EPF|的冪律分布且具有“長尾”特征使軟件結構在錯誤隨機植入時比錯誤受控植入時更加健壯；②錯誤介數大的節點的大量存在使得軟件系統比較脆弱，極易被破壞；③入度大(重用率高)的節點是系統的關鍵點，這些點的出錯將給系統造成極大的損壞；④軟件質量系數與網絡中的邊數有關，在網絡規模一定的情況下，邊數的增大將降低軟件質量系數；⑤軟件質量系數與軟件的結構熵有關，在網絡規模一定的情況下，軟件的結構熵越大(“無序”)，軟件質量系數就越低；⑥軟件質量系數與軟件的平均錯誤傳播域有關，在網絡規模一定的情況下，平均錯誤傳播域越大，軟件質量系數就越低。

[1]Potanin A, Noble J, Frean M, et al.Scale-free geometry in OO programs[J].Communications of the ACM, 2005, 48(5):99-103.

[2]Concas G, Marchesi M, Pinna S, et al.Power-laws in a large object-oriented software systems[J].IEEE Transactions on Software Engineering, 2007, 33(10): 687-708.

[3]Pan W F, Li B, Ma Y T, et al.Multi-granularity evolution analysis of software using complex network theory[J].Journal of Systems Science and Complexity, 2011, 24(6): 1068-1082.

[4]韓明暢, 李德毅, 劉常昱, 等.軟件中的網絡化特征及其對軟件質量的貢獻[J].計算機工程與應用, 2006, 42(20): 29-31.HAN Ming-chang, LI De-yi, LIU Chang-yu, et al.Networked characteristics in software and its contribution to software quality[J].Computer Engineering and Application, 2006, 42(20):29-31.

[5]閆棟, 祁國寧.大規模軟件系統的無標度特性與演化模型[J].物理學報, 2006, 55(8): 3799-3084.YAN Dong, QI Guo-ning.The scale-free feature and evolving model of large-scale software systems[J].Acta Phsica Sinica,2006, 55(8): 3799-3084.

[6]Krapivsky P L, Redner S.Network growth by copying[J].Physical Review E, 2005, 71(3): 036118.

[7]He K Q, Peng R, Liu J, et al.Design methodology of networked software evolution growth based on software patterns[J].Journalof Systems Science and Complexity, 2006, 19(2): 157-181.

[8]Pan W F, Li B, Ma Y T, et al.A novel software evolution model based on software networks[C]//1st International Conference of Complex Networks.Shanghai, 2009: 1281-1291.

[9]Vasa R, Schneider J G, Nierstrasz O.The inevitable stability of software change[C]//23nd IEEE International Conference on Software Maintenance.Paris, 2007: 4-13.

[10]Ma Y T, He K Q, Du D H, et al.A complexity metrics set for large-scale object-oriented software systems[C]//6th IEEE International Conference on Computer and Information Technology.Seoul, 2006: 189-194.

[11]Pan W F, Li B, Ma Y T, et al.Class structure refactoring of object-oriented software using community detection in dependency networks[J].Frontier of Computer Science in China,2009, 3(3): 396-404.

[12]MacCormack A, Rusnak J, Bald Win C Y.Exploring the structure of complex software designs: An Empirical Study of Open Source and Proprietary code[J].Manag Sci, 2006, 52:1015-1030.

[13]Liu J, Lu J H, He K Q, et al.Characterizing the structural quality of general complex software networks[J].International Journal of Bifurcation and Chaos, 2008, 18(4): 605-613.

[14]劉婧.基于復雜網絡的軟件結構分析及優化研究[D].武漢:武漢大學軟件工程國家重點實驗室, 2007L 10-32.LIU Jing.Research on software structure analysis and optimization by applying complex network methodology[D].Wuhan: Wuhan University.State Key Laboratory of Software Engineering, 2007: 10-32.

[15]李愛國, 洪炳镕, 王司.基于錯誤傳播分析的軟件脆弱點識別方法研究[J].計算機學報, 2007, 30(11): 1910-1921.LI Ai-guo, HONG Bing-rong, WANG Si.An approach for identifying software vulnerabilities based on error propagation analysis[J].Chinese Journal of Computers, 2007, 30(11):1910-1921.

[16]Voas J, Morell L J.Propagation and infection analysis (PIA)applied to debugging [C]//IEEE Southeastcon’90.New Orleans,LA, 1990: 379-383.

[17]Hiller M, Jhumka A, Suri N.EPIC: Profiling the propagation and effect of data errors in software[J].IEEE Transactions on Computers, 2004, 53(5): 512-530.

[18]Johansson A, Suri N.Error propagation profiling of operating systems[C]//2005 International Conference on Dependable Systems and Networks (DSN).Yokohama, 2005: 86-95.

[19]Myers C R.Software systems as complex networks: Structure,function, and evolvability of software collaboration graphs[J].Physical Review E, 2003, 68(4): 046116.

[20]Albert R, Jeong H, Barabasi A L.Error and attack tolerance of complex networks[J].Nature, 2000, 406(6794): 378-382.

[21]Batagelj V, Mrvar A.Pajek 1.24[EB/OL].[2012-10-11].http://pajek.imfm.si/doku.php?id=down load