基于堆叠泛化的设计模式检测方法*

冯 铁 , 靳 乐 , 张家晨 , 王洪媛

1(吉林大学 计算机科学与技术学院,吉林 长春 130012)2(吉林大学 软件学院,吉林 长春 130012)3(符号计算与知识工程教育部重点实验室(吉林大学),吉林 长春 130012)

设计模式通过标识对象、对象间的合作及责任分配来揭示设计机理,表明基于某种经验的、在特定的上下文中解决一个普遍设计问题的可复用体系结构[1,2].设计模式已经被广泛地应用在各种软件和工具库的设计与实现中.设计模式检测旨在从现有的软件设计文档或源代码当中识别所使用的设计模式实例,它不仅对于帮助维护人员理解软件系统的设计动机和原理、恢复软件设计和改善软件的可维护性具有重要意义,而且有助于软件体系结构的恢复和发现,同时也是评估软件质量的一个重要依据.

由于设计模式的应用大多是基于意图的,并未严格限制模式的具体实现,加之不同开发者对于设计模式的理解不一,这使得模式的实现千变万化.目前,设计模式检测主要存在以下问题:(1) 变体的检测效果不理想;(2) 结构相同意图不同的模式难以区分;(3) 行为型设计模式的检测复杂;(4) 组合爆炸问题依然突出.正是因为这些问题的存在,设计模式检测仍然是软件工程领域的一个重要的研究内容.

机器学习是人工智能领域的重要分支,它是使用经验来提高计算性能或做出准确预测的计算方法[3].机器学习技术适用于设计模式检测的原因如下:首先,设计模式检测活动本身就是对众多候选模式实例进行预测的过程,这符合机器学习的应用背景;其次,设计模式变体的检测与机器学习无需硬编码的特点相适应;最后,机器学习对语义信息的描述,有助于区分结构相同而意图不同的模式.

对于行为型设计模式的检测,目前主要的方法是借助于动态分析[4-6],但是动态分析一般要求目标项目完整可运行,这在实际中有时候是不可行的;另外,监控候选模式实例的运行需要生成相应的测试用例,如果手工生成,必然费时费力,如果自动生成,又难以做到有效的路径覆盖.如果能够充分利用静态代码分析技术,将对模式的检测研究深入到方法内部,并尝试用机器学习的方式去刻画模式的行为特征,就可以较大程度地降低行为型设计模式检测的难度.

本文提出一种新的设计模式检测方法,结合面向对象度量和模式微结构(以下简称度量和微结构)并使用典型的机器学习算法来实现设计模式的检测.针对每种设计模式,本文分别用度量和微结构(micro-structure,简称MS)训练出一个分类器,然后采用模型堆叠的方式训练出最终的分类器,从而实现对该设计模式的检测.

本文的主要贡献如下:(1) 提出了用多视图(设计模式度量视图和设计模式微结构视图)堆叠泛化的方法来解决设计模式检测问题;(2) 定义了模式必备微结构来缩减搜索空间,从而避免组合爆炸问题;(3) 对于检测出的模式实例,除给出角色映射外,还能给出具体的方法映射.最终实验表明,本文提出的方法在变体的识别、行为型设计模式的检测以及组合爆炸问题的解决等方面均有明显提升.

本文第1 节介绍本文相关工作.第2 节定义度量和微结构以及相关的基本概念与原理.第3 节详细介绍基于堆叠泛化的设计模式检测方法.第4 节在5 种设计模式上进行实验,通过实验数据的对比分析,验证所提方法的有效性.第5 节对本文的工作进行总结并对未来工作展望.

1 相关工作

自从GoF 等人提出软件设计模式概念以来[1],许多学者对设计模式的自动化检测进行了研究,提出了很多种设计模式检测方法.这些方法在所用技术、分析类型、所面向的源代码或模式的中间表示、是否精确匹配、是否完全自动化、是否面向特定模式、实验的信息项和指标等方面各不相同.接下来,本文从所用技术方面对一些具有代表性的方法进行归纳和介绍.

有些设计模式检测方法是基于相似度计算的[7,8].例如,Tsantalis 等人利用图的相似性算法实现了设计模式的检测[7],该方法不仅能够识别模式变体,而且还能够有效地解决模式检测过程中的组合爆炸问题(利用了设计模式大都包含继承层次这一事实).简单来说,该方法将设计模式角色之间的各种关系用邻接矩阵来表示,然后从源码中提取所有的继承层次,接着在模式查找阶段,用继承层次中的类去映射设计模式的各个角色,然后提取出这些角色类之间的各种关系矩阵,最后利用矩阵之间的相似性算法得到一个最终的相似度,如果相似度超过了事先选择的阈值,那么就找到了一个设计模式实例.该方法的缺点是对某些行为型设计模式的检测效果不好,同时空间复杂度也很高.

有些设计模式检测方法是基于图理论的[9-11].例如,Yu 等人从设计模式的子模式出发,将设计模式检测问题映射为图论中的图同构问题[9].他们定义了十几种能够表示设计模式结构特征的子模式.对于一个待检测系统,他们首先将系统源码和子模式用类关系有向图来表示,然后从系统源码的类关系有向图中找到和子模式的类关系有向图同构的子图,通过参照设计模式结构特征模型来组合这些子图,从而得到候选模式实例.为了追踪设计模式行为方面的特征,他们使用方法签名模板来过滤不符合条件的候选模式实例.他们方法的缺点是没有对子模式进行过滤,从而子模式挖掘和子模式组合的时间复杂度很高.另外,他们仅仅使用方法签名来追踪设计模式的行为特征,这显然是不够的.

