（计算机软件与理论专业论文）java程序中异常流的测试与可视化研究.pdf

摘要 异常处理机制是提高软件健壮性，可靠性的重要手段之一。它将程序中的正常 控制代码和错误处理代码分离，为程序员开发高可靠的软件提供了条件。但它也 给程序中引入了新的控制流和数据流。由于这些控制流和数据流的特殊性，它们 很难在白盒测试中被覆盖。这使得异常处理代码中的错误很难被排除。本文研究 了j a v a 程序中异常流的测试和可视化问题。在静态分析部分，本文提出了计算程 序中未处理异常的递归模型，并给出了利用此递归模型提取程序中的异常流信息 的算法。同时在静态分析部分本文也给出可视化程序中异常流的相关算法。在动 态测试部分，本文提出了以错误植入思想为指导，利用j a v ad e b u g g e r 对程序中的 异常流进行测试的方法。相关实验表明本文提出的方法具有一定的可行性。 关键词：异常处理机制软件测试静态分析控制流图 a b s t r a c t e x c e p t i o nh a n d l i n gm e c h a n i s mi so n eo ft h em o s ti m p o r t a n tm e t h o d s f o ri m p r o v i n g t h er e l i a b i l i t ya n dr o b u s t n e s so fs o f t w a r e i ts e p a r a t e st h ee r r o rh a n d l i n gc o d ef r o mt h e n o r m a lc o d e ，w h i c hp r o v i d e sc o n d i t i o nf o r p r o g r a m m e rt od e v e l o pm o r e r o b u s t s o f t w a r e b u tt h ee x c e p t i o nh a n d l i n gm e c h a n i s ma l s oi n t r o d u c e st h en e wc o n t r o lf l o w s a n dt h en e wd a t af l o w si nt h ep r o g r a m b e c a u s et h ep a r t i c u l a r i t yo ft h ec o n t r o lf l o w s a n dt h ed a t af l o w s ，t h e ya r er a r e l yc o v e r e di nt h ew h i t e - b o xt e s t i n g ，w h i c hm a k e st h e e r r o ri nt h ee x c e p t i o nh a n d l i n gc o d eh a r d l ye x c l u d e t h i sp a p e rs t u d i e st h et e s t i n ga n d v i s u a l i z a t i o no ft h ee x c e p t i o n a lf l o wi nj a v ap r o g r a m s i ns t a t i ca n a l y s i ss e c t i o n ，t h e p a p e rp r e s e n t sar e c u r s i v em o d e lf o rc a l c u l a t i n gt h eu n h a n d l e de x c e p t i o ni n t h e p r o g r a m sa n dt h e np r o v i d e sa na l g o r i t h mf o re x t r a c t i n gt h ee x c e p t i o nf l o wi n f o r m a t i o n i nt h ep r o g r a m sb a s e do nt h em o d e l s i m u l t a n e o u s l y , i nt h es t a t i ca n a l y s i ss e c t i o n ，t h e p a p e ra l s op r o v i d e st h ea l g o r i t h m sf o rv i s u a l i z i n gt h ee x c e p t i o n a lf l o wi nt h ep r o g r a m s i nt h ed y n a m i ct e s t i n gs e c t i o n ，t h ep a p e rp r e s e n t sam e t h o df o rt e s t i n gt h ee x c e p t i o n f l o w , w h i c hm a k eu s eo fj a v ad e b u g g e ri nt h ei nt h eg u i d a n c eo ft h ei d e ao ff a u l t i n j e c t i o n r e l e v a n te x p e r i m e n t si n d i c a t et h a tt h e m e t h o dp r e s e n t e db yt h ep a p e ri s f e a s i b l e k e y w o r d ：e x c e p t i o nh a n d l i n gm e c h a n i s m ；s o f t w a r et e s t i n g ；s t a t i ca n a l y s i s ；c o n t r o l f l o wg r a p h 西安电子科技大学 学位论文独创性( 或创新性) 声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在导 师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注 和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果； 也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明 并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名：狮 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保留 送交论文的复印件，允许查阅和借阅论文：学校可以公布论文的全部或部分内容， 可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后结合 学位论文研究课题再攥写的文章一律署名单位为西安电子科技大学。 ( 保密的论文在解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 本人签名：霉罐屋 导师签名：互幺 日期兰堕主主 e t g q 逛：主：垡 第一章绪论 第一章绪论 1 1 引言 本文所涉及的课题来源于与测试程序中异常处理代码相关的论文。 异常处理机制是许多现代高级编程语言的重要组成部分，它为程序员开发高 健壮性的软件提供了途径。但是它也给程序员，程序分析人员，软件测试人员带 来了新的问题。 就j a v a 语言中的异常处理机制而言就有如下问题需要他们面对：如何安排程 序中异常的抛出点和捕获点才能和事实相符? 哪些异常应该在底层处理，哪些异 常应该在高层处理? 程序中还有未处理的异常吗? 现在程序里的异常处理流程是 预期的吗? 每个异常处理者的代码是否能正确处理它所捕获的异常? 程序中的异 常控制流会对整个程序的控制流有什么影响? 如何在构建含有异常控制流的程序 控制流图? 如何分析因异常处理而引入的额外的数据流? 如何对含有异常处理代 码的程序进行控制依赖分析和程序切片分析? 如何高效的测试j a v a 程序中的异 常处理代码? 上面有些问题已经被很好的解决了，而有些还没有。本文就解决程序中还有 未处理的异常吗? 现在程序里的异常处理流程是预期的吗? 如何高效的测试j a v a 程序中的异常处理代码? 这三个问题作了研究。 1 2 国内外研究现状 s i n h a 等1 1 ，2 ，3 】就如何在控制流图里加入异常分支的控制流作了研究，她们研究 的目的主要是为了使传统的程序分析技术如控制流分析，数据流分析和控制依赖 分析等能正确的运用在带有异常处理机制的语言中。具体工作如下：以j a v a 程序 为例提出了构建带有异常控制流的程序控制流图的算法和带有异常分支的控制依 赖图的算法。并就它们在程序分片，结构测试等方面的应用做了探讨。她们指的 异常控制流仅指由t h r o w 语句引发的异常流。 s i n h a 等1 4 ，5 】在1 9 9 9 年提出了测试异常处理结构的标准。具体工作如下：她们在 前面构建的控制流图的基础上，从数据流的角度提出了测试异常处理结构的两组 标准，并讨论了两组标准与传统的数据流测试标准的关系。最后就这些标准在单 元测试，集成测试的应用做了讨论，但没有开发相应的测试工具。 s i n h a 等【6 ，7 】在2 0 0 4 年就软件开发过程中的隐式控制流的开发，维护，测试做了 讨论，并开发了相关支持工具。其中隐式控制流主要指异常控制流和函数多态调 j a v a 程序中异常流的测试与可视化研究 用引发的控制流。她们工作的重心在如何有效的支持程序员开发正确有效的异常 控制流。具体工作如下：总结了程序员在写与异常处理有关的代码时容易犯的错 误。利用她们前面建立的程序控制流图对程序中异常控制流做了可视化，从而将 程序的异常控制流直观的展现给程序员。一个简单的示例如图11 所示。 叵巫叵亟亚二 图11s i n h a 关丁异常流可视化的工作 此外她们还提出了几条测试j a v a 程序异常处理代码的准则，并用传统的白盒测 试方法专门对几个程序的异常处理分支做了测试，但效果不太好。异常处理分支 覆盖率最高的为2 5 ，最低的只有4 。 r o b i n a r d 等 8 , 9 , 2 0 i 开发了一个工具j e x 用来帮助软件开发人员来决定程序中的异 常流。他们的出发点是：j a v a 语言没有说明程序员如何在软件开发过程中部署异常 处理代码。具体工作如下：将s c h a e 衙和b u n d y 提出的a d a 异常处理模型进行调 整，使之适应j a v i i 语言的异常处理模型。然后以此模型为基础利用j a v a 程序的抽象 语法树和数据流分析技术将源程序转换成一种特定格式的中间文件。进而利用中 间文件将程序中的异常信息可视化出来以帮助程序员开发异常处理代码。 j o 等i ”i 提出了分别构造程序中正常控制流图和异常控制流图的想法及其实 现。他们在程序分析过程中涉及到异常流时，才将异常流的控制流图与正常控制流 图舍在一起。他们指的异常控制流仅指由t h o w 语句引发的异常流。 f u 等 1 3 , 1 4 , 1 5 , l 6 , 1 7 1 主要是对服务器端j a v a 软件中的i o 异常流进行了分析和测试。 具体工作如下：通过静态分析将程序巾与i o 操作有关的异常流提取出来，然后以 错误植入思想为指导利用静态分析得出的异常流信息对软件中与i o 有关得异常流 进行测试。2 0 0 7 年【1 7 1 他们在前面工作的基础上对程序中异常流的可视化做了研 究。 j i a n g 等1 1 8 , 1 9 魄出了用错误植入的方法测试c + + 中异常处理代码的方法并开 第一章绪论 3 一 发了一个半自动工具。2 0 0 6 年他们将r o b i l l a r d 等提出的j a v a 异常处理模型调整后用 在了c + + 程序中，以分析c + + 程序中的异常处理涮眇j 。 l u 等【2 0 j 改进t s i n h a 等提出的构建程序控制流图的算法，并将它用到了c + + 程 序中。改进的地方主要是：将数组操作，数值运算等可能引发的异常流也考虑在 了程序控制流图里。此外，他们还讨论了两种动态测试异的策略：基于约束求解 的异常测试策略和统计结构性异常策略。 1 3 目前存在的问题 由上面的现状可知：关于程序中异常处理代码的分析和测试，国内外研究者 已经做了大量的工作。但还有如下不足： 在引发异常语句的覆盖方面：s i n h a ，j o 的工作只考虑了由t h r o w 语句引发的 异常。r o b i l l a r d 的工作虽然考虑了所有可以引发异常的语句但是他们在静态分析 时仅做了数据流分析。这导致最后得出的异常的引发点不准确。 在动态测试方面：仅有f u 系统的提出了程序中i o 异常流的测试方案。没有 学者系统的提出测试异常处理代码的完整方案。 异常处理流的可视化方面：s i n h a 仅做了由t h r o w 语句引发的异常流的可视化。 此外从图1 1 可以看出她们的工具更像一个d e m o ，因为图中的方法的名字不是现 实软件中的名字。r o b i l l a r d 也做了一部分异常流可视化的工作。但由于他没有对 程序做控制流分析导致可视化出来的异常流不准确。 1 4 本文的主要工作及内容安排 本文的主要工作包括两个方面：一提出了一个测试j a v a 程序中异常流的方 案，并对其可行性作了测试。二给出了可视化j a v a 程序中异常流的相关算法。 测试j a v a 程序中异常流的方案包括静态分析和动态测试两个步骤。静态分析 是基础，动态测试是目标。静态分析的主要目的是：( 1 ) 检测程序中的异常流是否 完整，指出程序中未处理的异常。( 2 ) 提取程序中的异常流信息为动态测试异常处 理代码做准备。动态测试的主要目的是以静态分析提供的异常流信息为指导对 c a t c h 子句中代码进行测试，以保证每个异常处理者在语义上的正确性。在具体实 现上，静态分析部分：在将程序中隐式异常抛出点显式化后，提出了一个计算程 序中未处理异常的递归模型。然后在此模型上来检测程序中未处理的异常和提取 程序中异常流的信息。动态测试部分：提出了以错误植入思想为指导，利用j a v a d e b u g g e r 对程序中的异常处理代码进行测试的方法。 对于j a v a 程序中异常流的可视化，由于时间的关系，这部分工作只完成了相 4 一 j a v a 程序中异常流的测试与可视化研究 关算法的设计和关键数据结构的定义。因此本文只探讨这些。在具体设计上，本 文是以程序的控制流图为基础来实现异常流的可视化的。程序控制流图是基于基 本块的，在j a v a 源码级实现的。它的基本块与传统的程序控制流图中的基本块不 同。当基本块中的语句不抛出异常时，它是单入单出的。当基本块中的语句抛出 异常时，它是单入多出的，它为自己抛出的每种类型的异常建立一个出口。 此外，本文所说的库函数调用语句特指与i 0 相关的库函数。本文所讨论方法的 测试范围定位在不使用第三方库直接在j d k 基础上开发的j a v a 软件。本文所使用的 源程序的抽象语法树是通过j d k 的t o o l s j a r 中相关接口获得的。 本文的基本框架如下： 第一章简要的介绍了问题的背景，国内外研究现状，目前存在的问题及本文 所做的工作。 第二章简要的介绍了j a v a 异常处理机制的相关知识，以进一步说明本文工作 的必要性。 第三章主要探讨了计算j a v a 程序中未处理异常的递归模型，异常流的提取算 法和异常流可视化的相关算法。 第四章主要探讨了测试j a v a 程序中异常流的指导思想，实现方法及具体步骤。 第五章给出了一个简单的实验来说明本文方法的可行性。 第二章j a v a 异常处理机制简介 第二章j a v a 异常处理机制简介 2 1j a v a 异常类及其继承结构 在j a v a 语言中，异常是用类t h r o w a b l e 的对象或其子类的对象表示的【2 1 盈j 。 类t h r o w a b l e 及其子类称为异常类。所有用户自定义异常类都必须派生自类 t h r o w b l e 及其子类。 在j d k 中已经存在了一些预定义的异常类，它们的组织结构如图2 1 所示【2 2 1 。 用户可以根据实际情况在继承树的适当地方定义自己的异常类。 图2 1j a v a 语言异常类的继承结构图 在图2 1 中，r u n t i m e e x c e p t i o n 类，e r r o r 类及它们的子类的对象被称为 u n c h e c k e de x c e p t i o n 。而类e x c e p t i o n 派生的异常类( 除类r u n t i m e e x c e p t i o n 外) 及其子类的对象被称为c h e c k e de x c e p t i o n 。它们的区别在于编译器遇到c h e c k e d e x c e p t i o n 时要检查程序员是否为它提供了处理代码，而遇到u n c h e c k e de x c e p t i o n 则不检查。 2 2 引发异常的原因 j a v a 语言中异常可以由下述原因引发【2 l j ： 1 表达式的计算违反了j a v a 语言的正常语义。如：一个整数被0 除。 2 加载或链接程序各部分时发生错误。 3 对某些资源的使用超出了限制。如：程序申请的内存空间超过限制。 4 t h r o w 语句的执行。 5 类t h r e a d 的成员函数s t o p 被调用。 6 一 j a v a 程序中异常流的测试与可视化研究 6 虚拟机内部发生错误。 其中由l ，2 ，3 ，4 引发的异常被称为同步异常，由5 ，6 引发的异常被称为 异步异常。由于异步异常具有不可预见性，所以本文的工作只涉及同步异常。 2 3j a v a 异常处理的模型 目前主要有三种异常处理模型：终止模型，恢复模型和重试模型。j a v a 语 言使用的是终止模型。即，引发了的异常被处理后，程序的控制流不再回到引发 异常的点，而是转移至u t r y 语句后的第一条语句。具体过程如下：当程序中的某点 引发异常后，虚拟机将为它寻找处理者。如果在本函数中找到则程序控制流转到 此处理者，处理完后控制流转至s j t r y 语句后的第一条语句。如果没找到，则控制流 则沿着函数调用栈到此函数的调用者里寻找异常的处理者。如果找到则控制流转 到相应的处理者，处理完成后控制流转到相应缸y 语句后的第一条语句。如果没有 则继续沿函数调用栈寻找。如果最终也没找到则会导致当前线程终止。 由此可见 异常处理机制会给程序中引入新的控制流。这些控制流有函数内部的也有函数之 间的。 2 4j a v a 异常处理的使用 在j a v a 语言中与异常处理相关的语句有：t h r o w 语句，衄语句和t h r o w s 子句 【2 1 1 。其中t r y 语句包括t d r 子句，c a t c h 块和f i n a l l y 子句。c a t c h 块由一系列的c a t c h 子句组成。 t h r o w 语句用来引发异常，它的格式为：t h r o we x p r e s s i o n ；其中e x p r e s s i o n 可 以是一个异常变量( e g ：t h r o we ) ，一个函数调用语句( e g ：t h r o wf u n c o ；f u n e 的返回值类型为异常类) ，也可以是一个新建异常类对象语句( e g ：t h r o wn e w e ( ) ) 。 t r y 子句用来指定被保护的代码。它其中的代码要么全部执行完毕，要么执行 到发生异常的那条语句为止。c a t c h 子句中存放的是与其对应的t r y 子句中的代码 发生异常后的处理代码。 当t 巧子句中代码发生异常后，虚拟机会从头到尾的检查t 巧子句后的每一个 c a t c h 子句，看异常的类型是否与c a t c h 子句中声明的类型相容。如果找到赋值相 容的c a t c h 子句，则相应c a t c h 子句中的语句块就会被执行。其它的c t a c h 子句将 不会被执行。这就要求子类的c a t c h 语句一定要放在基类的c a t c h 语句之前。此外 需注意的一点是c a t c h 子句中的语句块也可以抛出异常。 f i n a l l y 子句中的语句块不管仃y 子句中是否发生异常都会得到执行。因此它常 第二章j a v a 异常处理机制简介 被用来做资源回收( 如关闭文件流等) 。 t h r o w s 子句用来定义函数可能抛出的异常类型。这些异常一般是c h e c k e d e x c e p t i o n 。使用t h r o w s 子句必须注意的一点是：当覆盖一个通过继承得到的方法 或者实现一个通过继承得到的抽象方法时，覆盖方法的t h r o w s 子旬必须和被继承 方法的t h r o w s 子旬相互兼容。 2 5 小结 7 一 由上述可知，( 1 ) 虚拟机在为抛出的异常寻找处理者时，是通过比较它们的类 型是否相同，或查看被抛出的异常的类型是否是捕获者类型的子类来实现的。至 于找到的捕获者是否能正确处理其捕获的异常则是由程序员保证的。( 2 ) 程序中的 异常流既可以是函数内的也可以是函数间的。如何安排它们是由程序员决定的。 ( 3 ) 编译器只检查程序中抛出的c h e c k e d 类型的异常是否有处理者。至于检查程序 中抛出的u n c h e c k e d 类型的异常是否有处理者的任务则留给了程序员。因此程序 员在j a v a 程序中使用异常处理机制时需要解决许多问题。但程序员是很容易犯错 误的。本文的目的就是为了帮助程序员检测异常处理代码中的错误和更好的设计 异常流。 第三章异常处代码的静态分析 第三章异常处理代码的静态分析 3 1 基本概念 9 一 为了后面介绍的方便，给出以下基本概念。 定义3 1 ：基本块：一段只能从它的第一条指令进入，并从它的最后一条指令 离开的最长的指令序列。基本块的第一条指令也称为首领1 2 5 j 。 从上述定义很容易看出基本块的第一条指令可以是【2 4 】：( 1 ) 例程的入口点，( 2 ) 分支的目标，或( 3 ) 直接紧跟在分支指令或返回指令之后的指令。 定义3 2 ：扩展基本块：从一个首领开始的最长的指令序列，在这个指令序列 中，除了第一个结点之外不含其他汇合结点【2 5 1 。其中汇合结点是指有多个前驱的 结点。 定义3 3 ：控制流图：g = ( n ，e ，s ，e ，v ) 其中n 是一个结点集，而e 则 是一个边集，s 和e 分别表示该图的唯一的出口和入口，每一个结点n e n 都是程 序中的一个状态，比如条件语句或者赋值语句，两个结点之间存在一条边e = ( n i ， n j ) e ，当且仅当它们之间存在一个从结点n i 到结点n j 的控制迁移。 在3 5 节我们将以扩展的基本块为结点构建j a v a 程序的控制流图。 定义3 4 ：一个变量v 的定义指的是控制流图上修改该变量值的结点，例如该 变量的赋值语句或者输入语句。 定义3 5 ：一个变量v 的使用指的是控制流图上应用该变量的结点，例如使用 该变量的条件语句或该变量在赋值号右边的赋值语句。 就异常处理代码而言，语句t h r o wn e we ( ) ，其中e 表示一个异常类，定义 了一个异常变量。而c a t c h ( ee ) 使用一个异常变量。为了更好的刻画异常变量 的这种定义使用关系以及后续讨论的方便我们给出以下定义： 定义3 6 ：设程序中引发的任意一个异常为e ，用e 来表示e 的引发点，c 来 表示e 的捕获点，将e 和c 之间的关系( e ，c ) 称为关于e 的e cl i n k 。 定义3 7 ：设程序中引发的任意一个异常为e ，用s 来表示引发e 的条件，e 来表示e 的引发点，c 来表示e 的捕获点，将s ，e 和c 之间的关系( s ，e ，c ) 称为关 于e 的c o n d i t i o n a le cl i n k 。 在3 4 节我们将给出提取j a v a 程序中c o n d i t i o n a le cl i n k 的算法。 3 2 计算程序中未处理异常的模型 程序中未捕获的异常就是那些有引发点但没有捕获点的异常。在j a v 耀序中异 1 0 j a v a 程序中异常流的测试与可视化研究 常的捕获点是c a t c h 子句。而异常的引发点直观上讲则可能是下面三种语句的一种： ( 1 ) 在程序运行过程中可能违反j a v a 语言的语意规则的语句，( 2 ) t h r o w 语句，( 3 ) 可能 引发异常的函数调用语句。 满足( 1 ) 的语句也称为异常的隐式引发点，因为它们不是用t h r o w 语句来引发异 常的。为了程序员更好的检查由满足( 1 ) 的语句是否会引发异常和建模的方便，我 们对这些隐式的异常引发点作了显式化。所谓显式化指在满足( 1 ) 的语句f j 植入代 码： i f ( c o n d i t i o n ) t h r o wn e we x c e p t i o n ( ) ； 其中c o n d i t i o n 和e x c e p t i o n 都是占位符，它们是j a v a 语言规范规定满足( 1 ) 的语句 抛出异常的条件和异常的类型。这样做可行的原因是j a v a 语言规范将哪些语句会在 什么情况下抛出什么异常作了很明确的规定。j a v a 语言中常见的隐式异常及其引发 条件如表3 1 所示： 表3 1j a v a 语言中常见的隐式异常及其引发条件 其中a ，b n l c 是可以进行除和取余运算的变量，d 是数组类型，e ，堤引用类型。 个简单的示例如下： i n tr e s u l t ，l e f t ，f i g h t ； r e s u l t = l e f t r i g h t ； 上面的代码片断中语句r e s u l t = l e f t r i g h t ；会n y , j n r i g h t 取值为0 而引发异常。在它的 前面植入上述形式的代码后的程序片断如下： i n tr e s u l t ，l e f t ，r i g h t ； 第三章异常处代码的静态分析 i f ( r i g h t = = o ) t h r o wn e w a r i t h m e t i c e x c e p t i o n ( ) ； r e s u l t = l e f t r i g h t ； 下面我们给出将j a v a 程序中隐式异常抛出点显式化的算法： 算法3 1 ：将j a v a 程序中隐式异常抛出点显式化的算法 输入：j a v a 源程序 输出：植入相关代码后的程序 1 获得j a v a 源程序的抽象语法树。 2 遍历抽象语法树查找可能引发隐式异常的语句，并将它们所在结点记录下来。 3 对记录下来的每个结点查看其父结点是否是i f 语句。如果不是对其作标记。如果 是且它的条件中没有排除当前结点发生异常的可能性则对其作标记。 4 对标记下来的每个结点根据其类型在己建库中查找其抛出异常的条件。 5 根据标记的结点在源程序中的位置确定植入代码的位置。 6 在将当前抽象语法树转换成源代码的过程中植入所需的代码。 其中的库是用x m l 文件表示的。其格式如下： i f ( s i g n - - = o ) 拌t h r o wn e wa r i t h m e t i c e x c e p t i o n o ； 其中的s i g n 是标记变量，在植入代码前需将它替换成实际程序中的变量。荐号表示 换行符。 经过前面的处理后，程序中可以引发异常的点就可以由t h r o w 语句的集合和会 引发异常的函数调用语句的集合来表示了。函数调用语句分为用户自定义函数调 用语句和库函数调用语句。用户自定义函数抛出的异常本质上还是由他体内的 t h r o w 语句和函数调用语句抛出的，而被调用的用户自定义函数抛出的异常我们又 可以将其归结为它体内的t h r o w 语句和函数调用语句抛出的。因此计算程序中未处 理异常的模型可递归的定义为： r a i s e ( f ) = t h r o w ( f ) uc a h ( f ) - c a t c h ( f ) ( 3 一1 ) c a l l ( f ) = uraise(f)(3-2) ，c 其中t h r o w ( f ) 表示f 中通过t h r o w 语句和可能引发异常的库函数抛出的异常的集合。 c a l l ( f ) 表示f 中调用的用户自定义函数抛出的异常的集合。c 表示f 中调用的用户自 j a v a 程序中异常流的测试与可视化研究 定义函数的集合。c a t c h ( f ) 表示f 中捕获的所有异常的集合。r a i s e ( f ) 表示f 中未处 理的异常的集合。 在3 4 节我们将用上述递归模型在计算程序中未处理异常的同时提取程序中的 c o n d i t i o n a le cl i n k 。 3 3f a c t o r e dc o n t r o lf l o wg r a p h 简介 f a c t o r e dc o n t r o lf l o wg r a p h ( f c f g ) 是c h o i 掣2 6 】在中间代码层次上优化异 常处理机制时提出的。j a v a 语言中许多语句都可能引发u n c h e c k e d 异常。这使的 基本块包含的指令非常少，进而导致控制流图中基本块非常多且小，不利于数据 流分析。f c f g 非常好的解决了这一问题。为了解释清楚它的优点，先给出下面 的示例，这个示例来自c h o i 等的文章 2 6 】。例3 1 表示一段j a v a 源代码。例3 2 表示例3 1 所示源代码翻译成的中间代码。图3 1 表示例3 2 所示中间代码的传统 的控制流图。图3 2 表示例3 2 所示中间代码的f a c t o r e dc o n t r o lf l o wg r a p h 。 第三章异常处代码的静态分析 图3 1例3 2 所示中间代码的控制流图 1 3 图3 2 例3 2 所示中间代码的f a c t o r e dc o n t r o lf l o wg r a p h 比较上面的图3 1 和图3 2 - i 矢h ，f a c t o r e dc o n t r o lf l o wg r a p h 无论在基本块数 1 4 j a v a 程序中异常流的测试与可视化研究 目上还是在边的数目上都比传统的控制流图少且更利于数据流分析。 f a c t o r e dc o n t r o lf l o wg r a p h 与传统的控制流图的不同点在于：每个基本块 都是扩展的基本块。在连接边中有些边被称为f a c t o r e de d g e 。f a c t o r e de d g e 是连接抛出异常e 的基本块和捕获异常e 的基本块的边。由基本块抛出的每一种 异常都对应一条f a c t o r e de d g e 。由基本块中不同语句抛出的相同异常仅由一条 f a c t o r e de g d e 来表示。此处的相同是严格的，不考虑异常类继承的情况。 在3 5 节我们将把上述f c f g 的思想用到源码一级来构建j a v a 程序的f c f g 。 3 4 j a v a 程序中c o n d i t i o n a le cl i n k 的提取 提取出程序中c o n d i t i o n a le cl i n k 不可避免的会涉及到类型分析和异常捕获者 的查找。这二者与类继承图和函数调用信息密切相关。因此本节将先讨论类继承 图的构建算法，类型分析的算法，收集函数调用信息的构建算法和查找函数定义 的算法。然后在讨论提取程序中c o n d i t i o n a le - cl i n k 的算法。 3 4 1 类继承图的构建算法 由于j a v a 语言不支持多重继承，所以j a v a 程序的类继承图可以由一棵树来表示 ( 不考虑类可以继承多个接口的情况) 。但是这棵树中各结点的孩子结点的数目很 不相同，有的有好几个孩子结点，有的可能一个都没有。因此我们用二叉树来表 示类继承图( 树) 。一个直观的示例如下图所示： c l a s so b je c c p u b l i co b j e c tc ) l l ； c l a s st h r o e a b l ee x c e n d so b j e c t p u b l i ct h r o w a b l ei ii l ； c l a s sr u n t i m e e x c e p t l o ne x t e n d se x c e p t i o n ( p u b l i cr u n t l m e e x c e p t i o nc i ； c l a s si o e x c e p c l o ne x t e n d se x c e p t i o n p u b l i ci o e x c e p c i o nci ) ； c l a s si n t e g e re x t e n d so b je e l p u b l i co b j e c c ii ) l ； c l a s se x c e p t i o ne x t e n d st h r o v a b l e p u b l i ce x c e p t i o nci ) ； c l a s sn o s u c h y l e l d e x c e p t l o ne x t e n d se x c e p t i o n p u b l i cn o s u c h f i e l d e x c e p t i o nc ) ， l ； 图3 3 类继承示意代码 第三章异常处代码的静态分析 ( a )( b ) 图3 4 类继承图：( a ) 类继承图的树表示，( b ) 类继承图的二叉树表示 这样构造类继承图的问题本质上就变成了构造一棵二叉树的问题。构造类继 承图的基本思路如下：首先通过j a v a 程序的抽象语法树，获得类继承对a b ( 表 示类a 继承自类b ) 或单个类c ( 表示c 继承自类o b j e c t ) 。然后根据a _ b ，c ， d e ，e 叶b 等揭示的类问的继承关系将它们构建到一棵二叉树上，其中a ，b ，c ， d ，e 为程序中的类的标识。 本文采取的是逐步构造二叉树的方法。每一次处理一个继承对或单个的类。 对于继承对a _ b ( 假设a ，b 都是程序中的类的标识，a 继承自b ) 来说，可能 的情况是：a ，b 都在已构造的部分二叉树中。a 在已构造的部分二叉树中， 而b 不在。a 不在已构造的部分二叉树中，而b 在。a ，b 都不在已构造的 部分二叉树中。对于单个的类c ( 假设c 是程序中的类) 来说，可能的情况是： c 在已构造的部分二叉树中。c 不在已构造的部分二叉树中。构造j a v a 程序 类继承图的核心算法如下： 算法3 2 ：构造类继承图的算法 输入：j a v a 源程序 输出：j a v a 程序的类继承图 初始条件：r o o t = n u l l ；r o o t 表示树的根结点。 1 通过程序抽象语法树获得类继承对及单个类的标识，并将它们依次存到一个数 据结构s 中。 2 如果s 非空，从其中取一个元素e ，判断e 是否是一个类继承对，如果是转3 ， 如果不是转8 。 3 检测e 中的两个类标识是否在己构造的部分二叉树中，如果两个都在转4 ，如果 基类在子类不在转5 ，如果子类在基类不在转6 ，如果两个都不在转7 。用变量b a s e 表示基类结点，用变量s u b 表示子类结点。 j a v a 程序中异常流的测试与可视化研究 4 6 s u b p a r e n t r i g h t = s u b r i g h t ；两个类标识都在己构造的部分二叉树中 i f f s u b r i g h t ! = n u l l ) s u b r i g h t p a r e n t 2 s u b p a r e n t ； p 2 b a s e 1 e f t ； i f ( p ! - - n u l l ) w h i l e ( p 一 n e x t1 2 n u l l ) p = p - n e x t ； ) p - r i g h t = s u b ； s u b p a r e n t = p ； ) e l s e b a s e 1 e f t = s u b ； s u b p a r e n t = b a s e ； ) g o t o1 0 ； p = b a s e 1 e f t ；5 类在已构造的部分- - y 树中而子类不在 i f ( p ! = n u l l ) w h i l e ( p 一 n e x t ! - - n u l l ) p = p 一 n e x t ； ) p 一 r i g h t _ s u b ； s u b - p a r e n t 2 p ； e l s e b a s e 1 e f t = s u b ； s u b p a r e n t = b a s e ； g o t o1 0 ； p = r o o t r i g h t ；子类在已构造的部分- - y 树中而基类不在 i f ( p 1 2 n u l l ) w h i l e ( p 一 n e x t ! = n u l l ) p = p - n e x t ； ) p 一 n e x t = b a s e ； 第三章异常处代码的静态分析旦 b a s e p a r e n t = p ； ) e l s e r o o t r i g h t = b a s e ； b a s e p a r e n t = r o o t ； ) p = s u b p a r e n t ； p f i g h t = s u b r i g h t ； i f ( s u b r i g h t ! = n u l l ) s u b r i g h t p a r e n t = p ； b a s e 1 e f t = s u b ； s u b p a r e n t = b a s e ； g o t o1 0 ； i f ( r o o t = n u l l ) 子类和基类都不在已构造的部分二叉树中 r o o t = b a s e ； r o o t 1 e f t = s u b ； s u b p a r e n t = r o o t ； ) e l s e p = r o o t r i g h t ； i f ( p ! - - n u l l ) w h i l e ( p n e x t ! = n u l l ) p - - p 。 n e x t ； p - n e x t = b a s e ； b a s e p a r e n t - p ； b a s e 1 e f t = s u b ； s u b p a r e n t = b a s e ； ) e l s e r o o t r i 曲t = b a s e ； b a s e p a r e n t = r o o t ； b a s e 1 e f t = s u b ； s u b p a r e n t = b a s e ； ) 1 8 j a v a 程序中异常流的测试与可视化研究 ) g o t olo ： 8 检测e 中的标识是否在己构造的二叉树中。如果不在转9 。如果在转l o 。用变 量c u r 来表示当前结点。 9 i f ( r o o t = n u l l ) 当前类不在继承树中 r o o t = c u r ； e l s e p = r o o t r i g h t ； i f ( p ! = n u l l ) w h i l e ( p 一 r i g h t ! = n u l l ) p = p - n e x t ； ) p - n e x t = c u r ； c u r - p a r e n t = p ； ， e l s e r o o t r i g h t = c u r ； c u r p a r e n t = r o o t ； ) ， g o t o10 ； 1 0 从s 中删除e ；g o t o2 ； 其中树结点的数据结构如下： c l a s st r e e n o d e s t r i n gt y p e n a m e ；l l 电节点代表的类名，s t r i n g 代表字符串类型 t r e e n o d ep a r e n t ；指向结点的父结点 t r e e n o d el e f t ；指向结点的左孩子 t r e e n o d er i g h t ；指向结点的右孩子 ) 注：关于j d k 中预定义的异常类之间的关系，我们预先将它们