学位论文 > 优秀研究生学位论文题录展示

基于Daikon的Java程序动态分析技术研究

作　者: 杨东晓
导　师: 胡成全
学　校: 吉林大学
专　业: 计算机系统结构
关键词: 不变式 Java程序动态分析技术研究时空复杂度偶然性源程序程序语言程序分析静态分析
分类号: TP311.11
类　型: 硕士论文
年　份: 2004年
下　载: 128次
引　用: 0次
阅　读: 论文下载

内容摘要

软件项目管理的不规范性，软件产业人员的高度流动性，使得留下了很多基线不一致的，不好读懂的程序，这些程序往往造价高昂，其中很多还有重用价值，这时就迫切需要有一种工具可以帮助人们分析程序，甚至自动给程序添加注释，在提高可理解性的同时，减少程序员的工作量。Daikon是国外一种把动态分析技术和静态分析技术相结合的程序分析开源工具，功能强大，但是国内还没有人研究。大多数现有的软件分析工具或者是使用静态分析技术，或者是使用动态分析技术，很少有把两种技术的优点集中起来的分析程序。Daikon使用了程序分析的很多原理和技术，可以向程序中自动添加注释，也可以得到关于程序的形式化的规格说明，并可以用来进行程序退化测试。本文对Daikon中包含的各种原理，技术和实现进行了阐述，并提出了一些改进思想。Daikon工具的各种语言前件在不同程序语言和Daikon之间架起了一座桥梁，对不同的程序语言编写的源程序进行处理，向源程序中添加了观察语句，观察每个程序点样本的值并把程序中各个变元的类型信息传递给Daikon。Daikon对所推导的不变式的置信度问题进行了处理，判断每个不变式的偶然性概率，偶然性概率太大的不变式就会被否定，另外有些不变式虽然偶然性概率不大，但是程序点范围内可见的不同样本值元组太少，不足以支持该不变式，也被否决。Daikon对分析出来的互相矛盾的不变式进行了解决，就是从这个矛盾不变式集合中随机的抽取一条不变式，直到剩下的不变式集合不矛盾为止，针对这点本文提出了利用启发式属性约简策略去替换这种随机策略，以得到更加优化的不变式集合。Daikon推导不变式时使用了“权威性变元”策略，相等变元中的一个被选择作为“权威变元”，它代表了所有和它相等的变元所拥有的关系。使用这种思想推导出的不变式需要人工进行等量替换，影响了所产生的注释的直观性，用户可以屏蔽相应的“权威性变元”策略。Daikon 利用面向对象的程序分片思想来实现其体系架构，本文对其架构给出了详细分析。Daikon使用数据流层次结构思想使其能更好地对<WP=49>面向对象的语言进行分析。本文对Daikon的整个分析流程给出了描述。本文测试发现Daikon能够很好地对面向对象语言编写的源程序进行分析（包括多态，多重继承，递归，异常等机制都有不错的效果），Daikon也可以对面向过程的语言进行处理。本文对Daikon的时空复杂度问题进行了讨论，描述了它的影响因素。对于变元之间一些很重要的关系（比如4变元不变式，还有一些非线性不变式等），Daikon没给出相应的实现，就是受时空复杂度的局限，系统设计的思想也是有意识的牺牲完备性来换取系统的效率。Daikon本身也有一些缺陷，例如对类集的支持不太好；执行离线操作以致对类频繁被调用的系统（比如实时系统）的支持不好；其所使用的外部程序Ajax（衡量变元间的可比较性）对一些大程序会失败等。本文实现了一种对于Daikon工具的改进，把多个测试人员使用Daikon工具得出的不变式集，进行合并比对；当两个测试人员得到了相同的不变式时，选取偶然性概率比较小的不变式作为合并以后的不变式。也可以把得出的结果插入到待分析的源程序中，得出关于程序的更加精确而完备的描述。通过此改进减少了Daikon单人测试的工作量，有利于Daikon工具的进一步实用化。本文为了合并不变式创建了一个中间树型，并使用访问者模式访问树型，进行相应程序点节点和不变式节点的合并操作，写入到一个新的InvMap映射对象中。访问者模式的实现使得这个改进具有很强的可扩展性，可以进一步扩展其它的功能。本文对相关程序分析系统，Houdini和类规格生成器进行了分析，对它们的实现原理也进行了描述，比较了它们和Daikon的优缺点。　　论文还提到了今后可以继续开展的课题，比如进一步减少系统时空开销从而可以分析变元之间更多的关系；用属性约简策略得到矛盾不变式的一个最优化子集，作者只是给出了一个思想，有待于进一步实现；进一步封装Daikon，使得Daikon可以利用图形界面更方便的对一个工程进行分析。

