對(duì)象依賴關(guān)系在變更影響分析中的應(yīng)用

楊鶴標(biāo) 陳小強(qiáng)

摘 要：面向?qū)ο筌浖到y(tǒng)中對(duì)象間的依賴關(guān)系會(huì)因?yàn)椴糠謱?duì)象的變更而波及到系統(tǒng)其它組成部分，對(duì)此，給出了一種對(duì)象依賴關(guān)系構(gòu)造方法。該方法從粒度上將面向?qū)ο笙到y(tǒng)中對(duì)象間的依賴關(guān)系簡化為接口依賴和方法依賴，通過搜索系統(tǒng)的層次結(jié)構(gòu)，將構(gòu)造出的依賴圖中復(fù)雜的多對(duì)多依賴關(guān)系轉(zhuǎn)化為依賴關(guān)系樹中較為簡潔的一對(duì)多依賴關(guān)系。當(dāng)具體對(duì)象發(fā)生變更時(shí)，從變更節(jié)點(diǎn)處搜索多叉樹獲得變更影響的波及范圍，根據(jù)變更度量方法得到變更產(chǎn)生的額外工作量，確定變更影響程度，為變更可能產(chǎn)生的風(fēng)險(xiǎn)評(píng)估和控制提供量化依據(jù)。通過一個(gè)實(shí)際案例展示了變更影響評(píng)估方法的可行性。

關(guān)鍵詞：面向?qū)ο?；?duì)象依賴關(guān)系樹；變更影響分析；波動(dòng)效應(yīng)

DOIDOI：10.11907/rjdk.181130

中圖分類號(hào)：TP319

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2018）010-0153-04

英文摘要Abstract：The dependency between objects in OOS impacts other components while some objects take changes，this paper proposes an object dependency constructing method，which simplifies the dependency between objects into interface and function dependency，searches the hierarchical structure of system，and converts the complex many-to-many dependency in dependency graph to concise one-to-many dependency of dependency trees.When concrete object changes，this paper determines the scope of change impact by searching the changed node，calculates the extra workload，confirming the degree of change impact and providing quantitative base for risk assessment and control that change causes. Last the feasibility of change impact evaluation method is proved by an example.

英文關(guān)鍵詞Key Words：object oriented； object dependency trees； change impact analysis； ripple effect

0 引言

面向?qū)ο笙到y(tǒng)中對(duì)象之間存在著錯(cuò)綜復(fù)雜的依賴關(guān)系[1-2]，在軟件開發(fā)過程中，客戶需求的變更又是客觀存在、不可避免的[3]，雖然面向?qū)ο箝_發(fā)技術(shù)提高了軟件開發(fā)效率，但變更影響通過對(duì)象間依賴關(guān)系的傳遞又影響到開發(fā)效率，且?guī)淼娘L(fēng)險(xiǎn)難以預(yù)測。傳統(tǒng)的依賴分析法大多基于控制依賴和數(shù)據(jù)依賴的依賴圖模型進(jìn)行程序分析[4-5]。該方法從語句粒度進(jìn)行分析研究，會(huì)得到大量冗余的依賴信息。當(dāng)軟件規(guī)模到達(dá)一定量級(jí)時(shí)，就無法直觀確定變更影響的范圍。面向?qū)ο蟮能浖到y(tǒng)是以對(duì)象為基礎(chǔ)的程序邏輯，當(dāng)遇到面向?qū)ο笾幸蚨鄳B(tài)技術(shù)而產(chǎn)生間接依賴關(guān)系時(shí)，傳統(tǒng)的程序依賴圖顯得力不從心[6]。分析面向?qū)ο笙到y(tǒng)中對(duì)象之間的依賴關(guān)系，確定需求變更波及效應(yīng)的涉及范圍，在變更之前就清晰認(rèn)識(shí)到變更造成的各種潛在影響，更易于對(duì)軟件項(xiàng)目的開發(fā)過程進(jìn)行控制以及降低項(xiàng)目開發(fā)風(fēng)險(xiǎn)。