还有一些设计模式检测方法是基于本体的[12-14].例如,Dietrich 等人使用Web 本体语言(OWL)来形式化地定义设计模式和其相关概念[12].他们开发了一款原型工具,该工具以设计模式的形式化描述和待检测的Java 项目为输入,输出待检测项目中该设计模式的实例.由于该方法采用的是准确匹配,因此很难对设计模式的变体进行检测.最后,他们提出可以去掉或弱化某些约束,从而实现模糊匹配,但是他们并未针对具体模式说明哪些约束可以被去掉或弱化.

最后,基于机器学习的设计模式检测方法也有很多[15-17],其中具有代表性的检测方法是下面3 个:

Alhusain 等人首次尝试了只使用机器学习的方法来实现设计模式的检测[15].他们的训练数据集是由MARPLE[18],SSA[7],WOP[12],FINDER[19]等4 种模式检测工具投票产生的.他们的模式检测方案包括两个阶段:在第1 阶段,他们通过特征选择算法为每个模式角色选择一个特征子集,然后根据该特征子集和相应的分类模型来确定每个模式角色的候选类,从而减小了模式的搜索空间;在第2 阶段,每种设计模式都有一个单独的分类器,该分类器使用表示角色类之间关系的特征作为输入.最后他们在JHotDraw 项目上进行了实验,但是结果并不是很理想.

Zanoni 等人也将机器学习技术应用到了设计模式检测当中,他们开发了一个名叫MARPLE 的Eclipse 插件,该插件可以从Java 源代码当中抽取设计模式[16].MARPLE 插件包括3 个主要模块:(1) 信息检测引擎,负责构建系统模型;(2) Joiner,负责从系统模型里面抽取设计模式候选实例;(3) Classifier,负责分类Joiner 的结果,把候选实例分类为正确的模式实例和错误的模式实例.他们为每种设计模式都找到了最佳的聚类算法和分类算法.他们方法的缺点是训练数据集需要人工产生,而人工产生数据集会受主观因素影响;Joiner 的召回率并不是100%;有效性和训练集大小的关系有待进一步验证;并未考虑系统库和第三方库中的代码.

Chihada 等人从面向对象度量的角度给出了设计模式的检测方法[17].他们的检测方法分为两个阶段:设计模式组织阶段和设计模式检测阶段.在设计模式组织阶段,他们从专家那里获取设计模式实例,然后通过实例计算特征向量,最终生成训练数据集,并学习出分类器.在设计模式检测阶段,它们首先补充源码图(由类图转化而来),也即让子类继承父类的各种关系,然后从源码图中枚举出候选实例,并从中过滤掉不包含抽象类或接口类的实例,然后用第1 阶段的分类器进行分类,从而判断候选实例是不是真正的模式实例.该方法的缺点是只考虑了设计模式的度量信息.

总体来讲,上述工作在一定程度上解决了设计模式检测问题,但或多或少存在前面提到的4 个问题.因此本文从这些问题出发,结合度量和微结构,提出了一种新的机器学习检测方法.该方法不仅能够提高变体的检测效果,而且对组合爆炸问题的解决也有很大贡献.同时,该方法尝试从微结构的角度去刻画模式的行为特征,对于行为型设计模式的检测效果也有明显提升.

2 面向对象度量与微结构

本节给出基于堆叠泛化的设计模式检测方法相关的两个概念(面向对象度量和微结构)的定义及表示方式,并列出了本文所使用的度量列表和微结构列表,着重定义了5 种方法类微结构以及相应的检测方法.

2.1 面向对象度量

通过有效的特征选择算法为每种设计模式找到合适的面向对象度量特征集,是基于堆叠泛化的设计模式检测方法的重要步骤之一.面向对象度量通过定量地估算面向对象系统的设计特性,如类的继承深度、对象间耦合、方法内聚程度等,来预测测试的复杂性、发现系统中的错误和促进软件的模块化,它在一定程度上衡量了软件的设计质量.另一方面,设计模式是设计经验的总结和提炼,设计模式实例的应用是改善设计质量的一个有效手段,从而针对设计模式实例的相关度量值也会呈现出一定的规律性.目前已经有许多学者利用面向对象度量进行了设计模式的检测研究[17,20-22],这些度量包括C&K 度量[23]、Lorenz 度量[24]、Tegarden 度量[25]、Hitz&Montazeri 度量[26]以及Briand 度量[27]等.面向对象度量可以分为属性级别的度量、方法级别的度量、类级别的度量(以下简称类度量)和系统级别的度量,用于设计模式检测的主要是类级别的度量.

通过对GoF 的23 个设计模式的观察和理解,表1 所示的面向对象度量在刻画和标识设计模式实例方面具有重要作用,因此本文选择表1 所示的69 种类度量并通过POM Tests 工具[21]来计算相应度量值.

Table 1 Metrics used in this paper表1 本文选取的度量列表

举例来讲,AID 表示一个类的平均继承深度(考虑多继承),它可以用来衡量一个类的抽象程度.一般而言,设计模式中的抽象角色类都具有较小的AID 值.CBO 表示一个类和其他类之间的耦合程度,CBOin 表示入耦合,CBOout 表示出耦合,设计模式是设计经验的总结和提炼,它的角色类之间一般不会有太高的耦合程度.NOC表示一个类的直接子类个数,NOC 越大,则代码的重用越好,但是抽象性减弱.

