成小芹， 王一莉

(南京工業(yè)大學電子與信息工程學院，江蘇南京211816)

0 引 言

在面向?qū)ο筌浖臏y試過程中，如何合理有效地分配有限的資源，從而在規(guī)定的時間內(nèi)完成軟件的測試，是一個非常重要的問題。目前是利用內(nèi)聚性、耦合性和復雜性來判別可能存在缺陷的類，然后據(jù)此分配測試資源。但是，僅僅通過識別可能有質(zhì)量缺陷的類不足以為資源的分配提供依據(jù)，還需要識別重要的類。對于重要的類而言，即使它們的內(nèi)聚性、耦合性和復雜性都很合理，也需要給它們分配相對多的資源進行更加仔細的測試，因為重要的類隱藏的故障就可能越多。從這個角度來說，類的重要性度量可以看作是提高軟件可測試性的一個補充。目前對類的重要性的度量的研究比較少，中心性是網(wǎng)絡(luò)分析中的最基本的概念之一，研究人員依據(jù)各種標準提出了許多中心性指標來度量網(wǎng)絡(luò)中的重要的節(jié)點，中介中心性就是其中一個很重要的指標，它可以用在很多方面，如社會關(guān)系學，生物學以及道路網(wǎng)絡(luò)等，在實際的應(yīng)用中依據(jù)節(jié)點的重要性和角色，制定出更加可行的解決方案。由此想到，中介中心性同樣可以應(yīng)用到類的重要性的度量中，找出類中重要的類，然后對這些類進行重點測試，從而提高軟件可測性?，F(xiàn)在面向?qū)ο蠹夹g(shù)在軟件工業(yè)中應(yīng)用比較廣泛，而除了與傳統(tǒng)測試方法具有相似之處，面向?qū)ο筌浖€為可測試性制造了一些獨特的障礙。類圖中存在的客戶供應(yīng)關(guān)系會引起可測試性問題。文章針對面向?qū)ο筌浖?，使用UML類圖對其進行類的重要性度量，希望能對合理安排軟件測試資源，保證軟件質(zhì)量，提供借鑒和參考。

1 類的重要性

1.1 重要類的定義

如果一個類被很多類依賴，那么對這個類進行修改有可能會影響許多依賴于它的類，一般可以認為這樣的類是重要的類。其實對于如何判斷重要的類可以根據(jù)用戶給定的標準來定義，例如，如果一個類直接或間接地依賴于許多其他的類，那么這個類就有可能比其他的類更容易產(chǎn)生故障，對測試者而言這樣的類也是重要的類，需要進行重點測試。

1.2 類重要性的標準

上文說到判斷重要的類的標準可以根據(jù)用戶的特定需求，下面列出常規(guī)的標準：

標準1：一個類是重要的當且僅當有很多重要的類依賴于它。

標準2：一個類是重要的當且僅當它依賴于很多重要的類。

標準3：一個類是重要的當且僅當它接近類間依賴圖的中心。

根據(jù)標準1的定義，一個類重要與否取決于2個要素：①依賴于它的類的數(shù)量越多，它就越重要；②依賴于它的類的重要程度越高，它就越重要。同樣地，標準2用被一個類依賴的其他類的數(shù)量和重要程度來定義該類的重要性。文章僅討論依據(jù)標準3來度量類重要性的中介中心性。

2 基于UML類圖的分析

現(xiàn)在面向?qū)ο蠹夹g(shù)在應(yīng)用中越來越廣泛，而面向?qū)ο筌浖闇y試提出了一些新的挑戰(zhàn)，如繼承、多態(tài)、動態(tài)綁定等。由于類圖常常不夠明確、完整，會導致對其錯誤的理解，結(jié)果可能引起錯誤地實現(xiàn)和無效的測試。由于繼承和動態(tài)綁定可能對測試工作產(chǎn)生影響，因此發(fā)現(xiàn)和掌握普遍隱含的控制依賴關(guān)系能為測試建立較好的基礎(chǔ)。

2.1 類圖中依賴關(guān)系

類圖是面向?qū)ο蠓椒ǖ暮诵?，UML類圖描述了系統(tǒng)中的類和類之間的相互關(guān)系，其本質(zhì)反映了系統(tǒng)中包含的各種對象的類型以及對象之間的各種靜態(tài)關(guān)系。在前文中也提到發(fā)現(xiàn)和掌握普遍隱含的控制依賴關(guān)系能為測試建立較好的基礎(chǔ)，對于一個比較復雜的系統(tǒng)模型來說，類與類之間的關(guān)系是非常復雜的，而隱含的控制依賴關(guān)系也就更加復雜。

