基于變量依賴關(guān)系模型的變量重要性度量方法

田興亞， 牟永敏， 張志華

(北京信息科技大學(xué)網(wǎng)絡(luò)文化與數(shù)字傳播北京市重點(diǎn)實(shí)驗(yàn)室，北京 100101)

軟件系統(tǒng)的運(yùn)行實(shí)質(zhì)上是程序變量按照程序員指定的邏輯相互影響來(lái)執(zhí)行的。Concas等[1]研究了十余款大型軟件系統(tǒng)，發(fā)現(xiàn)了軟件系統(tǒng)中的變量分布符合冪律分布，具有非常明顯的復(fù)雜網(wǎng)絡(luò)特征。為了提高軟件系統(tǒng)的安全性，就應(yīng)該找出那些重要變量，因?yàn)橐坏┻@些變量出現(xiàn)問(wèn)題就會(huì)給軟件系統(tǒng)帶來(lái)巨大的損失，如何識(shí)別出重要變量是一個(gè)非常有價(jià)值的研究課題。

在軟件開(kāi)發(fā)過(guò)程中，軟件系統(tǒng)面臨各種各樣需要變更的情況，包括增加模塊、修改模塊和刪除模塊。這些操作通常會(huì)涉及對(duì)變量的變更，由于變量間存在依賴關(guān)系, 使得變量的變更引起其他相關(guān)聯(lián)的變量發(fā)生變更，最終引起軟件故障。因此挖掘出變量的重要性，降低變量變更的代價(jià)，對(duì)軟件測(cè)試和維護(hù)具有重要的意義。

在軟件系統(tǒng)中, 變量的重要性有所不同。當(dāng)某個(gè)變量發(fā)生變更時(shí), 其對(duì)于整個(gè)程序的影響程度也不同, 尤其是重要的變量發(fā)生變化可能會(huì)對(duì)整個(gè)程序產(chǎn)生影響。在軟件結(jié)構(gòu)中，衡量一個(gè)變量是否重要，最重要的是衡量變量與其他變量的交互程度。在程序中使用的變量都直接或間接地相互影響，因此分析變量間的依賴關(guān)系對(duì)變量的重要性度量具有重要的作用。

目前，由于中外學(xué)者的關(guān)注點(diǎn)不同，所以針對(duì)不同場(chǎng)景提出了各種依賴關(guān)系，主要包括實(shí)體依賴關(guān)系、類依賴關(guān)系、函數(shù)依賴關(guān)系、語(yǔ)句依賴關(guān)系和變量依賴關(guān)系等。

Stevens等[2]首先提出用依賴關(guān)系來(lái)衡量一個(gè)構(gòu)件對(duì)另一個(gè)構(gòu)件的依賴程度。依賴程度越高，構(gòu)件的耦合性越高。為了便于理解各種依賴關(guān)系, 研究者們提出許多依賴圖的模型來(lái)描述各種依賴關(guān)系。

黃雅菁等[3]利用軟件系統(tǒng)中類和類之間的依賴關(guān)系，提出一種基于賦權(quán)類依賴圖的重構(gòu)定位方法，定位需要重構(gòu)的類。成小芹等[4-5]將中介中心性和類依賴關(guān)系圖相結(jié)合度量類重要性，有效地指導(dǎo)了測(cè)試資源的分配。

符煒等[6]討論了函數(shù)依賴關(guān)系，并結(jié)合程序切片技術(shù)，基于函數(shù)依賴圖進(jìn)行構(gòu)件抽取。程曉菊等[7]將函數(shù)依賴圖精簡(jiǎn)為函數(shù)切片依賴圖得到與代碼變化相關(guān)的函數(shù)最小集，極大地約簡(jiǎn)了測(cè)試用例集，提高了回歸測(cè)試的效率。

吳軍華等[8-9]提出基于程序依賴圖進(jìn)行程序代碼的克隆檢測(cè)，又采用依賴邊類型約束計(jì)算近似解，有效地提高了計(jì)算性能。

Harman等[10]闡述了變量依賴分析問(wèn)題與切片之間的關(guān)系，并實(shí)現(xiàn)了變量依賴關(guān)系分析的VADA系統(tǒng)。DaimlerChrysler公司目前正在利用它作為測(cè)試用例自動(dòng)生成方法的一部分。論文引入的方法為變量依賴關(guān)系分析增加了一個(gè)新的維度，即增加了對(duì)重要變量的自動(dòng)跟蹤。