定义 1(类度量表示(class metric representation),简称 CMR).类度量表示由一个三元组构成:CMR=(classA,metric,value).其中,classA表示某个具体的类,metric表示某个类度量,value表示classA的metric度量值.

2.2 微结构

设计模式微结构是指类或对象之间的静态或动态关系,作为设计模式的组成部分,它具有更小的粒度,每个设计模式的意图可以通过组合微结构的意图进行表达.定义合理的特征选择算法为每种设计模式找到微结构特征集,是基于堆叠泛化的设计模式检测方法的另一个重要步骤.Fontana 等人认为,子模式[28]、元素模式[29]、微模式[30]以及他们自己所提出的设计模式线索[31]都属于设计模式微结构范畴,并且也证实了微结构和设计模式检测之间的密切关系[32].随后,他们基于微结构给出了一种新的设计模式检测方法[16].不过,虽然提出了微结构这一术语,但却没有给出明确的定义.同时,他们也认为现有的微结构对设计模式检测来讲并不是完备的.本文将对微结构进行了明确定义,并提出几种新的微结构.

微结构可以分为两种:方法类微结构和非方法类微结构.其中:方法类微结构描述设计模式中包含的方法方面的信息,比如子模式中的Overriding Method[28]、元素模式中的Create Object[29]以及设计模式线索中的Multiple Redirections in Family[31]等;而非方法类微结构描述设计模式的角色类以及相关属性方面的信息,如Association,Inheritance,Private Self Instance 等.

定义2(微结构).表示类或对象之间的静态或动态的关系,每个微结构由三元组表示:MS=(classA/instance,classB/instance,relationalMask).其中,classA/instance和classB/instance表示该微结构的两个参与类或对象,而relationalMask表示它们之间的关系Mask值.对于方法类微结构,它是一个对应于classA/instance的比特向量,如果classA/instance的第n个方法和classB/instance之间体现了这种微结构关系,那么relationalMask的相应位置置1;对于非方法类微结构,若classA/instance和classB/instance存在这种微结构关系,则relationalMask置1.

为解决目前大多数基于机器学习的设计模式检测方法只能给出角色映射,而不能给出具体方法映射的问题,在定义方法类微结构时,本文采用比特向量记录相关微结构出现的位置和数目.一旦找到一个设计模式实例,就可以通过相关微结构元组中的比特向量以及它们之间的位运算来找到对应的方法映射.

图1 所示的Java 代码中包含了一个对象适配器模式的实例,其中,Contact 接口类扮演对象适配器模式的Target 角色,Employee 类扮演对象适配器模式的Adaptee 角色,ContactAdapter 类扮演对象适配器模式的Adapter角色.该模式实例中存在一个 Overriding Method 微结构(ContactAdapter,Contact,01011).其中,01011 表示ContactAdapter 的第2、第4 和第5 个方法是对Contact 的覆写.该模式实例中还存在另一个Delegation 微结构(ContactAdapter,Employee,01010).其中,01010 表示ContactAdapter 的第2 和第4 个方法是对Employee 的委托.通过对这两个微结构中的比特向量做与运算,也即01011&01010=01010,就能找到该对象适配器模式的方法映射.与运算值01010 表示ContactAdapter 的第2 和第4 个方法对应对象适配器模式的Request(·)方法.

Fig.1 An instance of object adapter pattern图1 一个对象适配器模式的实例

定义3(微结构的维度(dimension of micro-structure)).指定微结构所关联的类或对象的个数.对于定义2所定义的微结构,如果classA/instance与classB/instance相同,则称该微结构的维度为1;否则,称该微结构的维度为2.

定义4(返回类型微结构(return type)).如果类A中存在一个方法m,m的返回类型为类B,则称类A到类B存在返回类型微结构.返回类型微结构可以表示为三元组(classA,classB,ReturnTypeMask),其中,ReturnTypeMask是对应于classA的比特向量,如果classA的第n个方法的返回类型为classB,那么ReturnTypeMask的相应位置置1.显然,比特向量ReturnTypeMask的基数就是classA到classB的返回类型微结构的数目.

定义5(多通知微结构(multi-notify)).如果类A中存在某个包含循环的方法m,并且循环体内存在对类B的返回类型为空的方法的调用,则称类A到类B存在多通知微结构.多通知微结构可以表示为三元组(classA,classB,MultiNotifyMask),其中,MultiNotifyMask是对应于classA的比特向量.如果classA的第n个方法的内部有一个循环,并且循环体内有对classB的返回类型为空的方法的调用,那么MultiNotifyMask的相应位置置1.

定义6(参数化通知微结构(parameterized notify)).如果类A的某个方法m内存在对类B的带参数且返回类型为空的方法的调用,则称类A到类B存在参数化通知微结构.参数化通知微结构可以表示为三元组(classA,classB,ParameterizedNotifyMask),其中,ParameterizedNotifyMask是对应于classA的比特向量.如果classA的第n个方法内有对类B的带参数且返回类型为空的方法的调用,那么ParameterizedNotifyMask的相应位置置1.

定义7(参数依赖微结构(parameter dependence)).如果类A存在某个方法m,m的参数表中包含类型为类B的参数,则称类A到类B存在参数依赖微结构.参数依赖微结构表示为三元组:

其中,ParameterDependenceMask是对应于classA的比特向量,如果classA的第n个方法的参数表中包含classB类型的参数,那么ParameterDependenceMask的相应位置置1.

定义8(返回静态自身实例微结构(static self instance returned)).如果类A存在某个方法m,m的返回类型为staticclassA,则称类A 存在返回静态自身实例微结构.显然,该微结构是针对单个类而言的1 维微结构.返回静态自身实例可以表示为三元组:

其中,StaticSelfInstanceReturnedMask是对应于classA的比特向量.如果classA的第n个方法的返回类型为static classA,那么StaticSelfInstanceReturnedMask的相应位置置1.

为了在工厂方法模式、单例模式、对象适配器模式、组合模式以及观察者模式上进行实验,本文初步选用了16 种微结构,具体情况见表2.

Table 2 Micro-structures used in this paper表2 本文选取的微结构列表

需要说明的是:本文微结构的检测是在Java 字节码级别上进行的,检测工具使用了ASM 框架(一个Java 字节码操作和分析框架).

3 设计模式检测方法

本节首先给出该方法的总体框架,接着定义一些基本概念,然后利用定义好的概念对设计模式检测过程中的算法进行形式化描述,最后提出一种新的组合爆炸问题的解决方法.

3.1 设计模式检测框架

如图2 流程所示(图中某些概念见第3.2 节),设计模式检测方法分为两个阶段:第1 个阶段是模型训练阶段,第2 个阶段是模式识别阶段.基本思想是,结合度量和微结构进行设计模式检测.通过为每种设计模式找到合适的度量分类器和微结构分类器,进而训练出堆叠分类器,然后用这些分类器对一个候选的模式实例进行分类,从而预测候选的模式实例是不是真正的模式实例.

设计模式检测相关的度量和微结构是设计模式的两个独立视图,目前还无人提出同时考虑这两个视图的检测方法.另外,因为每个视图最适合的分类器可能不同,如果简单地将两个视图的特征混合到一起之后再训练出一个分类器,那么就有可能丢失这种差异性.因此,本文针对每个视图单独训练分类器,然后再进行模型堆叠.

Fig.2 Design pattern detection method based on metrics and micro-structures图2 度量和微结构相结合的设计模式检测方法

3.2 基本概念定义

为了方便描述模型训练算法和模式检测算法,本文给出如下符号和定义:

设计模式(design pattern,简称DP).DP 是23 种基本的设计模式之一或未来出现的其他设计模式.后续算法将采用此标记.

定义9(角色映射(role map),简称RM).角色映射是一个设计模式角色和角色类之间的对应关系,可以表示为二元组RM=(Role,Class).

举例来讲,对于QuickUML2001 项目中存在的一个工厂方法模式实例,存在以下4 个角色映射:

定义10(模式实例(pattern instance),简称PI).模式实例包括角色映射集合RoleMaps和该实例的类别标签Label,可以表示为PI=(RoleMaps,Label).其中,Label∈{CORRECT,INCORRECT}.Label=CORRECT表示该实例是一个正确的模式实例,或称为正实例;Label=INCORRECT表示该实例不是一个正确的模式实例,或称为负实例.

定义11(正负模式实例库(positive and negative pattern instances repository),简称PNPIR).正负模式实例库包括该实例库对应的设计模式DP和该设计模式的正负实例的集合,可以表示为二元组:

定义12(度量知识库(metrics repository),简称MR).度量知识库是一个面向对象度量的集合.

举例来讲,本文采用的度量知识库MR={ACAIC,ACMIC,AID,…,connectivity}(完整列表见表1).需要说明的是,度量知识库并不是一成不变的,可以根据模式检测的需要进行不断地更新.

定义13(微结构知识库(micro-structure repository),简称MSR).微结构知识库是一个设计模式微结构的集合.

举例来讲,本文采用的微结构知识库MSR={Overriding Method,Create Object,Return Type,…,Static Self Instance Returned}(完整列表见表2).需要说明的是,之所以选择这么少的微结构,是因为本文想先在5 种设计模式上进行实验,以验证所提方法的有效性.未来为了检测其他的设计模式,这个微结构知识库肯定会包括更多的内容.

定义14(设计模式度量特征(design pattern metric feature),简称DPMF).设计模式度量特征是一个三元组,可以表示为DPMF=(Role,Metric,Value).其中:Role是设计模式的某个角色;Metric是度量知识库中的某个度量;Value是该度量特征的具体数值,它等于角色Role对应的角色类的Metric度量值.

定义15(设计模式微结构特征(design pattern micro-structure feature),简称DPMSF).设计模式微结构特征是一个四元组,可以表示为DPMSF=(Role1,Role2,Microstructure,Value).其中:Role1 和Role2 是设计模式的的两个角色;Microstructure是微结构知识库中的某个微结构;Value是该微结构特征的具体数值,它等于Role1 对应的角色类→Role2 对应的角色类的Microstructure微结构的数目.

另外,本文是在Weka 平台上进行实验的,用到的特征选择算法有CfsSubsetEval,CorrelationAttributeEval,InfoGainAttributeEval,PrincipalComponents 和ReliefFAttributeEval,用一个集合来表示:FSASet={CfsSubsetEval,CorrelationAttributeEval,InfoGainAttributeEval,PrincipalComponents,ReliefFAttributeEval}.

同时,采用RandomForest,LibSVM,J48 等15 种常见的有监督学习算法,用一个集合来表示:

3.3 3个模型训练算法

在模型训练阶段,相关分类器的训练算法可以描述如下.

度量分类器训练算法以度量知识库、某种设计模式以及相应的正负模式实例库为输入,通过为实例库中的每个实例计算所有的度量特征,从而生成该设计模式的度量分类器的训练数据集.最后,通过遍历特征选择算法和分类算法找到最适合该设计模式的度量特征集和度量分类器.具体算法见表3.

Table 3 Metric classifier train algorithm表3 度量分类器训练算法