(1)關(guān)聯(lián)依賴：UML類圖中類間的關(guān)聯(lián)關(guān)系提供了不同的類間對象可以相互作用的連接。關(guān)聯(lián)可以是二元的，也可以是多元的。其中多元關(guān)系可以轉(zhuǎn)化為二元關(guān)系。為了更清楚地描述關(guān)聯(lián)，關(guān)聯(lián)可擁有自己的屬性。關(guān)聯(lián)有單向關(guān)聯(lián)和雙向關(guān)聯(lián)。

(2)聚集依賴：聚集關(guān)系表示類與類之間的整體與部分的關(guān)系。如果部分類完全隸屬于整體類，并且部分類與整體類之間有同樣的生命期，則這樣的聚集關(guān)系是強聚合關(guān)系，又稱為組成關(guān)系。

(3)繼承依賴：繼承是面向?qū)ο蟮囊环N機制，即利用現(xiàn)有的類來定義新的類，子類(繼承類)可以共享父類(被繼承類)的屬性和行為，也可以擁有自己特殊的屬性和行為，對父類進行擴展。這種機制可以避免重復定義屬性和方法，同時也使類間的關(guān)系更加的清晰和直觀。

(4)一般依賴：一般依賴關(guān)系描述的是兩個類之間語義上的連接關(guān)系。一個類是獨立的，另一個類是非獨立的(也即是依賴的)，它依賴于獨立的類；如果獨立的類發(fā)生了改變，將會影響依賴該類的類。也即是一個類使用了另一個類。最常見的一般依賴關(guān)系是一個類是另一個類中方法的參數(shù)類型。

介于以上介紹的4種依賴關(guān)系，為便于討論，將其合并為主要的兩類，一類是普通依賴，當一個類C使用了另一個類D時，我們稱之為普通依賴。另一類是繼承依賴，當C≠D時，并且C繼承自D時，我們稱之為繼承依賴。

2.2 CDG圖的構(gòu)造方法

在文獻[7]中，作者認為按照類圖進行測試設(shè)計時，類交互是最應(yīng)當重視的問題。類交互是指兩個類之間有兩條及兩條以上的依賴路徑。通常這種結(jié)構(gòu)是測試的難點，所以作者提出了用CDG(classdependencygraph)圖來捕獲類交互。與CDG圖相關(guān)的概念[7]介紹如下：

定義1 設(shè)類依賴圖CDG=(V,E)，V為節(jié)點vi集合，記為V={vi}，其中每一個節(jié)點表示面向?qū)ο笙到y(tǒng)的一個類，并且一個類有且只能由一個節(jié)點表示。E為節(jié)點間的有向邊集合，在兩節(jié)點間的一條邊表示在兩類之間存在依賴關(guān)系。每條邊上的標記表示類間依賴的類型。

定義2 邊標記，在CDG圖中的每一條邊表示系統(tǒng)中的兩個類之間的依賴。假設(shè)a∈C，b∈C，邊的標記代表依賴的類型。主要有兩種，正如前文所敘述的：①普通依賴(usage dependency)，用U表示，表示類a調(diào)用b，②繼承依賴 (inheritance)，用I表示，表示a繼承自b。

定義3 U標記。一般我們將方法集和U聯(lián)系起來，在方法集中，默認值是M(d)，轉(zhuǎn)化關(guān)系如圖1所示。

圖1 普通依賴

定義4 I標記。繼承標記包括兩個方面。假設(shè)a∈C，b∈C-{a}，且 a∈Parent(b)。

·邊，記為I-Child。從測試點來看，是需要從父類到子類的依賴的，因為任何時候父類發(fā)生時，子類一般也會發(fā)生。

·邊，記為I-Parent。這個從子類到父類的依賴是顯而易見的：當b調(diào)用方法m，m∈MINH(a)時，b依賴a。

I標記的轉(zhuǎn)化關(guān)系如圖2所示。

圖2 繼承依賴I的表示

這里要注明的是當a是接口的時候，邊是不存在的，因為在這種情況下，b是不能調(diào)用a的方法的，因此這時的轉(zhuǎn)化關(guān)系如圖3所示。而當a還依賴于其他的類的時候，從a發(fā)出的邊U標記是不存在的，這時U標記的邊被轉(zhuǎn)移到a的具體類，圖4是這一情況的轉(zhuǎn)化表示。

圖3 父類是接口情況的表示

3 中介中心性

3.1 基本概念

中介中心性的測量公式如下

圖4 接口依賴于其他類的情況

式中： ——從頂點 s∈V到頂點 t∈V的最短路徑的條數(shù)，

