基于动态调用图的Java程序修改影响分析技术

刘 震，缪 力

(湖南交通职业技术学院现代教育技术中心，中国 长沙 410132)

软件测试是软件生命周期中重要的一环，用在测试上的开销要占30%～50%[1]．软件回归测试指对修改之后的软件进行的测试，其目的主要是1)修改后新的功能测试；2)修改是否引入新的错误.由于程序各元素之间的关系非常复杂，如果没有分析方法，程序修改之后一般需要对整个程序重新测试，即RETEST-ALL方法．RETEST-ALL方法效率非常低．特别是当软件进入开发后期或者维护阶段，软件经常需要进行频繁却少量的修改.如果每次修改都需要重新运行全部的测试用例，将导致软件开发和维护的效率低下．为了提高测试效率，人们希望对修改的软件进行分析，找出软件中由于修改可能影响的部分，这就是修改影响分析.修改影响分析能使测试有目的的进行，提高测试效率，降低测试费用．如Rothermel通过控制流分析，提出一种安全的(safe)回归测试技术[2]，使得回归测试可以只运行与改动相关的小部分测试用例，而测试效果运行全部测试用例完全相同．

面向对象软件技术利用可重用性提高了软件开发的效率.随着面向对象软件开发技术的成熟，软件的规模越来越大，对其进行小部分修改后要回归测试．对于面向对象技术所开发的软件和其他方法所开发的软件，基于规格的测试是相同的.但对于基于程序的测试有很大区别，因为面向对象技术的特征对测试其所开发的程序有很大影响，相应的回归测试也一样受影响.在选择需重新执行的测试用例时必须考虑面向对象技术的特征．

随着面向对象技术的成熟，现在的大部分软件产品使用面向对象方法编写，所以面向对象的回归测试技术也逐渐成了回归测试研究中的重点．面向对象软件中主要是对象之间的依赖关系以及各种类之间的继承和组合关系，对象之间通过消息相互操作及影响．Leung和White[3-4]提出了回归测试的防火墙概念，Kung 等[5-7]针对面向对象的程序扩展为类防火墙，以类为测试的基本单元，先标识出改变的类与受改变影响的类，即构造一个类防火墙，然后对类防火墙中的类根据对象关系图以一定的顺序进行回归测试．

现有的影响分析算法大都基于程序的静态分析技术，通过分析程序源代码构建程序的类、方法等不同粒度的模型，然后基于该模型计算修改影响的范围．静态分析比较复杂，且是一种保守的分析技术，即如果分析得出模块A与修改相关，则这种相关只是可能相关；而如果分析得出模块A与修改无关，则肯定无关.因此，静态分析技术的精度不高．针对静态分析存在的问题，本文提出采用动态分析技术构造程序的类成员防火墙，从而降低计算复杂度，并提高分析精度，便于修改影响分析技术的实际运用．

1 基于动态信息的修改影响分析框架

基于动态信息的修改影响分析原理如图1所示．

图1 基于动态信息的修改影响分析原理框架图

首先要获得动态信息．动态信息一般需要在程序中插桩，使得程序可以输出运行中的信息，然后才能搜集．与C程序需要对源代码插桩不同，Java程序被编译为字节码在虚拟机上运行，因此可以直接对编译后的Java字节码程序插桩．插桩工具可基于Javaassist[8]或者BECL[9]等Java字节码操控工具提供的接口进行开发．对每条语句插桩将导致巨大的执行轨迹信息，并可能严重影响系统性能，导致一些具有实时要求的系统不能运行，因此，本文采用对每个方法插桩，记录方法调用信息．

表1为BECL与Javaassist的接口使用对比，同样是要插入“System.out.println()”语句以输出执行信息， BECL需要更多的编译知识，需要将语句分解为特定的格式插入，而Javaassist更加方便，可以直接插入该语句．

表1 BECL与Javaassist的接口使用对比表

运行插桩后的Java程序，程序根据插桩的设置输出执行轨迹信息，搜集轨迹信息并构造动态调用图；基于动态调用图，通过修改影响分析可以得出需要重新测试的模块，从而实现了高效的回归测试．

2 动态调用图(Dynamic Call Graph)

函数调用图是编译期对程序中函数调用关系的一种静态描述.在函数调用图中，节点表示函数，边表示函数之间的调用关系，因为对于虚函数调用点而言，必须根据运行时接受对象的实际类型才能确定具体调用的目标函数，所以函数调用图只是对程序运行时函数调用关系的一种近似．如果在编译期对虚函数调用点采用不同的静态处理策略，那么所得到的函数调用图在节点和边的数目上也不尽相同.然而所有处理策略的目标是一致的，那就是使通过静态分析构建的函数调用图能够更接近于程序运行时实际的函数调用情况．下面是模拟器程序函数调用图：

图2 一个函数调用图的示例

对于虚函数调用点而言，必须根据运行时接受对象的实际类型来确定具体调用的目标函数，因此静态调用图是不精确的．

例1一个导致静态调用图不精确的例子

class A extends Object{ A e; void m(){ A a=new A(); e=a; System.out.println(“is A”); }}class B extends A{ void m(){ System.out.println(“is B”); }} class C extends A { void m(){ System.out.println(“is C”); } Public static void main (String args[]){ A d,e; A f=new A(); B b=new B(); C c=new C(); d=b; e=d; e.m(); }}

由此可见，变量e在运行时的可能类型就包括A，B和C．

给出较为精确的面向对象程序的调用关系对于修改影响分析有重要意义.本文提出采用动态调用图(Dynamic Call Graph，以下简称DCG)作为修改影响分析的对象.与静态调用图相比，DCG直接从程序执行的动态信息中构造调用图，无需分析程序源代码，技术上实现比较简便.由于采用的是执行信息，无需进行虚函数的动态绑定分析，精度也比静态调用图有提高．

