異常傳播網絡靜態建模方法及特性分析

邱 翔 張 莉

(北京航空航天大學 計算機學院，北京100191)

軟件系統功能的多樣化和復雜化使軟件魯棒性問題已經成為業界關注的主要問題之一.異常處理作為提高系統魯棒性的重要手段，它將系統在異常情況下的正常控制流與處理該異常的控制流進行分離.但遺憾的是，軟件系統的復雜性使異常控制流的分析越發的困難.在復雜的軟件系統中，異常處理機制與編程語言緊密耦合［1］.因此，本文關注的是Java語言的異常處理機制.對于Java語言而言，一旦拋出異常，程序會搜索匹配該異常的第1個catch塊進行異常處理.由拋出異常的方法到最終確定包含該異常類型處理塊的方法所途經的調用鏈就是該異常類型的異常傳播路徑.由于異常傳播的全局性［2］、弱邊界性［3］，增加了軟件維護過程的難度和成本.

以往研究者對異常傳播現象進行分析時，關注的是對單一傳播路徑的抽取和異常拋出源點的確定，而在異常傳播過程中存在多條異常傳播路徑都包含的方法節點，本文稱為紐帶節點，這類方法節點讓軟件系統中的異常傳播路徑不再是孤立的鏈式結構.異常傳播路徑通過這些紐帶節點進行關聯，出現了異常傳播的網絡化現象［2］.

隨著系統科學的發展，復雜網絡已作為理解和抽象復雜系統的有效手段.通過對軟件元素及其之間的關系進行網絡化描述，并由此分析軟件拓撲結構的特性及其演化規律，為軟件的開發和維護過程提供理論支持［4－6］.以方法調用關系為基礎的軟件網絡圖［4］具有高聚集系數和平均距離很小的小世界特性，其度分布基本符合冪律分布.本文所討論的異常傳播網絡的基礎同樣是方法調用依賴關系.因此，本文也將關注它的小世界特性及其度分布的分布特征.

本文關注的是Java中的可檢測異常(Compiled-Exception)［1］，又稱編譯期異常，該類異常可以通過對代碼或編譯中間結果的靜態分析完成對其傳播路徑的搜索.如無特殊說明，下文所提及的異常傳播路徑指的是針對可檢測異常的異常傳播路徑.在以往研究工作的基礎之上，首先對異常傳播路徑進行提取，然后通過定義異常傳播路徑中方法之間的異常傳遞關系對異常傳播網絡化特征進行統一描述，提出了異常傳播網絡模型.最后基于5個開源軟件包對度分布、傳播異常類型的層次分布、聚集系數以及平均最短路徑等指標進行分析.

1 相關研究

現有的關于軟件靜態結構的復雜網絡建模研究都是借鑒傳統軟件工程的建模技術，主要是針對結構化軟件和面向對象軟件.通過復雜網絡理論，編程元素及其之間的關系可以用于構造軟件系統的基本拓撲結構.例如結構化軟件的子過程或函數以及它們之間的調用關系［4］;面向對象軟件的類以及類之間的關系［4－5］.

隨著軟件魯棒性問題在業界重視程度的提高，異常傳播這一研究領域也受到國內外研究者越來越多的關注.其中比較著名的研究是文獻［6］針對面向對象軟件提出的Jex異常傳播分析工具.文獻［7－8］提出了基于控制流的異常傳播分析方法，該方法主要關注異常拋出和捕獲的程序上下文環境.文獻［2］針對異常傳播過程中的“重拋出”問題，對Java服務應用Tomcat進行“重拋出”的識別和數據可達性分析.

上述研究者都沒有對異常傳播結構的網絡化特征進行建模和分析，而更多的關注于對異常傳播路徑的提取以及異常拋出源點的識別.

2 異常傳播網絡

2.1 異常傳播結構

以Java為例，異常傳播結構的生成主要有以下 3 種情況產生［8］:

1)方法中try塊拋出異常且該方法的catch塊捕獲了異常，程序繼續執行;

2)方法中try塊拋出異常，該方法也找到了匹配的處理程序，但在catch塊又重新拋出了異常或又引發其他異常，異常將向外層的try塊(如果有try塊的嵌套)傳播或沿方法調用序列傳播;