本文为设计模式dp的所有角色类计算所有的度量值.假设设计模式dp有n个角色,度量知识库mr有m个度量,那么训练数据集就有n×m个特征,外加一个分类标签.CMeFV 以设计模式的角色类和度量为输入,计算该角色类的相应度量特征值.第15 行的循环条件表示遍历FSASet 和CASet,从而找到使得分类效果最好的特征选择算法和有监督学习算法.其中,algo1 和algo3 分别表示某种特征选择算法,它们以训练数据集为输入,通过在训练数据集上进行特征选择,输出选择的特征子集;algo2 和algo4 分别表示某种分类算法,它们以训练数据集和特征子集为输入,通过训练,输出相应的分类器.

f1Measureof(*)表示括号内分类器在CORRECT 类别上的F1-Measure值.

微结构分类器训练算法以微结构知识库、某种设计模式以及相应的正负模式实例库为输入,通过为实例库中的每个实例计算所有的微结构特征,从而生成该设计模式的微结构分类器的训练数据集.最后,同样通过遍历特征选择算法和分类算法找到最适合该设计模式的微结构特征集和微结构分类器.具体算法见表4.

Table 4 Micro-structure classifier train algorithm表4 微结构分类器训练算法

CMsFV 以设计模式的两个角色类和微结构为输入,计算这两个角色类的相应微结构特征值.第18 行省略的部分同表3 的第14 行～第19 行.

堆叠分类器训练算法以某种设计模式以及相应的正负模式实例库、度量特征集、度量分类器、微结构特征集和微结构分类器为输入,通过为实例库中的每个实例计算相关的度量特征和微结构特征,从而生成该设计模式的堆叠分类器的初始训练数据集;然后,通过十折交叉的方法计算每个样本的度量分类器预测值和微结构分类器预测值,并将这两个值作为新的特征添加到样本当中;最后,通过遍历分类算法找到最适合该设计模式的堆叠分类器.具体算法见表5.

Table 5 Stacked classifier train algorithm表5 堆叠分类器训练算法

Table 5 Stacked classifier train algorithm (Continued)表5 堆叠分类器训练算法(续)

CMeF 以设计模式的实例和度量特征为输入,计算相应的设计模式度量特征;CMsF 以设计模式的实例和微结构特征为输入,计算相应的设计模式微结构特征;RandDiv 以折数10 和训练数据集为输入,输出随机划分的10个训练数据子集;ReTrainClassifier 以度量/微结构特征集、度量/微结构分类器以及重新训练用的数据集为输入,利用度量/微结构分类器的分类算法重新训练分类器;classify 以某个分类器和将要分类的样本的特征向量为输入,输出相应样本的类别标签,也即CORRECT 或INCORRECT.第28 行省略的部分代表遍历CASet,从而找到最适合设计模式dp的堆叠分类器classifier.

3.4 设计模式检测算法

在模式识别阶段,本文的设计模式检测算法可以描述如下.

设计模式检测算法以待检测系统的所有类(包括接口)、待检测的设计模式以及相应的度量特征集、度量分类器、微结构特征集、微结构分类器、堆叠分类器为输入,首先计算系统所有类的度量信息和微结构信息,然后生成候选实例,接着对每个候选实例计算度量特征和微结构特征,然后分别用度量分类器和微结构分类器进行分类,最后将两个分类器的预测结果作为新的特征再用堆叠分类器进行分类,从而预测候选实例是不是真正的模式实例.具体算法见表6.

CalcMe 以待检测系统的所有类和设计模式的度量特征集为输入,为每个类计算度量特征集中所涉及到的所有度量,输出待检测系统的度量信息,它可以看作是类度量表示(CMR)的集合;DetectMs 以待检测系统的所有类和设计模式的微结构特征集为输入,检测微结构特征集中所涉及到的所有微结构,输出待检测系统的微结构信息,它可以看作是微结构的集合;GenCandIns 以待检测系统的所有类以及待检测的设计模式为输入,通过执行本文的候选实例生成算法,输出待检测系统中相应设计模式的候选实例的集合;CMeF2/CMsF2 以候选实例、将要计算的度量特征/微结构特征以及待检测系统的度量信息/微结构信息为输入,通过简单检索,输出相应候选实例的相应度量特征/微结构特征.

需要说明的是:为了避免组合爆炸,本文的候选实例生成算法在考虑设计模式继承层次信息的基础之上加入了一些自己的考量,它的过程可以简单描述如下:(1) 从待检测系统中检测出所有的继承层次;(2) 根据设计模式所包含的继承层次信息,从待检测系统中枚举出候选模式实例;(3) 过滤掉那些不包含设计模式之必备微结构的候选实例(模式必备微结构是指正确模式实例必须具备的微结构,它是候选实例被评估为正确实例的必要非充分条件).本文是依据GoF 等人给出的定义以及经验数据来定义模式必备微结构的,不会对设计模式检测的正确率与召回率产生影响.举例来讲,对于工厂方法模式,GoF 等人给出的定义是,“定义一个用于创建对象的接口,让子类决定实例化哪一个类.”[1].显然,ConcreteCreator 对 Creator 的 Overriding Method 微结构和ConcreteCreator 对Product 类别的Create Object 微结构就是两个必要的微结构,因为它们是工厂方法模式定义的隐含信息.

Table 6 Design pattern detection algorithm表6 设计模式检测算法

以上便是本文所提方法的全部.为了丰富正负模式实例库,可以对堆叠分类器的分类结果进行人工检测,并把相应的实例添加到正负模式实例库中.