Sadi等[11]提出了一種基于自動(dòng)生成的依賴圖分析變量依賴關(guān)系的方法，依賴圖描述了程序變量之間的關(guān)聯(lián)關(guān)系，其中變量作為圖的頂點(diǎn)，變量之間的依賴關(guān)系作為圖的邊。通過(guò)自動(dòng)生成的依賴關(guān)系圖可以跟蹤關(guān)鍵變量，關(guān)鍵變量作為檢測(cè)程序順序執(zhí)行的關(guān)鍵，優(yōu)于現(xiàn)有的程序分析方法。但是該方法只分析了變量間的數(shù)據(jù)依賴關(guān)系，未考慮變量間控制依賴關(guān)系以及函數(shù)調(diào)用引起的變量依賴關(guān)系。

潘亞飛等[12]通過(guò)分析變量間的依賴關(guān)系，生成變量數(shù)據(jù)拓?fù)鋱D。為由變量帶來(lái)的軟件變更問(wèn)題提供了新的解決方法。

傅妤婧等[13]針對(duì)時(shí)態(tài)實(shí)體依賴圖提出時(shí)態(tài)實(shí)體依賴關(guān)系，并分析時(shí)態(tài)實(shí)體依賴圖的節(jié)點(diǎn)中心性、節(jié)點(diǎn)重要性、節(jié)點(diǎn)依賴度和邊的重要性等4個(gè)度量指標(biāo)。

節(jié)點(diǎn)的重要性度量方法有度中心性[14]、介數(shù)中心性、接近中心性[15]、特征向量中心性[16]等。

現(xiàn)有的依賴分析方法大多針對(duì)類、函數(shù)和語(yǔ)句的粒度來(lái)建模，文獻(xiàn)[12]雖然分析了變量間的依賴關(guān)系，為分析由變量引起的軟件變更提供了新思路。但是卻未深入分析哪些變量是能對(duì)程序產(chǎn)生更深度影響的變量，不能輕易發(fā)生變更。論文結(jié)合以上研究成果, 提出變量依賴關(guān)系模型的定義，并提出基于變量依賴關(guān)系模型的變量重要性度量(variable node importance measure，VNIM)方法，通過(guò)實(shí)驗(yàn)分析，證明了該方法在變量重要性度量方面的優(yōu)越性。

1 相關(guān)定義

定義1變量依賴關(guān)系模型(variable dependency model,VDM)：VDM=(V,E)，其中V是VDM模型中所有的變量集合，V={vi|vi∈程序變量}。E是VDM模型中變量之間依賴關(guān)系的邊集合，E={eij=(vi,vj)|vi,vj∈V} 。其中，eij的定義為

(1)

定義2依賴關(guān)系：由控制條件引起的控制依賴和由訪問(wèn)變量引起的數(shù)據(jù)依賴以及由函數(shù)調(diào)用引起的函數(shù)依賴。

定義3數(shù)據(jù)依賴(data dependency)：設(shè)s為程序P的賦值語(yǔ)句，令vi為在s中被賦值的變量，Ref(s)為在s中被使用的變量集合，若存在變量vj∈Ref(s)，則稱變量vi數(shù)據(jù)依賴于變量vj，記為dd(vi,vj)。數(shù)據(jù)依賴描述了在賦值語(yǔ)句中左部對(duì)右部的依賴關(guān)系。

定義4控制依賴(control dependency)：設(shè)s1和s2分別為程序P的賦值語(yǔ)句和控制語(yǔ)句，令vi為在s1中被賦值的變量，vj為在s2中控制條件的變量，若s1能否被執(zhí)行由s2的執(zhí)行狀態(tài)決定。則稱變量vi控制依賴于變量vj，記為cd(vi,vj)。

定義5函數(shù)依賴(function dependency)：變量v的取值依賴于函數(shù)F返回值，則稱變量v函數(shù)依賴于F，記為fd(v,F)。

定義6隱含依賴關(guān)系(implicit dependency)：隱含依賴關(guān)系是指針變量參與賦值運(yùn)算(地址賦值運(yùn)算“&”、指針解引用的賦值運(yùn)算“*”)引起的變量依賴關(guān)系，若變量vi隱含依賴于變量vj，則隱含依賴關(guān)系可以表示為id(vi,vj)。指針變量是存儲(chǔ)地址類型數(shù)據(jù)的變量，對(duì)于指向同一塊內(nèi)存地址的指針變量而言，通過(guò)任意指針改變?cè)搩?nèi)存的數(shù)值時(shí)，指向該內(nèi)存的所有指針變量的取值都將被改變，因而它們屬于相互依賴的隱含依賴關(guān)系。