3)方法中try塊拋出異常但該方法中沒有找到匹配的處理程序，異常將向外層的try塊(如果有try塊的嵌套)傳播或沿方法調用序列傳播.

由此可知，面向方法調用的軟件依賴圖構成異常傳播結構的基礎，方法之間的調用關系構成了異常傳播的路徑.

本文以往的工作［9］在方法層次對軟件依賴關系擴展，將方法和異常類型通過拋出關系和捕獲關系進行關聯，將軟件依賴關系和異常類型層次結構進行有機地結合，提出了軟件擴展依賴圖的概念.以軟件擴展依賴圖為基礎，提出了一種基于深度優先搜索的異常傳播路徑提取算法，將異常傳播結構描述成與某種被處理異常相關的方法調用鏈，即異常傳播路徑.

2.2 異常傳播網絡模型

采用文獻［9］提出的抽取算法對異常傳播結構進行抽取，可以獲取較為完整的異常傳播路徑.同時也可以得到與異常傳播路徑相關的異常拋出源點及與傳播過程相關的異常類型.本文在已有的工作基礎之上提出一種異常傳播網絡模型，定義如下:

異常傳播網絡 EPG=〈V，E〉，EPG為有向無權圖，V為節點集，對于任意vi∈V代表類或接口中的方法;E為節點之間邊的集合，對于任意有序對〈vi，vj〉∈V當且僅當vi與vj之間存在異常傳遞關系，即vi拋出異常E且vj是異常E的接收方法.

圖1為tomcat-coyote.jar的異常傳播網絡圖.

圖1 異常傳播網絡模型

3 異常傳播網絡的特性分析

本文以開源軟件DependceFinder(http://dep-find.sourceforge.net)對編譯后的中間結果jar包進行解析，生成描述方法調用關系的XML文件;開源框架 ASM(http://asm.ow2.org)可以實現對異常類型拋出和捕獲語義的識別，從而完成對異常傳播結構的抽取.

本文在對異常傳播網絡構建過程中，僅對jar包內的.class文件進行分析，并不包括第三方工具包，因此會對傳播路徑提取的完整性造成一定的影響.

本文將針對5個開源軟件進行異常傳播路徑的提取，選取的開源軟件如下:

1)ant.jar:流程腳本引擎，用于自動化調用程序完成項目的編譯、打包、測試等;

2)httpclient-4.0.1.jar:支持 HTTP 協議的客戶端編程工具包;

3)tomcat-coyote.jar:為 tomcat的容器提供了對底層socket連接數據的封裝;

4)log4j-1.2.16.jar:基于 java 的日志工具包;

5)jsse.jar:java安全套接字擴展包.

軟件包統計數據如表1所示.

表1 軟件包統計數據

3.1 度

度作為復雜網絡中節點的基本屬性之一，體現了節點在復雜網絡中的重要程度.節點vi的度定義為與該節點vi連接的其他節點的數目.作為有向網絡，度分為出度(out-degree)和入度(in-degree).在異常傳播網絡中，節點的出度表示該方法拋出異常過程的數目;而入度則表示該方法接收異常過程的數目，可能是對該異常類型的再次拋出或者處理.度的概念反映的是方法接收或拋出異常過程的數目，而忽略具體的異常類型.網絡中節點度的分布情況可以用分布函數P(k)表示.本 文 采 用 度 的 補 累 積 分 布 CCDF［10］(Complementary Cumulative Distribution Function)表示度的分布情況P(k)，即P(k)表示節點的度大于等于k(節點的出度或入度)的概率.

圖2 雙對數坐標系下異常傳播網絡度分布

圖2描述的是雙對數坐標系下5個軟件包異常傳播網絡度的CCDF分布.由圖可知:①異常傳播網絡的出度和入度分布在尾部都出現下墜現象，其主要原因是異常傳播網絡中存在極少的具有大量異常拋出過程數目或異常接收過程數目的方法節點，如tomcat-coyote.jar中入度的最大值為57，而此類節點只有1個，相似情況也發生在出度分布中;②5個軟件包的異常傳播網絡的規模差異較大，但其出度和入度分布卻十分相似;表2給出了度分布的線性相關系數.雖然異常傳播網絡分布尾部都出現下墜現象，但是其分布總體線性相關系數(R2)較高，說明傳播網絡的出度和入度基本滿足冪律分布.

