程序切片技术及其应用

　　本书主要介绍程序切片的起源和发展，程序切片技术的图论基础，程序切片的各种变体（如静态切片、动态切片、有条件切片、并发切片、面向对象程序的切片、体系结构切片和规约切片等），计算程序切片的各种方法，以及程序切片技术在软件调试、波动分析、软件测试、度量、重用、程序理解、逆向工程和软件安全等方面的应用，并讨论了程序切片技术的发展趋向。本书适合作为高等院校计算机软件专业学生学习"软件工程"、"软件分析与测试"等课程的参考书或工具书，也适合作为软件分析与测试研究人员的参考书。上篇程序切片技术基本原理第1章 概论1.1 程序切片技术的起源和发展1.1.1 从数据流方程到程序依赖图1.1.2 从可执行的程序切片到不可执行的程序切片1.1.3 静态切片、动态切片和有条件切片1.1.4 后向切片和前向切片1.1.5 从源程序代码切片到软件规约切片1.1.6 从单一切片到多种切片1.2 程序切片技术的应用概述1.2.1 程序调试1.2.2 软件维护1.2.3 同归测试1.2.4 软件度量1.2.5 软件重用1.2.6 软件安全1.3 程序切片工具简介1.3.1 支持C语言的PST1.3.2 支持Ada语言的PST1.3.3 支持Oberon-2语言的PST1.3.4 支持Java语言的PST1.3.5 其他PST小结思考题参考文献第2章 图论基础2.1 控制流图2.1.1 基本模块2.1.2 控制流图定义2.1.3 基本属性2.2 控制流分析2.2.1 控制流2.2.2 控制流的表示方法2.2.3 支配节点和后必经节点2.2.4 循环识别2.3 数据流分析2.3.1 可到达定义2.3.2 数据流方程2.3.3 活性分析2.4 数据依赖和控制依赖2.4.1 控制依赖2.4.2 数据依赖2.5 程序依赖图2.5.1 过程内依赖图2.5.2 过程间依赖图小结思考题参考文献第3章 静态程序切片3.1 引言3.2 Mark weiser程序切片3.2.1 初步理解3.2.2 基本术语3.2.3 Mark weiser的数据流算法3.3 过程内切片3.3.1 构造程序依赖图3.3.2 图可达性算法3.3.3 例子分析3.4 过程间切片3.4.1 构造系统依赖图3.4.2 构造特征子图的算法3.4.3 过程间切片的算法小结思考题参考文献第4章 动态程序切片4.1 引言4.2 基本术语4.2.1 程序依赖图和静态切片4.2.2 执行历史和动态切片准则4.3 Agrawal和Horgan的动态切片4.3.1 动态切片方法14.3.2 动态切片方法24.3.3 动态切片方法34.3.4 动态切片方法44.4 Korel和Laski的动态切片小结思考题参考文献第5章 有条件程序切片5.1 引言5.2 有条件切片5.2.1 准静态切片5.2.2 同时动态切片5.2.3 一般的有条件切片模型5.2.4 有条件切片计算5.3 切片模型关系分析5.4 分割分析小结思考题参考文献第6章 面向对象程序切片6.1 引言6.2 传统系统依赖图的缺陷分析6.3 面向对象系统依赖图6.3.1 OOSDG的基本组成模型6.3.2 OOSDG对SDG的扩充6.3.3 类依赖图6.3.4 虚函数调用图的构造6.3.5 OOSDG的构造算法6.3.6 基于OOSDG的程序切片算法小结思考题参考文献第7章 并发程序切片7.1 引言7.2 Cheng的并发程序切片思想7.3 Krinke多线程程序静态切片方法7.3.1 线程控制流图7.3.2 线程程序依赖图7.3.3 基于tPDG的切片7.4 Nanda和Ramesh的并发程序切片方法7.5 并发程序的动态切片7.5.1 进程图和静态程序依赖图7.5.2 进程图到并发图7.5.3 构建DPDG7.6 面向对象并发程序的切片方法7.6.1 Zhao的早期方法7.6.2 Java并发程序的切片方法小结思考题参考文献第8章 规约切片8.1 形式规约切片8.1.1 静态形式规约切片8.1.2 动态形式规约切片8.1.3 其他形式规约切片8.2 基于规约的程序切片8.2.1 前置和后置条件8.2.2 基于规约的切片8.3 体系结构规约切片8.3.1 体系结构规约8.3.2 体系结构切片定义8.3.3 体系结构信息流图和体系结构切片的计算8.4 动态软件体系结构切片8.5 JVM规约切片小结思考题参考文献第9章 新型切片变体9.1 无定型切片9.1.1 程序投影9.1.2 无定型简单性度量9.1.3 无定型静态切片9.1.4 无定型有条件切片9.1.5 无定型切片的实现以及相关问题9.2 削片9.2.1 静态削片9.2.2 动态削片9.2.3 削片的性质和构造策略9.3 砍片小结思考题参考文献中篇程序切片技术的基本应用第lO章 程序调试10.1 引言10.1.1 什么是程序渊试10.1.2 为什么用切片进行调试10.2 如何用切片辅助程序调试10.2.1 调试中的错误分析及切片选取10.2.2 面向对象程序切片与调试10.3 基于切片的调试工具10.3.1 C-Debug10.3.2 SPYDER小结思考题参考文献第11章 波动分析11.1 引言11.2 程序切片与REA过程11.3 后向切片存在的必要性11.3.1 定义修改11.3.2 使用修改11.3.3 控制修改11.4 程序切片运算11.5 直接波动和诱导波动11.5.1 通用程序切片11.5.2 REA例子小结思考题参考文献第12章 软件测试12.1 引言12.2 基于程序切片的软件测试12.2.1 例子简介12.2.2 依赖图模型12.2.3 基本性质12.3 回归测试12.3.1 受影响的定义一使用关系类型12.3.2 BackwardWalk算法12.3.3 ForwardWalk算法12.3.4 进一步讨论12.3.5 回归测试的一般步骤12.4 基于切片技术的软件测试工具模型小结思考题参考文献第13章 软件维护13.1 引言13.2 软件维护模型13.3 分解切片与软件维护13.3.1 分解切片13.3.2 使用分解切片的几条规则13.4 联合切片与软件维护13.4.1 联合切片13.4.2 利用联合切片维护软件13.5 基于切片的软件维护模型小结思考题参考文献第14章 复杂性度量14.1 引言14.2 早期基于切片的度量14.3 内聚度量14.3.1 数据切片14.3.2 胶水、强力胶水和粘性14.3.3 内聚度量14.3.4 类内切片和类内聚14.4 耦合度量14.4.1 Java源代码中存在的耦合问题分析14.4.2 基于切片的Java耦合度量框架小结思考题参考文献第15章 软件安全15.1 引言15.2 软件安全分析的几种常用方法15.2.1 失效模式效应分析法15.2.2 软件故障树分析法15.2.3 Petri网分析法15.3 临界安全组件与软件故障树分析15.3.1 共同模式失效问题15.3.2 临界安全组件15.4 基于程序切片的共同模式失效分析方法15.4.1 基本原理15.4.2 例子分析小结思考题参考文献第16章 软件重用16.1 引言16.2 转换切片Lj重用16.3 有条件切片与重用16.4 规约驱动切片与重用16.5 软件体系结构切片与重用小结思考题参考文献第17章 应用扩展17.1 程序分析理解17.1.1 Lucia等人的初步思想17.1.2 Korel的大型程序理解手段17.1.3 Kumar的CONCEPT技术17.2 逆向工程和再工程17.2.1 传统切片17.2.2 接口切片17.3 Tip的类型错误定位方法17.3.1 静态语义规约和类型检17.3.2 项重写和依赖追踪17.3.3 切片精确度问题17.4 程序验证17.5 其他应用小结思考题参考文献下篇程序切片技术展望第18章 层次切片模型及其实现18.1 面向对象程序的层次结构模型18.2 层次切片模型18.3 SSA算法的基本思想18.4 HSM和SSA的实现18.4.1 代码信息树18.4.2 依赖图的生成算法和切片算法18.5 Jato：Java程序切片工具18.5.1 依赖图生成层18.5.2 切片生成层18.6 层次切片复杂度小结思考题参考文献第19章 层次切片模型的应用19.1 静态信息流分析19.2 耦合度量19.2.1 方法m1和m2之间的耦合度量19.2.2 类c的耦合度量19.3 内聚度量19.3.1 子功能内聚19.3.2 功能内聚19.4 复杂度度量小结思考题参考文献第20章 结束语20.1 基本原理总结20.2 基本应用总结20.3 未来研究课题20.3.1 程序切片的形式语义20.3.2 无定型程序切片20.3.3 规约切片20.3.4 基于规约程序切片20.3.5 软件体系结构切片20.3.6 程序切片应用参考文献附录附录A 汉英名词对照附录B 缩略语英汉对照