本文根據(jù)面向?qū)ο蟮奶匦?，從?duì)象這一粒度層面對(duì)面向?qū)ο笙到y(tǒng)中的依賴關(guān)系進(jìn)行分析，提出了一種對(duì)象層依賴關(guān)系構(gòu)造方法。該方法在提出的依賴和節(jié)點(diǎn)表示法基礎(chǔ)上，通過剖析面向?qū)ο笙到y(tǒng)的結(jié)構(gòu)關(guān)系構(gòu)造對(duì)象依賴圖，再對(duì)依賴圖進(jìn)行遍歷得到各組成部分之間的依賴關(guān)系樹，將依賴圖中多對(duì)多的輻射狀依賴關(guān)系轉(zhuǎn)化為依賴關(guān)系樹中較為簡潔的一對(duì)多樹形依賴關(guān)系，可以方便快捷地確定對(duì)象之間的依賴關(guān)系；當(dāng)發(fā)生對(duì)象變更時(shí)，以變更對(duì)象節(jié)點(diǎn)為初始點(diǎn)搜索依賴關(guān)系樹，獲取依賴于變更節(jié)點(diǎn)的其它對(duì)象節(jié)點(diǎn)，從而確定變更產(chǎn)生的影響范圍。根據(jù)對(duì)象之間的依賴因子計(jì)算出變更產(chǎn)生的額外工作量，為項(xiàng)目過程控制及風(fēng)險(xiǎn)分析提供定量依據(jù)。

1 建模

依賴關(guān)系指系統(tǒng)組成部分之間存在的一種語義連接。當(dāng)一個(gè)對(duì)象發(fā)生變更時(shí)，與之有依賴關(guān)系的另一個(gè)對(duì)象也發(fā)生相應(yīng)變更，從而保證系統(tǒng)語義上的完整性和一致性[7]。通常將前者稱為源對(duì)象節(jié)點(diǎn)，后者稱為目標(biāo)對(duì)象節(jié)點(diǎn)。如果源對(duì)象節(jié)點(diǎn)不依賴于其它對(duì)象節(jié)點(diǎn)，稱這樣的對(duì)象節(jié)點(diǎn)為底層節(jié)點(diǎn)。

1.1 對(duì)象依賴關(guān)系定義

定義1：對(duì)象依賴關(guān)系表示為一個(gè)三元組Dependence={（OS，OT，depType）| OS∈O，OT ∈O，Reachability（OT，OS）=1}，其中O是面向?qū)ο笙到y(tǒng)中對(duì)象節(jié)點(diǎn)的集合，OS表示源對(duì)象節(jié)點(diǎn)，OT表示目標(biāo)對(duì)象節(jié)點(diǎn)，depType表示依賴類型，Reachability表示對(duì)象之間的可達(dá)性。

定義2 ：對(duì)象可達(dá)性。Reachability（Om，On）：Om，On是程序中的對(duì)象節(jié)點(diǎn)，存在著一條成功執(zhí)行軌跡[8]Path，Ni是Path中的程序節(jié)點(diǎn)。Om通過節(jié)點(diǎn)Ni調(diào)用On，稱Om與On的可達(dá)性為1，即Reachability（Om，On）=1；反之Reachability（Om，On）=0，記作：

Reachability（Om，On）=1，OminvokeOn0，else

1.2 依賴性質(zhì)

當(dāng)依賴源對(duì)象節(jié)點(diǎn)OS發(fā)生變更時(shí)，依賴目標(biāo)對(duì)象節(jié)點(diǎn)OT也會(huì)發(fā)生相應(yīng)變化。分析對(duì)象依賴關(guān)系可得出如下幾種性質(zhì)：

性質(zhì)1： 自反性。軟件系統(tǒng)中的任一對(duì)象都是依賴于自身的，即N，（N，N）∈Dependence。

性質(zhì)2： 傳遞性。如果對(duì)象節(jié)點(diǎn)N1依賴于對(duì)象節(jié)點(diǎn)N2，對(duì)象節(jié)點(diǎn)N2依賴于對(duì)象節(jié)點(diǎn)N3，則對(duì)象節(jié)點(diǎn)N1也依賴于對(duì)象節(jié)點(diǎn)N3，即N1，N2，N3，（N1，N2）∈Dependence Λ （N2，N3）∈Dependence→（N1，N3）∈Dependence。