4 实验评估

为了评估所提方法的有效性,本文进行了相关实验:在模型训练阶段,为实验的每个设计模式找到了合适的度量特征集和微结构特征集,并在此基础上训练出了度量分类器、微结构分类器和堆叠分类器;在模式识别阶段,在7 个开源项目上进行了实验,并且和现有的两种工具进行了对比分析.

4.1 模型训练评估

目前可用的度量和微结构有很多,可以使用的分类算法也有很多.对于设计模式检测这一问题,本文的思路是:尽可能生成更多的候选度量特征和候选微结构特征,然后再进行特征选择和分类算法选择,通过遍历特征选择算法和分类算法,从而为每种设计模式找到合适的特征集和分类器.现阶段可用的模式实例库主要包括P-MARt[33],DPB[34]和Percerons[35]等,本文通过抽取MARPLE 项目[16]中的训练样本和网络搜集的一些训练样本构造正负模式实例库.具体情况见表7.

Table 7 PNPIR used in this paper表7 本文用到的正负模式实例库的情况

在表7 中,正的模式实例数是指正确的模式实例个数,即正样本的个数;负的模式实例数是指不正确的模式实例个数,即负样本的个数.对于设计模式检测来讲,什么样的正负样本比例最合适,并没有先验的知识.本文正负模式实例的比例初步控制在1:3 以内.

Fig.3 Observer pattern[1]图3 观察者模式[1]

下面以观察者模式为例,介绍特征选择和算法选择的结果.观察者模式的类图如图3 所示.从图3 中可以看出:观察者模式应该有4 个角色,分别是Subject,ConcreteSubject,Observer,ConcreteObserver.但是在实际应用中,经常存在ConcreteSubject/ConcreteObserver 角色缺失或和相应的父类合并的情况.不过,无论如何总会有一个Subject 类别的角色和一个Observer 类别的角色,因此对于观察者模式的检测而言,可以只考虑一个Subject 类别的角色和一个Observer 类别的角色,从而如果找到了这样一个组合,那么剩下缺失或合并的角色很容易就能通过检查它们所在的继承层次来发现.

表8～表10(只显示前5 项数据)是观察者模式3 个分类器的训练结果.

从表8 可以看出:不进行特征选择,并且使用RandomForest 算法进行模型训练时,所取得的F1-Measure 最高.从表9 可以看出:使用ReliefFAttributeEval 进行特征选择,并且使用RandomCommittee 算法进行模型训练时,所取得的F1-Measure 最高.从表10 可以看出,观察者模式的堆叠分类器应该采用RandomForest 算法.

Table 8 Training results of observer pattern’s metric classifier表8 观察者模式度量分类器的训练结果

Table 9 Training results of observer pattern’s micro-structure classifier表9 观察者模式微结构分类器的训练结果

Table 10 Training results of observer pattern’s stacked classifier表10 观察者模式堆叠分类器的训练结果

表11 显示了观察者模式的微结构特征列表,它是对观察者的候选微结构特征进行特征选择的结果.另外,因为从表8 可以看出:在训练度量分类器的时候,不进行特征选择并且使用RandomForest 算法训练时就已经取得了最好的分类效果,而且好于用CorrelationAttributeEval 进行特征选择后再训练的结果,所以这里并没有给出观察者的度量特征列表.从表11 可以看出:对于观察者模式,它的微结构特征集包括14 个特征(表中的1 表示相应位置的微结构特征被选中).需要说明的是:在使用ReliefFAttributeEval 进行特征选择时,本文使用0 作为ReliefF 评估值的阈值.另外,从表11 还可以看出:本文新提出的5 种方法类微结构中,有4 种与观察者模式的检测有关.

Table 11 List of micro-structure features of observer pattern表11 观察者模式的微结构特征列表

4.2 模式识别评估

在模式识别阶段:首先,对待检测的系统进行预处理,也即计算待检测系统的度量信息和抽取待检测系统的所有微结构;其次,根据微结构信息生成候选实例;再次,计算候选实例的度量特征和微结构特征;最后,用相应的度量分类器、微结构分类器和堆叠分类器进行分类,从而预测一个候选实例是否为真正的模式实例.

本文首先在JHotDraw v5.1,JRefactory v2.6.24 和JUnit v3.7 这3 个开源项目上进行了实验,正如第3 节所述,为了避免组合爆炸,本文在考虑设计模式继承层次信息的基础之上,加入了设计模式必备微结构的考量.对于工厂方法模式,具体情况见表12.

Table 12 Candidate instances of factory method pattern表12 工厂方法模式的候选实例的组合情况

假设待检测项目有n个类,那么对于k个角色的设计模式,默认情况下,它总共有A(n,k)个候选实例.其中,A(n,k)的计算公式如下:

举例来讲,对于表12 中JhotDraw v5.1,它共有155 个类(不考虑内部匿名类),如果从中产生工厂方法模式(k=4)的候选实例,那么候选实例的个数=A(155,4)=555120720.可以看出:默认情况下,工厂方法模式的候选实例的数量非常大.在考虑工厂方法模式的继承层次信息后,候选实例的数量减少到322 624,缩减了99%以上(具体过程见Tsantalis 等人的论文[7]);如果再考虑工厂方法模式的必备微结构信息(参见第3.4 节),那么候选实例的数量又会进一步缩减90%以上(最终只剩下4 301 个候选实例).