——從s到t經(jīng)過頂點 的最短路徑的條數(shù)。

引理1 頂點 在頂點s到t的最短路徑上，，s，t∈V，當且僅當dG(s,t)=dG(s,)+dG(,t)。這里dG表示兩頂點之間的距離。

定義1 從頂點s出發(fā)的最短路徑上頂點 的前驅(qū)頂點集合為：Ps()={u∈V|∈E,dG(s,)=dG(s,u)+ (u,)}；是邊上的權(quán)值函數(shù)。

引理2 對于頂點

定義2 通過給定的成對的頂點的距離及路徑條數(shù)，可以得到經(jīng)過 的一對頂點s，t∈V的對-依賴性，也即式(2)所示

為了得到頂點 的中介中心性值必須計算出這個頂點上所有的對-依賴性

定理1 任何頂點 上的s∈V的依賴性遵循關(guān)系

由此可以看出計算頂點的中介中心性需要兩部分：①計算所有頂點之間的最短路徑的長度和數(shù)目；②計算所有的對-依賴性。

3.2 中介中心性的計算

圖的廣度優(yōu)先搜索(breadth_firstsearch)遍歷算法能夠用于計算圖中任何兩點之間的最短路徑值。為了計算任意兩點之間的最短路徑的條數(shù)以及節(jié)點的中介中心性值(以下稱Betweenness值)，在傳統(tǒng)的廣度優(yōu)先搜索算法基礎(chǔ)上，對此進行了擴展，在擴展了的廣度優(yōu)先搜索算法中，采用隊列和棧兩種數(shù)據(jù)結(jié)構(gòu)來存放節(jié)點，依據(jù)節(jié)點不同的存儲位置，把圖中的每個節(jié)點在遍歷的過程中標記為3個狀態(tài)：①沒有進入隊列的節(jié)點，將其狀態(tài)定義為未探查；②進入隊列的節(jié)點，將其狀態(tài)定義為已探查但未訪問；③出隊列且入棧的節(jié)點，將其狀態(tài)定義為已訪問。

為計算節(jié)點的Betweenness值，算法可以分為兩個部分來實現(xiàn)：①遍歷算法，主要是實現(xiàn)對圖進行廣度優(yōu)先遍歷，計算節(jié)點從源點s到 的距離，最短路徑條數(shù)等。②回溯算法，計算節(jié)點 的前驅(qū)節(jié)點的對-依賴性。

為計算類依賴關(guān)系圖(CDG)中的節(jié)點的Betweenness值，算法的原理描述如下：

(1)從CDG圖中任意選擇一個節(jié)點作為源節(jié)點s，以此節(jié)點開始對圖進行廣度優(yōu)先搜索遍歷，同時計算出從源節(jié)點s到每個節(jié)點 的距離d(s,)、最短路徑的條數(shù) (s,)、節(jié)點 的前驅(qū)節(jié)點集合P()以及記錄節(jié)點的訪問順序。

(2)在(1)遍歷的基礎(chǔ)上，以s為源節(jié)點的遍歷順序記錄在棧中，從棧頂?shù)墓?jié)點開始對每個節(jié)點進行回溯，也即按照節(jié)點的逆序訪問順序?qū)γ總€節(jié)點進行回溯處理，用下面的公式對節(jié)點 的前驅(qū)節(jié)點的對-依賴性的值進行更新

之所以采用逆序訪問順序是因為對節(jié)點 進行回溯處理完后，節(jié)點 的 ()值就不會再改變，而采用廣度優(yōu)先搜索遍歷為任意先后進行回溯的節(jié)點 ，，滿足d(s,)≥d(s,)提供了保障，當d(s,)≥d(s,)這樣的關(guān)系成立時，說明s到 的最短路徑一定不經(jīng)過 。

(3)對每個節(jié)點 ，計算CBnew()=CBold()+ ()

(4)對CDG圖中的每個節(jié)點重復執(zhí)行(1)～(3)，最后得到圖中所有節(jié)點的Betweenness值。

算法實現(xiàn)的代碼如下表示：

4 應(yīng)用示例

在本文研究的基礎(chǔ)上結(jié)合一個小規(guī)模的類圖，應(yīng)用文章所介紹的方法作分析。

4.1 CDG圖的節(jié)點的中介中心性

這一節(jié)中將通過一個小型類圖，應(yīng)用上文所介紹的CDG圖，計算其頂點的Betweenness值，通過比較各個節(jié)點的中介中心性的值來識別重要的類。圖5是個小規(guī)模的類圖，其對應(yīng)的CDG圖如圖6所示。

圖5 小型類圖