动态调用图构造算法

输入：程序调用信息的执行轨迹集合TC={tc1,tc2,…,tcn},其中tci={mi1in,mi2in,…，mi2out…mi1out…},mijin表示进入mij方法，mijout表示退出mij方法；

输出：动态调用图 DCG

Fori=1…ndo{

For eachmj∈tcido{

Ifmjmarked “in”//调用方法进入

Push (mj,currentmethod) ;将当前所在的方法压入堆栈

Ifminnot in DCG

Addnode(DCG,mj)；//如果轨迹中节点不在DCG中，增加该节点

If (top(currentmethod),min)

Addedge (DCG, top(currentmethod)，mj); //如果轨迹中节点的调用关系不在DCG中，增加边

Else // 调用方法退出

Pop (mj,currentmethod)//将当前所在的方法弹出堆栈

}

}

算法说明：算法的输入是执行轨迹集合TC={tc1,tc2,…,tcn}，其中每条轨迹tci记录了每个方法m进入和退出的信息，分别标志为in 和out．

构造DCG需要节点和边的信息.节点通过将轨迹中记录的调用信息加入DCG中得到，即Addnode(DCG,mj)．注意到方法调用是以堆栈方式进行，即先进后出，因此，设置currentmethod为调用堆栈，每次遇到标志为in的节点，表示方法被调用，即将该方法压入堆栈，此时，接下来的标志为in的节点都与该方法存在调用关系，通过Addedge (DCG, top(currentmethod)，mj)将调用关系加入DCG中，直到遇到标志为out的节点，表示该方法调用退出，此时弹出堆栈，退回上一层调用方法．算法从所有的执行轨迹中提取方法调用的信息，从而构造出DCG．

3 修改影响分析算法与实验

得到了DCG之后，就可以用DCG进行修改影响分析，通过后向切片来计算修改影响集合．

定义(k-类方法后向切片)令E是一个程序，给定切片准则m∈M.则BSlice(E)m,k是E关于m的k-类方法切片，若

所谓后向切片，是指BSlice (E)m中的元素与m是调用关系而不是被调用关系，修改影响分析的假设是，如果m′调用m，那么m的修改将影响到m′，而m′的修改并不影响m．k表示调用层次对修改的影响关系，越是靠近m的调用越可能被影响，设定k层之后的影响忽略不计．

BSlice(E)m,k的计算方法为标准的图可达算法.基于该算法，计算修改导致的影响集合．

输入：动态调用图 DCG，被修改的方法集合M, 调用层k

输出：修改影响集合affectedM

For eachmi∈Mdo{

affectedM=affectedM∪BSlice(E)m,k

}

我们以2个Java程序进行实验，并通过修改一些方法引入错误，其中设定k为4，需要重新测试的方法数量由程序开发人员和测试专家确定．

表3 实验结果对比

实验结果表明本文的方法可以极大地提高修改影响分析的效率.遗漏的需要重测的方法数量少，具有较高的实用价值．遗漏主要是因为k的设置(实验设置k=4).当k设置为6时，将包括所有需要重新测试的方法，但是修改影响的集合将急剧增长到124和202，影响了测试效率．

4 结论

软件回归测试指对修改之后的软件进行的测试.由于程序各元素之间的关系非常复杂，如果没有分析方法，程序修改之后一般需要对整个程序重新测试，导致软件开发和维护的效率低下．修改影响分析能使测试有目的的进行，提高测试效率，降低测试费用．现有的影响分析算法大都基于程序的静态分析技术，分析方法比较复杂且精度不高．针对静态分析存在的问题，本文提出采用动态分析技术构造Java程序的动态调用图，基于动态调用图，采用k-类方法后向切片计算修改影响集合．实验表明该方法简便易行，分析精度高，便于修改影响分析技术在大型Java程序测试中的实际运用．

参考文献：

[1] BEIZER B. Software testing techniques[M]. New York: Van Nostrand Reinhold, 1990.

[2] ROTHERMEL G, HARROLD M J. A safe, efficient regression test selection technique[J]. ACM Transactionson Software Engineering and Methodology, 1997,6(2): 173-210.

[3] LEUNG H K N, WHITE L. A study of integration testing and software regression at the integration level: proceeding of software maintenance, San Diego, CA, USA November 26-29, 1990[C]. San Diego:[s.n.],1990.

[4] LEUNG H K N, WHITE L. A firewall concept for both control-flow and data-flow in regression integration testing: proceeding of software maintenance, Orlando, FL USA, November 9-12,1992[C]. Orlando:[s.n.],1992.

[5] KUNG D, GAO J, HSIA P,etal. Class firewall, test order, and regression testing of object-oriented programs[J]. J Object-Oriented Program, 1995, 8(2): 51-65.

[6] JANG Y K, CHAE H S, KWON Y R,etal. Change impact analysis for a class hierarchy: proceeding of Asia pacific software engineering, Taibei, Taiwan, December 02-04,1998[C]. Taibei:[s.n.],1998.

[7] BARBARA G R, FRANK T. Change impact analysis for object-oriented programs: PASTE’01 proceeding of the 2001 ACM SIGPLAN-SIGSOFT workshop on program analysis for software tools and engineering, Snowbird, Utah, USA, June 18-19, 2001[C]. New York: ACM, 2001.

[8] CHIBA S. Load-time structural reflection in java[J]. Lecture Notes Comput Sci, 2000, 1850:313-336.

[9] DAHM M. Byte code engineering, java-informations-tage ,Düsseldorf, Germany, September 1999[C].Düsseldorf:[s.n.],1999.