通常,每种设计模式都对应一个堆叠分类器.对于实验的5 种设计模式,由于它们在结构上各不相同,因此都分别对应一个堆叠分类器(对于结构相同的设计模式,比如State 模式和Strategy 模式,未来我们准备让它们共用一个堆叠分类器,训练的方法和前面提到的差不多,稍加修改即可).模式检测的过程也就是将一个个候选模式实例分类为CORRECT 或INCORRECT 的过程,因此是二分类问题,对应的混淆矩阵如下.

其中,a+b+c+d等于候选模式实例的个数.由于本文的目的是检测出正确的模式实例,因此选择CORRECT类别的准确率作为第一个度量指标,记准确率Precision=a/(a+c),相应的召回率Recall=a/(a+b)本应该作为第2个度量指标,但是考虑到生成的候选模式实例并不一定涵盖所有正确的模式实例,同时也为了能够在不同的设计模式检测方法之间进行比较(基于机器学习的方法和非基于机器学习的方法),因此第2 个度量指标召回率Recall应该等于a/所有检测方法检测到的正确的模式实例个数.最后一个度量指标:

根据前面所提出的设计模式检测方法,本文开发了设计模式检测工具OOSdpd 的原型,并且在JHotDraw v5.1,JRefactory v2.6.24 和JUnit v3.7 这3 个开源项目上进行了实验.之所以选择这些项目,是因为这些项目大量使用了设计模式,特别是JHotDraw,同时很多设计模式检测方法也都是以这3 个项目为例进行实验的,这样一来就比较容易对比分析.虽然目前有很多种设计模式检测方法,但是提供检测工具的却很少,本文在P-MARt[33],SSA[7]和所提出的方法之间进行比较,具体实验数据见表13～表15.

Table 13 Experimental data of the JHotDraw project表13 JHotDraw 项目的实验数据

Table 14 Experimental data of the JRefactory project表14 JRefactory 项目的实验数据

Table 15 Experimental data of the JUnit project表15 JUnit 项目的实验数据

一般来讲,不同的设计模式检测方法针对同一项目、同一设计模式的检测结果也不同,除了方法上的原因之外,还有一个重要的原因,那就是它们选择的模式出现类型不同[36],也即计数模式实例的方法不同.因此,为了在不同的方法之间进行比较,本文使用如下模式出现类型:FactoryMethod:(Creator,Product),Singleton:(Singleton),Adapter:(Target,Adapter),Composite:(Component,Composite),Observer:(Subject,Observer).另外需要说明的是:P-MARt 和SSA 这两种检测方法并不是基于机器学习的,它们的准确率Precision=检测出的实例中正确的个数/检测出的实例的总个数,召回率Recall=检测出的实例中正确的个数/所有检测方法检测到的正确的模式实例个数,F1-Measure=2×Precision×Recall/(Precision+Recall).

从表13～表15 的实验数据来看,本文的方法多数情况下具有较高的准确率和召回率,其中,总数指的是所有检测方法检测到的正确的模式实例个数.从图4 可以看出:对于工厂方法模式、单例模式和对象适配器模式,本文的方法具有更高的F1-Measure(该值是3 个项目的平均值).对于组合模式,3 种方法的检测结果一样,因此它们的F1-Measure 也一样.这是因为实验的项目中,组合模式的实例很少,每个项目最多只有一个,3 种方法都能轻松应对.对于观察者模式,本文的方法的F1-Measure 高于SSA,但是比P-MARt 稍低,这主要是因为本文的方法目前尚不支持部分角色类存在于第三方库中的情况.另外,P-MARt 和SSA 的准确率也并非总是100%的.举例来讲,对于JHotDraw v5.1 中的单例模式,P-MARt 和SSA 都检测出了两个单例模式实例CH.ifa.draw.util.Clipboard 和CH.ifa.draw.util.Iconkit,但是本文的方法只检测到了一个模式实例 CH.ifa.draw.util.Clipboard.实际上,虽然CH.ifa.draw.util.Iconkit 很像单例模式,但它并不是,因为它有一个访问权限为public 的构造函数,因此它不符合单例模式的要求.

Fig.4 Comparison of detection results on different design patterns图4 不同设计模式检测效果对比

图5 显示了不同检测方法针对不同开源项目的检测效果.需要说明的是:这里的AverageF1-Measure代表对于某个开源项目,5 种设计模式检测结果的F1-Measure的平均值.从中可以看出:本文的方法多数情况下检测效果最好,只有在JUnit v3.7 项目上弱于P-MARt.其主要原因还是上面提过的,观察者模式的检测效果不如P-MARt.另外,对于SSA 和本文的方法,JHotDraw v5.1 的检测效果最好,可能的原因有两个:(1) JHotDraw v5.1 的模式实例占比(模式实例数/项目总类数)更高;(2) JHotDraw 起源于Gamma 的一个教学实例,而他是软件设计模式概念的提出者之一.最后,从检测效果的稳定性来看,SSA 和本文的方法更加稳定,而P-MARt 针对不同项目的检测效果差别很大.

Fig.5 Comparison of detection results on different open source projects图5 不同开源项目检测效果对比

上面实验的项目规模都比较小,而且目前大部分设计模式的检测研究都集中在这3 个项目上.为了验证本文的方法在其他项目上的有效性,以及观察有效性随着项目规模的变化情况,本文又在ASM v1.4.2(59 个类),Dom4j v1.6.1(189 个类),Guice v3.0(425 个类)和Struts v2.5.14.1(2 742 个类)等4 个开源项目上进行了实验.其中,ASM 是常用的Java 字节码操作框架,Dom4j 是十分优秀的XML 解析包,Guice 是帮助代码实现控制反转的函数库,Struts 是基于MVC 的Web 框架.具体实验数据见表16～表19.