定義7變量重要性的評(píng)判標(biāo)準(zhǔn)：變量是否重要取決于應(yīng)用場(chǎng)景和用戶給定的標(biāo)準(zhǔn)，現(xiàn)針對(duì)由變量引起的軟件變更場(chǎng)景提出變量重要性的評(píng)判標(biāo)準(zhǔn)。

標(biāo)準(zhǔn)1一個(gè)變量是重要的當(dāng)且僅當(dāng)有很多重要的變量依賴于它。

標(biāo)準(zhǔn)2一個(gè)變量是重要的當(dāng)且僅當(dāng)它接近變量依賴關(guān)系模型的中心。

標(biāo)準(zhǔn)1遞歸地定義一個(gè)變量是否重要取決于 2個(gè)要素：①依賴于該變量的變量數(shù)量越多，變量越重要；②依賴于該變量的變量重要性越高，變量越重要。根據(jù)標(biāo)準(zhǔn)1的定義可知，如果一個(gè)變量被很多其他變量依賴，那么對(duì)這個(gè)變量的修改可能會(huì)影響許多依賴于它的變量;如果一個(gè)變量被重要的變量依賴，那么對(duì)這個(gè)變量的修改可能會(huì)影響到重要變量從而對(duì)軟件產(chǎn)生較大的影響。

標(biāo)準(zhǔn)2定義變量的重要性取決于變量的中心性，中心性越高的變量被刪除后對(duì)變量依賴關(guān)系模型的破壞程度就越大，也就說(shuō)明這些變量越重要。

對(duì)于不同類型的代碼語(yǔ)句定義了不同的變量依賴關(guān)系如表1所示。

表1 不同類型語(yǔ)句的變量依賴關(guān)系

2 變量依賴關(guān)系模型的構(gòu)建

2.1 變量依賴關(guān)系分析

2.1.1 數(shù)據(jù)依賴關(guān)系分析

變量的數(shù)據(jù)依賴體現(xiàn)在代碼中的賦值語(yǔ)句上，在賦值語(yǔ)句的算術(shù)表達(dá)式中，等號(hào)左側(cè)的變量數(shù)據(jù)依賴于等號(hào)右側(cè)的變量，該語(yǔ)句作用是賦值等操作。如式(2)所示兩行賦值語(yǔ)句：

(2)

假設(shè)所有的變量有意義，變量c的取值取決于表達(dá)式等號(hào)的右側(cè)變量a和b。變量a和b的任何變化都會(huì)引起變量c的變化，這是變量c對(duì)變量a和b的直接依賴。變量e的取值同時(shí)受到變量c和d的影響，因此變量a和b通過(guò)直接影響變量c，從而間接影響變量e。

2.1.2 控制依賴關(guān)系分析

在程序代碼中，控制節(jié)點(diǎn)體現(xiàn)了程序的邏輯結(jié)構(gòu)，反映了程序執(zhí)行的走向，包含了變量的控制流和數(shù)據(jù)流信息。因此，分析控制依賴關(guān)系對(duì)收集程序的關(guān)鍵信息具有重要作用。圖1所示的C程序代碼中6～10行為含有控制依賴關(guān)系的代碼段，變量h的取值控制依賴于變量con。當(dāng)滿足控制語(yǔ)句的判別條件時(shí)，函數(shù)f的返回值影響變量h，不滿足條件時(shí)，變量e影響變量h。

圖1 C程序片段示例Fig.1 C program fragment example

2.1.3 函數(shù)依賴關(guān)系分析

函數(shù)依賴是一種特殊的數(shù)據(jù)依賴，由于源代碼中的功能塊用函數(shù)進(jìn)行封裝，所以需要做函數(shù)層面的變量依賴關(guān)系分析，即需要函數(shù)返回值的依賴影響關(guān)系。例如intq=f1(5)，f1函數(shù)定義如圖2所示。

圖2 f1函數(shù)Fig.2 f1 function

變量q的取值依賴于函數(shù)f1的返回值，即q函數(shù)依賴于f1中的變量b。在f1函數(shù)中，變量b數(shù)據(jù)依賴于變量c，同時(shí)控制依賴于變量a。變量q的函數(shù)依賴關(guān)系如圖3所示。

圖3 變量q的函數(shù)依賴關(guān)系Fig.3 Function dependency of variable q