性質(zhì)3 ：時(shí)序性。對(duì)象節(jié)點(diǎn)之間的依賴在時(shí)間上存在順序性，即N1，N2，N3，在同一時(shí)間點(diǎn)，（N1，N2）∈Dependence Λ （N1，N3）∈Dependence是不成立的。

性質(zhì)4 ：方向性。對(duì)象節(jié)點(diǎn)之間的依賴具有方向性，即依賴的方向是由依賴目標(biāo)對(duì)象節(jié)點(diǎn)指向依賴源目標(biāo)節(jié)點(diǎn)，記為ST→SS。

性質(zhì)5 ：多樣性。系統(tǒng)自身的性質(zhì)決定了對(duì)象節(jié)點(diǎn)之間的依賴關(guān)系多種多樣。一個(gè)系統(tǒng)由對(duì)象節(jié)點(diǎn)之間通過各種類型的依賴聯(lián)系在一起。

根據(jù)依賴關(guān)系性質(zhì)可有以下兩種推論：

推論1 ：非循環(huán)依賴性。根據(jù)傳遞性和方向性可以推導(dǎo)出對(duì)象節(jié)點(diǎn)之間不存在循環(huán)依賴，即N1，N2，N3，（N1，N2）∈Dependence Λ （N2，N3）∈Dependence Λ（N3，N1）∈Dependence是不成立的。

推論2 ：直接依賴性與間接依賴性。兩個(gè)對(duì)象節(jié)點(diǎn)之間的依賴路徑上不包含其它對(duì)象節(jié)點(diǎn)，則將其稱為直接依賴，反之稱其為間接依賴。

1.3 對(duì)象依賴關(guān)系分類

面向?qū)ο筌浖袑?duì)象間多層抽象特性[9]使不同的依賴關(guān)系對(duì)接口、類或方法的依賴程度有所不同，依賴程度的差異性增加了變更影響分析中變更度量的難度，導(dǎo)致變更影響分析不準(zhǔn)確。確定對(duì)象節(jié)點(diǎn)間的依賴類型可得到對(duì)象之間的依賴程度，從而提高變更影響的準(zhǔn)確性。

本文將對(duì)象之間的依賴關(guān)系總結(jié)為接口依賴和方法依賴兩大類。接口依賴指對(duì)象之間通過接口進(jìn)行交互，從而產(chǎn)生依賴關(guān)系，主要包括包級(jí)別的依賴和類級(jí)別的依賴；方法依賴又稱函數(shù)依賴，指對(duì)象通過方法的調(diào)用產(chǎn)生依賴關(guān)系[10]，主要包含函數(shù)級(jí)別的依賴。各個(gè)級(jí)別的依賴關(guān)系又可進(jìn)一步細(xì)分，具體的依賴類型劃分如表1所示。

2 對(duì)象依賴關(guān)系提取

在構(gòu)建面向?qū)ο笠蕾噲D的基礎(chǔ)上，對(duì)依賴圖進(jìn)行搜索，得到底層節(jié)點(diǎn)集合；再以底層節(jié)點(diǎn)中的元素為起始點(diǎn)深度優(yōu)先搜索面向?qū)ο蟮囊蕾囮P(guān)系圖，將依賴于底層節(jié)點(diǎn)的對(duì)象節(jié)點(diǎn)作為子節(jié)點(diǎn)，構(gòu)造出以底層節(jié)點(diǎn)為根節(jié)點(diǎn)的對(duì)象依賴關(guān)系樹，通過該方法可將依賴圖中復(fù)雜的多對(duì)多依賴關(guān)系轉(zhuǎn)化為關(guān)系樹中較為簡潔的一對(duì)多依賴關(guān)系，降低確定依賴關(guān)系的復(fù)雜度。

2.1 依賴圖表示

本文在文獻(xiàn)[11]提出的面向?qū)ο笠蕾噲D表示方法基礎(chǔ)上，對(duì)依賴圖中的對(duì)象節(jié)點(diǎn)和依賴關(guān)系設(shè)定相應(yīng)的圖形表示法，依賴關(guān)系圖中使用到的依賴邊和程序節(jié)點(diǎn)及其表示法如表2、表3所示。

