【毕业学位论文】（Word原稿）AspectJ程序分析及编织优化相关技术研究-计算机软件与理论博士论文

分类号： 密 级： 公开 论文编号： 博 士 学 位 论 文 论文题目 序分析及编织优化相关技术研究 申请学位类别 工学博士 专业名称 计算机软件与理论 研究方向 计算机软件与理论 论文提交日期 2008 年 10 月 N A or Y 2008 东南大学学位论文独创性声明 本人声明所呈 交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名： 日期： 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印件和电子文档，可 以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布（包括以电子信息形式刊登）论文的全部内容或中、英文摘要等部分内容。论文的公布（包括以电子信息形式刊登）授权东南大学研究生院办理。 研究生签名： 导师签名： 日期： 摘 要 一门新的程序设计语言，它是在 言的基础上扩充了 统而来的。 言的面向方面程序设计方法能够 弥补传统面向对象技术在 模块化软件中 横切关注点方面的不足 ，因此它 不仅是人们研究 言的主要平台，在现实中也有着广泛的应用。 言既对程序分析领域提出了新问题，也对传统的分析提出了新的挑战。我们对 序的面向方面调用图及其构造，以及动态通知的编织优化进行了深入的研究，并按照新的需求重新考虑了序类型分析和指向分析等问题。 论文的主要研究成果包括： (1) 提出了基于 解的 序类型分析的新方法 ，该方法是流敏感、属性敏感以及上下文敏感的，能够在复杂度可接受的情况下 构造出更加精确的程序调用图 。 方法的基本思想是 将程序抽象为命题逻辑公式，然后利用 解器求解来完成分析。我们以方法为单位进行抽象，首先将方法转换成 后将 变量和 属性抽象为布尔向量，类型被编码为具体的向量，相关语句的公式通过 联结符 “ ”联结成方法的公式。我们通过求取方法抽象的概要进一步缩小方法公式的规模并化简推导过程。对于方法概要公式，既可以单独求解（过程内分析） ， 也可以按照上下文不敏感或敏感的方式联结起来求解（过程间分析）。 (2) 提出了基于 解的 序指向分析的新方法 ，该方法 同样 是流敏感、属性敏感以及上下文敏感的，能够有效缓解传统方法精确分析时的状态空间爆炸问题 。方法的基本思想和 主要 分析流程与基于 解的 序类型分析方法相同。主要区别在于指向分析方法是一个反复迭代、逐步求精的过程，它利用已有的分析结果精化当前的方法公式，再次组成程序 的公式并求解，从而获得更加精确的分析结果，如此反复直至达到稳定 。 (3) 提出了适合 序 分析 的面向方面调用图 ， 该调用图能够表示 言定义的多种程序执行事件，并且能够在上下文不敏感的情况下间接表示出与节点相关的部分 对象的动态类型，解决了传统上下文不敏感调用图的缺陷。我们在传统调用图的基础上 增加 了节点 的 种类，定义了节点的类型 并区分静态节点类型和动态节点类型 ，另外还定义了 边的种类。 我们将 基于 解的 序类型分析方法用于上下文不敏感面向方面调用图的构造 。对于基程序和方面程序中的通知，我们采用基于 方法分析。对于通知在程序中的织入点，我们通过对切点做快速的解析来估计。对于静态通知，我们能够 准确 的估计通知的织入点，但对于动态通知，我们只能估计出所有可能的织入点。要想进一步提高动态通知织入点的估计精度，可以运用 我们提出的 动态通知编织 优化 方法 。 (4) 提出了基于上下文不敏感面向方面调用图 的 序动态通知编织 优化 方法 ， 相比较其它优化方法，该方法考虑了具有 分别与对象的动态类型和程序运行时调用栈有关的两类动态性的通知的编织优化 。 我们的 方法在上下文不敏感面向方面调用图上求解程序运行到可能织入点时的调用栈表达式，并利用面向方面调用图的动态类型推导能力推导调用栈表达式中节点的所有可能的类型，然后 将该表达式与切点匹配，若切点包含表达式中的所有模式，则将通知调用无条件织入该节点；若切点不包含其中任一种模式，则通知调用 不织入；至于其它情况，通知调用仍需条件织入。 关键词 ： 言 、调用图、类型分析、指针分析、面向方面程序设计、 言、编织、优化 、 is a of to in be a to OP in in it We a on of of on we as of as (1) We a is AT it a of an In a a to by AT as an we of to SA to of so as to of . we to of of in in we it as a (2) We a is AT it in of as in is an it of on to s to a We a is (3) We a of of s of is as an of 1) is 2) of a of of of is ) CG We an of at CG In we to of in of be To be in (4) We on CG of s of of on of in we of a to on of 1) if it is 2) if of it is 3) if of is a 目 录 第一章 引言 . 1 题依据 . 1 内外研究现状 . 2 要研究内容 . 3 文主要成果 . 4 文结构 . 5 第二章 基于 解的 序调用图构造 . 6 究现状 . 7 本思想 . 8 序抽象初步：语句及结构抽象 . 11 态单赋值形式 . 12 句抽象 . 12 构抽象 . 13 序抽象进阶：方法抽象 . 18 组和属性的表示 . 18 法锚点 . 20 展形式及其构造 . 25 法抽象 . 26 法概要 . 28 序抽象高级 I：过程内分析 . 29 序抽象高级 程间分析 . 32 法公式的联结 . 32 体分析与分部分析 . 34 下文不敏感分析与上下文敏感分析 . 34 统 . 36 统框架 . 36 展形式转换模块 . 38 序抽象模块 . 38 式的求解 . 39 章小结 . 40 第三章 基于 解的 序指向分析 . 41 析方法 . 41 本思想 . 42 析流程 . 42 类型分析方法的差异 . 42 例研究 . 45 下文不敏感分析 . 45 下文敏感分析 . 47 型分析与指向分析的综合 . 50 章小结 . 51 第四章 向方面调用图及其构造 . 52 向方面调用图 . 52 点分类 . 53 点类型 . 54 的分类 . 57 点动态类型推导 . 58 向方面调用图的构造 . 59 程序 构造 . 59 知关联及通知 构造 . 60 章小结 . 61 第五章 态通知编织优化 . 62 题分析 . 62 织优化 . 64 点转换 . 64 造 . 65 用栈表达式求解 . 65 切点表达式匹配 . 67 例研究 . 68 章小结 . 69 第六章 总结与展望 . 70 文总结 . 70 来工作展望 . 70 致 谢 . 72 参考文献 . 73 附录一 攻读博士学位期间完成的论文列表 . 80 附录二 攻读博士学位期间参加的科研项目列表 . 81 东南大学博士学位论文 1 第一章 引言 题依据 软件 的 模块化是软件工程领域中的一个重要研究课题。模块化的软件具有更好的 可重用性、可维护性、可扩展性和可验证性，是实现软件工厂的必经之路 1随着软件 规模的 日益庞大 ， 人们对软件模块化程度的要求也越来越高。 软件 的模块化不仅需要程序员具备 良好的模块化 程序设计思想，更离不开程序设计 语言的 支持， 不同设计范式的程序设计语言具有不同的模块化能力。 过程式程序设计语言 （ 例如 C、 等 ）支持函数级别 的封装，而 面向对象程序设计语言 （ 例如 C+、 、 等等 ） 则支持对象级别的封装，其模块化能力强于前者。 虽然 面向对象程序设计方法 仍然是当前软件设计方法的主流，但其在模块化能力上的不足逐渐暴露出来。 等 人 指出 软件中存在一些具有横 越多个模块的行为，使用传统的软件开发方法不能够达到有效模块化的特殊关注点 ，他们 将这些特殊关注点称为横切关注点 （ 6 例如，图 抽象类， 两个具体的类。 一个关注点，其功能是当图形元素改变坐标后即时更新在视图上的显示，方法实现。如果利用传统程序开发技术，我们必须在 及 6 个方法中都添加 方法调用语句。因此，关注点 一个横切关注点，其横越了 个类共 6 个方法。 为了能够有效的封装横切关注点， 等人 提出了面向方面的程序设计思想 6并且通过对言扩充 统设计出了 言 12其它面向方面程序设计语言还有 69,20以及 1,22（ 目和 目于 2005 年合并 18） ，它们都是 对 在众多的 言中， 为典型，是研究 言及其应用的主要平台。 言 统的核心是 预 定义的连接点 模型 （ 以及增加的切点（ 类型间声明（ 通知（ 方面（ 新的语言设施 13。 言将横切关注点封装为方面 。 例如，我们可以将图 示的横切关注点封装为 如下的 方面程序。 .); ; : | ; F i g u r e E l e m e n tm o v e B y ( i n t , i n t )r e f r e s h ( )P o i n tg e t X ( )g e t Y ( )s e t X ( i n t )s e t Y ( i n t )m o v e B y ( i n t , i n t )d r a w ( )L i n eg e t P 1 ( )g e t P 2 ( )s e t P 1 ( P o i n t )s e t P 2 ( P o i n t )m o v e B y ( i n t , i n t )d r a w ( )2D i s p l a y U p d a t i n 切关注点示例 东南大学博士学位论文 2 其中， 切点， 过通配符选定了 类的所有以“ 头的方法，即 法以及 的 法， 定了 的 法（由于 子类，因此也包括它们的 法），紧接着的通知指定当调用 完 定的方法后执行语句“ ;”。这样我们就把原先需要在 6 处插入的语句封装到了一处。待到编译时， 言的编译程序将方面织入到程序中。方面被编译成普通的类，通知被编译成普通的方法，通知的调用插入到由切点指定的程序点处，编织后的 序是一个普通的 节码程序 23,24。 这种织入方式将编织代价转移到编译时，并且使得 程序 执行不需要修改 拟机 。但它对动态通知的编织效果不好，会留下大量的滞留程序，用于程序运行时做检查，满足条件则执行通 知，不满足则跳过通知继续执行。目前， 译程序没有采用任何优化技术消除滞留程序，从而造成编织后程序执行效率的低下。这就给 序分析提出了具体的问题，即我们如何通过分析 来 优化对动态通知的编织，提高编织后程序的执行效率。 动态通知的编织优化离不开 序的调用图， 但 言引入的新的语言设施给传统程序调用图及其构造带来了新的挑战。一方面，节点种类单一的传统程序调用图 已经无法表示 接点模型中定义的丰富的程序事件。因此，需要研究适合 序 分析 的调 用图。 另一方面， 构造调用图的传统方法达到了构造精度的瓶颈，在复杂度可接受的情况下无法构造出较为精确的调用图，不能满足优化的需求。因此，需要研究构造程序调用图的新方法。由于 言的 展， 因此我们首先研究 序调用图的构造，然后将构造方法扩展到 序中。 构造 质是进行类型分析。而 别名关系对 包括 类型分析 在内的面向对象程序分析的精度 有着较大的影响 。现有的指向分析方法大都是流不敏感且上下文不敏感的，因此分析出的别名关系不够精确， 从而造成其它程序分析精 度的低下。为此，研究一种实用的更加精确的 实 意义。 综上所述，本课题研究的目的旨在通过对 提出 一种 出一种适合 研究其构造方法； 研究动态通知编织的优化问题， 分析 通知 织入的确定性 ， 减少 滞留程序，改善程序运行效率。 内外研究现状 (1) 序 调用图的构造 面向对象程序调用图构造是面向对象程序分析中的经典问题，自九十年代以来，人们对其进行了广泛而深入的研究，提出了 从简单到复杂的 多种构造方法，主要包括 5,26、 7、 列 （包括 28、 列 （ 包括 29、以及 k 0） 30,31。 这些方法 都是流不敏感的，并且 除 k 1）以外 的 方法 也 是上下文不敏感的 ，因此 虽然 它们的 构造速度较快，但精度低。 而精度稍高的 k 1） 的 空间 复杂 度难以被人们接受。因而目前的程序分析仍然大都采用快速但粗糙的 方法 构造程序的调用图 。 (2) 序指向分析 指向分析 的目的是 分析变量的指向集，从中可以 归纳出 变量间的别名关系，而准确的别名关系能够提高大多数程序分析的精度，因而 指向分析 一直 是程序分析中的热点和难点之一。人们在指向分析方面做了大量的研究工作，提出