圖6 小型類圖的CDG圖

利用文章描述的算法，可以計算出這個小型類圖的CDG圖的各個節(jié)點的中介中心性值，如表1所示。根據(jù)這個值可以看出圖中b1的Betweenness值是最大的，說明b1的依賴性較強，是重要的類，在測試中應(yīng)該分配較多的資源以發(fā)現(xiàn)該類中隱藏的質(zhì)量缺陷，而c的Betweenness值是最小的，說明它的重要性很低，在圖中也可以很清晰地看出來，那么在測試的過程中就可以花費相對少的人力和時間。通過分析比各個節(jié)點的Betweenness值，可以很明了地看出節(jié)點重要性的等級，在測試的過程中就可以有的放矢，充分合理地分配有限的資源。

表1 節(jié)點的Betweenness值及等級

為了便于問題的討論，以上只是一個小型類圖的CDG圖的類重要性的度量。而在實際的應(yīng)用中，面向?qū)ο筌浖囊?guī)模是很大的，其對應(yīng)的類圖也是錯綜復雜的，而類圖對應(yīng)的CDG圖也必將更加的復雜。通過上述方法所度量的節(jié)點的中介中心性值可以指導我們的測試活動，從而提高軟件的可測試性、保證軟件的質(zhì)量。

4.2 分析總結(jié)

類圖中反映的類之間的依賴關(guān)系是基于類圖的重要性度量的基礎(chǔ)，而將由類圖轉(zhuǎn)化而來的CDG圖與中介中心性結(jié)合起來分析節(jié)點的重要性，對軟件測試有指導作用。在現(xiàn)代軟件工程理論中，軟件測試應(yīng)該貫穿于軟件的整個生命周期，可見軟件測試在軟件產(chǎn)品的開發(fā)過程中的地位是非常關(guān)鍵的，而且它的測試工作量也是非常多且繁重的。

從測試方法角度看，目前軟件測試主要分為靜態(tài)測試和動態(tài)測試，文章所提出的方法主要是屬于靜態(tài)測試范疇，對CDG圖的節(jié)點的重要性進行度量，根據(jù)結(jié)果進行測試資源的合理分配。從動態(tài)測試的角度來看，類測試是動態(tài)測試的一個方面，從這方面來說，度量類重要性對動態(tài)測試也是有一定的優(yōu)化作用，可以提高動態(tài)測試的效率。

5 結(jié)束語

由以上分析可知，本文提出的將中介中心性應(yīng)用到類依賴關(guān)系圖(CDG圖)中的方法，用來度量和分析面向?qū)ο筌浖念愰g依賴結(jié)構(gòu)，以此分析面向?qū)ο筌浖念惖闹匾?，對合理分配測試資源、減少軟件測試成本、提高軟件質(zhì)量有指導作用。文中所研究的內(nèi)容，對現(xiàn)實中大型的面向?qū)ο筌浖臏y試有一定的參考價值。當然，文中所研究的中介中心性的算發(fā)的時間復雜度是O(n3)，可以從邊的類型考慮，以降低其時間復雜度，需要后續(xù)的研究發(fā)現(xiàn)，這也是今后研究的重要方向。

[1]Ulrik Brandes.On variants of shortest-path betweenness centrality and their generic computation[J].Social Networks,2008,30(2):136-145.

[2]He Shan,Li Sheng,Ma Hongru.Betweenness centrality in finite components of complex networks[J].Physica A:Statistical Mechanics and its Applications,2009,388(19):4277-4285.

[3]Tore Opsahl,Filip Agneessens,John Skvoretz.Node centrality in weighted networks:Generalizing degree and shortest paths[J].Social Networks,2010,32(3):245-251.

[4]Newman M E J.A measure of betweenness centrality based on random walks[J].Social Networks,2005,27(1):39-54.

[5]胡順仁,陳偉民,廖昌榮,等.基于UML類圖的類之間依賴關(guān)系圖論問題研究[J].計算機工程,2006,32(12):1-2.

[6]殷劍宏,吳開亞.圖論及其算法[M].合肥:中國科學技術(shù)大學出版社,2003.

[7]Benoit Baudry,Yves Le Traon.Measuring design testability of a UML class diagram[J].Information and Software Technology,2005,47(13):859-879.

[8]范晶,秦卓瓊,張國清.基于中介中心性提高復雜網(wǎng)絡(luò)容量的方法[J].計算機仿真,2008,25(3):167-170.

[9]唐晉韜,王挺.復雜社會網(wǎng)絡(luò)的介數(shù)性質(zhì)近似計算方法研究[J].計算工程與科學,2008,30(12):9-14.