對(duì)于依賴圖中的每一個(gè)對(duì)象節(jié)點(diǎn)N，入度indegree（N） 表示依賴于節(jié)點(diǎn)N的節(jié)點(diǎn)數(shù)，出度outdegree（N）表示節(jié)點(diǎn)N依賴的節(jié)點(diǎn)數(shù)。由此可知，底層節(jié)點(diǎn)的出度為0，通過引入出度與入度的概念可有效解決依賴關(guān)系有向圖中可能存在的循環(huán)依賴問題。

2.2 底層節(jié)點(diǎn)確定

根據(jù)底層節(jié)點(diǎn)解釋可知，通過遍歷依賴圖中對(duì)象節(jié)點(diǎn)，找出所有出度為0的節(jié)點(diǎn)，就可得到底層節(jié)點(diǎn)的集合，算法1說明了底層節(jié)點(diǎn)確定過程。

算法1：

findRootNode

輸入：源程序的依賴圖

輸出：RootNode

RootNode=，RootClass=，RootMethod=

//calculate the RootClass

for i=1 to n

if outdegree（class（i））=0 then

RootClass= RootClass ∪ class（i）

//calculate the RootMethod

for i=1 to m

if outdegree（method（i））=0 then

RootMethod= RootMethod ∪ method（i）

//calculate the RootNode

RootNode= RootClass ∪ RootMethod

2.3 依賴關(guān)系樹構(gòu)造

依賴關(guān)系多叉樹的構(gòu)造步驟：將依賴圖中出度為0的節(jié)點(diǎn)集合RootNode作為初始隊(duì)列，對(duì)隊(duì)列中的元素執(zhí)行出隊(duì)操作，并以出隊(duì)元素作為起始節(jié)點(diǎn)對(duì)依賴圖進(jìn)行深度優(yōu)先搜尋，搜索到的關(guān)聯(lián)節(jié)點(diǎn)執(zhí)行入隊(duì)操作。重復(fù)上述操作，直至隊(duì)列為空時(shí)終止。算法2和算法3說明了將依賴關(guān)系圖轉(zhuǎn)化為依賴關(guān)系樹的實(shí)現(xiàn)過程。

算法2：

DFS（G）

while indegree（RootNode）！=0

for each RootNode∈G.V

DFS-VISIT（G，RootNode）

// output the dependency set and dependency path

indegree（RootNode）--

connect（）；//connect the childtree

算法3：

DFS-VISIT（G，u）

for each v∈G.Adj（u） //v is the childnode of u

if indegree（v）！=0

DFS-VISIT（G，v）

indegree（v）--

// connect childnode to v by dependency path

//Construct the dependenceTree

為迅速找到變更節(jié)點(diǎn)影響到的程序節(jié)點(diǎn)，在得到依賴關(guān)系樹后對(duì)其進(jìn)行分割處理，將父節(jié)點(diǎn)和子節(jié)點(diǎn)組成的子樹作為一棵深度為2的依賴關(guān)系樹，建立直接依賴關(guān)系樹。通過分析變更節(jié)點(diǎn)子節(jié)點(diǎn)子樹，可方便地找到變更所影響到的節(jié)點(diǎn)結(jié)合。但此種方法缺點(diǎn)是會(huì)生成數(shù)量眾多的依賴關(guān)系樹，空間復(fù)雜度較高。

3 變更影響評(píng)估

在面向?qū)ο筌浖木S護(hù)過程中，軟件變更是無法避免的，且變更會(huì)對(duì)系統(tǒng)其它部分產(chǎn)生難以預(yù)料的波動(dòng)效應(yīng)[12]，軟件變更影響分析可確定潛在影響。變更影響分析包含一個(gè)變更元素的集合changeSet，以及變更影響到需要維護(hù)的元素集合impactSet。在遍歷對(duì)象依賴關(guān)系樹的基礎(chǔ)上得到變更影響集合，再根據(jù)對(duì)象間的依賴因子計(jì)算變更帶來的額外工作量。

3.1 變更影響集合確定

變更提議是軟件開發(fā)人員在現(xiàn)有軟件上提出的變更[13]，其組成的集合changeSet可根據(jù)實(shí)際變更要求準(zhǔn)確定位到對(duì)象依賴關(guān)系樹中的若干個(gè)節(jié)點(diǎn)；以changeSet中的每個(gè)元素為根節(jié)點(diǎn)依次遞歸遍歷其對(duì)應(yīng)的依賴關(guān)系樹，得到每個(gè)元素的影響集合[14]impactSet，算法4描述了確定影響集合的過程。

