基于抽象語法樹的修改影響分析方法

高 燦， 侯秀萍， 孫士明

（長春工業大學 計算機科學與工程學院，吉林 長春 130012）

0 引 言

在軟件測試和維護過程中，一旦發現軟件系統中存在錯誤，則應立即排除它們，為了保證程序的修改沒有引入新的錯誤，則必須對其進行回歸測試。為了節省測試成本、提高測試效率，回歸測試只需要測試那些由于修改而受到影響的部分[1]。

面向對象程序中，多態允許對同樣的請求可以有不同的響應，動態綁定允許在程序運行時才決定它的執行體，類的繼承和使用過程使得面向對象程序具有模塊化、層次化和有利于代碼重用等優點，但同時又使得程序修改的擴散效應更加明顯[2]。例如，繼承使得一個類的成員變量和成員函數能夠被一些子類所重用[3]，所以，當修改父類的時候就會導致與它相關的類也要在回歸測試的過程中重新進行測試。

在回歸測試中，重新測試所有的類從測試代價和成本上講是完全沒有必要的，僅測試那些修改的內容和修改影響到的內容就能夠達到和全部重測同樣的效果。楊芙清[4]等通過分析面向對象軟件系統的特性，定義了對象之間的依賴關系，通過依賴關系導出測試對象的方法序列。Rothermel[5]等提出通過構建程序依賴圖（Program Dependence Graph）來表示數據依賴和控制依賴，并找出關于繼承、封裝和多態等構造關系的子類和其它類[6]。

文中針對面向對象程序具有繼承、封裝、多態等特點，深入研究了程序修改的影響范圍，提出了基于抽象語法樹的修改影響分析方法，為測試人員提供合理的測試范圍，期望能夠達到減少回歸測試花銷，提高測試效率的目的。

1 程序依賴關系研究

1.1 依賴關系定義（Dependence Relationship，DR）

面向對象程序的封裝性要求把屬性和方法封裝在一起形成類，不同的類通過方法的調用實現交互。

定義1 類C定義為屬性集V和方法集M的并集，記為：

定義2 類C與C′之間的依賴關系D定義為在集合C和C′上的二元關系，記為：

其中，序偶〈x，y〉表示元素x依賴于元素y，即元素y的變化會影響到元素x。

定義3 數據依賴（Data Dependence，DD）。設類C中存在屬性v∈V，若屬性集V發生屬性類型和值的調整及屬性數量的增減等變化，導致類C′中引用屬性v的方法發生變化，則稱類C′數據依賴于類C，記為：C′DDC。

定義4 控制依賴（Control Dependence，CD）。設類C中存在方法m∈M，若方法集M發生訪問類型、參數和語句的變化及方法數量的增減等情況，導致類C′中調用方法m的方法發生變化，則稱類C′控制依賴于類C，記為：C′DCC。

1.2 依賴關系存儲結構設計

根據程序依賴關系的定義，可以解析源文件語法樹，抽取其數據依賴和控制依賴關系，將其存于相應的存儲結構中，為修改影響分析提供依據。其主要結構設計如下：

1）數據依賴關系表（Date Dependence Relationship Table，DDRT）。

DDRT：：＝ （Class，Field，Method），其中：

Class：類名；

Field：屬性名；

Method：使用該變量的方法名。

2）控制依賴關系表（Control Dependence Relationship Table，CDRT）。

CDRT ：：＝（Class，Method，Method＿call，Class＿call），其中：

Class：類名；

Method：方法名；

Method＿call：被調用的方法名；

Class＿call：被調用方法所在的類名。

2 基于抽象語法樹的修改影響分析

在軟件測試過程中要對程序源代碼的語法結構進行合理存儲，以利于確定修改信息，因此需要找到一種源代碼語法層次信息的載體，也就是從程序源代碼文件生成的抽象語法樹（Abstract Syntax Tree，AST）[8]，并通過遍歷Java源程序的抽象語法樹獲取源程序中的類名、方法名、屬性名和調用信息等內容存儲在二維表中。Eclipse開發平臺中的JDT（Java Development Tooling）工具通過對源程序進行語法分析和詞法分析可以將源代碼解析成抽象語法樹，用戶只需要指明源文件的存儲位置并調用ASTParser類中的creatAST（）方法就可以得到源程序中的類名、方法名、屬性名和調用信息等內容并進行存儲，以便后續使用。

對于一個面向對象程序P，通過遍歷抽象語法樹建立其DDRT表和CDRT表分別為T1，T2；設修改后的程序為P′，其DDRT表和CDRT表分別為T′1，T′2。

針對面向對象程序的特點，將程序的修改定義為6種原子修改，分別為：

1）增加方法；

2）刪除方法；

3）修改方法；

4）增加屬性；

5）刪除屬性；

6）修改屬性。

所有的修改都可以視為這幾種操作的組合。

2.1 增加方法（Added Method）