2.1.4 隱含依賴關(guān)系分析

如圖4所示，第 4行定義一個(gè)整型指針b,并且b指向了a的地址。第5行定義一個(gè)整型的指針c并且c指向了b的地址。假設(shè)a、b、c的內(nèi)存地址分別為0x100、0x200、0x300，則三者之間的訪問(wèn)形式如圖5所示。

圖4 含指針的C程序Fig.4 C program with pointer

圖5 指針變量的訪問(wèn)形式Fig.5 Access form of pointer variable

指針b可以通過(guò)訪問(wèn)變量a的地址訪問(wèn)到變量a的值，屬于直接訪問(wèn)的形式。指針c可以通過(guò)b再訪問(wèn)a的地址訪問(wèn)到變量a的值，屬于間接訪問(wèn)的形式。假如重新對(duì)變量a進(jìn)行賦值，令a=10，則b和c訪問(wèn)的值也會(huì)變?yōu)?0。因此，指針變量b和c依賴于變量a。令*b=20，通過(guò)解引用，可以重新給a賦值為20，同理**c也可以重新給a賦值為20。因此，變量a也依賴于指針變量b和c。由此，可以認(rèn)為對(duì)于指向同一塊內(nèi)存地址的變量而言，它們屬于相互依賴關(guān)系。

算法1描述了變量間依賴關(guān)系的提取算法，此算法的主要目標(biāo)是查找變量并提取變量間的依賴關(guān)系。抽象語(yǔ)法樹(shù)中含有程序的所有的信息，抽象語(yǔ)法樹(shù)可以理解為源代碼的樹(shù)形結(jié)構(gòu)，樹(shù)中的每個(gè)節(jié)點(diǎn)信息都和源代碼的信息一一對(duì)應(yīng)。需要對(duì)抽象語(yǔ)法樹(shù)中的節(jié)點(diǎn)進(jìn)行遍歷和解析，提取變量、函數(shù)、賦值信息和控制信息等關(guān)鍵信息。根據(jù)節(jié)點(diǎn)中關(guān)鍵字的不同，定義不同的依賴關(guān)系。并將相應(yīng)的變量和依賴關(guān)系類型標(biāo)簽加到結(jié)果集中。算法1如下：

算法1 變量間依賴關(guān)系的提取算法輸入:預(yù)處理后的源程序輸出:變量依賴關(guān)系集合定義:令mark為變量依賴關(guān)系類型標(biāo)簽Step1:利用抽象語(yǔ)法樹(shù)生成工具得到源代碼樹(shù)形結(jié)構(gòu)的數(shù)據(jù),源代碼的信息和樹(shù)中的節(jié)點(diǎn)信息一一對(duì)應(yīng)。Step2:基于抽象語(yǔ)法樹(shù),從 node 的根節(jié)點(diǎn)開(kāi)始遍歷,提取變量、函數(shù)、賦值信息和控制信息等關(guān)鍵信息。Step3:遍歷關(guān)鍵節(jié)點(diǎn),若存在賦值關(guān)鍵字“assign”,則令mark=“dd”;若存在循環(huán)控制關(guān)鍵字“for”、“while”或“if”分支控制字,則令mark=“cd”;若存在函數(shù)調(diào)用關(guān)鍵字“call”,則令mark=“fd”; 若存在指針類型的關(guān)鍵字如“array” 或“pointer”,則令mark=“id”Step4:將變量和相應(yīng)的依賴關(guān)系標(biāo)簽加入到結(jié)果集中。Step5:循環(huán)上述過(guò)程,直到整個(gè)對(duì)象全部遍歷完成。

在圖1的示例代碼中，變量c數(shù)據(jù)依賴于a和b，變量e數(shù)據(jù)依賴于c和d。變量h控制依賴于變量con、函數(shù)依賴于f和數(shù)據(jù)依賴于變量e。對(duì)程序變量的依賴關(guān)系分析過(guò)程如表2所示。

表2 程序變量的依賴關(guān)系分析

2.2 變量依賴關(guān)系模型構(gòu)建的方法實(shí)現(xiàn)

提取變量間的依賴關(guān)系之后，如前文所述，利用變量間的依賴關(guān)系生成變量依賴關(guān)系模型。變量依賴關(guān)系模型的頂點(diǎn)是代碼段的變量,邊由依賴變量指向被依賴變量。