算法4：

travel（node）

impactSet=，child_node=

for each node in changeSet do

for i=1 to node.child_list do

impactSet= impactSet∪child_node（i）

travel（childnode（i））

return impactSet

得到每個(gè)變更元素的影響集合后，可進(jìn)一步求出影響集合之間的交集。該交集表示眾多變更所共同影響到的元素，通過這一步驟可降低影響集合的冗余度，提高變更影響分析的準(zhǔn)確度。

3.2 變更影響度量

變更影響程度在軟件工程中體現(xiàn)為變更所產(chǎn)生的實(shí)際工作量，本文對(duì)文獻(xiàn)[15]和文獻(xiàn)[16]中的評(píng)估公式加以修改，根據(jù)變更集合元素和變更影響集合中每個(gè)元素的依賴因子以及依賴關(guān)系所屬級(jí)別的工作負(fù)載，得到實(shí)施變更所產(chǎn)生的實(shí)際工作量大小。變更的工作量計(jì)算見公式（1）。

changeDegree=∑WLi*depFactor（OS，OT）（1）

式（1）中，WLi表示變更每個(gè)級(jí)別所需的工作負(fù)載，本文將包、類和方法級(jí)別的工作負(fù)載分別設(shè)為8、4和2；depFactor（OS，OT）表示兩者之間的依賴因子。圖1表示對(duì)象節(jié)點(diǎn)之間的依賴關(guān)系范例。

假設(shè)此依賴關(guān)系的工作負(fù)載為4，節(jié)點(diǎn)之間的依賴因子為depFactor（N1，N2）=0.8，depFactor（N2，N3）=0.4，depFactor（N3，N4）=0.6。通過上述條件可得到節(jié)點(diǎn)N1變更產(chǎn)生的額外工作量changeDegree=4*0.8+4*0.4+4*0.6=7.2。

4 案例分析

選取雇員管理系統(tǒng)中的部分程序源碼，采用本文方法構(gòu)建對(duì)象間的依賴關(guān)系。根據(jù)本文提出的圖形表示法得到示例程序的依賴圖如圖2所示，經(jīng)依賴樹構(gòu)造算法產(chǎn)生的依賴關(guān)系樹如圖3所示。關(guān)系樹中的子節(jié)點(diǎn)直接依賴于父節(jié)點(diǎn)，通過觀察依賴關(guān)系樹，可以清晰得到兩個(gè)節(jié)點(diǎn)之間是否存在依賴關(guān)系。

假設(shè)軟件系統(tǒng)開發(fā)完成后，因?yàn)榭蛻粜枨蟀l(fā)生變化，需要對(duì)employeeService和EmployeeDAO進(jìn)行修改，遍歷這兩個(gè)節(jié)點(diǎn)對(duì)應(yīng)的依賴關(guān)系樹可得到依賴于變更節(jié)點(diǎn)的依賴集合分別為{employeeServiceImpl，XXXEmployeeAction}和{EmployeeDAOImpl，employeeServiceImpl}，對(duì)影響集合中相同節(jié)點(diǎn)處理后得到影響的對(duì)象為{employeeServiceImpl，XXXEmployeeAction，EmployeeDAOImpl}。

通過底層節(jié)點(diǎn)提取算法對(duì)源程序的依賴關(guān)系分析可得到底層節(jié)點(diǎn)集合RootNode={Employee}。

變更集合元素和變更影響集合元素之間的工作負(fù)載都為4，對(duì)象間依賴關(guān)系和依賴因子如表4所示。結(jié)合分析得到的工作負(fù)載和依賴因子，可計(jì)算出此次變更所產(chǎn)生的額外工作總量changeDegree=4*0.6+4*0.2+4*0.6+4*0.2=6.4。

5 結(jié)語

