程序切片技术在程序理解中的应用

摘 要：随着计算机软件技术的飞速发展,软件系统的规模变得越来越大,软件的维护工作也随之越来越复杂.绝大部分软件开发的主要精力都消耗在维护或者扩展原有的系统上面,而不是重新开发新系统.因此,对于软件系统的维护问题变得极其重要,对于遗留软件的维护、理解在软件开发过程中已经变得越来越重要.分别介绍了程序理解的模型及工具,并结合程序切片技术探讨程序切片在程序理解中的应用.

关 键 词：程序切片；程序理解；逆向工程

中图分类号：TP311文献标识码：A文章编号：2095-2163（2013）02-0097-03

0引言

大多数软件系统在开发过后都会经历一个相当长的维护过程.在这个过程中,软件维护人员常常需要根据已知测试结果和反馈得来的BUG进行各类纠错,并且还可能会需要进行修改以致重新设计.实践经验表明,软件开发的绝大部分精力都耗费在对原有系统的维护上面,而不是用于新系统的重新开发.专家估计用于维护的资源和时间已经占到总开发的50%到70%[1],因而需要对其给予高度重视,并对其实现有效调控.

程序理解是从计算机程序中获取有效知识信息的一个重要过程.这些知识信息可以用于程序排错、完善程序、重用程序以及整理文档等很多方面的工作[2].简单来讲,程序理解就是通过特定的方法和技术来得到一个认知,就是这个程序是“做什么”的以及是“如何做”的.如果对其进行完整、周密的定义,可以将程序理解看作如下的一个任务：以软件维护、升级和再实践为目的,在不同的抽象层次上建立有关基本软件的概念模型,包括从程序代码本身的模型到基本应用领域的模型.基于以上定义,程序理解的基础是要建立软件产品间的直接对应关系,维护人员借助这些对应关系,就可以根据自身拥有的软件系统的相关知识,快速定位到与其存在关联的一系列软件产品,比如,找到实现相应业务逻辑的可执行代码,或者在看到代码以后,了解到这些代码可实现的具体业务逻辑,又或是根据一个业务逻辑,找到与其有关的特定业务逻辑.

但是,程序理解是一个复杂的任务,因其涉及对软件系统不同抽象层次的有效理解及其之间的精确知识匹配.例如,存在于系统问题域和系统实现域之间的巨大“语言差距”就是程序理解的难点之一.程序理解过程的复杂性主要表现在如下几个方面：

（1）具体应用领域与程序设计领域之间的专业鸿沟有待跨越.在理解某一应用领域的程序时,不仅需要程序方面的知识,还需要这一领域的专业知识,专业知识的匮乏必然给程序理解带来相当的理解难度.

（2）软件系统的耦合度非常高.各个功能模块出现了交叉,由此导致程序理解难度的增加.

（3）软件系统的不断升级,导致程序逻辑结构的混乱.

（4）程序理解过程中,缺少必要的源程序说明文档及相关文字材料.

（5）程序理解中,人员的心理因素也是程序理解难度增加的一个不可忽视的影响因素.

1程序理解模型及工具

11程序理解模型

随着程序理解的发展,现已提出了许多模型[2],这些模型在程序理解过程中发挥着关系全局的重要作用.在程序理解中,采用一种有效的程序理解模型,有助于实现高质量、高成功率的程序理解,下面对程序理解的主要模型进行简单的说明和论述.

（1）自顶向下模型.程序理解时,采用自顶向下的理解方式,是首先检测设已经理解,然后去验证所提出的检测设,最后再修改此检测设的一个顺序理解过程.这种理解方式需要程序员熟悉该程序应用领域的有关背景知识,然后将这些背景知识和具体程序源代码不断尝试对应的过程.详述此过程就是,将对程序进行检测设作为开始,其后在代码中验证该检测设是否成立.当初始检测设获得验证后,可以精化出附属的子检测设,于是这些大、小检测设就构成了一个树状结构,并按照深度优先原则,不断地进行着验证的深一层精化.Soloway和Ehrlich已通过经验性研究发现,自顶向下的理解方式常常发生在程序员较为熟悉编写代码的技术和编码风格的时候.