算法2描述了變量依賴關(guān)系模型構(gòu)建的實(shí)現(xiàn)過(guò)程。以變量依賴關(guān)系集合作為輸入，遍歷變量依賴關(guān)系集合，得到集合中每個(gè)變量及其依賴關(guān)系；提取變量并繪制變量節(jié)點(diǎn)，如果變量i與變量j之間存在依賴關(guān)系，提變量依賴關(guān)系類型標(biāo)簽，繪制一條從變量i到變量j的邊，并把標(biāo)簽的取值賦值給邊；循環(huán)上述過(guò)程直至遍歷完成，最終得到變量依賴關(guān)系模型。算法2如下：

算法2 變量依賴關(guān)系模型構(gòu)建算法輸入:變量依賴關(guān)系集合r_array輸出:變量依賴關(guān)系模型1. Begin each element of r_array2. Draw parent3. Until all elements of r_array traversed4. If parent has child5. For each child of child_arr6. Draw child7. Draw edge from parent to child8. set edge_value=mark9. End loop10. elif parent in child of new_parent11. child=parent, parent=new_parent12. Draw edge from parent to child13. set edge_value=mark14. else draw parent15. End loop16. End

將算法2應(yīng)用于圖1的示例程序，最終得到變量依賴關(guān)系模型。圖6繪制了程序從第1～10行變量依賴關(guān)系模型的逐步構(gòu)建過(guò)程。

圖6 變量依賴關(guān)系模型自動(dòng)生成過(guò)程Fig.6 Variable dependency model automatic generation process

變量依賴關(guān)系模型是程序中變量信息傳播的直接映射，反映了程序中變量的相關(guān)依賴信息如控制依賴信息和函數(shù)依賴信息等。

變量依賴關(guān)系模型的功能如下。

(1)自動(dòng)跟蹤程序中的變量和方法，明確變量和函數(shù)調(diào)用在整個(gè)程序中的分布情況。

(2)跟蹤變量在整個(gè)程序中的使用情況及其依賴關(guān)系，依賴關(guān)系包含了變量的數(shù)據(jù)依賴關(guān)系、控制依賴關(guān)系、函數(shù)依賴關(guān)系和指針引起的隱含依賴關(guān)系。

(3)可以直觀地展示各變量間依賴關(guān)系類型及其傳播方向。

(4)通過(guò)變量依賴關(guān)系模型并結(jié)合變量的出度和入度可以分析變量在程序中的重要性。

(5)當(dāng)出現(xiàn)變量問(wèn)題引起的軟件錯(cuò)誤時(shí)，通過(guò)變量依賴關(guān)系模型可以快速定位到最可能出錯(cuò)的根源變量，可以有效地指導(dǎo)軟件測(cè)試活動(dòng)。

3 基于VDM的變量重要性度量方法

3.1 相關(guān)概念

3.1.1 節(jié)點(diǎn)中心性

在網(wǎng)絡(luò)圖中，節(jié)點(diǎn)中心性(node centrality)可以表示節(jié)點(diǎn)在圖中與其他節(jié)點(diǎn)相關(guān)聯(lián)的程度。中心性越高，與其他節(jié)點(diǎn)的關(guān)聯(lián)程度就越高，該節(jié)點(diǎn)能夠影響到的其他節(jié)點(diǎn)就越多。

節(jié)點(diǎn)中心性定義如下：

(3)

式(3)中：in(pi)代表在網(wǎng)絡(luò)圖中節(jié)點(diǎn)pi的入度；out(pi)表示節(jié)點(diǎn)pi的出度；N表示節(jié)點(diǎn)總數(shù)。

在網(wǎng)絡(luò)圖中，假設(shè)節(jié)點(diǎn)pi的度為deg(pi)，則節(jié)點(diǎn)pi的中心性也可以表示為

(4)

中心性只考慮了節(jié)點(diǎn)在網(wǎng)絡(luò)中的位置，并沒(méi)有考慮依賴于該節(jié)點(diǎn)的節(jié)點(diǎn)重要性貢獻(xiàn)，也并未考慮節(jié)點(diǎn)本身的重要性信息，考慮較為片面。

3.1.2 節(jié)點(diǎn)重要性

傅妤婧[13]提出的節(jié)點(diǎn)重要性(node importance)與中心性相比，更多地關(guān)注了節(jié)點(diǎn)的入度。即節(jié)點(diǎn)的入度數(shù)越大，依賴于該節(jié)點(diǎn)的其他節(jié)點(diǎn)個(gè)數(shù)越多，當(dāng)該節(jié)點(diǎn)發(fā)生改變時(shí)，會(huì)有更多的節(jié)點(diǎn)直接受到其影響。