軟件項(xiàng)目開發(fā)過程中變更是不可避免的，在變更實(shí)施之前，準(zhǔn)確預(yù)測變更對(duì)系統(tǒng)產(chǎn)生的影響范圍及程度，對(duì)降低開發(fā)風(fēng)險(xiǎn)尤為重要。本文在分析面向?qū)ο笙到y(tǒng)組成部分的依賴關(guān)系基礎(chǔ)上，提出一種對(duì)象依賴關(guān)系構(gòu)造方法。該方法將依賴圖中的多對(duì)多依賴關(guān)系轉(zhuǎn)化為一對(duì)多的依賴關(guān)系樹，通過遍歷以變更節(jié)點(diǎn)為起始點(diǎn)的依賴關(guān)系樹，得到變更影響波及的范圍。根據(jù)對(duì)象間依賴因子計(jì)算變更產(chǎn)生的額外工作量，為項(xiàng)目開發(fā)過程分析提供定量依據(jù)。案例分析表明，該方法具有較高的準(zhǔn)確度。為提高變更影響分析精度，今后可進(jìn)一步研究接口和方法中屬性的類型信息。

參考文獻(xiàn)：

[1] ZHAO J.Applying program dependence analysis to Java software[C].Workship on Software Engineering and Database Systems，Taiwan，1998：162-169.

[2] MIKHAILOV A，HMELNOV A，CHERKASHIN E，et al.Control flow graph visualization in compiled software engineering[C].International Convention on Information and Communication Technology，Electronics and Microelectronics.2016：1313-1317.

[3] 劉華虓，金英，馬鵬飛.一種需求變更影響分析方法[J].計(jì)算機(jī)研究與發(fā)展，2013，50（8）：1769-1777.

[4] DENARO G，MARGARA A，PEZZE M，et al.Dynamic data flow testing of object oriented systems[C].IEEE International Conference on Software Engineering.ACM，2015：947-958.

[5] NAJUMUDHEEN E S F，MALL R，SAMANTA D.A dependence graph-based test coverage analysis technique for object-oriented programs[C].Sixth International Conference on Information Technology：New Generations.IEEE Computer Society，2009：763-768.

[6] COOPER D，CHAN M W，MEHRA G，et al.Using dependence graphs to assist manual and automated object oriented software inspections[C].Australian Software Engineering Conference.IEEE Computer Society，2006：262-269.

[7] 楊鶴標(biāo)，陳震.面向?qū)ο蟠a變更影響分析模型的研究[J].計(jì)算機(jī)工程與設(shè)計(jì)，2010，31（19）：4232-4234.

[8] 曹鶴玲，姜淑娟，鞠小林，等.基于動(dòng)態(tài)切片和關(guān)聯(lián)分析的錯(cuò)誤定位方法[J].計(jì)算機(jī)學(xué)報(bào)，2015（11）：2188-2202.

[9] 李軒，郝克剛，葛瑋.面向?qū)ο筌浖攘康姆治龊脱芯縖J].計(jì)算機(jī)技術(shù)與發(fā)展，2006，16（11）：38-41.

[10] 歐陽，胡順仁，汪治華.面向?qū)ο笙到y(tǒng)的類之間依賴關(guān)系度量研究[J].計(jì)算機(jī)科學(xué)，2004，31（2）：181-183.

[11] CHEN J L，WANG F J，CHEN Y L.An object-oriented dependency graph for program slicing[C].Technology of Object-Oriented Languages，1997.TOOLS 24.Proceedings.IEEE，1997：121-130.

[12] SUN X，LI B，LEUNG H，et al.Static change impact analysis techniques：a comparative study [J].Journal of Systems & Software，2015，109（C）：137-149.

[13] LEE M，OFFUTT A J，ALEXANDER R T，et al.Algorithmic analysis of the impacts of changes to object-oriented software[EB/OL].https：//ieeexplore.ieee.org/document/868959/arnumber=868959.

[14] NEJATI S，SABETZADEH M，ARORA C，et al.Automated change impact analysis between SysML models of requirements and design[C].ACM Sigsoft International Symposium on Foundations of Software Engineering.ACM，2016：242-253.

[15] YANG H B，LIU Z H，MA Z H.An algorithm for evaluating impact of requirement change[EB/OL].http：//www.doc88.com/p-6931564788263.html

[16] 楊鶴標(biāo)，張繼敏，朱玉全.一種需求變更影響的評(píng)估算法[J].計(jì)算機(jī)工程，2006，32（23）：82-84.

（責(zé)任編輯：杜能鋼）