章的组织结构第二章相关理论综述设计模式设计模式的组成设计模式的分类设计模式挖掘技术源代码的中间表示形式面向结构特征的技术面向行为特征的技术类图与概述类图概述本章小结第三章基于子模式的结构分析方法子模式的基本定义种子模式模型设计模式结构特征模型万方数据杭州电子科技大学硕士学位论文结构型模式的结构特征模型创建型模式的结构特征模型行为型模式的结构特征模型基于子模式的结构分析方法类关系有向图子模式实例挖掘算法子模式生成候选模式算法本章小结第四章基于方法签名的行为分析方法和模式挖掘过程方法签名模板定义设计模式方法签名模板结构型模式的方法签名模板创建型模式的方法签名模板行为型模式的方法签名模板设计模式实例挖掘过程预处理阶段设计模式实例挖掘步骤本章小结第五章实验测试结果和性能分析实验环境与实验评估指标实验环境实验评估指标实验结果及分析效度威胁分析本章小结第六章总结与展望本文工作总结未来展望致谢参考文献附录万方数据杭州电子科技大学硕士学位论文第章绪论课题研究背景与意义在世纪年代，由合著的书的出版正式掀开了软件业设计模式的序幕，著作中提到种设计模式被广泛应用到面向对象的软件开发中。近年来，在软件开发过程中越来越频繁地使用设计模式缩短软件开发周期，并且通过复用已经存在的开发经验提高软件质量。设计高质量可重用的系统并不是件容易的事情。针对软件开发中常见的问题，设计模式提供了文档化的可重用的解决方案，因此系统设计人员通常使用设计模式设计高质量的软件系统。然而，在实际软件开发过程中，大量使用设计模式也带来了系列负面问题。方面，对于许多遗留用来表述类中定义的元素的数量等信息。图使用抽象语法树表示的系统源码图使用抽象语义图表示的系统源码面向结构特征的技术基于模板匹配的模式挖掘技术模板匹配方法已广泛地应用在计算机视觉领域，用于在个图中检测模板。通过计算模板与图的互相关系值评估它们的匹配程度。模板匹配算法可定义为−∙其中用于表示匹配模板的向量，表示待匹配图的向量万方数据杭州电子科技大学硕士学位论文表示偏移量。公式描述了如何计算模板和图的相互关系值，的值越大表示图和模板越匹配。文献改进了模板匹配算法并将其应用在设计模式挖掘研究中。对公式进行了改进并定义了归化相互关系数∙∙利用公式计算得到的匹配度的范围是−，的值越高说明与越相似当时，则说明与完全匹配。使用该算法的前提必须把系统用矩阵表示，同时模式也用矩阵表示，将计算到的结果作为设计模式探测的结果。基于相似度评分的模式挖掘技术等人提出了种基于相似度评分的算法用于设计模式挖掘领域。使用该算法时首先使用表示系统的有向图和表示个设计模式的有向图，和表示图中顶点数。接着定义个∗的相似矩阵，中的每个值表示中的顶点与中的顶点的相似度，或者也称为顶点与顶点之间的相似度评分。计算相似矩阵的算法描述如下令。迭代偶数次，当收敛时停止迭代。输出，的值是最后次迭代时的值。其中，和分别表示图和图的邻接矩阵用于填充∗的矩阵−表示范数为的矩阵。面结构特征的设计模式挖掘技术是这三者之中研究最多的，因为它相对容易检测得到。面向行为特征的技术设计模式恢复过程中也会使用面向行为特征的方法，该方法般是在结构特征分析得到设计模式候选实例的基础之上，再进步检测候选实例中不同角色中发生的方法调用等行为信息。基于模型检测的模式挖掘技术文献中，提出使用模型检测的方法挖掘设计模式，该研究是在结构分析的基础上，再对得到的候选设计模式实例利用模型检测的方法分析其行为特征。模型检测方法的流程如图所示。万方数据杭州电子科技大学硕士学位论文控制流解析候选设计模式实例设计模式库特性顺序图规范恢复的设计模式实例模型检测图基于模型检测的设计模式挖掘流程图模型检测方法首先从源代码中提取与设计模式候选实例相关的时序图，时序图的构建是基于控制流分析技术产生个方法调用树。接着依据设计模式库中提供的信息，使用规范表示候选设计模式实例的时序图，同时定义设计模式应该具备的特性，最后将特性和规范作为工具的输入，验证候选设计模式实例的真伪。模型检测器的工作模式如图所示。系统抽象模型系统具有的属性模型检测器确定具有种属性或确定没有没有属性反例图的工作流程图基于自动机的模式挖掘技术文献研究了基于自动机的设计模式挖掘技术，该方法的目标是检测每个候选设计模式实例，判断在程序执行过程中，其角色所对应的类之间方法的调用关系是否符合行为型设计模式的要求。若符合，则断定该设计模式候选实例就是设计模式实例。其中将行为型设计模式的行为特征使用个自动机表示。以行为型设计模式中的模式为例，首先构建状态模式的非确定有限自动机，如图所示。接着再将模式的转换成确定性有限自动机如图所示。描述的是符合行为型设计模式方法调用万方数据杭州电子科技大学硕士学位论文的痕迹，因此那些不符合行为型设计模式中定义的方法调用顺序的就是无效的状态，如图所示。εεε图模式的模式的从个可选的方法调用开始状态和状态，状态至状态表示个循环，次循环执行两个方法调用，状态和状态之间的转换操作在时刻只能选择个方法调用。状态至状态是模式中定义的第二个循环，最终的状态是行为型设计模式中最后次方法调用的状态，即图中的状态。模式的万方数据杭州电子科技大学硕士学位论文拒绝状态的图模式的及拒绝状态基于自动机的设计模式挖掘技术虽然能正确地识别出系统中存在的设计模式实例，但该算法的输入需要段可执行的程序或者设计测试用例，增加了挖掘方法的难度。类图与概述类图统建模语言是构建软件系统模型的标准方法，它具有创建系统的多种结构模型的能力，如静态结构和动态行为等。提供了种基本模型图，如下表所示。表基本模型模型用途用例图描述系统本身提供的各种用例与系统外部的各类参与者之间的关系。类图展示系统中类的静态结构。对象图是类图的种实例化图。包图是种分组机制。状态图描述类对象拥有的所有状态，状态之间变迁等事件。时序图描述对象之间的消息传递的先后次序等动态协作关系。合作图对象之间消息传递等动态协作关系的另种展示方式。活动图描述系统中每个活动的执行流程。构件图展示程序代码的包或自系统等物理结构。配置图展示软件在硬件环境中所需要的配置关系。本文提出的基于子模式的结构分析方法，是在设计模式的类图的基础上进行描述的。下面主要对类图进行详细的介绍。类或接口万方数据硕士学位论文题目基于子模式和方法签名的设计模式挖掘方法研究研究生张艳艳专业软件工程指导教师俞东进教授完成日期年月万方数据杭州电子科技大学硕士学位论文基于子模式和方法签名的设计模式挖掘方法研究研究生张艳艳指导教师俞东进教授年月万方数据杭州电子科技大学硕士学位论文，万方数据杭州电子科技大学学位论文原创性声明和使用授权说明原创性声明本人郑重声明所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经发表或撰写过的作品或成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。申请学位论文与资料若有不实之处，本人承担切相关责任。论文作者签名日期年月日学位论文使用授权说明本人完全了解杭州电子科技大学关于保留和使用学位论文的规定，即研究生在校攻读学位期间论文工作的知识产权单位属杭州电子科技大学。本人保证毕业离校后，发表论文或使用论文工作成果时署名单位仍然为杭州电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文学校可以公布论文的全部或部分内容，可以允许采用影印缩印或其它复制手段保存论文。保密论文在解密后遵守此规定论文作者签名日期年月日指导教师签名日期年月日万方数据杭州电子科技大学硕士学位论文摘要设计模式是在项目中使用的种最佳实践，关注于解决应用程序高级结构开发问题。近年来，设计模式被广泛地应用于软件开发中，这在给软件开发人员带来了便利的同时，也导致些新问题的产生。例如，当系统中缺少对设计模式使用信息的记录时，系统的可理解性和可维护性将大大降低。因此，高效准确地恢复系统中存在的设计模式实例，对理解系统架构和软件再工程具有重要意义。然而，恢复设计模式实例并不是项简单的任务。本文提出了个新颖的方法用于从系统源代码中挖掘定义的种设计模式实例。本文方法的关键在于，从不同的设计模式中提取相同的更易于挖掘的结构子模式，并使用子模式定义种设计模式的结构特征模型。本文使用类关系有向图表示系统源代码子模式和设计模式，在此基础上利用基于素数组合的图同构算法挖掘子模式实例，然后按照设计模式结构特征模型的定义，使用联接类合并特定的子模式实例以生成设计模式候选实例。在此基础上，再将设计模式候选实例的方法调用等行为特征与预先定义的方法签名模板进行匹配，以过滤掉不满足条件的模式实例。与传统的挖掘方法相比，本文通过子模式的合并识别设计模式，减少了搜索空间同时采用方法签名进行行为分析，可避免设计代码覆盖率较高的测试用例，降低了设计模式挖掘工作的难度。最后，基于对设计模式结构特征和行为信息的研究，本文实现了个设计模式实例挖掘工具，并对九个开源项目进行测试，实验结果表明本文方法取得了较高的准确率和召回率。关键词设计模式，设计模式恢复，子模式，图挖掘，方法签名万方数据杭州电子科技大学硕士学位论文万方数据杭州电子科技大学硕士学位论文