（2）自底向上模型.检测设程序理解人员并不透彻了解具体业务逻辑,此时就需从阅读程序源代码来理解程序,再通过自底向上的方式创建程序控制流抽象,直至建立高层抽象.具体来说,该种理解方式中,程序理解人员会逐行理解程序源码,逐步建立上一层的抽象模型.这些较高层次的抽象表现形式又将组合在一起,提取出更高层次的抽象结果.在这个过程中,语法知识与特定编程语言相关,需要考虑的是程序中的语句和基本单元,而语法知识的积累则有助于程序员形成精神模型.程序的语义知识则与特定语言无关,并随着程序员精神模型的不断建立而渐次获取相应内容,内容所描述的就是程序应用领域的业务知识.大量实验研究表明,当程序员采用这种方法来理解程序时,更多关注的是程序中的结构化信息,同时在脑海中根据这些结构化信息,首先建立程序模型.如程序员将聚焦程序中的控制流程,建立控制流图,又或者集中在程序中的数据上,建立数据流图,再根据数据流图来实现程序理解.

（3）综合模型.这种模型是自底向上和自顶向下模型的结合,并根据上述模型建立相应的知识库,在知识库的辅助下完成程序理解过程.

12程序理解工具

目前,已经存在多种支持程序理解的软件工具,下面择选较为典型的程序理解软件工具做以分析介绍.

（1）Understand.是一款分析大型软件工程的有力工具,由Scitool公司开发.该工具能够分析出函数声明或定义、数据结构的定义、交叉引用以及函数的调用图等程序内部信息,并且也可以计算出函数的复杂度和控制语句的嵌套深度.同时Understand还集成了代码编辑器、代码和代码分析器,提供了功能强大的用户界面,可将分析结果以各种形式（图形、图表、架构图等）呈现给用户,为程序员进行代码开发、维护、调试提供了更大程度的便利.目前,Understand已能支持C/C++/C#、Ada、Ja、FORTRAN、Delphi和Jovial等众多编程语言,实现程序理解.（2）JBPAS.是由北大青鸟研制开发的一款支持C++语言的程序理解辅助系统,由信息管理器、C++前端分析器及程序分析工具集三大主体部分构成.该系统能够生成OOD（Object-OrientedDesign）文档和Rose文档.C++前端分析器则是通过数据库的概念模型对C++程序源代码展开分析,再将抽取出的程序片段信息保存在数据库中.

（3）BDCom-C++.是一款支持C++语言的程序理解系统,由信息管理器、信息抽取器和用户界面所组成.该系统以增量式分析技术对程序源代码实现静态分析,信息库则是由增量型数据库组成,同时存储了经由信息抽取器分析后所收集到的程序信息.第2期杜均,等：程序切片技术在程序理解中的应用智能计算机与应用第3卷

（4）Rigi.是一个可裁剪、可扩展的逆向工程环境的程序理解系统,主要由Rigi-server、Rigi-reverser和Rigi-edit3这三大部分组成.其中,Rigi-server是一个用于存储从源程序代码抽取所得信息的静态信息库；Rigi-reverser是一个支持C、COBOL等程序语言的静态信息解析器；Rigi-edit则是一个交互性的窗口编辑器,通过图形方式展示和操控程序的静态信息.Rigi的一个重要功能就是,可过滤掉用户不感兴趣的信息,但却不支持对程序源代码文本的直接搜索功能的实现.

2程序切片

21程序切片定义

程序切片概念是由Weiser于1979年在其博士论文中首次提出[3].Weiser等人通过对程序源代码的分析以及对控制流程图（CFG）的研究发现,程序的某一输出只与源程序中的部分语句相关,即使删除其它语句也不会影响这一输出结果.这个发现表明,对该输出来说,源程序和删除无关语句后得到的可执行程序在语义上是一致的.Weiser等人即将这种只与某个输出有关的语句段落所构成的程序,称为源程序的一种切片[4].由数类实践可知,程序切片技术在软件分析、理解、调试、测试、度量、重用、软件质量保证、逆向工程等许多方面已经获得广泛的应用,并获得良好应用效果.