定義節(jié)點(diǎn)的重要性為直接依賴于該節(jié)點(diǎn)的所有節(jié)點(diǎn)中心性之和。則節(jié)點(diǎn)pi的重要性為

(5)

式(5)中：C(pj)表示依賴于節(jié)點(diǎn)pi的節(jié)點(diǎn)pj的中心性。

式(5)的節(jié)點(diǎn)重要性計(jì)算方法除了考慮節(jié)點(diǎn)鏈入數(shù)量的因素，還結(jié)合了鄰接節(jié)點(diǎn)的中心性影響因素。但該方法有一個(gè)很大的缺陷，假如一個(gè)節(jié)點(diǎn)沒(méi)有任何鏈入，則該節(jié)點(diǎn)的重要性為0，這顯然是不合理的。該方法一定程度上刻畫(huà)了節(jié)點(diǎn)的重要性，但同時(shí)也忽略了很多因素，僅僅考慮鄰接節(jié)點(diǎn)的數(shù)量和中心性情況，以此來(lái)衡量節(jié)點(diǎn)的重要性，有很大的局限性。

3.1.3 PageRank方法

PageRank方法是Google著名的網(wǎng)頁(yè)重要性排名算法，該算法是特征向量中心性的一個(gè)變種。PageRank值越大表示網(wǎng)頁(yè)重要性越高。

假設(shè)存在節(jié)點(diǎn)pi，則其PageRank值計(jì)算方式如下：

(6)

式(6)中：M(pi)代表鏈入節(jié)點(diǎn)pi的節(jié)點(diǎn)集合；Lo(pj)表示節(jié)點(diǎn)pj的鏈出數(shù)；N代表所有的節(jié)點(diǎn)總數(shù)；α是阻尼系數(shù)，針對(duì)網(wǎng)頁(yè)排序其取值一般為0.85。

PageRank方法認(rèn)為節(jié)點(diǎn)是否重要取決于兩點(diǎn)：依賴于該節(jié)點(diǎn)的數(shù)目和這些鄰接節(jié)點(diǎn)的重要性。但是卻忽略了節(jié)點(diǎn)的中心性因素，根據(jù)節(jié)點(diǎn)在網(wǎng)絡(luò)中所屬的位置不同，其對(duì)信息傳播的作用也是不相同的。

基于上述思想，并結(jié)合定義6提出的變量的重要性評(píng)判標(biāo)準(zhǔn)，引入了“樞紐性”來(lái)衡量變量在變量間信息傳播的作用即中心性影響，并結(jié)合鄰接變量的重要性貢獻(xiàn)提出了一種新的基于變量依賴關(guān)系模型的變量重要性度量(variable node importance measure,VNIM)方法。

3.2 VNIM方法

重要變量指的是能對(duì)程序產(chǎn)生更深度影響的變量，其影響包括對(duì)程序信息的傳播以及對(duì)全局變量的鏈接作用。PageRank 方法只考慮了鄰接節(jié)點(diǎn)的重要性貢獻(xiàn)，卻未考慮節(jié)點(diǎn)本身的樞紐性，考慮較為片面。樞紐性是指節(jié)點(diǎn)所在位置，反映了節(jié)點(diǎn)的中心性影響。針對(duì)PageRank存在的局限性問(wèn)題，提出VNIM方法，方法不僅考慮了鄰接節(jié)點(diǎn)的重要性貢獻(xiàn)，還結(jié)合了節(jié)點(diǎn)的樞紐性作用。

假設(shè)存在變量vi,則其VNIM的計(jì)算方式為

(7)

式(7)中：DP(vi)表示依賴于vi的變量集合；IC(vj)表示變量vj對(duì)變量vi的重要性貢獻(xiàn)度；VNIM0(vi)表示變量vi的初始重要性；H(vi)表示變量vi的樞紐度(hub Degree)。

(8)

式(8)中：N代表所有的變量總數(shù)。

重要性貢獻(xiàn)度(importance contribution)： 若存在一條變量依賴關(guān)系vj→vi，變量vj對(duì)變量vi的重要性貢獻(xiàn)度為變量vj自身的重要性與其出度的比值，即:

IC(vj)=VNIM(vj)/o(vj)

(9)

式(9)中：o(vj)表示變量vj的出度。

樞紐度H(vi)的定義如下：

H(vi)=C(vi)

(10)