當增加一個方法時，還要同時增加對這個方法的調用，受到影響的部分為修改后的程序中直接和間接調用它的那些方法。因此，設新增加的方法為（C，m），按下述遞歸規則定義受其影響的方法集合AAM（C，m）定義為 ：

從AMi（C，m）構成 AMi＋1（C，m），如果不增加任何新的元素，有

2.2 刪除方法（Deleted Method）

當刪除一個方法時，對于這個方法的調用也同時被刪除，因此，受到影響的部分為修改前的程序中調用它的那些方法。設刪除的方法為（C，m），則受到影響的方法集合DM（C，m）定義為：

從DMi（C，m）構成 DMi＋1（C，m），如果不增加任何新的元素，有

2.3 修改方法（Changed Method）

對方法的修改包括以下幾種情況：

1）修改方法的訪問類型（public，protected和private）。

若將訪問類型由public或者protected類型變為private類型，則方法不能被其它方法調用，因此，修改后的程序中不會出現對它的調用關系，受到影響的部分為修改前的程序中直接和間接調用該方法的其它方法，也就是相當于刪除一個方法，對于此類情況的處理方法同式（4）；反之，若將訪問類型由private類型變為public或者protected類型，則方法能被其它方法調用，因此，修改后的程序中調用該方法的其它方法受到影響，也就是相當于增加一個方法，處理方法同式（3）。

2）修改方法的參數（包括參數類型、參數個數和參數值）和方法體中的語句時，修改前和修改后的程序中直接和間接調用該方法的其它方法都會受到影響，因此處理按照方法式（3）和式（4），并取兩種方法計算出的結果的并集。

2.4 增加屬性（Added Property）

當增加一個屬性時，受到影響的部分為修改后的程序中使用它的那些方法以及調用那些方法的其它方法。因此，設新增加的屬性為（C，v），則受影響的方法集合AP（C，v）定義為：

從APi（C，v）構成APi＋1（C，v），如果不增加任何新的元素，有

2.5 刪除屬性（Deleted Field）

當刪除一個屬性時，受到影響的部分為修改前的程序中使用它的那些方法以及調用那些方法的其它方法。因此，設刪除的屬性為（C，v），則受影響的方法集合DP（C，v）定義為：

從DPi（C，v）構成DPi＋1（C，v），如果不增加任何新的元素，有

2.6 修改屬性（Changed Property）

當修改一個屬性時，受到影響的部分為修改后的程序中使用它的那些方法以及調用那些方法的其它方法。因此，設修改的屬性為（C，v），則受影響的方法集合CP（C，v）定義為：

從CPi（C，v）構成CPi＋1（C，v），如果不增加任何新的元素，有

2.7 其它修改

除了以上提到的6種原子修改外，還有基于類粒度的修改，如增加類（Added Class）、刪除類（Deleted Class）和修改類（Changed Class）。

增加類表示在一個空類中增加新的方法和屬性。因此，可以使用式（3）和式（5）中提供的方法來確定受到修改影響的方法集。

刪除類相當于對一個類刪除它的所有屬性和方法。因此，可以使用式（4）和式（6）中提供的方法鑒別修改影響范圍。

修改類相當于對一個類中的屬性和方法的修改，因此，可以使用式（3）、式（4）和式（7）中提供的方法確定修改影響范圍。

3 實驗結果

通過以上提到的集中方法，對一個Java測試程序進行了修改影響分析實驗。該程序中包含6個類和20個方法，實驗結果見表1。

表1 實驗結果

從表中可以看出，與全部重測所有類中的所有方法相比，基于抽象語法樹的修改影響分析方法能夠減少回歸測試中重新測試的方法數量，從而有效提高回歸測試的效率，但是這種方法僅適合少量修改的情況。

4 結 語

介紹了一種針對面向對象程序的基于抽象語法樹的修改影響分析方法，建議在回歸測試中對修改的方法本身及受到屬性和方法修改所影響的方法進行測試。雖然沒有實現全面的自動化測試，但也在一定程度上提高了測試的效率，減少了測試的代價，在后續的研究過程中將繼續關注修改范圍的自動化確定和回歸測試用例的選擇等問題。

[1]White L J，Leung H K N.A firewall concept for both control－flow and date－flow in regression integration testing[C]／／Proceedings of the Conference on Software Maintenance，1992：262－270.

[2]雷海虹，繆力，張大方.面向對象程序的兩種修改影響分析方法[J].計算機工程與科學，27（5）：101－103.

[3]陳躍峰，李中彬，谷驍勇.Java編程那些事兒[M].北京：清華大學出版社，2010：150－152.

[4]方菲，孫家骕，楊芙清.面向對象軟件回歸測試技術研究[J].軟件學報，2001，12（3）：372－376.

[5]Rothermel G，Harrold M J.Selecting Regression Tests for Object－Oriented Sofware Proc.[C]／／IEEE International Conference on Softuare Maintenance，1994：14－25.

[6]馬玉州.面向對象軟件的回歸測試方法研究[D]：[碩士學位論文].長春：吉林大學，2009.