基于依赖性分析的程序切片技术研究

摘要

程序切片是一种重要的程序分析理解方法,用于从源程序中抽取对程序中特定点上的特定变量有影响的语句和控制条件,组成新的程序(称作切片),然后通过分析切片来分析源程序的行为.二十多年来,人们对它进行了广泛而深入的研究,取得了许多研究成果,使得它在软件调试、测试、维护、度量、程序变换、软件逆向工程与再工程等方面得到广泛应用,受到广大软件研究、开发人员的高度重视.论文主要工作包括:(1)通过对切片理论的研究,一定程度上解决了当前在大型程序切片、面向对象程序切片、并发程序切片及动态切片等方面存在的一些问题,提高了切片的效率和精确度;(2)进一步拓宽了切片技术的应用范围,将依赖性分析及程序切片技术应用于软件可测试性分析、测试覆盖率分析、类内聚度度量等方面;(3)对系统实现的若干问题进行了探索.论文工作的主要成果表现在以下几个方面:1.对传统的依赖性分析方法进行了改进,提出了一种新的子程序依赖性分析方法.在此方法中,依赖图的计算以子程序为单位,子程序间相对独立,内部数据、语句之间的依赖关系对外不可见,仅提供参数间的依赖关系作为对外接口.2.为了解决目前大型程序切片效率低的问题,提出了一种渐增式依赖性分析方法,根据用户需要逐渐建立依赖图,而不是预先建立整个系统的依赖图.与此对应,我们提出了部分切片的概念,可以只对感兴趣的部分进行切片,而非针对整个程序.3.为了有效描述面向对象程序的特性,提出了一种新的面向对象程序切片方法.在此方法中,类的依赖图由组成类的方法的依赖图组成,它们与类的方法一一对应.当构建子类的依赖图时,父类的依赖图无需重建,子类直接继承其父类的依赖图.在此基础上进一步提出了一些关于对象切片、类切片、类层次切片以及类粗粒度切片的概念和方法.4.为了提高动态切片的追踪效率,提出了一种利用静态分析的结果来减少动态追踪的信息量方法.5.为了简洁、有效地描述并发程序,提出了一种并发程序流图.基于这种表示,建立了并发程序依赖性分析模型.由于充分分析了各种并发行为,并考虑了并发和同步的语义,所构建的并发程序依赖图比已有其它方法都精确.在此基础上,提出来一种新的并发程序切片方法,它可以在多项式时间内分析得到较精确的并发程序切片.6.将程序切片技术应用于软件可测试性分析,提出了一种模块级的可测试性分析方法,使得它更能适用于黑盒测试.7.提出了一种利用程序切片计算关于变量测试覆盖率分析的方法,在计算覆盖率时,只考虑与这些变量有关的代码,结果更加准确.8.为了克服了现有方法只分析某个方面的不足,提出了一种基于依赖性分析的类内聚度度量方法,并证明了它满足优良的内聚度度量方法应该具有的性质,为综合评价类内聚度提供了指南.

目录

文摘

英文文摘

东南大学学位论文独创性声明及使用授权说明

主要符号、术语列表及主要算法列表

第一章引言

1.1选题依据

1.2国内外研究现状

1.3主要研究内容

1.3.1切片技术研究

1.3.2切片应用研究

1.3.3切片系统实现研究

1.4论文主要成果

1.5论文结构

第二章基本概念

2.1控制流图

2.2子程序内依赖性分析

2.2.1控制依赖

2.2.2数据依赖

2.2.3程序依赖图

2.3子程序间依赖性分析

2.4程序切片

第三章顺序程序切片技术研究

3.1改进的子程序间切片方法

3.1.1改进的程序依赖图

3.1.2参数依赖集

3.1.3参数映射

3.1.4关于参数的切片

3.1.5子程序间切片

3.2大型程序切片技术研究

3.2.1概述

3.2.2依赖性分析

3.2.3大型程序切片算法

3.2.4转换与比较

3.3面向对象程序切片技术研究

3.3.1面向对象程序依赖性分析

3.3.2面向对象程序切片

3.4类的粗粒度静态切片

3.4.1基本概念与性质

3.4.2依赖关系计算

3.4.3类的静态粗粒度切片

3.4.4实例研究

3.5本章小结

第四章并发程序切片技术研究

4.1研究现状及关键问题

4.2并发程序表示

4.3并发程序依赖性分析

4.3.1定义

4.3.2任务间数据依赖的计算方法

4.3.3 CPDG的构造方法

4.3.4性质

4.4可并发执行语句对检测算法

4.4.1相关研究

4.4.2并发程序流图的简化

4.4.3检测会合能否完成

4.4.4检测会合能否被触发

4.4.5死语句检测

4.5并发程序切片

4.6分析与比较

4.7本章小结

第五章动态切片技术研究

5.1引言

5.2基本概念

5.2.1执行记录及切片准则

5.2.2动态切片的分类

5.3相关研究

5.4基于依赖性分析的动态切片算法

5.4.1切片准则

5.4.2动态切片算法

5.4.3实例分析

5.4.4补充说明

5.5动态对象切片

5.6本章小结

第六章应用研究

6.1基于状态切片的软件可测试性分析

6.1.1 PIE分析

6.1.2状态切片

6.1.3基于静态状态切片的可测试性分析

6.1.4基于动态状态切片的可测试性分析

6.2基于程序切片的测试覆盖率分析

6.2.1基本概念

6.2.2计算测试覆盖率

6.2.3试验结果分析

6.3基于依赖性分析的类内聚度度量

6.3.1类内聚度度量方法

6.3.2相关研究比较

6.4本章小结

第七章程序切片系统实现技术研究

7.1APST总体框架

7.2公共信息库

7.2.1组成

7.2.2组织

7.3用户界面

7.4几个问题

7.5与系统实现有关的成果

第八章总结与展望

8.1论文总结

8.2未来工作展望

致谢

参考文献

附录一攻读博士学位期间完成的论文列表

附录二攻读博士学位期间参加的科研项目列表