C(vi)的定義曾在式(5)提到，表示變量的中心性。變量的樞紐度等于其中心性，反映了變量在變量間信息傳播的作用。

為了消除程序規(guī)模對(duì)變量重要性的影響，需要對(duì)變量的重要度做歸一化處理如下：

(11)

變量的VNIM是由所有依賴于該變量的其他變量重要性經(jīng)過(guò)遞歸算法得到的。除了考慮鏈入變量的數(shù)量及鄰接變量的重要性貢獻(xiàn)因素，還結(jié)合了變量的樞紐性影響，綜合兩者因素可以獲得更好的度量結(jié)果。

如果一個(gè)變量被很多變量依賴，或被少數(shù)幾個(gè)重要的變量依賴，則變量的重要性較高。因此，有較少鏈入數(shù)的變量可能比有較多鏈入數(shù)的變量重要性更高。同時(shí)根據(jù)變量樞紐性作用的不同，變量的重要性也不相同。

VNIM方法具有如下性質(zhì)。

(1)傳遞性：由于VNIM的計(jì)算考慮了鄰接變量的重要性貢獻(xiàn)因素，因而VNIM方法具有傳遞性。

假設(shè)變量b、c和d依賴于變量a，那么變量a的VNIM與其樞紐度的比值為變量b、c和d對(duì)變量a的重要性貢獻(xiàn)度與變量a初始重要性之和。

則變量a的VNIM與其樞紐度的比值為

(12)

(2)傳遞的均勻性：變量的VNIM值均勻地向后傳遞。

假設(shè)變量a和c依賴于變量b，變量a，e和f三個(gè)變量依賴變量d。變量a、b、c、d、e和f之間的依賴關(guān)系如圖7所示。

圖7 變量依賴關(guān)系示例圖Fig.7 Sample diagram of variable dependencies

則變量a、e和f對(duì)變量d的重要性貢獻(xiàn)度分別為

(13)

鄰接變量對(duì)變量的重要性貢獻(xiàn)度與鄰接變量的出度成正比，變量a既依賴于變量b又依賴于變量d，因而變量a對(duì)變量d的重要性貢獻(xiàn)度為變量a自身的重要性的1/2。

4 實(shí)驗(yàn)分析

通過(guò)一個(gè)VDM示例圖將VNIM方法與傅妤婧[13]提出的節(jié)點(diǎn)重要性度量方法和PageRank方法進(jìn)行對(duì)比，展示VNIM方法在變量重要性度量方面的準(zhǔn)確性。用例圖如圖8所示。

圖8 VDM示例圖Fig.8 VDM example diagram

利用本文描述的方法，可以計(jì)算出VDM示例圖中各個(gè)變量的中心性值、NI值、PageRank(PR)值和VNIM值，計(jì)算結(jié)果如表3所示。

表3 各種指標(biāo)計(jì)算結(jié)果

通過(guò)計(jì)算結(jié)果的呈現(xiàn)，可以發(fā)現(xiàn)這幾種方法對(duì)變量重要性的排名結(jié)果有所不同。

通過(guò)表3可以發(fā)現(xiàn)，通過(guò)傅妤婧[13]提出的節(jié)點(diǎn)重要性度量方法計(jì)算得出變量a、g和h的重要性為0，這顯然不合理，因?yàn)樽兞縜、g和h雖然不被任何其他變量所依賴，但是它們?cè)谧兞康男畔鞑ブ衅鸬搅酥匾淖饔谩Ｍ瑫r(shí)，計(jì)算結(jié)果中出現(xiàn)了很多變量重要性相同的現(xiàn)象，如變量b、c、f和j的重要性完全相同，這是由于NI值的計(jì)算方法只關(guān)注了其鄰接變量的中心性指標(biāo)，未考慮變量間信息的傳播，也未考慮變量本身的重要性信息等，考慮較為片面。而在變量依賴關(guān)系模型中，可能會(huì)出現(xiàn)大量變量的中心性一致的情況，在程序規(guī)模足夠大的情況下，可能會(huì)導(dǎo)致變量的重要性難以有效區(qū)分。

表4為各個(gè)變量重要性的排名結(jié)果，括號(hào)內(nèi)的數(shù)字表示排名的并列情況。由于變量i幾乎被所有變量直接或間接地依賴，因而能對(duì)程序產(chǎn)生更深度的影響。所以在PageRank方法中，變量i排名第一。傅妤婧[13]提出的節(jié)點(diǎn)重要性度量方法只考慮了鄰接變量的中心性因素，同樣得出變量i最為重要。 而VNIM方法結(jié)合鄰接變量的重要性貢獻(xiàn)以及變量在信息傳播的作用，也把變量i排在了第一位。