表2 度分布線性相關系數

存在極少的具有大量出度或入度的節點是異常傳播網絡度分布尾部出現下墜現象的根源，而異常傳播網絡更多地關注同時具有高出度和高入度的方法節點，如 tomcat-coyote.jar中 org.apache.jk.config.WebXml2Jk.generate 方法入度為30，出度為31，這類節點是促使傳播結構網絡化的紐帶節點，又稱之為集散(hub)節點.文獻［11］的研究表明:降低入度hub之間的相互連接、減少入度hub的后繼節點數量可以降低大范圍變更的頻繁發生，提高軟件穩定性.針對這些集散節點的代碼變更將直接造成整個傳播網絡結構的變化.因此，這些節點將是軟件設計初期、后期程序理解以及維護的重點.

3.2 異常類型層次結構

在面向對象語言中，一個異常被表示為一個類的實例，這就為異常傳播路徑的提取帶來了挑戰.由于異常的分類來源于類的層次結構，因此，在對異常類型進行捕獲時可以發生如下情況:對異常類型A的捕獲語句可以實現對A的一系列子類型的捕獲，而異常的拋出也存在這種情況.而在算法實現過程中，異常類型層次結構是判斷方法所拋出的異常類型是否被捕獲的關鍵因素.

本文將異常傳播路徑中拋出或處理的異常類型信息與異常傳播網絡拓撲特征進行綜合分析以發現軟件開發人員在設計異常處理機制時對異常類型層次使用的傾向性.其中異常類型層次結構的第0層為Java的頂層異常類型，即java.lang.Th-rowable;第 1層 代 表 繼 承 于 java.lang.Throwable的異常類型，如 java.lang.Exception;第2～4層以此類推.

3.2.1 異常類型的拋出

在異常傳播結構提取時，是以對該異常的處理方法為搜索起點，配合異常類型層次結構的分析過程，實現對異常類型拋出關系的識別，如圖3所示.本文對拋出異常類型層次分布的描述以度分布為基礎，對于圖中的每個點的含義為:出度為k的節點集合的平均拋出異常類型層次，主要描述了節點異常拋出數目與拋出異常類型層次之間的對應關系.從圖中可以看出，ant.jar，tomcat-coyote.jar，jsse.jar拋出的異常類型層次比較穩定.ant.jar，tomcat-coyote.jar大部分集中在第 2 層，以java.io.IOException(繼承 java.lang.Exception)為主;jsse.jar大部分集中在第 3 層，以 java.net.SocketException(繼承 java.io.IOException)為主;在異常傳播過程中存在“不要傳播抽象異常”的原則［12］，而這5個軟件包都違背了上述原則，在其異常傳播過程中所拋出的異常類型主要集中在IOException或SocketException等抽象異常類型.

圖3 異常傳播網絡中拋出異常類型層次分布情況

3.2.2 異常類型的捕獲

與異常類型的拋出相比較，異常類型的捕獲總是在含有catch塊的方法節點中，因此，對于每一條傳播路徑，只有一個方法節點捕獲相關異常類型，如圖4所示.本文對捕獲異常類型層次分布的描述與拋出異常類型的層次描述類似，對于圖中的每個點的含義為:節點入度為k的節點集合的平均捕獲異常類型層次.圖中可見，與異常的拋出相對應，對異常的捕獲主要集中高層異常類型java.lang.Exception 或 java.io.IOException.其中一個原因是 java.lang.Exception 或 java.io.IOException作為異常類型層次結構的較高層次，在catch塊中可以處理所有子異常類型，為開發者提供了便捷，但為后續的軟件維護增加了異常語義分析的難度.另外，自定義異常的廣泛應用也是異常類型層次多樣化的一個原因.此外，異常類型的捕獲節點都集中在入度較少的節點中，同時也印證了4.1節中入度較高的節點是中轉節點的結論.

圖4 異常傳播網絡中捕獲異常類型層次分布情況

3.3 網絡平均距離與聚集系數