22程序切片分类

目前,程序切片主要分成以下三类,分析如下.

（1）静态切片.是指在计算程序切片时,不需考虑程序运行时候的具体输入,只是采用静态分析法,对由程序源代码所得到的程序切片展开分析.该切片方法对程序的输入通常不作任何检测设,而是要考虑程序中能够执行的所有轨迹,故而计算量较大.静态切片的例子如图1（a）所示.

（2）动态切片.在考虑特定输入情况下,需要采用动态分析方法计算得到程序的动态切片.因此,动态切片的计算过程依赖于程序的特定输入,计算时需利用程序中的某一特定执行路径,计算工作量也较静态切片小上很多.

（3）条件切片.由于静态切片得到的切片结果过于宽泛,而动态切片得到的结果又过于精细,因此在计算条件切片时,可增加一个附加条件,只有满足这个条件的输入才能进入分析,这样就很好避免了切片结果过于宽泛和精细问题.条件切片示例如图1（b）所示.

23程序切片工具

（1）Wisconsin.是一个支持对C程序进行静态切片的实用工具,主要包括三大功能：前向切片、后向切片和消片.同时,还提供生成控制流图和函数调用图等程序相关的设计图.与其他C语言分析工具类似,Wisconsin也会将源程序代码转换为合适的中间代码表示形式,以方便其后的程序切片工作进程.

（2）ChopShop.是由CarnegieMellon大学计算机科学学院开发的一种逆向工程工具,能帮助程序员理解还不曾熟悉的C程序代码.该工具采用了一种新算法,即静态程序切片的模块产生机制,藉此而成为一种全新的数据流分析技术.这种算法的采用使得生成结果比标准形式的切片更容易达成逻辑理解.ChopShop完全遵守ANSI标准,可以产生两种形式的切片结果：文本形式和图形化形式,而且还可以对结果进行分析并提供程序语言特性的处理功能.值得一提的是,ChopShop还是首个为过程提供数据抽象机制的程序切片工具.

（3）Ghinsu.是由Florida大学计算机和信息科学系主体研发,并得到软件工程研究中心（SERC）提供基金赞助的一个项目,在其中集成了众多辅助工具的程序切片系统,可用于软件工程的诸多活动中,重点是在维护活动过程中发挥一些辅助作用.只是迄至目前为止,该系统仅仅支持C语言,并不支持其他语言.

（4）Unrel.是一个原型程序切片工具,可以对标准C程序源代码实施静态程序切片.该项目得到美国核控制委员会（NRC）和国家通信系统（NCS）的指定基金的鼎力援助.Unrel可以对程序切片进行组合和逻辑集合操作,通过这些操作可以识别在计算中至少出现一次的代码.这些daima信息对描述高级集成软件重要且实用,因为包含在这种代码中的一次失败就可能导致软件中多个逻辑构件的故障[5].

（5）PSS/Ada.是由杨洪等人设计完成的一个Ada程序的静态切片生成系统.该系统可以对Ada程序进行静态数据依赖分析和控制依赖分析,并可通过这些分析结果得出Ada程序语句间存在的波动效应,相应地生成特殊形式的Ada程序切片.这一切片是从Ada程序中抽取某些语句、并以相同顺序重新组成的—个新程序段.PSS/Ada系统是一个可以实现Ada软件的测试、排错、分析、理解和维护的有效工具,在Ada程序的并行性检查、波动性分析、复杂性度量等方面也提供一定层次的支持力度.另外,PSS/Ada系统作为对Ada程序设计支持环境APSE的工具集的扩充,也进一步丰富了Ada软件的开发环境[5].

3结束语

作为一种程序理解的方法,程序切片其实就是基于原始程序而构造的一个删减版本,切片计算时,需删减程序中与兴趣点无关的部分,从而能够将关键、分散的变量由原本复杂的程序中提取出来,进而组成新的程序片段.通过对这一片段展开具体分析,可以得到所关注变量与其他变量之间的联系,从而加速实现对程序的全面、精准理解.