由于P-MARt 实际上是人工标注的实例库,并没有提供可用的检测工具,因此本文的方法只和SSA 工具进行对比.需要说明的是:为了统计方便,对象适配器模式采用了Adapter:(Adapter)模式出现类型.

Table 16 Experimental data of the ASM project表16 ASM 项目的实验数据

Table 17 Experimental data of the Dom4j project表17 Dom4j 项目的实验数据

Table 18 Experimental data of the Guice project表18 Guice 项目的实验数据

Table 19 Experimental data of the Struts project表19 Struts 项目的实验数据

从表16 可以看出,本文的方法只在单例模式上弱于SSA.从表17 可以看出,本文的方法在实验的5 种设计模式上均好于SSA.从表18 可以看出,本文的方法在工厂方法模式上明显弱于SSA.这主要是因为Guice v3.0 项目中包含了很多内部类实现的工厂方法模式,而本文的方法用的POM Tests 度量计算工具并不支持内部类,因此许多实例没有检测出来;另外,对于单例模式,和SSA 相比,本文的方法准确率高,但是召回率低,不过两者的F1-Measure非常接近.从表19 可以看出,本文的方法在所有模式上均好于SSA.

图6 显示的是每种设计模式的平均检测效果,从中可以看出:本文的方法只在单例模式上弱于SSA,但是差距并不明显;在组合模式和观察者模式上,本文的方法明显好于SSA,这主要是因为本文的方法使用了更多能够体现模式结构和行为特征的微结构信息.图7 显示的是针对不同项目规模,SSA 和本文的方法在5 种设计模式上的平均检测效果对比,从中可以看出:对于不同规模的项目,本文方法的检测效果和SSA 的检测效果都有一定的波动,但是本文方法的检测效果更加稳定.另外,对于规模比较小的项目(ASM v1.4.2 和Guice v3.0),本文的方法和SSA 相比优势并不明显;但是对于规模比较大的项目(Struts v2.5.14.1),本文的方法要明显好于SSA.因此,从实验数据来看,本文的方法更加适合规模比较大的项目.

Fig.6 Comparison of detection results on different design patterns图6 不同设计模式检测效果对比

Fig.7 Comparison of detection results on different project scale图7 不同项目规模检测效果对比

通过以上两组对比实验可以看出,本文的方法和P-MARt 以及SSA 相比,多数情况下具有更高的识别准确率和召回率.对于单例模式,本文的方法还需要进一步改进.对于观察者模式,本文的方法的检测效果要明显好于单纯基于结构相似度计算的SSA.

虽然目前有很多种基于机器学习的设计模式检测方法,但是我们没能找到任何一款可用的检测工具,而且这些方法多数也没有指明所采用的模式出现类型,因此很难以拿本文的方法与它们进行比较.

4.3 有效性分析

影响外部有效性的因素主要有以下3 点.

1)与其他基于机器学习的检测方法一样,本文的训练数据集也是由人工产生的,这就会受到主观因素的影响.因此,需要找到一个广泛认可的设计模式实例库作为训练数据集的来源;

2)本文以工厂方法模式为例,定义了它的两个必备微结构,从而显著地缩减了候选实例的搜索空间,避免了组合爆炸.但是对于其他设计模式,定义模式必备微结构对避免组合爆炸的有效程度还需要进一步研究;

3)虽然本文在观察者模式上取得了更好的检测效果,但是对于其他行为型设计模式的检测效果还需要进一步验证.

影响内部有效性的因素主要有以下两点:(1) 由于训练样本不够丰富以及所采用的度量知识库和微结构知识库不够完备,本文提出的方法对单例模式的检测效果还不够理想,不足以验证所提方法的有效性;(2) 如果模式实例中含有部分存在于第三方库中角色类,本文的方法无法准确检测,需要进一步研究如何将第三方库中的有效信息加载到检测目标项目中.

5 总结与展望

针对目前设计模式检测方法的研究中存在的若干问题,本文提出了一种基于机器学习的设计模式检测方法.首先,针对模式实例变体检测效果不理想的问题,本文利用面向对象度量特征和微结构特征进行基于堆叠泛化的学习,实验结果表明,对变体的检测效果有较大改善;其次,针对行为型设计模式的检测复杂和难以实现的问题,本文从微结构的角度追踪行为型设计模式的行为特征,对于观察者模式,相较于SSA 等经典方法取得了更高的F1-Measure值;再次,针对设计模式检测中的发生的组合爆炸问题,本文在考虑设计模式继承层次信息的基础之上,加入特定的设计模式微结构的考量,从而进一步缩减了模式的搜索空间.

具体地讲,本文采用机器学习的方式分别从度量和微结构两个视图训练分类器,然后采用模型堆叠的方式训练出最终的分类器.在几个开源项目上的实验表明:本文的方法相对于P-MARt 和SSA 来讲,具有更好的模式检测效果.

在未来工作中,本文将从如下几个方面进行改进和扩展.

(1) 本文应用比特向量表示方法类微结构的位置和数目,并通过比特向量及其位运算识别设计模式的方法映射.在未来工作中我们会将这些位置信息也输入分类器,更充分地利用微结构的位置信息,从而更加准确地追踪设计模式的行为特征;

(2) 找到更为广泛认可的设计模式实例库作为训练数据集的来源,从而提高设计模式检测的准确率;

(3) 进一步研究将第三方库中的有效信息加载到检测目标项目中的方法并完善度量知识库和微结构知识库,从而提高设计模式检测方法的可用性.