全文目录

第一章前言  5-7
  1.1 研究背景  5-6
  1.2 Daikon发展历史和现状  6-7
  1.3 本文工作  7
第二章 DAIKON工具原理研究  7-28
  2.1 Daikon工具的基本工作原理  7-9
  2.2 Daikon各种语言前件的作用以及实现原理  9-10
  2.3 Daikon中的数据跟踪文件和类型声明文件结构  10-11
  2.4 不变式推导  11-20
    2.4.1 推导不变式过程中所考察的变元  11-13
    2.4.2 推导不变式过程中所考察的派生变元  13-15
    2.4.3 不变式的置信度问题  15-17
    2.4.4 利用数据流层次结构思想处理不变式  17-18
    2.4.5 条件不变式的推导和逻辑蕴含  18-19
    2.4.6 对互相矛盾的不变式的解决  19
    2.4.7 使用ESC/Java对输出不变式进一步处理  19-20
    2.4.8 验证Daikon推导不变式的效果  20
  2.5 Daikon的输出结果形式  20-23
  2.6 用Daikon改进测试案例  23-24
  2.7 用Daikon来防止程序退化  24-25
  2.8 Daikon的运行时间和空间复杂性  25-26
  2.9 Daikon工具的不足之处  26-28
第三章 DAIKON主要体系结构及具体工作流程  28-32
  3.1 Daikon中关键类PptMap类的数据结构  28-29
  3.2 Daikon主要工作流程:  29-30
  3.3 Daikon软件包中关键子软件包的功能介绍  30-32
第四章 DAIKON工具的改进  32-42
  4.1 合并不变式的主要思想  32-34
  4.2 主类的工作流程图  34-35
  4.3 树型的创建以及合并访问者对象访问情况  35-36
  4.4 程序中关键类的关键方法描述  36-39
  4.5 对Daikon所作改进的优缺点  39
  4.6 系统运行环境  39
  4.7 合并不变式中所使用的一些Daikon类关键方法描述  39-42
第五章总结  42-45
  5.1 相关程序分析技术  42-43
    5.1.1 Houdini  42-43
    5.1.2 Java类规格生成器  43
  5.2 本文所做工作的意义  43
  5.3 今后的研究课题  43-45
参考文献  45-47
致谢  47-48
摘要  48-50
ABSTRACT  50-53

相似论文

高考数学压轴题背景溯源分析及其备考教学研究,G633.6
猪细小病毒河南流行株的分离、鉴定及部分生物学特性研究,S852.65
温州市水稻高产栽培技术研究,S511
综合材料绘画语言实践中的“偶然性”,J205
日本小学音乐科教材分析研究,G623.71
中职数学变式教学的策略研究,G633.6
高中数学变式教学研究,G633.6
民航空管DVOR/DME导航台信号覆盖与飞行程序综合分析及应用研究,V351.37
关于高中数学三角模块的教学研究,G633.6
基于多粒度依赖关系图的变更影响分析方法研究,TP311.53
永磁接触器设计及静动态特性分析,TM572.1
基于多样化对象所有权的软件可信性质研究,TP311.52
基于隔离环境的恶意软件网络行为监测与分析,TP393.08
嵌入式环境下代码动态性能分析的研究与实现,TP368.1
微小型机床的结构参数优化及动态特性分析,TG502.31
方滑枕变形处理及补偿的研究,TG548
长距离大运量胶带输送机动态特性研究,TD528.1
储油罐防雷技术研究,TE972
逆变式弧焊电源的输入整流拓扑研究,TM461
基于粒子群优化算法的电梯群控系统的调度研究,TU857
严寒地区商场建筑空调动态负荷分析,TU831.2