　　李必信男，1969年出生，安徽庐江人，博士后，现任东南大学计算机科学与工程系教授。1998年2月至2000年12月，在南京大学计算机科学与技术系攻读博士学位，师从著名软件工程学者郑国梁教授；2001年4月至2002年3月，在芬兰图尔库（Turku）计算机科学中心（TUCS）做博士后研究，师从著名软件工程专家、精化演算创始人RalphJohanBack教授；2002年4月至2004年1月，受聘于欧洲信息和数学联盟（ERCIM），并被派往挪威科学技术大学（NTNU）和荷兰国家计算机和信息研究中心（CWI）从事教学和研究工作。2004年2月加盟东南大学，并开始组建ERICS（EmpiricalResearchinComputerScience）研究组。目前ERlCS的主要研究方向为软件开发新技术与新方法、经验软件工程、程序切片技术、软件分析与测试、软件语言、软件建模与验证和软件过程改进等。1999年以来，先后在JournalofInformationandComputationalScience，InformationandSoftwareTechnology，JournalofComputerScie

上篇程序切片技术基本原理
第1章 概论
1.1 程序切片技术的起源和发展
1.1.1 从数据流方程到程序依赖图
1.1.2 从可执行的程序切片到不可执行的程序切片
1.1.3 静态切片、动态切片和有条件切片
1.1.4 后向切片和前向切片
1.1.5 从源程序代码切片到软件规约切片
1.1.6 从单一切片到多种切片
1.2 程序切片技术的应用概述
1.2.1 程序调试
1.2.2 软件维护
1.2.3 同归测试
1.2.4 软件度量
1.2.5 软件重用
1.2.6 软件安全
1.3 程序切片工具简介
1.3.1 支持C语言的PST
1.3.2 支持Ada语言的PST
1.3.3 支持Oberon-2语言的PST
1.3.4 支持Java语言的PST
1.3.5 其他PST
小结
思考题
参考文献
第2章 图论基础
2.1 控制流图
2.1.1 基本模块
2.1.2 控制流图定义
2.1.3 基本属性
2.2 控制流分析
2.2.1 控制流
2.2.2 控制流的表示方法
2.2.3 支配节点和后必经节点
2.2.4 循环识别
2.3 数据流分析
2.3.1 可到达定义
2.3.2 数据流方程
2.3.3 活性分析
2.4 数据依赖和控制依赖
2.4.1 控制依赖
2.4.2 数据依赖
2.5 程序依赖图
2.5.1 过程内依赖图
2.5.2 过程间依赖图
小结
思考题
参考文献
第3章 静态程序切片
3.1 引言
3.2 Mark weiser程序切片
3.2.1 初步理解
3.2.2 基本术语
3.2.3 Mark weiser的数据流算法
3.3 过程内切片
3.3.1 构造程序依赖图
3.3.2 图可达性算法
3.3.3 例子分析
3.4 过程间切片
3.4.1 构造系统依赖图
3.4.2 构造特征子图的算法
3.4.3 过程间切片的算法
小结
思考题
参考文献
第4章 动态程序切片
4.1 引言
4.2 基本术语
4.2.1 程序依赖图和静态切片
4.2.2 执行历史和动态切片准则
4.3 Agrawal和Horgan的动态切片
4.3.1 动态切片方法1
4.3.2 动态切片方法2
4.3.3 动态切片方法3
4.3.4 动态切片方法4
4.4 Korel和Laski的动态切片
小结
思考题
参考文献
第5章 有条件程序切片
5.1 引言
5.2 有条件切片
5.2.1 准静态切片
5.2.2 同时动态切片
5.2.3 一般的有条件切片模型
5.2.4 有条件切片计算
5.3 切片模型关系分析
5.4 分割分析
小结
思考题
参考文献
第6章 面向对象程序切片
6.1 引言
6.2 传统系统依赖图的缺陷分析
6.3 面向对象系统依赖图
6.3.1 OOSDG的基本组成模型
6.3.2 OOSDG对SDG的扩充
6.3.3 类依赖图
6.3.4 虚函数调用图的构造
6.3.5 OOSDG的构造算法
6.3.6 基于OOSDG的程序切片算法
小结
思考题
参考文献
第7章 并发程序切片
7.1 引言
7.2 Cheng的并发程序切片思想
7.3 Krinke多线程程序静态切片方法
7.3.1 线程控制流图
7.3.2 线程程序依赖图
7.3.3 基于tPDG的切片
7.4 Nanda和Ramesh的并发程序切片方法
7.5 并发程序的动态切片
7.5.1 进程图和静态程序依赖图
7.5.2 进程图到并发图
7.5.3 构建DPDG
7.6 面向对象并发程序的切片方法
7.6.1 Zhao的早期方法
7.6.2 Java并发程序的切片方法
小结
思考题
参考文献
第8章 规约切片
8.1 形式规约切片
8.1.1 静态形式规约切片
8.1.2 动态形式规约切片
8.1.3 其他形式规约切片
8.2 基于规约的程序切片
8.2.1 前置和后置条件
8.2.2 基于规约的切片
8.3 体系结构规约切片
8.3.1 体系结构规约
8.3.2 体系结构切片定义
8.3.3 体系结构信息流图和体系结构切片的计算
8.4 动态软件体系结构切片
8.5 JVM规约切片
小结
思考题
参考文献
第9章 新型切片变体
9.1 无定型切片
9.1.1 程序投影
9.1.2 无定型简单性度量
9.1.3 无定型静态切片
9.1.4 无定型有条件切片
9.1.5 无定型切片的实现以及相关问题
9.2 削片
9.2.1 静态削片
9.2.2 动态削片
9.2.3 削片的性质和构造策略
9.3 砍片
小结
思考题
参考文献
中篇程序切片技术的基本应用
第lO章 程序调试
10.1 引言
10.1.1 什么是程序渊试
10.1.2 为什么用切片进行调试
10.2 如何用切片辅助程序调试
10.2.1 调试中的错误分析及切片选取
10.2.2 面向对象程序切片与调试
10.3 基于切片的调试工具
10.3.1 C-Debug
10.3.2 SPYDER
小结
思考题
参考文献
第11章 波动分析
11.1 引言
11.2 程序切片与REA过程
11.3 后向切片存在的必要性
11.3.1 定义修改
11.3.2 使用修改
11.3.3 控制修改
11.4 程序切片运算
11.5 直接波动和诱导波动
11.5.1 通用程序切片
11.5.2 REA例子
小结
思考题
参考文献
第12章 软件测试
12.1 引言
12.2 基于程序切片的软件测试
12.2.1 例子简介
12.2.2 依赖图模型
12.2.3 基本性质
12.3 回归测试
12.3.1 受影响的定义一使用关系类型
12.3.2 BackwardWalk算法
12.3.3 ForwardWalk算法
12.3.4 进一步讨论
12.3.5 回归测试的一般步骤
12.4 基于切片技术的软件测试工具模型
小结
思考题
参考文献
第13章 软件维护
13.1 引言
13.2 软件维护模型
13.3 分解切片与软件维护
13.3.1 分解切片
13.3.2 使用分解切片的几条规则
13.4 联合切片与软件维护
13.4.1 联合切片
13.4.2 利用联合切片维护软件
13.5 基于切片的软件维护模型
小结
思考题
参考文献
第14章 复杂性度量
14.1 引言
14.2 早期基于切片的度量
14.3 内聚度量
14.3.1 数据切片
14.3.2 胶水、强力胶水和粘性
14.3.3 内聚度量
14.3.4 类内切片和类内聚
14.4 耦合度量
14.4.1 Java源代码中存在的耦合问题分析
14.4.2 基于切片的Java耦合度量框架
小结
思考题
参考文献
第15章 软件安全
15.1 引言
15.2 软件安全分析的几种常用方法
15.2.1 失效模式效应分析法
15.2.2 软件故障树分析法
15.2.3 Petri网分析法
15.3 临界安全组件与软件故障树分析
15.3.1 共同模式失效问题
15.3.2 临界安全组件
15.4 基于程序切片的共同模式失效分析方法
15.4.1 基本原理
15.4.2 例子分析
小结
思考题
参考文献
第16章 软件重用
16.1 引言
16.2 转换切片Lj重用
16.3 有条件切片与重用
16.4 规约驱动切片与重用
16.5 软件体系结构切片与重用
小结
思考题
参考文献
第17章 应用扩展
17.1 程序分析理解
17.1.1 Lucia等人的初步思想
17.1.2 Korel的大型程序理解手段
17.1.3 Kumar的CONCEPT技术
17.2 逆向工程和再工程
17.2.1 传统切片
17.2.2 接口切片
17.3 Tip的类型错误定位方法
17.3.1 静态语义规约和类型检
17.3.2 项重写和依赖追踪
17.3.3 切片精确度问题
17.4 程序验证
17.5 其他应用
小结
思考题
参考文献
下篇程序切片技术展望
第18章 层次切片模型及其实现
18.1 面向对象程序的层次结构模型
18.2 层次切片模型
18.3 SSA算法的基本思想
18.4 HSM和SSA的实现
18.4.1 代码信息树
18.4.2 依赖图的生成算法和切片算法
18.5 Jato--Java程序切片工具
18.5.1 依赖图生成层
18.5.2 切片生成层
18.6 层次切片复杂度
小结
思考题
参考文献
第19章 层次切片模型的应用
19.1 静态信息流分析
19.2 耦合度量
19.2.1 方法m1和m2之间的耦合度量
19.2.2 类c的耦合度量
19.3 内聚度量
19.3.1 子功能内聚
19.3.2 功能内聚
19.4 复杂度度量
小结
思考题
参考文献
第20章 结束语
20.1 基本原理总结
20.2 基本应用总结
20.3 未来研究课题
20.3.1 程序切片的形式语义
20.3.2 无定型程序切片
20.3.3 规约切片
20.3.4 基于规约程序切片
20.3.5 软件体系结构切片
20.3.6 程序切片应用
参考文献
附录
附录A 汉英名词对照
附录B 缩略语英汉对照