網絡中2個節點i和j之間的距離dij定義為連接這2個節點的最短路徑上的邊數.網絡中的平均最短路徑長度L定義為任何2個節點之間距離的平均值，即

式中N為網絡中的節點數［13］.對于平均距離較大的網絡，信息在網絡節點中傳播開來需要較長的時間.而對于平均距離較小的網絡，網絡的連接會相對較強，不容易被破壞，信息的傳遞也會更迅速、更穩定和更加準確可靠［11］.本文對任意2個節點之間的最短路徑采用BFS(廣度優先算法)進行可達節點的搜索，但對于異常傳播網絡而言，并不是強連通圖，因此，對于2個節點之間的不可達現象將不在平均最短路徑的計算范圍內.

聚集系數一般和平均最短路徑同時提到，它們是反映復雜網絡“小世界”特性的2個重要性質［13］.所謂網絡的聚集特性，意指網絡中你朋友的朋友可能彼此也是朋友.假設網絡中的一個節點vi有ki條邊與其他節點相連，這ki個節點成為節點vi的鄰居.這ki個節點的實際邊數為Ei和總的可能的邊數ki(ki－1)/2之比定義為節點vi的聚集系數Ci，即Ci=2Ei/ki(ki－1).整個網絡的聚集系數C為網絡中所有節點聚集系數Ci平均值［13］.

本文對表1中的軟件包進行平均路徑長度和聚集系數進行分析可知:①除了tomcat-coyote.jar的聚集系數大于隨機網絡，ant.jar，httpclient-4.0.1.jar和jsse.jar的聚集系數與隨機網絡持平，而log4j-1.2.16.jar的聚集系數為 0.對于小世界網絡，其聚集系數C?Crand，以上開源軟件包的異常傳播網絡都不具備“小世界”的特性，該現象主要是與異常傳播的“弱邊界性”相關，在復雜軟件系統中，異常的產生和處理過程并不一定在一個局部化區域內，異常傳播頻繁跨越組件的邊界［2］，降低了方法節點之間的緊密程度;②ant.jar，tomcat-coyote.jar和 jsse.jar的平均最短路徑都在兩跳以上，而 httpclient-4.0.1.jar和 log4j-1.2.16.jar的平均最短路徑小于兩跳.異常傳播網絡的平均最短路徑的主要影響因素是異常傳播路徑的跳數.除 tomcat-coyote.jar，ant.jar和 jsse.jar外，其余2個軟件包的異常傳播路徑中長度為2跳的比例都在90%以上，能夠遵循Shenoy提出的第3條規律:異常捕獲的代碼位置盡可能地靠近異常拋出的位置［14］，而 tomcat-coyote.jar，ant.jar和 jsse.jar的多跳數傳播路徑的比例(tomcat-coyote.jar-34.2%，ant.jar-74.9% 和 jsse.jar-52.8%)明顯大于其余2個軟件包［9］.

4 結論

在軟件工程領域，復雜網絡的廣泛應用使研究者對軟件結構有了更深一步的了解.傳統軟件網絡化建模聚焦于軟件的各個層次，通過實例化軟件各個層次的元素以及元素之間的關系，形成網絡化結構.本文在以往工作的基礎之上，通過定義異常在方法之間的傳遞關系，首次將單一、分割的異常傳播路徑進行網絡化建模.

本文選取5個不同類型的軟件包所抽取的異常傳播網絡進行特征分析.由分析可知，異常傳播網絡的出度和入度基本符合冪律分布;由異常類型層次的分析結果可知，異常傳播過程大多數違反了“不要傳播抽象異常”的原則;此外，由于異常傳播的“弱邊界性”，軟件異常傳播網絡的聚集系數都很低，使得無法體現“小世界”特性.

通過度分布、傳播異常類型的層次分布、聚集系數以及平均最短路徑等指標對其進行分析可知:①異常傳播網絡以網絡化的形式描述了軟件系統的異常處理架構，根據其度分布的特點，實施對集散節點數量的有效控制，能夠有效地降低軟件變更和維護的成本;②雖然在異常傳播過程中抽象異常仍然是軟件設計者在異常拋出和處理過程中的首選，但是將抽象異常實例化能夠有效協助追蹤異常傳播的源頭;③異常傳播網絡結構的聚集系數較低，沒有呈現軟件系統的高內聚特征，因此需要軟件設計者注重異常處理結構設計時的邊界性設計，以提高系統結構的穩定性和魯棒性.例如可以利用系統中各個模塊中確定的邊界為異常處理提供一個清晰的說明，因為這樣可以清晰地理解異常傳播路徑［12，15］.

