（计算机系统结构专业论文）基于切片技术的软件理解辅助系统设计与实现.pdf

大连理工大学硕士学位论文 摘要 随着计算机技术的发展和软件系统规模的扩大，现有软件系统往往积累了大量的行 业知识，包括系统需求、业务规则和设计决策等，因此对软件系统的维护显得越来越重 要。而对原有系统的理解是对软件进行维护的前提，只有正确理解了原有系统的功能， 才能高效率地对原有系统进行维护和改进。因此，软件理解在软件维护过程中发挥着重 要的作用。 程序切片技术是m a r kw e i s e r 提出的一种程序分析的技术，它通过计算与某个用户 感兴趣的变量相关的语句集来分解程序。程序切片技术的提出。极大地丰富了程序分析 和程序理解的理论基础。在软件工程的各个领域如程序分析、理解、测试、调试、度量 等，程序切片技术都得到了广泛的应用。本文设计的系统以程序切片技术为基础，采用 的是w e i s e r 提出的数据流迭代算法。 由于c 语言编制程序中指针的广泛使用，如果对指针作保守估计，将极大损害数据 流分析结果的精确度。本文考察了指针分析的表示法、指针问题的复杂度、以及指针问 题的分类，在介绍了一种上下文敏感的过程间指针分析算法的基础上，针对函数指针间 接进行的函数调用，本文利用a t k i n s o n 函数类型签名过滤的思想，给出了一种提高函数 指针指向精确度的方案。 本文最后给出了系统的设计与实现，在程序分析前端的预处理器中，对系统头文件 的包含作了过滤处理，这样就使得程序经过词法分析、语法分析之后，在中间代码产生 器中产生的中间代码的数目大大减少。在分析后端实现了程序切片器、交叉引用器、模 块内聚度量、文件及函数依赖显示器等。实现中用到的技术有l e x 、y a c c 、d o m 4 j 、 j a v a s w i n g 、j f r e e c h a r t 等。由于中间代码采用了x m l 表示存储，在此基础上开发新的 后端分析工具是很容易的。本文中的系统对于软件人员关注变量使用，方便理解程序提 供了帮助。 关键词：软件理解；程序切片；指向分析；模块内聚度量 大连理工大学硕士学位论文 t h ed e s i g na n di m p l e m e n t a t i o no fs o f t w a r ec o m p r e h e n s i o na s s i s t a n c e s y s t e mb a s e do np r o g r a ms l i c i n g a b s t r a c t w i t ht h ed e v e l o p m e n to fc o m p u t e rt e c h n o l o g ye n dt h ei n c r e m e n to fs i z eo fs o f t w a r e s y s t e m ，t h es o f t w a r et o d a y h a sa g g r e g a t e dal o to fk n o w l e d g eo fs p e c i f i cf i e l d ，i n c l u d i n gt h e s y s t e mr e q u i r e m e n t s ，d e s i g na n dr u l e s s ot h em a i n t e n a n c eo fs o f t w a r eb e c o m e sm o r ea n d m o r ei m p o r t a n t b e f o r eo n em a i n t a i n i n gt h es y s t e m ，o n em u s tu n d e r s t a n di tt h o r o u g h l y u n l e s sg e t saf u l lc o m p r e h e n s i o no f o l ds y s t e m ，o n ec a n tm a i n t a i nt h es y s t e me f f i c i e n t l ya n d i m p r o v et h eo l ds y s t e m i no n ew o r d , s o f t w a r ec o m p r e h e n s i o np l a y sa ni m p o r t a n tr o l ei nt h e f f r o c so f s o t t w a r em a i n t e n a n c e p r o g r a ms l i c i n gi sat e c h n i q u ef o rp r o g r a ma n a l y s i sp r o p o s e db ym a r kw d s e r , w h i c h a n a l y z et h es y s t e mb yc o m p u t i n gar e l a t e ds t a t e m e n ts e to f p a r t i c u l a rv a r i a b l eo f p r o g r a m ，a n d t h es e ti sc a l l e dp r o g r a ms l i c e t h et h e o r yb a s e so f b o t hs o f t w a r ea n a l y s i sa n dc o m p r e h e n s i o n a r er i c h e n e db yt h ee m e r g e n c eo fp r o g r a ms l i c i n g p r o g r a ms l i c i n gi sw i d e l yu s e di ne v e r y f i e l do fs o f t w a r ee n g t n e e r i n gs u c ha ss o l t w a r ed e b u g g i n g t e s t i n ga n dm e t r i c sa n ds oo n 1 1 1 e s y s t e md e s i g n e da n di m p l e m e n t e di nt h i sp a p e ri sb a s e do nt h ep r o g r a ms l i c i n gt e c h n i q u e ，a n d t h i sp a p e ra d o p t st h ed a m f l o wi t e r a t i o na l g o r i t h mw h i c hi sp r o p o s e db ym a r kw e i s e r d u et ow i d e l yu s eo fp o i n t e r si nt h ep r o g r a mw r i t t e nb yc ，i fac o n s e r v a t i v ee s t i m a t ei s t a k e n , t h ee x a c t n e s s c a l lb e g r e a t l y h a r m e d t 1 1 i sp a p e rg i v e sad e s c r i p t i o no ft h e r e p r e s e n t a t i o no f p o i n t s - t oa n a l y s i s ，t h ec o m p l e x i t yo f t h ep r o b l e ma n dt h ec l a s s i f i c a t i o no f i t a f t e ra ni n t r o d u c t i o no fa ni n t e r - p r o c e d u r a la n dc o n t e x t s e n s i t i v ep o i n t e ra n a l y s i sa l g o r i t h m ， a l li m p r o v e m e n to f a n a l y s i so f f u n c t i o nc a l l sv i af u n c t i o np o i n t e r si sg i v e ni nt h i sp a p e r 1 1 l ed e s i g no fs y s t e mi sg i v e ni nt h i sp a p e r i nt h ep r e p r o c e s s o ro ft h ef r o n t e n do f s y s t e m ，t h ei n c l u s i o no fs y s t e mh e a df i l e sa r ed i s c a r d e d a f t e rt h ep r o c e s so fl e x i c a la n a l y z e r a n dp a r s e r , t h ei n t e r m e d i a t ec o d e sp r o d u c e db yt h ei n t e r m e d i a t ec o d eg e n e r a t o ra r eg r e a t l y d e c r e a s e d a tt h eb a c k e n do f s y s t e m ，ap r o g r a ms l i c e r , ag r o s s r e f e r e n c e r , am o d u l a rc o h e s i o n m e t r i c sa n a l y z e ra n dad 印e n d e n c ed i s p l a y e ro f f i l e sa n df u n c t i o n sa r eg i v e n t e c h n i q u e ss u c h a sl e x ，y a c c ，d o m 4 j ，j a v as w i n ga n ds oo na r eu s e di nt h ei m p l e m e n t a t i o n d u et ot h e i n t e r m e d i a t ec o d e sa r er e p r e s e n t e db yx m lf i l e s ，i ti sc o n v e n i e n tt od e v e l o pn e wb a c k e n d t o o l s t h es y s t e mp r o v i d e db yt h i sp a p e rc a nh e l pp e o p l ef o c u so nt h ev a r i a b l e sw h i c ht h c y a r ei n t e r e s t e di na n dg i v eah a n dt ot h e mf o rt h eu n d e r s t a n d i n go f p r o g r a m s k e y w o r d s ：s o f t w a r e c o m p r e h e n s i o n ；p r o g r a m a n a l y s i s ；p o i n t s t o a n a l y s i s ；m o d u l a r c o h e - s i o nm e t r i c s 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：舌1 琅；告日期：兰：! ：! ! ! ! ! 人连理：i 大学硕十研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位 论文版权使用规定”，同意大连理工大学保留并向国家有关部门或机构送交 学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连理工 大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也可 采用影印、缩印或扫描等复制手段保存和汇编学位论文。 作者签名： 孑，1 ；共；告 导师虢圣蚓垫 大连理工大学硕士学位论文 1 绪论 随着计算机技术的飞速发展，计算机应用的领域不断扩大，人们对计算机软件产品 的功能、质量、开发成本和时间提出了越来越高的要求。计算机软件系统在各个领域经 过了几十年应用的积累，规模越来越大，功能越来越复杂，使得更多大型软件的开发必 须考虑原先己经运行了多年的系统，包括系统的需求、设计决策、业务逻辑、业务规则、 历史数据等等。这些系统称为遗留系统( l e g a c ys y s t e m ) ，遗留系统是一种巨大的、长期 的投资，因此充分利用这些有用的资产对遗留系统改造和新系统的开发显得尤为重要 在利用遗留系统前必须充分地理解系统，而在很多情况下，由于设计文档的缺失或 者由于系统演变导致的文档和系统不一致，遗留系统唯一可靠的信息只是程序源代码， 其它很多信息必须由此导出。 1 1 什么是程序理解 分析和理解程序是维护工作的第一步，能否准确、迅速、全面地理解程序是决定维 护工作成败的关键【l 】。软件理解就是通过一定的设施和方法来弄清一个程序是“做什么” 以及“如何做” 2 1 。 c h i k o f s k y 和c r o s s 把程序理解定义为：通过分析一个目标系统、识别系统的各个组 件以及它们之间的关系，生成另外一种形式或者更高抽象层次的系统表示的过程。通常， 这意味着通过分析程序的源代码为系统建立一个再工程的框架设计。为了便于理解，再 工程的设计必须要建立在己有的软件设计基础之上。 1 2 程序理解的任务 程序理解的任务 3 1 就是要揭示程序的功能与实现机制，即理解系统的外部行为和内 部构造，其具体任务可分解如下： ( 1 ) 通过检查单个的程序设计结构，把程序表示成抽象语法树、符号表或普通源文 本，这其中包括手工代码阅读、程序分析、静态分析、动态分析等几个过程。 ( 2 ) 尽量做到程序隐含信息的显式表示及程序内部关系的可视化。如控制流和数据 流分析，各种程序视图的构造等。 ( 3 ) 从源代码中提取信息，并存放在通用的数据库中，然后通过对数据库进行查询 来获取程序的有关信息。 ( 4 ) 检查程序构造过程中的结构关系，明确表示程序组成部分之间的依赖关系。 ( 5 ) 识别程序的高层概念，如标准算法、数据结构、语法及语义匹配等。在进行程 基于切片技术的软件理解辅助系统设计与实现 序理解时，如果程序具有良好的结构，那么理解任务会变得相对容易一些，但是如果程 序不具备良好的结构，程序员就必须对程序源代码进行更仔细的分析，了解设计者是如 何用程序解决各种问题的。因此程序设计人员在程序设计阶段应该对程序所要解决的问 题进行说明，这样做可以使设计者的想法对他人保持开放，在以后解决软件运行和维护 过程中出现的意外问题时，其他的程序理解者或程序维护员可以更容易地掌握设计者的 思想。但是并非所有的设计者在编码前都会对要解决的问题进行详尽的分析，并对它们 进行注释，这种注释说明不够完整、不够详细时，对程序的分析就会很复杂。 1 3 软件理解方法 李必信等人在文献 4 】指出：软件理解方法有工程法、程序切片法、格局识别法、概 念赋值和概念分析法、模式识别法、程序分析法、智能理解法。下面对工程法、程序切 片法、程序分析法等作简单介绍 ( 1 ) 工程法 工程法就是利用工程的办法来进行程序理解的方法，它包括正向工程、逆向工程、 再结构、再用工程以及软件再工程等。下面分别作简要介绍。 正向工程和逆向工程 传统的软件处理过程就是把一个系统高层抽象和独立于设计的逻辑实现转变成物 理实现的过程，这就是正向工程过程。逆向工程被认为是不改变主题系统的活动，它只 是一种检查过程，而不是变换过程。如图1 1 所示，通过对人工制品的确认、人工制品 之间关系的发现及抽象分层来方便软件理解过程。 正向工程 逆向工程 图1 1 正向t 程与逆向工程 f i g 1 1e n g i n e e r i n ga n dn n me a g i n c c r i a g 一般认为，逆向工程就是分析主题系统，确定它的当前成分和成分之间的依赖，以 及提取并创建系统抽象和设计信息的过程。李必信等人认为，逆向工程是一个3 步过程， 即：一、模型建( m o d e lc r e a t i n g ) ：使用概念模型化技术构造应用于特定领域的模型； 二、提取( e x t r a c t i o n ) ：使用合适的提取机制从主题系统聚集原始数据；三、抽象 2 大连理工大学硕士学位论文 ( a b s t r a c t i o n ) ：创建便于软件理解的抽象，并允许结果信息的开发。具体来说有以下一 些方法：抽象和组合、设计恢复和概念赋值、反工程、概括资源流和软件结构、变更和 影响分析、可维护性分析、迁移分析、事务分析等等。 再构造 再构造( r e s t r u c t u r i n g ) 是在同一个相关的抽象级别上把一种表示转换成另一种表 示，而保持主题系统的外部行为不变的过程。 重用工程 重用工程( r e u s ee n g i n e e r i n g ) 是确认软件系统中可再用的部分以及改变一软件系统 使之更加可再用的过程。相关工作有：对象恢复、抽象数据类型( j 缸 t ) 确认、数据精化、 成分确认、建立可再用成分库 软件再工程 软件再工程( s o f t w a r er e e n g i n e e r i n g ) 是检查和更新改造一个主题系统，并以一种新 的形式重建的过程。相关工作有：逆向和正向工程、抽象和实现、再用工程、数据再工 程、形式转换、再模块化等。 ( 2 ) 程序切片法 程序切片( p r o g r a ms l i c i n g ) 是根据控制流和数据流分析而提出的一种程序分析技 术。在过去2 0 多年中，程序切片技术取得巨大发展p 】。下面列举了几种具有代表性的切 片方法。 语句切片 这种传统的程序切片技术是一种条件切片，它是根据程序的顺序、循环和选择结构 进行程序切片的。程序员可以用构成语句的程序切片来识别程序的错误，同时也用来理 解程序的行为。该类程序切片包括静态切片和动态切片两种，它们的不同之处是：定义 静态切片时需考虑程序的所有执行路径( 可靠的或不可靠的) ；而动态切片只考虑从一个 输入到程序的特定的执行路径。 无定型程序切片 无定型程序切片是由m a r kh a r m a n 和s e b a s t i a nd a n i c i c 于1 9 9 7 年提出的一种程序 切片方法【6 】。与传统程序切片相比，无定型切片不仅在保存一个程序语义投影的同时简 化了程序，还可以使用任何简化的转换。而这些转换保留了这个语义映射，因此，在传 统切片方法的基础上增强了简化能力并可用来帮助软件理解。 过程问和过程内切片 根据过程间或过程内分析、数据流分析、需求分析来切片程序，这类切片方法可计 算其它方法不能识别的过程间或过程内的控制相关，并且可重用程序切片的信息，以便 基于切片技术的软件理解辅助系统设计与实现 更好地改进程序的效率。 面向对象切片 近来程序切片技术已被应用到面向对象领域，1 9 9 6 年l o r e nl a r s o n 和m a r r yj e a n h a r r o l d 把切片技术应用与面向对象的系统相关图和过程相关图中，使得对面向对象程 序( 特别是c + + 程序) 的调试、代码理解、程序测试、逆向工程和度量分析变得相对容易 的多。 ( 3 ) 程序分析法 程序分析包括静态程序分析和动态程序分析两种：静态程序分析( s t a t i cp r o g r a m a n a l y s i s ) 无须执行程序，而只是根据一些模型推断程序本质结果的过程。它包括词法以 及语法分析、类型检查和推理、控制和数据流分析、结构化分析、交叉引用、复杂度度 量等过程；动态程序分析( d y n a m i cp r o g r a ma n a l y s i s ) 是在一个发现系统运行时依赖的过 程。它包括对象实例依赖、动态链接和多态性、方法调用图、登记和回调函数、路径覆 盖测试、内存管理、功能瓶颈、分支、并发等。 1 。4 程序理解研究现状 理解一个软件系统的程序通常是一个比较困难的过程，因为其中信息容易丢失、前 后不一致和冗余爆炸。源程序往往成为程序理解过程中唯一可以信赖的事物。事实证明， 许多软件可视化工具和浏览工具能够提供对程序理解有帮助的信息。具体地说，软件可 视化工具能够采用图形和文本方式浏览、分析和表述软件的信息，这些都在某种程度上 加强了对软件的理解。 ( 1 ) 国内研究现状 目前国内在程序理解系统研究方面主要的成果有北大青鸟工程的青鸟程序理解系 统 b p a s ( j a d eb i r dp r o g r a ma n a l y s i ss y s t e m ) 【”、梅宏等人提出的s m a l l t a l k 程序理解辅助 系统b d c o m s t ”、南京大学的刘小东和李必信等提出的针对c 斗+ ，a v a 语言的程序分析 系统o o p s e n 等。下面重点介绍一下j b p a s 。 如图1 ，2 所示，青鸟程序理解系统j b p a s 是一个针对c + + 语言的程序理解系统，由 一个c + + 分析器前端和一组分析工具组成。分析器前端采用e e r ( e n h a n c e de n t i t y r e l a t i o n s h i p ) 为c + + 程序建立概念模型，该模型较为全面，以适合多种程序信息需求。通 过增量分析技术静态分析程序源代码，按照概念模型抽取程序信息并将信息保存在增量 数据库中。最后，启动增量库链接器，将各个增量数据库链接成程序信息库。分析器前 端由信息抽取器和信息管理器组成。j b p a s 分析器前端分析工具包括程序理解工具 ( p r o g r a mu n d e r s t a n d i n gt 0 0 1 ) 、设计文档逆向生成工具( r e v e r s ed e s i g nd o c u m e n t 一4 大连理工大学硕士学位论文 g e n e r a t o r ) 、面向对象测试支持工具( o b j e c t - o r i e n t e dt e s t i n gs u p p o r t e r ) 、面向对象度量工 具( o b j e c t - o r i e n t e dm e t r i c ss u p p o r t e r ) 、构件提取工具( c o m p o n e n te x u a c t o r ) 和c + + 到o l e 转换工具( c + + t oo l et r a n s l a t o r ) 等工具。 程 可视化视图 信 序息j 信抽 信息抽取器 息 交互式理解 取i 表部i l 词法分析i 不 文档生成 分 j 0 j 7 语法分析 信 信i 息 一，程序信息库息 官息抽取部分 库 i | 陌| | l 接 口 图1 2j b p a s 体系结构 f i g 1 2 a r c h i t e c t u r eo f j b p a s ( 2 ) 国外研究现状 国外在程序理解方面的研究追溯到1 9 7 0 年，随着程序证明、程序维护和人工智能 的发展，人们开始了涉足程序理解这一领域。在最近2 0 年来，程序理解系统开始被人 们提出。c a r n e g i em e l l o n 大学软件工程研究所c m u s e i 成立了专门的再工程中心，致 力于通过软件逆向工程进行程序理解技术的研究、增强和实践推广。其中，c h i k o f s 等 人于1 9 9 3 年发起的逆向工程会议每年举行一次，研究和讨论软件逆向工程的问题、技 术及其支持工具。大量的研究成果都集中在程序理解的辅助工具上。程序理解技术发展 至今，己经研制开发出许多工具，例如：刚每、s n i f f + 、r a t i o n a lr o s e 、m i c r o s o f tv i s i o 等工具，下面对r i 舀和s n i f f + 进行简单介绍1 1 0 1 。 v a g i 是一个h a u s ia m 等人提出的支持逆向工程的程序理解工具，它的工作由两部 分组成：剖析阶段和发掘阶段。剖析阶段主要的工作是：剖析源程序，用自带的图像编 辑器生成一个能够操作和浏览的资源流平面图。随后的发掘阶段是一个半自动化的阶 段，涉及了一些模式识别技巧和领域知识。此阶段中逆向工程人员通过剖析阶段建立的 平面图，确定源程序中含有的子系统，构造出有意义的高层抽象模型这些子系统能够递 归地收缩和打开，形成一个层次结构。r j 百能够通过根据用户关心的类型过滤掉不需要 基于切片技术的软件理解辅助系统设计与实现 的信息，方便用户的浏览。不过，r i g i 不支持直接地搜索源代码文本。总之，v a g i 主要 的工作放在揭示系统的抽象和子系统层次的生成。这些层次结构为在工具中从容地浏览 起到了重要的作用。这些信息在软件维护过程中能够作为并发程序理解的文档，以供参 考。 s n i f f + 是一个开放的软件开发环境，它为c 、c h 、f o r t r a n 、j a v a 和c o r b ai d l 等语言提供项目管理、源程序浏览、交叉引用和超强搜索的功能，目前的最新版本是3 0 。 一些相对独立的工具通过集成实现了这些功能。这些工具都是工作在由s n i f f + 剖析源 程序生成的符号表基础上。项目管理窗口列出了源程序的头文件和实现文件符号浏览器 显示了函数，常量、宏和变量等符号。这些符号可以自定义显示条件。源代码编辑器用 语法规则高亮显示源代码。交叉引用窗口显示了符号引用或被引用的依赖树。搜索窗口 显示了源代码文本搜索后的结果。 1 5 本文的组织 本文针对a n s ic 语言编制的程序，在程序切片技术的基础上，使用了经过改进后 的上下文敏感的指针分析算法，设计并实现了一个程序理解辅助系统。论文的结构安排 如下： 第一章是全文的绪论，阐述了程序理解的概念、任务、研究方法和研究现状。重点 介绍了其中比较著名的几个程序理解系统。 第二章对程序切片技术进行了介绍，重点阐述了w e i s e r 数据流切片的定义、性质以 及算法，最后举例说明了该算法。 第三章针对c 语言中指针的使用给数据流分析带来的复杂性，重点介绍了一个上下 文敏感、流敏感的指针分析算法，并介绍了函数指针在过程问指向分析时的改进，并以 一个例子进行了说明。 第四章给出了程序理解辅助系统的设计和实现。重点介绍了程序切片器、交叉引用 器、函数调用图、模块内聚度量器的实现原理和算法。本章和第三章是本文的重点。 第五章给出最后总结与展望，指出下一步要做的工作。 大连理工大学硕士学位论文 2 程序切片技术 2 ，1 程序切片技术简介 ( 1 ) 程序切片的定义 程序切片技术是一种分析和理解程序的技术，通过对源程序中的兴趣点进行程序切 片来辅助分析和理解程序【“】。程序切片概念最早是由m a r kw e i s e r 于1 9 7 9 年在他的博士 论文中提出的，在1 9 8 1 年的国际软件工程大会( i c s e 8 1 ) 以及后来的i e e et r a n s a c t i o n s o ns o f t w a r ee n g i n e e r i n g 杂志上做了进一步的形式化的阐述。 m a r kw e i s e r 提出：切片准则是一种对于“在某些程序语句集中定义或使用的某些 变量的值”的规格说明i 删。利用数据流分析技术可以找到所有可能对此产生影响的程序 代码，这些程序代码称为一个程序切片( p r o g r a ms l i c e ) 。根据m a r kw e i s e r 的定义，程序 切片是一个可执行程序，它的行为应该与源程序的那个特定行为子集是等价的。下面图 2 1 中给出了一个数据切片的例子。关于语句1 2 中变量z 的值的切片如图2 1 中右部所 示。 图2 1 程序切片举例 f i g 2 1 e x a m p l eo f p r o g r a ms l i c e 对于一个给定的程序，根据不同的切片准则，通常会存在不同的切片，并且有下面 的结论成立。 公理2 1 任何一个程序至少存在一个程序切片，即程序本身。 ( 2 ) 程序切片技术的发展 程序切片在2 0 多年的发展过程中经过了一系列的演化：程序切片的算法从数据流 基于切片技术的软件理解辅助系统设计与实现 方程到程序依赖图；切片本身的概念也从可执行的程序切片到不可执行的程序切片；从 源代码切片到软件体系结构切片等。程序切片技术的发展可以分为下面四个阶段1 6 j ： 第一阶段( 1 9 8 1 1 9 8 4 ) ：m a r k w e i s e r 在1 9 7 9 年首先提出了程序切片的概念，这一阶 段主要是他在进行研究。该阶段的特点是切片算法是基于控制流图( c o n t r o lf l o wg r a p h ) 的，并利用数据流方程和信息流方程来获得某个程序的切片。这类切片算法在计算那些 顺序结构的程序以及具有简单基本结构的程序时比较适用。 第二阶段( 1 9 8 4 - 1 9 8 7 ) ：这一阶段主要是基于程序依赖图的程序切片阶段。 o t t e m t e i n s 等人在1 9 8 4 年至1 9 8 7 年之间分别引入了基于程序依赖图( p r o g r a m d e p e n d e n c e g r a p h ) 的图可达性算法，这种算法可以用于计算程序过程内后向切片。 第三阶段( 1 9 8 8 1 9 9 4 ) ：这一阶段称为基于系统依赖图( s y s t e md e p e n d e n c eg r a p h ) 的 程序切片阶段。h o r w i t z 、t r a p s 和d b i n l d e y 等人分别引入了前向切片的概念及其算法 和过程间切片的概念以及两阶段图形可达性算法。同一时期，k o r e l 和l a s k i 等人还引入 了动态切片的概念和算法。这阶段应该说是程序切片技术发展的比较成熟的阶段。其 中，两阶段图可达性程序切片算法的提出是这一阶段的标志性成果之一。 第四阶段( 1 9 9 4 至今) ：这一阶段称之为面向对象的程序切片阶段。从1 9 9 4 年开始， 随着面向对象编程语言和面向对象设计思想的逐渐成熟，针对面向对象的程序切片技术 的研究也随之兴起。这一阶段的程序切片研究以面向对象程序为主。在这一阶段，还出 现了程序切片的多种变体，如无定型切片、度量切片、数据切片、条件切片以及约束切 片等。 ( 3 ) 程序切片技术的应用 程序切片技术在软件分析、理解、调试、测试、度量、软件质量保证、逆向工程等 方面有着广泛的应用。下面简单介绍其在程序调试、软件维护、软件测试、软件度量以 及软件安全中的应用1 6 】。 程序调试 在软件调试的过程中，对于程序中缺陷的定位是一项困难的工作。程序切片技术这 可以帮助程序员容易地进行错误定位。如果检测到程序点s 上的某个变量v 存在错误， 则可以通过计算后向切片 来定位错误，导致缺陷产生的代码就被限定到这个切片 中，通常情况下，这要大大减轻要分析的代码量。 软件维护 软件维护是软件生命周期的一个重要的组成部分，其费用占整个系统费用的一半以 上。软件维护的主要困难在于要正确地理解现有程序，并且在对现有程序进行修改时不 能引入新的错误。 一8 一 大连理工大学硕士学位论文 软件测试 回归测试是在对程序进行修改之后，为了保证程序的正确性以及修改不会带来副作 用，而对系统进行重新测试。由于对系统进行全部重新测试可能会消耗巨大的资源，并 且大多数情况下只有很小部分的代码会受到修改程序的影响，因此，只有那些受到影响 的代码需要重新测试。程序切片技术可以帮助程序员获得那些受到影响的代码，从而有 助于选择测试用例，进一步分析需要测试的代码，简化回归测试过程。 软件度量 软件度量的两个重要度量指标是内聚( c o h e s i o n ) 和耦合( c o u p l i n g ) 。其中内聚度是 指模块内部各成分之间的关联程度。模块的内聚度越高，越容易理解、修改和维护。为 了度量模块的内聚度，l m o t t 和j j t h u s s 提出了数据切片的概念。m h a r m a n 首次把 程序切片技术运用到模块间的耦合度量中，李必信把这种方法推广到面向对象的程序 中，并基于层次切片模型建立了一个用于度量j a v a 程序耦合的框架。 软件安全、 软件虽然不会对人类和社会造成直接的伤害，但是如果软件中存在错误，则这些错 误有可能通过软件和硬件的接口使硬件发生误操作，并造成严重的安全事故。软件安全 分析的几种常用方法有：失效模式效应分析法、软件故障树分析法、p e t r i 网络分析法等。 k b g a l l a g h e l 和j r l y l e 最早考虑使用程序切片技术来分析软件安全问题。在他们的研 究中，重点考虑了共同模式失效和输入与输出不匹配等问题。基于程序切片技术的软件 安全分析还处于起步阶段。 2 2 程序切片算法 程序切片算法经历了由数据流方程算法到图可达性算法的发展过程。m a r kw e i s e r 最初提出的计算切片的算法是基于数据流分析技术的；k j o t t e n s t e i n 和l m o t t e n s t e i n 首次使用程序依赖图来计算程序切片，简化了数据流方程求解切片的复杂度。此外， b e r g e r e t t i 和c a r t e 提出了基于信息流关系的切片算法。本文中采用的是w e i s e r 数据流分 析算法。 2 2 1 数据流算法 m a r kw e i s e r 提出的切片算法是基于数据流分析技术的。下面首先对数据流分析技 术作简介，然后给出具体的算法过程，最后给出了该算法的一个例子。 ( 1 ) 数据流分析 为了收集例如活跃变量、表达式可用性等信息，需要对程序进行数据流分析。数据 流分析问题按照程序执行时的路径分为任意路径数据流分析问题和全路径数据流分析 基于切片技术的软件理解辅助系统设计与实现 问题两种；按照信息流的方向与控制流的方向是否一致，可以分为前向流和后向流问题。 数据流分析框架如表2 1 所示【1 3 1 。 表2 1 在数据流分析中使用的方程 t a b 2 1 e q u a t i o n su s e di nd a t af l o wa n a l y s i s ( 2 ) 算法原理 m a r kw e i s e r 提出了计算语句近似最少静态后向切片的迭代算法。算法分为两层迭 代，直至求得的结果集稳定。算法如下i i i 】： 求解传递数据依赖。程序出现循环时，需要进行迭代计算。 求解控制依赖，把特定的控制谓词加入到切片结果中。对于新加入的每个谓词， 重复步骤，加入该谓词依赖的语句。 算法从得到的相关语句集合中确定相关变量的连续集，切片的最终结果则是相关语 句集合的不动点。首先，经过上面步骤迭代，确定“直接相关变量”。在程序控制流 图( c f g ) 中，节点i 的“直接相关变量”表示为硭( f ) 。迭代过程的初始值为群( 甩) = 矿， 对于任意的不为n 的节点m 其初始值为衅( 肌) = o 。公式( 2 1 ) 给出了一个方程组，这个 方程组定义了对于c f g 中的一条边 ，在点j 处的相关变量集是如何影响点i 处的 相关变量集的。这个方程组的最小解就是在控制流图点i 处的直接相关变量集。从相关 变量集合璎可以得到直接相关语句集合罐。公式( 2 1 ) 给出了踺的定义：霹包含所有 这样的节点i ：在节点i 中定义了与其后继节点相关的变量。 硭( o = 震( f ) u 絮职r e f d ( o ：篡罴四 亿- ， v iv ，d e f ( f ) n ( ) 四 霹= i l ( d 盯o ) n 硭( 埘乃，( f ，j e e ( c f g ) 算法的外层迭代则考虑了程序的控制依赖。在i f 或者w h i l e 的语句体中至少有一条 语句加入到切片中，则语句的条件中引用的变量是间接相关的。分支语句b 的影响范围 大连理工大学硕士学位论文 定义为集合i n f l ) ，即所有控制依赖于语句b 的语句的集合。公式( 2 2 ) 给出了由于有 节点i 在集合硭中而问接相关的分支语句硭的定义。接着确定间接相关变量集雕+ 1 ( f ) ， 除了在集合硭( f ) 中的变量，硭“( f ) 还包含由于和硭中的语句阃接数据依赖而相关的变 量。这是通过再次执行步骤而得到的，只是这时的切片准则变为了集合( 6 ，r e f ( b ) ) 中 的元素，这里的b 是集合群中的一个分支语句。公式( 2 2 ) 给出了第k + 1 次迭代时间接 相关语句集硭“的定义，集合路1 由集合成中的所有语句以及所有定义相关变量集 群“( ，) 中变量的语句构成 量：= 6 1 3 i 硭，f e n f l ( b ) 拳0 ) - - 硭1 i ) u u 。硭雒删卸 ( 2 2 ) 硭“( d = 磋u i i 口l e f ( f ) n 8 r 1 u ) o ， e ( c f g ) 集合群“( f ) 和集合$ 1 分别是程序所有变量和语句集合的非减子集，集合硭“计算 得到的不动点即是要求计算的切片结果。 p i n ( n ) ：j 俾d 删一删例u ，、 l r e f ( n ) u ( i f ”= i t h e n a l l v i n 功 ( 2 3 ) r o u t ( n ) = u n i o n r i n ( m ) , o ，a l l m i m m e d i a t e $ 1 1 c c 鲫o r s o f 刀 从上面的分析过程可以看出，m a r kw e i s e r 算法实质是对给定的切片标准迭代求解 数据流方程组( 2 3 ) 。显然，这是一个任意路径的后向流问题。对每个程序语句建立对应 的方程，对该方程组进行迭代，求得其不动点，即是要求的( 静态后向) 切片结果。 及其切片 f i g 2 2p r o g r a mpa n ds l i c eo f c r i t e r i o n 基于切片技术的软件理解辅助系统设计与实现 ( 3 ) 算法应用举例 图2 2 中的程序p ，在切片标准 下的计算过程如表2 2 所示。表2 2 给出了控制流图中每个节点的d e f 集、r e f 集、i n f l 集以及由w e i s e r 算法得到的相关 变量集合。从表2 2 可知，硭= 2 ，4 ，7 ，8 ) ，硭= 5 ，硭= l ，2 ，4 ，5 ，7 ，8 。在这个例子 中，间接相关语句集合在砖处到达了不动点。考虑到切片标准本身的语句 1 0 ) ，这个结 果和图2 2 中的切片结果是一致的。 表2 2 在程序p 上运行g e i s e r 算法结果 t a b 2 2r u nw e i s e ra l g o r i t h mo np r o g r a mp n o d ed e fr e fi n f l 硭 li n a刀a0 2 i )ooa n ) 3 【s i h n 】o 力 i f i ，n ) 4 p r o d u c t ao i i( i n 5o tn 6 , 7 , 8 p r o d u c t , i ) p r o d u c t ，i ，n 6( s u n l 8 1 1 1 1 1 ，i )0 f p r o d u c t ，i p r o d u c t ，i ，n 7 p r o d u c t p r o d u c t , i ) o p r o d u c t ，i j p r o d u c t ，i ，n s ( i j i a p r o d u c t ，i ) p r o d u c t ，i ，n j 9a s u m a p r o d u c t ) ( p r o d u c t ) 1 0a p r o d u c t )a p r o d u c t ) p r o d u c t 2 2 2 图可达性算法 k j o t t e n s t e i n 和l m o t t e n s t c i n 提出了基于依赖图的过程内程序切片算法。要计算 过程内程序切片，首先要分析过程内可能存在的各种依赖关系，然后在此基础上构造过 程依赖图，再利用图可达性算法即可获得过程内程序切片【6 】。 ( 1 ) 程序依赖图 在只有一个过程的程序中，过程依赖图就是程序依赖图。程序依赖图由语句节点和 语句之间的依赖关系组成。其中，语句节点可分为以下三种类型。复合语句开始节点、 复合语句结束节点、其他的语句节点。语句之间的依赖关系包括：数据依赖、普通依赖、 控制依赖关系。一般做法是先在c f g 上构造控制依赖图和数据依赖图，然后把两个图 合并即可得到p d g 。 ( 2 ) 图可达性算法 令 是对程序p 进行切片的切片准则，( n ，e ) 是程序p