表4 變量重要性排名結(jié)果

雖然三種方法都把變量i排在了第一位，但是其考慮的因素卻大大不同，尤其是傅妤婧[13]提出的節(jié)點(diǎn)重要性度量方法在變量重要性度量方面有明顯缺陷。對(duì)比VNIM方法和PageRank方法，排名結(jié)果中出現(xiàn)較大差異的為變量a、g和h的重要性排名結(jié)果，在PageRank方法中三者重要性相同，而在VNIM方法中的排名為a>g>h。仔細(xì)觀察圖6可以發(fā)現(xiàn)，變量a、g和h的入度都為0，出度分別為3、2和1。入度為0表明即沒(méi)有任何變量依賴于這些變量，由于PageRank重點(diǎn)關(guān)注的是鄰接變量的重要性貢獻(xiàn)和數(shù)量，并沒(méi)有考慮變量的樞紐性影響因素，所以得出三個(gè)變量的重要性相等的結(jié)論。而VNIM方法既考慮了鄰接變量的數(shù)量以及重要性貢獻(xiàn)，又綜合了變量的樞紐性影響因素，因而與前者的排名結(jié)果不同。

顯然，變量a、g和h的重要性是不同的，雖然不被任何變量依賴，但是變量起到了信息傳播的作用，根據(jù)變量的中心性不同，其傳播作用的大小也不相同。變量a的度更大，起到的樞紐性作用更大，能對(duì)程序產(chǎn)生更深度的影響，因而變量a相比變量g和h的重要性要更大一些。同理，變量e的重要性大于變量j，變量a的重要性大于變量b、c和f。

從表4可以看出，PageRank方法和NI方法的排名結(jié)果出現(xiàn)了很多變量重要性一致的情況，尤其是NI方法的排名結(jié)果最為明顯，變量b、c、f和j重要性完全一致。VNIM方法結(jié)合了鄰接變量的重要性貢獻(xiàn)和變量的樞紐性作用，綜合衡量變量在程序中的重要性，彌補(bǔ)了其他兩個(gè)方法的不足，其重要性排序結(jié)果更為準(zhǔn)確合理。

上述的分析結(jié)果說(shuō)明VNIM方法對(duì)比傅妤婧[13]提出的節(jié)點(diǎn)重要性度量方法和PageRank方法在評(píng)價(jià)變量重要性度量方面更加準(zhǔn)確有效，變量重要性排序結(jié)果更具有實(shí)際意義。

在變量依賴關(guān)系模型中，衡量變量是否對(duì)程序產(chǎn)生了更深度的影響，不僅要考慮依賴于該變量的數(shù)量和重要性貢獻(xiàn)，還要結(jié)合變量在信息傳播中的作用。VNIM方法充分利用了變量間的依賴信息，對(duì)變量的重要性度量結(jié)果更加準(zhǔn)確。

5 結(jié)論

變量重要性度量是軟件測(cè)試領(lǐng)域的重要研究點(diǎn)，尤其是在變更影響分析和測(cè)試用例的生成、排序和優(yōu)化方面具有很重要的作用。提出利用變量之間的依賴關(guān)系構(gòu)建變量依賴關(guān)系模型。自動(dòng)生成的變量依賴關(guān)系模型描述了變量之間的所有依賴關(guān)系，包括數(shù)據(jù)依賴關(guān)系、控制依賴關(guān)系、函數(shù)依賴關(guān)系以及指針引起的隱含依賴關(guān)系，并將圖論和程序變量重要性度量相結(jié)合，基于變量依賴關(guān)系模型進(jìn)行變量的重要性度量。根據(jù)變量在變量間信息傳播的作用，提出變量“樞紐性”的概念，并通過(guò)實(shí)驗(yàn)證明了該方法在分析變量重要性度量方面更加有效。

在軟件生命周期中，許多軟件錯(cuò)誤是由變量問(wèn)題引起的，通過(guò)變量依賴關(guān)系模型可以快速定位到最可能出錯(cuò)的根源變量。基于變量依賴關(guān)系模型變量重要性度量方法，可以更好地評(píng)價(jià)軟件內(nèi)部變量的重要性，對(duì)變更影響分析和測(cè)試用例生成提供了新思路，有利于指導(dǎo)軟件測(cè)試和提高軟件的測(cè)試效率。