在構建異常傳播網絡過程中，異常傳播路徑抽取的完整性將決定網絡的規模，由于本文考慮的抽取對象僅局限于軟件包本身的.class文件而不包含第三方文件，會對傳播路徑的完整性造成一定的影響.因此，進一步提高異常傳播結構的完整性是下一步工作的重點.

References)

［1］Wikipedia.Exception handling［EB/OL］.2011［2011-03-31］.http://en.wikipedia.org/wiki/Exception_handling#Checked_exceptions

［2］Fu C，Ryder B G.Exception-propagation analysis:revealing exception handling architecture in Java server applications［C］//Proc 29th international Conference on Software Engineering.Washington DC:IEEE Computer Society，2007:230－239

［3］Van Dooren M，Steegmans E.Combining the robustness of checked exceptions with the flexibility of unchecked exceptions using anchored exception declarations［C］//Proc OOPSLA'05.New York:ACM Press，2005:455－471

［4］Myers C R.Software systems as complex networks:structure function and evolvability of software collaboration graphs［J］.Physical Review E，2003，68(42):46116-1－46116-15

［5］Ma Yutao，He Keqing，Du Dehui，et al.A complexity metrics set for large-scale object-oriented software systems［C］//Proceedings of the Sixth IEEE International Conference on Computer and Information Technology.Washington DC:IEEE Computer Society，2006:189－195

［6］Robillard M，Murphy G.Static analysis to support the evolution of exception structure in object-oriented systems［J］.ACM Transactions on Software Engineering and Methodology，2003，2(12):191－221

［7］Mao Chengying，Lu Yansheng.Improving the robustness and reliability of object-oriented programs through exception analysis and testing［C］//Proc 10th IEEE International Conference on Engineering of Complex Computer Systems.Washington DC:IEEE Computer Society，2005:432－439

［8］姜淑娟，徐寶文，史亮，等.一種基于異常傳播分析的依賴性分析方法［J］.軟件學報，2007，18(4):832－841

Jiang Shujuan，Xu Baowen，Shi Liang，et al.An approach to analyzing dependence based on exception propagation analysis［J］.Journal of Software，2007，18(4):832－841(in Chinese)

［9］Qiu Xiang，Zhang Li，Lian Xiaoli.Static analysis for Java exception propagation structure［C］//2010 International Conference on Progress in Informatics and Computing.Washington DC:IEEE Computer Society，2010:1041－1046

［10］Siganos G，Faloutsos M，Faloutsos P，et al.Power laws and the AS-levelintemettopology［J］.IEEE/ACM Trans on Networking，2003，11(4):514－524

［11］錢冠群.基于復雜網絡的軟件靜態結構分析［D］.北京:北京航空航天大學計算機學院，2009

Qian Guanqun.Software static structure analysis based on complex network method［D］.Beijing:School of Computer Science and Engineering，Beijing University of Aeronautics and Astronautics，2009(in Chinese)

［12］Robillard M，Murphy G.Designing robust Java programs with exceptions［J］.ACM SIGSOFT Software Engineering Notes，2000，6(25):2－10

［13］何克清.軟件網絡［M］.北京:科學出版社，2007

He Keqing.Software network［M］.Beijing:Science Press，2007(in Chinese)

［14］Shenoy S.Best practices in EJB exception handling［EB/OL］.New York:IBM，2002［2011-03-31］.http://www.ibm.com/developerworks/java/library/j-ejbexcept/index.html

［15］Malayeri D，ldrich J.Practical eception secifications［J］.Advanced Topics in Exception Handling Techniques，LNCS，2006，4119:200－220

［16］Cacho N，Dantans F，Garcia A，et al.Exception flows made explicit:an exploratory study［C］//Proc XXIII Brazilian Symposium on Software Engineering.Washington DC:IEEE Computer Society，2009:43－53